A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0–1 quadratic problems leading to quasi-Newton methods

This article presents a family of semidefinite programming bounds, obtained by Lagrangian duality, for 0–1 quadratic optimization problems with linear or quadratic constraints. These bounds have useful computational properties: they have a good ratio of tightness to computing time, they can be optimized by a quasi-Newton method, and their final tightness level is controlled by a real parameter. These properties are illustrated on three standard combinatorial optimization problems: unconstrained 0–1 quadratic optimization, heaviest $k$ -subgraph, and graph bisection.     

Unconstrained formulation of standard quadratic optimization problems

A standard quadratic optimization problem (StQP) consists of finding the largest or smallest value of a (possibly indefinite) quadratic form over the standard simplex which is the intersection of a hyperplane with the positive orthant. This NP-hard problem has several immediate real-world applications like the Maximum Clique Problem, and it also occurs in a natural way as a subproblem in quadratic programming with linear constraints. We propose unconstrained reformulations of StQPs, by using different approaches. We test our method on clique problems from the DIMACS challenge.     

随机模糊的等比例-最小方差投资组合优化研究

Markowitz的均值-方差模型在投资组合优化中得到了广泛的运用和拓展,其中多数拓展模型仅局限于对随机投资组合或模糊投资组合的研究,而忽略了实际问题同时包含了随机信息和模糊信息两个方面。本文首先定义随机模糊变量的方差用以度量投资组合的风险,提出具有阀值约束的最小方差随机模糊投资组合模型,基于随机模糊理论,将该模型转化为具有线性等式和不等式约束的凸二次规划问题。为了提高上述模型的有效性,本文以投资者期望效用最大化为压缩目标对投资组合权重进行压缩,构建等比例-最小方差混合的随机模糊投资组合模型,并求解该模型的最优解。最后,运用滚动实际数据的方法,比较上述两个模型的夏普比率以验证其有效性。     

On the Relationship Between Regression Analysis and Mathematical Programming

The interaction between linear, quadratic programming and regression analysis are explored by both statistical and operations research methods. Estimation and optimization problems are formulated in two different ways: on one hand linear and quadratic programming problems are formulated and solved by statistical methods, and on the other hand the solution of the linear regression model with constraints makes use of the simplex methods of linear or quadratic programming. Examples are given to illustrate the ideas.     

Solving quadratic convex bilevel programming problems using a smoothing method

In this paper, we present a smoothing sequential quadratic programming to compute a solution of a quadratic convex bilevel programming problem. We use the Karush-Kuhn-Tucker optimality conditions of the lower level problem to obtain a nonsmooth optimization problem known to be a mathematical program with equilibrium constraints; the complementary conditions of the lower level problem are then appended to the upper level objective function with a classical penalty. These complementarity conditions are not relaxed from the constraints and they are reformulated as a system of smooth equations by mean of semismooth equations using Fisher-Burmeister functional. Then, using a quadratic sequential programming method, we solve a series of smooth, regular problems that progressively approximate the nonsmooth problem. Some preliminary computational results are reported, showing that our approach is efficient.     

On Polynomial Optimization Over Non-compact Semi-algebraic Sets

The optimal value of a polynomial optimization over a compact semi-algebraic set can be approximated as closely as desired by solving a hierarchy of semidefinite programs and the convergence is finite generically under the mild assumption that a quadratic module generated by the constraints is Archimedean. We consider a class of polynomial optimization problems with non-compact semi-algebraic feasible sets, for which an associated quadratic module, that is generated in terms of both the objective function and the constraints, is Archimedean. For such problems, we show that the corresponding hierarchy converges and the convergence is finite generically. Moreover, we prove that the Archimedean condition (as well as a sufficient coercivity condition) can be checked numerically by solving a similar hierarchy of semidefinite programs. In other words, under reasonable assumptions, the now standard hierarchy of semidefinite programming relaxations extends to the non-compact case via a suitable modification.     

On safe tractable approximations of chance constraints

A natural way to handle optimization problem with data affected by stochastic uncertainty is to pass to a chance constrained version of the problem, where candidate solutions should satisfy the randomly perturbed constraints with probability at least 1 − ?. While being attractive from modeling viewpoint, chance constrained problems “as they are” are, in general, computationally intractable. In this survey paper, we overview several simulation-based and simulation-free computationally tractable approximations of chance constrained convex programs, primarily, those of chance constrained linear, conic quadratic and semidefinite 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.     

Quartic Formulation of Standard Quadratic Optimization Problems

A standard quadratic optimization problem (StQP) consists of finding the largest or smallest value of a (possibly indefinite) quadratic form over the standard simplex which is the intersection of a hyperplane with the positive orthant. This NP-hard problem has several immediate real-world applications like the Maximum-Clique Problem, and it also occurs in a natural way as a subproblem in quadratic programming with linear constraints. To get rid of the (sign) constraints, we propose a quartic reformulation of StQPs, which is a special case (degree four) of a homogeneous program over the unit sphere. It turns out that while KKT points are not exactly corresponding to each other, there is a one-to-one correspondence between feasible points of the StQP satisfying second-order necessary optimality conditions, to the counterparts in the quartic homogeneous formulation. We supplement this study by showing how exact penalty approaches can be used for finding local solutions satisfying second-order necessary optimality conditions to the quartic problem: we show that the level sets of the penalty function are bounded for a finite value of the penalty parameter which can be fixed in advance, thus establishing exact equivalence of the constrained quartic problem with the unconstrained penalized version.     

A sequential quadratically constrained quadratic programming method with an augmented Lagrangian line search function

Based on an augmented Lagrangian line search function, a sequential quadratically constrained quadratic programming method is proposed for solving nonlinearly constrained optimization problems. Compared to quadratic programming solved in the traditional SQP methods, a convex quadratically constrained quadratic programming is solved here to obtain a search direction, and the Maratos effect does not occur without any other corrections. The “active set” strategy used in this subproblem can avoid recalculating the unnecessary gradients and (approximate) Hessian matrices of the constraints. Under certain assumptions, the proposed method is proved to be globally, superlinearly, and quadratically convergent. As an extension, general problems with inequality and equality constraints as well as nonmonotone line search are also considered.     

Solving non-linear portfolio optimization problems with the primal-dual interior point method

Stochastic programming is recognized as a powerful tool to help decision making under uncertainty in financial planning. The deterministic equivalent formulations of these stochastic programs have huge dimensions even for moderate numbers of assets, time stages and scenarios per time stage. So far models treated by mathematical programming approaches have been limited to simple linear or quadratic models due to the inability of currently available solvers to solve NLP problems of typical sizes. However stochastic programming problems are highly structured. The key to the efficient solution of such problems is therefore the ability to exploit their structure. Interior point methods are well-suited to the solution of very large non-linear optimization problems. In this paper we exploit this feature and show how portfolio optimization problems with sizes measured in millions of constraints and decision variables, featuring constraints on semi-variance, skewness or non-linear utility functions in the objective, can be solved with the state-of-the-art solver.     

Accelerating convergence of a globalized sequential quadratic programming method to critical Lagrange multipliers

This paper concerns the issue of asymptotic acceptance of the true Hessian and the full step by the sequential quadratic programming algorithm for equality-constrained optimization problems. In order to enforce global convergence, the algorithm is equipped with a standard Armijo linesearch procedure for a nonsmooth exact penalty function. The specificity of considerations here is that the standard assumptions for local superlinear convergence of the method may be violated. The analysis focuses on the case when there exist critical Lagrange multipliers, and does not require regularity assumptions on the constraints or satisfaction of second-order sufficient optimality conditions. The results provide a basis for application of known acceleration techniques, such as extrapolation, and allow the formulation of algorithms that can outperform the standard SQP with BFGS approximations of the Hessian on problems with degenerate constraints. This claim is confirmed by some numerical experiments.

     

A Branch-and-Bound Approach for Solving a Class of Generalized Semi-infinite Programming Problems

A nonconvex generalized semi-infinite programming problem is considered, involving parametric max-functions in both the objective and the constraints. For a fixed vector of parameters, the values of these parametric max-functions are given as optimal values of convex quadratic programming problems. Assuming that for each parameter the parametric quadratic problems satisfy the strong duality relation, conditions are described ensuring the uniform boundedness of the optimal sets of the dual problems w.r.t. the parameter. Finally a branch-and-bound approach is suggested transforming the problem of finding an approximate global minimum of the original nonconvex optimization problem into the solution of a finite number of convex problems.     

An exact penalty function method for nonlinear mixed discrete programming problems

In this paper, we consider a general class of nonlinear mixed discrete programming problems. By introducing continuous variables to replace the discrete variables, the problem is first transformed into an equivalent nonlinear continuous optimization problem subject to original constraints and additional linear and quadratic constraints. Then, an exact penalty function is employed to construct a sequence of unconstrained optimization problems, each of which can be solved effectively by unconstrained optimization techniques, such as conjugate gradient or quasi-Newton methods. It is shown that any local optimal solution of the unconstrained optimization problem is a local optimal solution of the transformed nonlinear constrained continuous optimization problem when the penalty parameter is sufficiently large. Numerical experiments are carried out to test the efficiency of the proposed method.     

关于二次函数的约束优化的算法研究

在本篇论文中,我们尝试用共轭方向法来处理二次函数的约束优化问题．我们 首先讨论了一下正定时的情况,再讨论负定时的情况．对于正定二次函数的优化问题,我 们提出一个算法,可以构造一列收敛到最优点的数列．对于负定二次函数的优化问题,我 们给出了一些结果．     

A superlinearly convergent method of quasi-strongly sub-feasible directions with active set identifying for constrained optimization

Combining the norm-relaxed sequential quadratic programming (SQP) method and the idea of method of quasi-strongly sub-feasible directions (MQSSFD) with active set identification technique, a new SQP algorithm for solving nonlinear inequality constrained optimization is proposed. Unlike the previous work, at each iteration of the proposed algorithm, the norm-relaxed quadratic programming (QP) subproblem only consists of the constraints corresponding to an active identification set. Moreover, the high-order correction direction (used to avoid the Maratos effect) is yielded by solving a system of linear equations (SLE) which also includes only the constraints and their gradients corresponding to the active identification set, therefore, the scale and the computation cost of the high-order correction directions are further decreased. The arc search in our algorithm can effectively combine the initialization processes with the optimization processes, and the iteration points can get into the feasible set after a finite number of iterations. Furthermore, the arc search conditions are weaker than the previous work, and the computation cost is further reduced. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ). If the strong second-order sufficient conditions are satisfied, then the active constraints are exactly identified by the identification set. Without the strict complementarity, superlinear convergence can be obtained. Finally, some elementary numerical results are reported.     

Dual Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints

A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap.     

Acceleration of the leastpth algorithm for minimax optimization with engineering applications

Over the past few years a number of researchers in mathematical programming and engineering became very interested in both the theoretical and practical applications of minimax optimization. The purpose of the present paper is to present a new method of solving the minimax optimization problem and at the same time to apply it to nonlinear programming and to three practical engineering problems. The original problem is defined as a modified leastpth objective function which under certain conditions has the same optimum as the original problem. The advantages of the present approach over the Bandler-Charalambous leastpth approach are similar to the advantages of the augmented Lagrangians approach for nonlinear programming over the standard penalty methods.This work was supported by the National Research Council of Canada under Grant A4414, and from the University of Waterloo.