A relaxed cutting plane algorithm for solving fuzzy inequality systems

This paper studies a system of infinitely many fuzzy inequalities with concavemembership functions. By using the tolerance approach, we show that solving such system can be reduced to a semi-infinite programming problem. A relaxed cutting plane algorithm is proposed. In each iteration, we solve a finite convex optimization problem and add one or two more constraints. The proposed algorithm chooses a point at which the infinite constraints are violated to a degree rather than at which the violation is maximized. The iterative process ends when an optimal solution is identified. A convergence proof, under some mild conditions, is given. An efficient implementation based on the "method of centres" with "entropic regularization" techniques is also included. Some computational results confirm the efficiency of the proposed method and show its potential for solving large scale problems.     

Nonlinear goal programming using multi-objective genetic algorithms

Goal programming is a technique often used in engineering design activities primarily to find a compromised solution which will simultaneously satisfy a number of design goals. In solving goal programming problems, classical methods reduce the multiple goal-attainment problem into a single objective of minimizing a weighted sum of deviations from goals. This procedure has a number of known difficulties. First, the obtained solution to the goal programming problem is sensitive to the chosen weight vector. Second, the conversion to a single-objective optimization problem involves additional constraints. Third, since most real-world goal programming problems involve nonlinear criterion functions, the resulting single-objective optimization problem becomes a nonlinear programming problem, which is difficult to solve using classical optimization methods. In tackling nonlinear goal programming problems, although successive linearization techniques have been suggested, they are found to be sensitive to the chosen starting solution. In this paper, we pose the goal programming problem as a multi-objective optimization problem of minimizing deviations from individual goals and then suggest an evolutionary optimization algorithm to find multiple Pareto-optimal solutions of the resulting multi-objective optimization problem. The proposed approach alleviates all the above difficulties. It does not need any weight vector. It eliminates the need of having extra constraints needed with the classical formulations. The proposed approach is also suitable for solving goal programming problems having nonlinear criterion functions and having a non-convex trade-off region. The efficacy of the proposed approach is demonstrated by solving a number of nonlinear goal programming test problems and an engineering design problem. In all problems, multiple solutions (each corresponding to a different weight vector) to the goal programming problem are found in one single simulation run. The results suggest that the proposed approach is an effective and practical tool for solving real-world goal programming problems.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

A differential inclusion-based approach for solving nonsmooth convex optimization problems

This article presents a differential inclusion-based neural network for solving nonsmooth convex programming problems with inequality constraints. The proposed neural network, which is modelled with a differential inclusion, is a generalization of the steepest descent neural network. It is proved that the set of the equilibrium points of the proposed differential inclusion is equal to that of the optimal solutions of the considered optimization problem. Moreover, it is shown that the trajectory of the solution converges to an element of the optimal solution set and the convergence point is a globally asymptotically stable point of the proposed differential inclusion. After establishing the theoretical results, an algorithm is also designed for solving such problems. Typical examples are given which confirm the effectiveness of the theoretical results and the performance of the proposed neural network.     

A finite steps algorithm for solving convex feasibility problems

This paper develops a new variant of the classical alternating projection method for solving convex feasibility problems where the constraints are given by the intersection of two convex cones in a Hilbert space. An extension to the feasibility problem for the intersection of two convex sets is presented as well. It is shown that one can solve such problems in a finite number of steps and an explicit upper bound for the required number of steps is obtained. As an application, we propose a new finite steps algorithm for linear programming with linear matrix inequality constraints. This solution is computed by solving a sequence of a matrix eigenvalue decompositions. Moreover, the proposed procedure takes advantage of the structure of the problem. In particular, it is well adapted for problems with several small size constraints.     

A nonisolated optimal solution for special reverse convex programming problems

In this paper, an efficient algorithm is proposed for globally solving special reverse convex programming problems with more than one reverse convex constraints. The proposed algorithm provides a nonisolated global optimal solution which is also stable under small perturbations of the constraints, and it turns out that such an optimal solution is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and the numerical experiment is given to illustrate the feasibility of the presented algorithm.     

Global optimization of signomial mixed-integer nonlinear programming problems with free variables

Mixed-integer nonlinear programming (MINLP) problems involving general constraints and objective functions with continuous and integer variables occur frequently in engineering design, chemical process industry and management. Although many optimization approaches have been developed for MINLP problems, these methods can only handle signomial terms with positive variables or find a local solution. Therefore, this study proposes a novel method for solving a signomial MINLP problem with free variables to obtain a global optimal solution. The signomial MINLP problem is first transformed into another one containing only positive variables. Then the transformed problem is reformulated as a convex mixed-integer program by the convexification strategies and piecewise linearization techniques. A global optimum of the signomial MINLP problem can finally be found within the tolerable error. Numerical examples are also presented to demonstrate the effectiveness of the proposed method.     

一类线性乘积规划问题的分支定界缩减方法

提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Reverse Convex Programming Approach in the Space of Extreme Criteria for Optimization over Efficient Sets

The problem of minimizing a convex function over the difference of two convex sets is called ‘reverse convex program’. This is a typical problem in global optimization, in which local optima are in general different from global optima. Another typical example in global optimization is the optimization problem over the efficient set of a multiple criteria programming problem. In this article, we investigate some special cases of optimization problems over the efficient set, which can be transformed equivalently into reverse convex programs in the space of so-called extreme criteria of multiple criteria programming problems under consideration. A suitable algorithm of branch and bound type is then established for globally solving resulting problems. Preliminary computational results with the proposed algorithm are reported.     

Limit vector variational inequality problems via scalarization

This paper presents a global optimization approach for solving signomial geometric programming (SGP) problems. We employ an accelerated extended cutting plane (ECP) approach integrated with piecewise linear (PWL) approximations to solve the global optimization of SGP problems. In this approach, we separate the feasible regions determined by the constraints into convex and nonconvex ones in the logarithmic domain. In the nonconvex feasible regions, the corresponding constraint functions are converted into mixed integer linear constraints using PWL approximations, while the other constraints with convex feasible regions are handled by the ECP method. We also use pre-processed initial cuts and batched cuts to accelerate the proposed algorithm. Numerical results show that the proposed approach can solve the global optimization of SGP problems efficiently and effectively.     

Scatter Search—Wellsprings and Challenges

This article is concerned with two global optimization problems (P1) and (P2). Each of these problems is a fractional programming problem involving the maximization of a ratio of a convex function to a convex function, where at least one of the convex functions is a quadratic form. First, the article presents and validates a number of theoretical properties of these problems. Included among these properties is the result that, under a mild assumption, any globally optimal solution for problem (P1) must belong to the boundary of its feasible region. Also among these properties is a result that shows that problem (P2) can be reformulated as a convex maximization problem. Second, the article presents for the first time an algorithm for globally solving problem (P2). The algorithm is a branch and bound algorithm in which the main computational effort involves solving a sequence of convex programming problems. Convergence properties of the algorithm are presented, and computational issues that arise in implementing the algorithm are discussed. Preliminary indications are that the algorithm can be expected to provide a practical approach for solving problem (P2), provided that the number of variables is not too large.     

Solving dual problems using a coevolutionary optimization algorithm

In solving certain optimization problems, the corresponding Lagrangian dual problem is often solved simply because in these problems the dual problem is easier to solve than the original primal problem. Another reason for their solution is the implication of the weak duality theorem which suggests that under certain conditions the optimal dual function value is smaller than or equal to the optimal primal objective value. The dual problem is a special case of a bilevel programming problem involving Lagrange multipliers as upper-level variables and decision variables as lower-level variables. Another interesting aspect of dual problems is that both lower and upper-level optimization problems involve only box constraints and no other equality of inequality constraints. In this paper, we propose a coevolutionary dual optimization (CEDO) algorithm for co-evolving two populations—one involving Lagrange multipliers and other involving decision variables—to find the dual solution. On 11 test problems taken from the optimization literature, we demonstrate the efficacy of CEDO algorithm by comparing it with a couple of nested smooth and nonsmooth algorithms and a couple of previously suggested coevolutionary algorithms. The performance of CEDO algorithm is also compared with two classical methods involving nonsmooth (bundle) optimization methods. As a by-product, we analyze the test problems to find their associated duality gap and classify them into three categories having zero, finite or infinite duality gaps. The development of a coevolutionary approach, revealing the presence or absence of duality gap in a number of commonly-used test problems, and efficacy of the proposed coevolutionary algorithm compared to usual nested smooth and nonsmooth algorithms and other existing coevolutionary approaches remain as the hallmark of the current study.     

Solving a class of geometric programming problems by an efficient dynamic model

In this paper, a neural network model is constructed on the basis of the duality theory, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle to solve geometric programming (GP) problems. The main idea is to convert the GP problem into an equivalent convex optimization problem. A neural network model is then constructed for solving the obtained convex programming problem. By employing Lyapunov function approach, it is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the original problem. The simulation results also show that the proposed neural network is feasible and efficient.     

A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

Coradiant sets and $$\varepsilon $$-efficiency in multiobjective optimization

In multi-parametric programming an optimization problem is solved as a function of certain parameters, where the parameters are commonly considered to be bounded and continuous. In this paper, we use the case of strictly convex multi-parametric quadratic programming (mp-QP) problems with affine constraints to investigate problems where these conditions are not met. Based on the combinatorial solution approach for mp-QP problems featuring bounded and continuous parameters, we show that (i) for unbounded parameters, it is possible to obtain the multi-parametric solution if there exists one realization of the parameters for which the optimization problem can be solved and (ii) for binary parameters, we present the equivalent mixed-integer formulations for the application of the combinatorial algorithm. These advances are combined into a new, generalized version of the combinatorial algorithm for mp-QP problems, which enables the solution of problems featuring both unbounded and binary parameters. This novel approach is applied to mixed-integer bilevel optimization problems and the parametric solution of the dual of a convex problem.     

Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems

Many global optimization approaches for solving signomial geometric programming problems are based on transformation techniques and piecewise linear approximations of the inverse transformations. Since using numerous break points in the linearization process leads to a significant increase in the computational burden for solving the reformulated problem, this study integrates the range reduction techniques in a global optimization algorithm for signomial geometric programming to improve computational efficiency. In the proposed algorithm, the non-convex geometric programming problem is first converted into a convex mixed-integer nonlinear programming problem by convexification and piecewise linearization techniques. Then, an optimization-based approach is used to reduce the range of each variable. Tightening variable bounds iteratively allows the proposed method to reach an approximate solution within an acceptable error by using fewer break points in the linearization process, therefore decreasing the required CPU time. Several numerical experiments are presented to demonstrate the advantages of the proposed method in terms of both computational efficiency and solution quality.     

Simplicial Branch-and-Reduce Algorithm for Convex Programs with a Multiplicative Constraint

Optimization problems that involve products of convex functions in the objective function or in the constraints arise in a variety of applications. These problems are difficult global optimization problems. During the past 15 years, however, a number of practical algorithms have been proposed for globally solving these types of problems. In this article, we present and validate a branch-and-reduce algorithm for finding a global optimal solution to a convex program that contains an additional constraint on the product of several convex functions. To globally solve this problem, the algorithm instead globally solves an equivalent master problem. At any stage of the algorithm, a disconnected set consisting of a union of simplices is constructed. This set is guaranteed to contain a portion of the boundary of the feasible region of the master problem where a global optimal solution lies. The algorithm uses a new branch-and-reduce scheme to iteratively reduce the sizes of these sets until a global optimal solution is found. Several potential computational advantages of the algorithm are explained, and a numerical example is solved.     

Bandwidth packing problem with queueing delays: modelling and exact solution approach

In this paper we develop a general but smooth global optimization strategy for nonlinear multilevel programming problems with polyhedral constraints. At each decision level successive convex relaxations are applied over the non-convex terms in combination with a multi-parametric programming approach. The proposed algorithm reaches the approximate global optimum in a finite number of steps through the successive subdivision of the optimization variables that contribute to the non-convexity of the problem and partitioning of the parameter space. The method is implemented and tested for a variety of bilevel, trilevel and fifth level problems which have non-convexity formulation at their inner levels.     

A primal-dual interior point method for optimal zero-forcing beamformer design under per-antenna power constraints

In this paper, we consider an optimal zero-forcing beamformer design problem in multi-user multiple-input multiple-output broadcast channel. The minimum user rate is maximized subject to zero-forcing constraints and power constraint on each base station antenna array element. The natural formulation leads to a nonconvex optimization problem. This problem is shown to be equivalent to a convex optimization problem with linear objective function, linear equality and inequality constraints and quadratic inequality constraints. Here, the indirect elimination method is applied to reduce the convex optimization problem into an equivalent convex optimization problem of lower dimension with only inequality constraints. The primal-dual interior point method is utilized to develop an effective algorithm (in terms of computational efficiency) via solving the modified KKT equations with Newton method. Numerical simulations are carried out. Compared to algorithms based on a trust region interior point method and sequential quadratic programming method, it is observed that the method proposed is much superior in terms of computational efficiency.