American Institute of Mathematical Sciences

Advanced
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

Ziye Shi 1, and  Qingwei Jin 2,

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.
Keywords: Quadratic programming, copositive programming., optimality condition, algorithm.
Mathematics Subject Classification: 49N15, 49M37, 90C26, 90C2.
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-19. Google Scholar

[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.  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-28. 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, Springer, 2010, 3-20. Google Scholar

[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.  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, M. Bassett and S. Pistikopoulos), Omni Press, 2008, 73-82. 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., San Francisco, CA, 1979.  Google Scholar

[8]

J.-B. Hiriart-Urruty and A. Seeger, Variational approach to copositive matrices, SIAM Rev., 52 (2010), 593-629. 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-541. 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-282. 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-228. 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-1490. 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-793. 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-22. 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-594. 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-411. 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-267. 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-653. 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-721. 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-1039. 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-547. 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-19. Google Scholar

[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.  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-28. 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, Springer, 2010, 3-20. Google Scholar

[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.  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, M. Bassett and S. Pistikopoulos), Omni Press, 2008, 73-82. 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., San Francisco, CA, 1979.  Google Scholar

[8]

J.-B. Hiriart-Urruty and A. Seeger, Variational approach to copositive matrices, SIAM Rev., 52 (2010), 593-629. 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-541. 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-282. 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-228. 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-1490. 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-793. 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-22. 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-594. 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-411. 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-267. 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-653. 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-721. 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-1039. 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-547. 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, 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, 2020, 16 (2) : 623-631. 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]

Bhawna Kohli. Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020114
[6]

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
[7]

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
[8]

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
[9]

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075
[15]

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
[16]

Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2331-2343. doi: 10.3934/jimo.2020071
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences