On the complexity of quadratic programming with two quadratic constraints

被引：0
作者：
Luca Consolini
Marco Locatelli
机构：
[1] Università di Parma,Dipartimento di Ingegneria dell’Informazione
来源：
Mathematical Programming | 2017年 / 164卷
关键词：
Quadratic problems; Complexity; Bivariate polynomial systems; 90C20 Quadratic programming; 90C26 Nonconvex programming, global optimization; 90C30 Nonlinear programming;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The complexity of quadratic programming problems with two quadratic constraints is an open problem. In this paper we show that when one constraint is a ball constraint and the Hessian of the quadratic function defining the other constraint is positive definite, then, under quite general conditions, the problem can be solved in polynomial time in the real-number model of computation through an approach based on the analysis of the dual space of the Lagrange multipliers. However, the degree of the polynomial is rather large, thus making the result mostly of theoretical interest.
引用
收藏
页码：91 / 128
页数：37
相关论文
共 18 条
  • [1] Ai W(2008)Strong duality for the CDT subproblem: a necessary and sufficient condition SIAM J. Optim. 19 1735-1756
  • [2] Zhang S(1996)Hidden convexity in some nonconvex quadratically constrained quadratic programming Math. Program. 72 51-63
  • [3] Ben-Tal A(2014)Hidden conic quadratic representation of some nonconvex quadratic optimization problems Math. Program. 143 1-29
  • [4] Teboulle M(2013)Second-order cone constraints for extendedtrust-region subproblems SIAM J. Optim. 23 432451-236
  • [5] Ben-Tal A(2015)On the complexity of computing with planar algebraic curves J. Complex. 31 206-131
  • [6] den Her tog D(2015)Some results for quadratic problems with one or two quadratic constraints Oper. Res. Lett. 43 126-524
  • [7] Burer S(1995)Incorporating condition measures into the complexity theory of linear programming SIAM J. Optim. 5 506-313
  • [8] Anstreicher K(1995)Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations SIAM J. Optim. 5 286-226
  • [9] Kobel A(1999)Approximating quadratic programming with bound and quadratic constraints Math. Program. 84 219-17
  • [10] Sagraloff M(1999)Approximating global quadratic optimization with convex quadratic constraints J. Glob. Optim. 15 1-267
12