Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm

In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.     

An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters

Real engineering design problems are generally characterized by the presence of many often conflicting and incommensurable objectives. Naturally, these objectives involve many parameters whose possible values may be assigned by the experts. The aim of this paper is to introduce a hybrid approach combining three optimization techniques, dynamic programming (DP), genetic algorithms and particle swarm optimization (PSO). Our approach integrates the merits of both DP and artificial optimization techniques and it has two characteristic features. Firstly, the proposed algorithm converts fuzzy multiobjective optimization problem to a sequence of a crisp nonlinear programming problems. Secondly, the proposed algorithm uses H-SOA for solving nonlinear programming problem. In which, any complex problem under certain structure can be solved and there is no need for the existence of some properties rather than traditional methods that need some features of the problem such as differentiability and continuity. Finally, with different degree of α we get different α-Pareto optimal solution of the problem. A numerical example is given to illustrate the results developed in this paper.     

On a pair of nonlinear mixed integer programming problems

We consider maximin and minimax nonlinear mixed integer programming problems which are nonsymmetric in duality sense. Under weaker (pseudo-convex/pseudo-concave) assumptions, we show that the supremum infimum of the maximin problem is greater than or equal to the infimum supremum of the minimax problem. As a particular case, this result reduces to the weak duality theorem for minimax and symmetric dual nonlinear mixed integer programming problems. Further, this is used to generalize available results on minimax and symmetric duality in nonlinear mixed integer programming.     

非光滑半定规划的一阶最优性条件

首次考虑了非光滑半定规化问题．运用与非线性规划类似的技巧,把现存的理论扩展到约束是结构稀疏矩阵的情况,给出了其一阶最优性条件。考虑了严格互补条件不成立的情形．在约束矩阵为对角阵条件下,所用的正则条件与传统非线性优化意义下的是一致的．     

An active set strategy for solving optimization problems with up to 200,000,000 nonlinear constraints

Numerical test results are presented for solving smooth nonlinear programming problems with a large number of constraints, but a moderate number of variables. The active set method proceeds from a given bound for the maximum number of expected active constraints at an optimal solution, which must be less than the total number of constraints. A quadratic programming subproblem is generated with a reduced number of linear constraints from the so-called working set, which is internally changed from one iterate to the next. Only for active constraints, i.e., a certain subset of the working set, new gradient values must be computed. The line search is adapted to avoid too many active constraints which do not fit into the working set. The active set strategy is an extension of an algorithm described earlier by the author together with a rigorous convergence proof. Numerical results for some simple academic test problems show that nonlinear programs with up to 200,000,000 nonlinear constraints are efficiently solved on a standard PC.     

Interior-point methods for nonconvex nonlinear programming: Jamming and numerical testing

The paper considers an example of Wächter and Biegler which is shown to converge to a nonstationary point for the standard primal–dual interior-point method for nonlinear programming. The reason for this failure is analyzed and a heuristic resolution is discussed. The paper then characterizes the performance of LOQO, a line-search interior-point code, on a large test set of nonlinear programming problems. Specific types of problems which can cause LOQO to fail are identified.Research of the first and third authors supported by NSF grant DMS-9870317, ONR grant N00014-98-1-0036.Research of the second author supported by NSF grant DMS-9805495.     

Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method

In this paper, we propose a convergent Lagrangian and objective level cut method for computing exact solution to two classes of nonlinear integer programming problems: separable nonlinear integer programming and polynomial zero-one programming. The method exposes an optimal solution to the convex hull of a revised perturbation function by successively reshaping or re-confining the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence of the Lagrangian method on a revised domain. Computational results are reported for a variety of nonlinear integer programming problems and demonstrate that the proposed method is promising in solving medium-size nonlinear integer programming problems.     

An approach to find redundant objective function(s) and redundant constraint(s) in multi-objective nonlinear stochastic fractional programming problems

Structural redundancies in mathematical programming models are nothing uncommon and nonlinear programming problems are no exception. Over the past few decades numerous papers have been written on redundancy. Redundancy in constraints and variables are usually studied in a class of mathematical programming problems. However, main emphasis has so far been given only to linear programming problems. In this paper, an algorithm that identifies redundant objective function(s) and redundant constraint(s) simultaneously in multi-objective nonlinear stochastic fractional programming problems is provided. A solution procedure is also illustrated with numerical examples. The proposed algorithm reduces the number of nonlinear fractional objective functions and constraints in cases where redundancy exists.     

Optimality conditions for nonconvex semidefinite programming

This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse. The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained when the constraint matrix is diagonal. Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000     

A redundancy detection algorithm for fuzzy stochastic multi-objective linear fractional programming problems

The computational complexity of linear and nonlinear programming problems depends on the number of objective functions and constraints involved and solving a large problem often becomes a difficult task. Redundancy detection and elimination provides a suitable tool for reducing this complexity and simplifying a linear or nonlinear programming problem while maintaining the essential properties of the original system. Although a large number of redundancy detection methods have been proposed to simplify linear and nonlinear stochastic programming problems, very little research has been developed for fuzzy stochastic (FS) fractional programming problems. We propose an algorithm that allows to simultaneously detect both redundant objective function(s) and redundant constraint(s) in FS multi-objective linear fractional programming problems. More precisely, our algorithm reduces the number of linear fuzzy fractional objective functions by transforming them in probabilistic–possibilistic constraints characterized by predetermined confidence levels. We present two numerical examples to demonstrate the applicability of the proposed algorithm and exhibit its efficacy.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

A new reformulation-linearization technique for bilinear programming problems

This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new Reformulation-Linearization Technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This RLT process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

A polyhedral branch-and-cut approach to global optimization

A variety of nonlinear, including semidefinite, relaxations have been developed in recent years for nonconvex optimization problems. Their potential can be realized only if they can be solved with sufficient speed and reliability. Unfortunately, state-of-the-art nonlinear programming codes are significantly slower and numerically unstable compared to linear programming software.In this paper, we facilitate the reliable use of nonlinear convex relaxations in global optimization via a polyhedral branch-and-cut approach. Our algorithm exploits convexity, either identified automatically or supplied through a suitable modeling language construct, in order to generate polyhedral cutting planes and relaxations for multivariate nonconvex problems. We prove that, if the convexity of a univariate or multivariate function is apparent by decomposing it into convex subexpressions, our relaxation constructor automatically exploits this convexity in a manner that is much superior to developing polyhedral outer approximators for the original function. The convexity of functional expressions that are composed to form nonconvex expressions is also automatically exploited.Root-node relaxations are computed for 87 problems from globallib and minlplib, and detailed computational results are presented for globally solving 26 of these problems with BARON 7.2, which implements the proposed techniques. The use of cutting planes for these problems reduces root-node relaxation gaps by up to 100% and expedites the solution process, often by several orders of magnitude.The research was supported in part by ExxonMobil Upstream Research Company, the National Science Foundation under awards DMII 0115166 and CTS 0124751, and the Joint NSF/NIGMS Initiative to Support Research in the Area of Mathematical Biology under NIH award GM072023.     

New Theoretical Results on Recursive Quadratic Programming Algorithms

Recursive quadratic programming is a family of techniques developed by Bartholomew-Biggs and other authors for solving nonlinear programming problems. The first-order optimality conditions for a local minimizer of the augmented Lagrangian are transformed into a nonlinear system where both primal and dual variables appear explicitly. The inner iteration of the algorithm is a Newton-like procedure that updates simultaneously primal variables and Lagrange multipliers. In this way, as observed by Gould, the implementation of the Newton method becomes stable, in spite of the possibility of having large penalization parameters. In this paper, the inner iteration is analyzed from a different point of view. Namely, the size of the convergence region and the speed of convergence of the inner process are considered and it is shown that, in some sense, both are independent of the penalization parameter when an adequate version of the Newton method is used. In other words, classical Newton-like iterations are improved, not only in relation to stability of the linear algebra involved, but also with regard to the ovearll convergence of the nonlinear process. Some numerical experiments suggset that, in fact, practical efficiency of the methods is related to these theoretical results.     

An accelerated multiplier method for nonlinear programming

This paper describes an accelerated multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems. The unconstrained problems are solved using a rank-one recursive algorithm described in an earlier paper. Multiplier estimates are obtained by minimizing the error in the Kuhn-Tucker conditions using a quadratic programming algorithm. The convergence of the sequence of unconstrained problems is accelerated by using a Newton-Raphson extrapolation process. The numerical effectiveness of the algorithm is demonstrated on a relatively large set of test problems.This work was supported by the US Air Force under Contract No. F04701-74-C-0075.     

On the convergence of cross decomposition

Cross decomposition is a recent method for mixed integer programming problems, exploiting simultaneously both the primal and the dual structure of the problem, thus combining the advantages of Dantzig—Wolfe decomposition and Benders decomposition. Finite convergence of the algorithm equipped with some simple convergence tests has been proved. Stronger convergence tests have been proposed, but not shown to yield finite convergence.In this paper cross decomposition is generalized and applied to linear programming problems, mixed integer programming problems and nonlinear programming problems (with and without linear parts). Using the stronger convergence tests finite exact convergence is shown in the first cases. Unbounded cases are discussed and also included in the convergence tests. The behaviour of the algorithm when parts of the constraint matrix are zero is also discussed. The cross decomposition procedure is generalized (by using generalized Benders decomposition) in order to enable the solution of nonlinear programming problems.     

A Null Space Approach for Solving Nonlinear Complementarity Problems

In this work, null space techniques are employed to tackle nonlinear complementarity problems （NCPs）. NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The NCP conditions are divided into two groups, Some equalities and inequalities in an NCP are treated as constraints, While other equalities and inequalities in an NCP are to be regarded as objective function. Two groups are all updated in every step. Null space approaches are extended to nonlinear complementarity problems. Two different solvers are employed for all NCP in an algorithm.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

Improved logarithmic linearizing method for optimization problems with free-sign pure discrete signomial terms

Free-sign pure discrete signomial (FPDS) terms are vital to and are frequently observed in many nonlinear programming problems, such as geometric programming, generalized geometric programming, and mixed-integer non-linear programming problems. In this study, all variables in the FPDS term are discrete variables. Any improvement to techniques for linearizing FPDS term contributes significantly to the solving of nonlinear programming problems; therefore, relative techniques have continually been developed. This study develops an improved exact method to linearize a FPDS term into a set of linear programs with minimal logarithmic numbers of zero-one variables and constraints. This method is tighter than current methods. Various numerical experiments demonstrate that the proposed method is significantly more efficient than current methods, especially when the problem scale is large.     

Efficient decomposition and linearization methods for the stochastic transportation problem

The stochastic transportation problem can be formulated as a convex transportation problem with nonlinear objective function and linear constraints. We compare several different methods based on decomposition techniques and linearization techniques for this problem, trying to find the most efficient method or combination of methods. We discuss and test a separable programming approach, the Frank-Wolfe method with and without modifications, the new technique of mean value cross decomposition and the more well known Lagrangean relaxation with subgradient optimization, as well as combinations of these approaches. Computational tests are presented, indicating that some new combination methods are quite efficient for large scale problems.