Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: 49N15, 49M37, 90C26, 90C20.


    \begin{equation} \\ \end{equation}
  • [1]

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


    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.


    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.


    M. Dür, Copositive programming - a survey, in Recent Advances in Optimization and its Applications in Engineering, Springer, 2010, 3-20.


    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.


    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.


    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.


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


    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.


    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.


    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.


    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.


    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.


    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.


    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.


    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.


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


    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.


    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.


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(271) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint