On the complexity of quadratic programming with two quadratic constraints (Q2364486)

This paper deals with problems of the form \[ \begin{aligned} \min & \frac{1}{2}x^{T}Qx+q^{T}x \\ \text{s.t.} & \frac{1}{2}x^{T}x\leq \frac{1}{2} \\ & \frac{1}{2}x^{T}Ax+a^{T}x\geq u, \end{aligned} \tag{1} \] where \(A\) is a positive definite \(n\times n\) symmetric matrix. This type of problem arises as a subproblem to be solved at each iteration of a trust-region algorithm for equality constrained nonlinear problems. It was known that some particular instances of (1) were solvable in polynomial time (e.g., in the case when \(q=a=0\)). The main result of the paper, Theorem 5.2, shows that, under rather mild conditions, the so-called Algorithm 1 is a polynomial time algorithm to compute an \(\varepsilon \)-optimal solution for Problem (1). The preparation of the proof consists of three steps: 1. Identification of the KKT points for (1); 2. Discussion for the case where the Hessian of the Lagrangian function is singular, and for the case it is non-singular; and 3. Derivation of feasible solutions of (1) from approximate KKT points. As the authors point out, the degree of the polynomial is rather large, thus making the result mostly of theoretical interest.