Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems

Ziye Shi; Qingwei Jin

doi:10.3934/jimo.2014.10.871

Article Contents

2014, Volume 10, Issue 3: 871-882. Doi: 10.3934/jimo.2014.10.871

This issue Previous Article An alternating linearization method with inexact data for bilevel nonsmooth convex optimization Next Article A nonlinear conjugate gradient method for a special class of matrix optimization problems

Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems

Ziye Shi^1, and
Qingwei Jin^2,

1.
Department of Mathematical Sciences, Tsinghua University, Beijing, 100084
2.
Department of Management Science and Engineering, Zhejiang University, Hangzhou, Zhejiang 310058

Received: October 2011

Revised: July 2013

Published: July 2014

Abstract / Introduction Related Papers Cited by

Abstract

In this paper, we present an optimality condition which could determine whether a given KKT solution is globally optimal. This condition is equivalent to determining if the Hessian of the corresponding Largrangian is copositive over a set. To find the corresponding Lagrangian multiplier, two linear conic programming problems are constructed and then relaxed for computational purpose. Under the new condition, we proposed a local search based scheme to find a global optimal solution and showed its effectiveness by three examples.

Keywords:

Mathematics Subject Classification: 49N15, 49M37, 90C26, 90C20.

Citation:

Related Papers

Cited by

References

[1]	I. M. Bomze, Copositivity conditions for global optimality in indefinite quadratic programming problems, Czechosl. J. Oper. Res., 1 (1992), 7-19.
[2]	I. M. Bomze, Copositive optimization - recent developments and applications, Eur. J. Oper. Res., 216 (2012), 509-520.doi: 10.1016/j.ejor.2011.04.026.
[3]	Z. Deng, S.-C. Fang, Q. Jin and W. Xing, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme, Eur. J. Oper. Res., 229 (2013), 21-28.doi: 10.1016/j.ejor.2013.02.031.
[4]	M. Dür, Copositive programming - a survey, in Recent Advances in Optimization and its Applications in Engineering, Springer, 2010, 3-20.
[5]	D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization, J. Global Optim., 17 (2000), 127-160.doi: 10.1023/A:1026537630859.
[6]	D. Y. Gao, Advances in canonical duality theory with applications to global optimization, in Proceedings of the Fifth International Conference on Foundations of Computer-Aided Process Operations (FOCAPO 2008) (eds. M. Ierapetriou, M. Bassett and S. Pistikopoulos), Omni Press, 2008, 73-82.
[7]	M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, CA, 1979.
[8]	J.-B. Hiriart-Urruty and A. Seeger, Variational approach to copositive matrices, SIAM Rev., 52 (2010), 593-629.doi: 10.1137/090750391.
[9]	V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions, Math. Program., 110 (2007), 521-541.doi: 10.1007/s10107-006-0012-5.
[10]	J. Linderoth, A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program. Ser. B, 103 (2005), 251-282.doi: 10.1007/s10107-005-0582-7.
[11]	M. S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Applications of second-order cone programming, Linear Algebra Appl., 284 (1998), 193-228.doi: 10.1016/S0024-3795(98)10032-0.
[12]	C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems, SIAM J. Optim., 21 (2011), 1475-1490.doi: 10.1137/100793955.
[13]	C. Lu, Z. Wang, W. Xing and S.-C. Fang, Extended canonical duality and conic programming for solving 0-1 quadratic programming problems, J. Ind. Manag. Optim., 6 (2010), 779-793.doi: 10.3934/jimo.2010.6.779.
[14]	P. M. Pardalos and S. A. Vavasis, Quadratic programming with one negative eigenvalue is NP-hard, J. Global Optim., 1 (1991), 15-22.doi: 10.1007/BF00120662.
[15]	J.-M. Peng and Y.-X. Yuan, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J. Optim., 7 (1997), 579-594.doi: 10.1137/S1052623494261520.
[16]	A. Saxena, P. Bonami and J. Lee, Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, Math. Program. Ser. B, 124 (2010), 383-411.doi: 10.1007/s10107-010-0371-9.
[17]	J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Math. Oper. Res., 28 (2003), 246-267.doi: 10.1287/moor.28.2.246.14485.
[18]	J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Interior point methods, Optim. Methods Softw., 11/12 (1999), 625-653.doi: 10.1080/10556789908805766.
[19]	Y. Tian, S.-C. Fang, Z. Deng and W. Xing, Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming, J. Ind. Manag. Optim., 9 (2013), 703-721.doi: 10.3934/jimo.2013.9.703.
[20]	Y. Tian and C. Lu, Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems, J. Ind. Manag. Optim., 7 (2011), 1027-1039.doi: 10.3934/jimo.2011.7.1027.
[21]	J. Zhou, D. Chen, Z. Wang and W. Xing, A conic approximation method for the 0-1 quadratic knapsack problem, J. Ind. Manag. Optim., 9 (2013), 531-547.doi: 10.3934/jimo.2013.9.531.