Tightening a copositive relaxation for standard quadratic optimization problems

We focus in this paper the problem of improving the semidefinite programming (SDP) relaxations for the standard quadratic optimization problem (standard QP in short) that concerns with minimizing a quadratic form over a simplex. We first analyze the duality gap between the standard QP and one of its SDP relaxations known as “strengthened Shor’s relaxation”. To estimate the duality gap, we utilize the duality information of the SDP relaxation to construct a graph G ^?. The estimation can be then reduced to a two-phase problem of enumerating first all the minimal vertex covers of G ^? and solving next a family of second-order cone programming problems. When there is a nonzero duality gap, this duality gap estimation can lead to a strictly tighter lower bound than the strengthened Shor’s SDP bound. With the duality gap estimation improving scheme, we develop further a heuristic algorithm for obtaining a good approximate solution for standard QP.     

On zero duality gap in nonconvex quadratic programming problems

We present in this paper new sufficient conditions for verifying zero duality gap in nonconvex quadratically/linearly constrained quadratic programs (QP). Based on saddle point condition and conic duality theorem, we first derive a sufficient condition for the zero duality gap between a quadratically constrained QP and its Lagrangian dual or SDP relaxation. We then use a distance measure to characterize the duality gap for nonconvex QP with linear constraints. We show that this distance can be computed via cell enumeration technique in discrete geometry. Finally, we revisit two sufficient optimality conditions in the literature for two classes of nonconvex QPs and show that these conditions actually imply zero duality gap.     

SDP reformulation for robust optimization problems based on nonconvex QP duality

In a real situation, optimization problems often involve uncertain parameters. Robust optimization is one of distribution-free methodologies based on worst-case analyses for handling such problems. In this paper, we first focus on a special class of uncertain linear programs (LPs). Applying the duality theory for nonconvex quadratic programs (QPs), we reformulate the robust counterpart as a semidefinite program (SDP) and show the equivalence property under mild assumptions. We also apply the same technique to the uncertain second-order cone programs (SOCPs) with “single” (not side-wise) ellipsoidal uncertainty. Then we derive similar results on the reformulation and the equivalence property. In the numerical experiments, we solve some test problems to demonstrate the efficiency of our reformulation approach. Especially, we compare our approach with another recent method based on Hildebrand’s Lorentz positivity.     

Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations

We propose in this paper a general D.C. decomposition scheme for constructing SDP relaxation formulations for a class of nonconvex quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. More specifically, we use rank-one matrices and constraint matrices to decompose the indefinite quadratic objective into a D.C. form and underestimate the concave terms in the D.C. decomposition formulation in order to get a convex relaxation of the original problem. We show that the best D.C. decomposition can be identified by solving an SDP problem. By suitably choosing the rank-one matrices and the linear underestimation, we are able to construct convex relaxations that dominate Shor’s SDP relaxation and the strengthened SDP relaxation. We then propose an extension of the D.C. decomposition to generate an SDP bound that is tighter than the SDP+RLT bound when additional box constraints are present. We demonstrate via computational results that the optimal D.C. decomposition schemes can generate both tight SDP bounds and feasible solutions with good approximation ratio for nonconvex quadratically constrained quadratic problems.     

Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems

In this paper we first establish a Lagrange multiplier condition characterizing a regularized Lagrangian duality for quadratic minimization problems with finitely many linear equality and quadratic inequality constraints, where the linear constraints are not relaxed in the regularized Lagrangian dual. In particular, in the case of a quadratic optimization problem with a single quadratic inequality constraint such as the linearly constrained trust-region problems, we show that the Slater constraint qualification (SCQ) is necessary and sufficient for the regularized Lagrangian duality in the sense that the regularized duality holds for each quadratic objective function over the constraints if and only if (SCQ) holds. A new theorem of the alternative for systems involving both equality constraints and two quadratic inequality constraints plays a key role. We also provide classes of quadratic programs, including a class of CDT-subproblems with linear equality constraints, where (SCQ) ensures regularized Lagrangian duality.     

A new class of alternative theorems for SOS-convex inequalities and robust optimization

In this paper, we present a new class of alternative theorems for SOS-convex inequality systems without any qualifications. This class of theorems provides an alternative equations in terms of sums of squares to the solvability of the given inequality system. A strong separation theorem for convex sets, described by convex polynomial inequalities, plays a key role in establishing the class of alternative theorems. Consequently, we show that the optimal values of various classes of robust convex optimization problems are equal to the optimal values of related semidefinite programming problems (SDPs) and so, the value of the robust problem can be found by solving a single SDP. The class of problems includes programs with SOS-convex polynomials under data uncertainty in the objective function such as uncertain quadratically constrained quadratic programs. The SOS-convexity is a computationally tractable relaxation of convexity for a real polynomial. We also provide an application of our theorem of the alternative to a multi-objective convex optimization under data uncertainty.     

均衡约束数学规划问题的一类广义Mond-Weir型对偶理论

针对均衡约束数学规划模型难以满足约束规范及难于求解的问题,基于Mond和Weir提出的标准非线性规划的对偶形式,利用其S稳定性,建立了均衡约束数学规划问题的一类广义Mond-Weir型对偶,从而为求解均衡约束优化问题提供了一种新的方法.在Hanson-Mond广义凸性条件下,利用次线性函数,分别提出了弱对偶性、强对偶性和严格逆对偶性定理,并给出了相应证明.该对偶化方法的推广为研究均衡约束数学规划问题的解提供了理论依据.     

Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers

In this paper, under the existence of a certificate of nonnegativity of the objective function over the given constraint set, we present saddle-point global optimality conditions and a generalized Lagrangian duality theorem for (not necessarily convex) polynomial optimization problems, where the Lagrange multipliers are polynomials. We show that the nonnegativity certificate together with the archimedean condition guarantees that the values of the Lasserre hierarchy of semidefinite programming (SDP) relaxations of the primal polynomial problem converge asymptotically to the common primal–dual value. We then show that the known regularity conditions that guarantee finite convergence of the Lasserre hierarchy also ensure that the nonnegativity certificate holds and the values of the SDP relaxations converge finitely to the common primal–dual value. Finally, we provide classes of nonconvex polynomial optimization problems for which the Slater condition guarantees the required nonnegativity certificate and the common primal–dual value with constant multipliers and the dual problems can be reformulated as semidefinite programs. These classes include some separable polynomial programs and quadratic optimization problems with quadratic constraints that admit certain hidden convexity. We also give several numerical examples that illustrate our results.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

An Exact Formula for Radius of Robust Feasibility of Uncertain Linear Programs

We present an exact formula for the radius of robust feasibility of uncertain linear programs with a compact and convex uncertainty set. The radius of robust feasibility provides a value for the maximal ‘size’ of an uncertainty set under which robust feasibility of the uncertain linear program can be guaranteed. By considering spectrahedral uncertainty sets, we obtain numerically tractable radius formulas for commonly used uncertainty sets of robust optimization, such as ellipsoids, balls, polytopes and boxes. In these cases, we show that the radius of robust feasibility can be found by solving a linearly constrained convex quadratic program or a minimax linear program. The results are illustrated by calculating the radius of robust feasibility of uncertain linear programs for several different uncertainty sets.     

球约束凸二次规划的一个新算法

首先利用Lagrange对偶 ,将球约束凸二次规划问题转化为无约束优化问题 ,然后运用单纯形法求解无约束优化问题 ,从而获得原问题的最优解     

Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons

At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be formulated as semidefinite programs (SDPs). The primary purpose of this paper is to present a systematic comparison of SDP relaxations for QCQP. Using theoretical analysis, it is shown that the recently developed doubly nonnegative relaxation is equivalent to the Shor relaxation, when the latter is enhanced with a partial first-order relaxation-linearization technique. These two relaxations are shown to theoretically dominate six other SDP relaxations. A computational comparison reveals that the two dominant relaxations require three orders of magnitude more computational time than the weaker relaxations, while providing relaxation gaps averaging 3% as opposed to gaps of up to 19% for weaker relaxations, on 700 randomly generated problems with up to 60 variables. An SDP relaxation derived from Lagrangian relaxation, after the addition of redundant nonlinear constraints to the primal, achieves gaps averaging 13% in a few CPU seconds.     

Faster,but weaker,relaxations for quadratically constrained quadratic programs

We introduce a new relaxation framework for nonconvex quadratically constrained quadratic programs (QCQPs). In contrast to existing relaxations based on semidefinite programming (SDP), our relaxations incorporate features of both SDP and second order cone programming (SOCP) and, as a result, solve more quickly than SDP. A downside is that the calculated bounds are weaker than those gotten by SDP. The framework allows one to choose a block-diagonal structure for the mixed SOCP-SDP, which in turn allows one to control the speed and bound quality. For a fixed block-diagonal structure, we also introduce a procedure to improve the bound quality without increasing computation time significantly. The effectiveness of our framework is illustrated on a large sample of QCQPs from various sources.     

Nonlinear Lagrangian Theory for Nonconvex Optimization

The Lagrangian function in the conventional theory for solving constrained optimization problems is a linear combination of the cost and constraint functions. Typically, the optimality conditions based on linear Lagrangian theory are either necessary or sufficient, but not both unless the underlying cost and constraint functions are also convex.We propose a somewhat different approach for solving a nonconvex inequality constrained optimization problem based on a nonlinear Lagrangian function. This leads to optimality conditions which are both sufficient and necessary, without any convexity assumption. Subsequently, under appropriate assumptions, the optimality conditions derived from the new nonlinear Lagrangian approach are used to obtain an equivalent root-finding problem. By appropriately defining a dual optimization problem and an alternative dual problem, we show that zero duality gap will hold always regardless of convexity, contrary to the case of linear Lagrangian duality.     

Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality

In this paper we show that a convexifiability property of nonconvex quadratic programs with nonnegative variables and quadratic constraints guarantees zero duality gap between the quadratic programs and their semi-Lagrangian duals. More importantly, we establish that this convexifiability is hidden in classes of nonnegative homogeneous quadratic programs and discrete quadratic programs, such as mixed integer quadratic programs, revealing zero duality gaps. As an application, we prove that robust counterparts of uncertain mixed integer quadratic programs with objective data uncertainty enjoy zero duality gaps under suitable conditions. Various sufficient conditions for convexifiability are also given.     

Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

Journal of Global Optimization - We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix...     

On the global optimality of generalized trust region subproblems

Quadratically constrained quadratic programming is an important class of optimization problems. We consider the case with one quadratic constraint. Since both the objective function and its constraint can be neither convex nor concave, it is also known as the ‘generalized trust region subproblem.’ The theory and algorithms for this problem have been well studied under the Slater condition. In this article, we analyse the duality property between the primal problem and its Lagrangian dual problem, and discuss the attainability of the optimal primal solution without the Slater condition. The relations between the Lagrangian dual and semidefinite programming dual is also given.     

Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint

In this paper, we consider the problem of minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that under a mild assumption, this problem can be solved by solving a linearly constrained convex univariate minimization problem. Finally, the superior efficiency of the new approach compared to the known semidefinite relaxation and a known approach from the literature is demonstrated by solving several randomly generated test problems.     

Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation.     

A complete characterization of strong duality in nonconvex optimization with a single constraint

We first establish sufficient conditions ensuring strong duality for cone constrained nonconvex optimization problems under a generalized Slater-type condition. Such conditions allow us to cover situations where recent results cannot be applied. Afterwards, we provide a new complete characterization of strong duality for a problem with a single constraint: showing, in particular, that strong duality still holds without the standard Slater condition. This yields Lagrange multipliers characterizations of global optimality in case of (not necessarily convex) quadratic homogeneous functions after applying a generalized joint-range convexity result. Furthermore, a result which reduces a constrained minimization problem into one with a single constraint under generalized convexity assumptions, is also presented.