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 and 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.

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

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.

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

[1]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete and 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 and 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 and Management Optimization, 2020, 16 (2) : 623-631. doi: 10.3934/jimo.2018170
[4]

Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055
[5]

Gang Li, Yinghong Xu, Zhenhua Qin. Optimality conditions for composite DC infinite programming problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022064
[6]

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

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

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

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

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

Bhawna Kohli. Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3209-3221. doi: 10.3934/jimo.2020114
[12]

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

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 and Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[14]

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 and Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125
[15]

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

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

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

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

Yue Qi, Tongyang Liu, Su Zhang, Yu Zhang. Robust Markowitz: Comprehensively maximizing Sharpe ratio by parametric-quadratic programming. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021235
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy