On the complexity of quadratic programming with two quadratic constraints
成果类型：
Article
署名作者：
Consolini, Luca; Locatelli, Marco
署名单位：
University of Parma
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-016-1073-8
发表日期：
2017
页码：
91-128
关键词：
摘要：
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.