July  2014, 10(3): 871-882. doi: 10.3934/jimo.2014.10.871

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

1. 

Department of Mathematical Sciences, Tsinghua University, Beijing, 100084, China

2. 

Department of Management Science and Engineering, Zhejiang University, Hangzhou, Zhejiang 310058, China

Received  October 2011 Revised  July 2013 Published  November 2013

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.
Citation: Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871
References:
[1]

I. M. Bomze, Copositivity conditions for global optimality in indefinite quadratic programming problems,, Czechosl. J. Oper. Res., 1 (1992), 7. Google Scholar

[2]

I. M. Bomze, Copositive optimization - recent developments and applications,, Eur. J. Oper. Res., 216 (2012), 509. doi: 10.1016/j.ejor.2011.04.026. Google Scholar

[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. doi: 10.1016/j.ejor.2013.02.031. Google Scholar

[4]

M. Dür, Copositive programming - a survey,, in Recent Advances in Optimization and its Applications in Engineering, (2010), 3. Google Scholar

[5]

D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization,, J. Global Optim., 17 (2000), 127. doi: 10.1023/A:1026537630859. Google Scholar

[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, (2008), 73. Google Scholar

[7]

M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness,, W. H. Freeman and Co., (1979). Google Scholar

[8]

J.-B. Hiriart-Urruty and A. Seeger, Variational approach to copositive matrices,, SIAM Rev., 52 (2010), 593. doi: 10.1137/090750391. Google Scholar

[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. doi: 10.1007/s10107-006-0012-5. Google Scholar

[10]

J. Linderoth, A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs,, Math. Program. Ser. B, 103 (2005), 251. doi: 10.1007/s10107-005-0582-7. Google Scholar

[11]

M. S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Applications of second-order cone programming,, Linear Algebra Appl., 284 (1998), 193. doi: 10.1016/S0024-3795(98)10032-0. Google Scholar

[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. doi: 10.1137/100793955. Google Scholar

[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. doi: 10.3934/jimo.2010.6.779. Google Scholar

[14]

P. M. Pardalos and S. A. Vavasis, Quadratic programming with one negative eigenvalue is NP-hard,, J. Global Optim., 1 (1991), 15. doi: 10.1007/BF00120662. Google Scholar

[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. doi: 10.1137/S1052623494261520. Google Scholar

[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. doi: 10.1007/s10107-010-0371-9. Google Scholar

[17]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions,, Math. Oper. Res., 28 (2003), 246. doi: 10.1287/moor.28.2.246.14485. Google Scholar

[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. doi: 10.1080/10556789908805766. Google Scholar

[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. doi: 10.3934/jimo.2013.9.703. Google Scholar

[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. doi: 10.3934/jimo.2011.7.1027. Google Scholar

[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. doi: 10.3934/jimo.2013.9.531. Google Scholar

show all references

References:
[1]

I. M. Bomze, Copositivity conditions for global optimality in indefinite quadratic programming problems,, Czechosl. J. Oper. Res., 1 (1992), 7. Google Scholar

[2]

I. M. Bomze, Copositive optimization - recent developments and applications,, Eur. J. Oper. Res., 216 (2012), 509. doi: 10.1016/j.ejor.2011.04.026. Google Scholar

[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. doi: 10.1016/j.ejor.2013.02.031. Google Scholar

[4]

M. Dür, Copositive programming - a survey,, in Recent Advances in Optimization and its Applications in Engineering, (2010), 3. Google Scholar

[5]

D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization,, J. Global Optim., 17 (2000), 127. doi: 10.1023/A:1026537630859. Google Scholar

[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, (2008), 73. Google Scholar

[7]

M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness,, W. H. Freeman and Co., (1979). Google Scholar

[8]

J.-B. Hiriart-Urruty and A. Seeger, Variational approach to copositive matrices,, SIAM Rev., 52 (2010), 593. doi: 10.1137/090750391. Google Scholar

[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. doi: 10.1007/s10107-006-0012-5. Google Scholar

[10]

J. Linderoth, A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs,, Math. Program. Ser. B, 103 (2005), 251. doi: 10.1007/s10107-005-0582-7. Google Scholar

[11]

M. S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Applications of second-order cone programming,, Linear Algebra Appl., 284 (1998), 193. doi: 10.1016/S0024-3795(98)10032-0. Google Scholar

[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. doi: 10.1137/100793955. Google Scholar

[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. doi: 10.3934/jimo.2010.6.779. Google Scholar

[14]

P. M. Pardalos and S. A. Vavasis, Quadratic programming with one negative eigenvalue is NP-hard,, J. Global Optim., 1 (1991), 15. doi: 10.1007/BF00120662. Google Scholar

[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. doi: 10.1137/S1052623494261520. Google Scholar

[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. doi: 10.1007/s10107-010-0371-9. Google Scholar

[17]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions,, Math. Oper. Res., 28 (2003), 246. doi: 10.1287/moor.28.2.246.14485. Google Scholar

[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. doi: 10.1080/10556789908805766. Google Scholar

[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. doi: 10.3934/jimo.2013.9.703. Google Scholar

[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. doi: 10.3934/jimo.2011.7.1027. Google Scholar

[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. doi: 10.3934/jimo.2013.9.531. Google Scholar

[1]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653

[2]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[3]

Mansoureh Alavi Hejazi, Soghra Nobakhtian. Optimality conditions for multiobjective fractional programming, via convexificators. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018170

[4]

Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059

[5]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

[6]

Yuhua Sun, Laisheng Wang. Optimality conditions and duality in nondifferentiable interval-valued programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 131-142. doi: 10.3934/jimo.2013.9.131

[7]

Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361

[8]

Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1133-1151. doi: 10.3934/jimo.2018089

[9]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[10]

Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779

[11]

Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125

[12]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[13]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543

[14]

Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99

[15]

Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585

[16]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[17]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032

[18]

Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial & Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851

[19]

Xiuhong Chen, Zhihua Li. On optimality conditions and duality for non-differentiable interval-valued programming problems with the generalized (F, ρ)-convexity. Journal of Industrial & Management Optimization, 2018, 14 (3) : 895-912. doi: 10.3934/jimo.2017081

[20]

Ram U. Verma. General parametric sufficient optimality conditions for multiple objective fractional subset programming relating to generalized $(\rho,\eta,A)$ -invexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 333-339. doi: 10.3934/naco.2011.1.333

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]