Exact feasibility in the bit model for the CDT problem and quadratic programs with a fixed number of quadratic constraints

Bienstock's note on the polynomial solvability of the CDT (Celis–Dennis–Tapia) problem proves that minimizing a quadratic function subject to a fixed number $p$ of quadratic constraints, one of them strictly convex — the CDT problem being the case of two ellipsoidal constraints — is solvable in polynomial time in the bit model in a weak (ε-relaxed) sense, conditional on a weak feasibility oracle for systems of $K$ fixed quadratic equations on the unit sphere (Assumption 1.2). The note explicitly asks whether exact, non-weak feasibility of such problems can be decided in polynomial time using only this weak oracle, with a tolerance ε whose bit-length $\log\varepsilon^{-1}$ is polynomially bounded in the input size. The note poses this exact-versus-weak-oracle question for the fixed- $p$ problem as open.

Background

The classical trust-region subproblem (TRS) asks for the minimum of a quadratic function over a Euclidean ball in $\mathbb{R}^n$ ; it is polynomial-time solvable and central to nonlinear optimization. The CDT problem — named after Celis, Dennis, and Tapia, who introduced it in 1985 as the subproblem arising in equality-constrained trust-region methods — minimizes a quadratic function over the intersection of two ellipsoids, i.e. over two quadratic constraints. Its exact complexity in the Turing (bit) model of computing — where inputs are rationals of bounded bit-length and all arithmetic must be exact or carried to polynomially many bits — is subtle: optimal values and even all feasible points may be irrational, so a bit-model algorithm must handle algebraic numbers with controlled precision. General quadratic programming is worse: with one negative eigenvalue in the objective it is already NP-hard (Pardalos–Vavasis, 1991), so positive results must restrict the number of quadratic constraints.

A key tool is a 1993 theorem of Barvinok: for each fixed integer $K$ there is a polynomial-time algorithm deciding feasibility of a system $x^{T}M_i x = 0$ ( $1 \le i \le K$ ), $\|x\|^{2} = 1$ , with rational $n \times n$ matrices $M_i$ ; however, that proof is phrased in a model of computing over the reals. Grigoriev and Pasechnik (2005) proved related and in some respects stronger sampling results: for a fixed number $k$ of quadratic maps, sample points in every connected component of the set $Z(p(Q(X)))$ (the zero set of a polynomial $p$ of degree $d$ composed with the quadratic map $Q$ ) can be computed in $(dn)^{O(k)}$ arithmetic operations, and when the ground ring is $\mathbb{Z}$ the bitsizes of all intermediate data are bounded by $(dn)^{O(k)}$ times the input bitsize; in particular, emptiness of such sets is decidable within the same bound.

Building on this, Bienstock (2014/2016) proved, under an explicit assumption, that the CDT problem and its generalization (2) — minimize a quadratic $g_0(x)$ subject to $g_i(x) \le 0$ for $1 \le i \le p$ , where $p$ is fixed and at least one $g_i$ with $i \ge 1$ is strictly convex — can be solved in polynomial time in the bit model in the weak sense. Here a vector $\hat{x}$ is ε-feasible for a system $f_i(x) \le 0$ if $f_i(\hat{x}) \le \varepsilon$ for all $i$ ; a weak feasibility algorithm either proves a system infeasible or proves it ε-feasible. The assumption (Assumption 1.2 of the note) is that for each fixed $K$ there is a weak feasibility algorithm for systems of the sphere-constrained form above, running in time polynomial in the data size and $\log\varepsilon^{-1}$ . The note states that Barvinok's construction and Grigoriev–Pasechnik's results fulfill this role, while recording that Barvinok's original algorithm is a real-model construction whose bit-model extension was asserted only informally (personal communication, 2014) — so the assumption is stated rather than proved. What the framework does not deliver is exactness: all feasibility and optimality decisions are relaxed by ε. The note closes its value-estimation section with an explicit open question: can exact (non-weak) feasibility of problem (2) be proved using only a weak feasibility oracle, with a tolerance ε whose bit-length $\log\varepsilon^{-1}$ is polynomially bounded in the size of the coefficients?

Problem Statement

Let problem (2) be: minimize a quadratic function $g_0(x)$ over $x \in \mathbb{R}^n$ subject to $g_i(x) \le 0$ for $1 \le i \le p$ , where $p \ge 1$ is a fixed integer, the $g_i$ are quadratic polynomials with rational coefficients, and at least one $g_i$ with $i \ge 1$ is strictly convex. Let a weak feasibility oracle be an algorithm that, given a system $x^{T}M_i x = 0$ ( $1 \le i \le K$ , $K$ fixed), $\|x\|^{2} = 1$ , with rational matrices $M_i$ , and a tolerance $0 < \varepsilon < 1$ , either proves the system infeasible or proves it ε-feasible (there is $\hat{x}$ with $|\hat{x}^{T}M_i\hat{x}| \le \varepsilon$ for all $i$ and $\|\hat{x}\|^{2}$ within ε of 1), in time polynomial in the input bit-size and $\log\varepsilon^{-1}$ . The oracle is a black box: a procedure that uses it may rely on no property of it beyond this weak-feasibility specification, and must be correct for every algorithm satisfying that specification.

The question, stated explicitly as open in Bienstock's note: is exact (non-weak) feasibility of problem (2) — deciding, with zero tolerance, whether there exists $x \in \mathbb{R}^n$ with $g_i(x) \le 0$ for all $1 \le i \le p$ — decidable in polynomial time in the bit model using only such a weak feasibility oracle, with every oracle call made at a tolerance ε whose bit-length $\log\varepsilon^{-1}$ is polynomially bounded in the total bit-size of the coefficients in (2)?

A positive answer is a proof, with algorithm and bit-complexity analysis, that exact feasibility of problem (2) is decidable in polynomial time in the bit model using only such a weak feasibility oracle at polynomially bounded $\log\varepsilon^{-1}$ — that is, deriving the zero-tolerance decision within the note's oracle framework. A negative answer is a proof that the weak-oracle route cannot work — for instance, a family of instances of problem (2) with polynomially bounded rational data for which any decision scheme of this framework requires an oracle tolerance ε with $\log\varepsilon^{-1}$ superpolynomial in the input size — together with the proof of that lower bound. The question concerns exact (zero-tolerance) feasibility of problem (2) using only the weak feasibility oracle within the note's framework and at full scope; an ε-relaxed decision, a restriction to special constraint geometries (e.g. two balls), a bound on the number of oracle calls alone, an answer that relies on the oracle answering exactly rather than merely ε-feasibly, or an exact decision procedure that bypasses the weak-oracle framework altogether is a different question.

References

D. Bienstock, 'A note on polynomial solvability of the CDT problem', SIAM Journal on Optimization 26(1):488–498 (2016), DOI 10.1137/15M1009871 (preprint arXiv:1406.6429), https://doi.org/10.1137/15M1009871
A. I. Barvinok, 'Feasibility testing for systems of real quadratic equations', Discrete & Computational Geometry 10:1–13 (1993), DOI 10.1007/BF02573959, https://doi.org/10.1007/BF02573959
D. Grigoriev, D. V. Pasechnik, 'Polynomial-time computing over quadratic maps I: sampling in real algebraic sets', Computational Complexity 14:20–52 (2005), DOI 10.1007/s00037-005-0189-7 (preprint arXiv:cs/0403008), https://doi.org/10.1007/s00037-005-0189-7
S. Sakaue, Y. Nakatsukasa, A. Takeda, S. Iwata, 'Solving generalized CDT problems via two-parameter eigenvalues', SIAM Journal on Optimization 26(3):1669–1694 (2016), DOI 10.1137/15100624X, https://doi.org/10.1137/15100624X
D. Bienstock, A. del Pia, R. Hildebrand, 'Complexity, exactness, and rationality in polynomial optimization', Mathematical Programming 197(2):661–692 (2023; published online 2022), DOI 10.1007/s10107-022-01818-3 (preprint arXiv:2011.08347), https://doi.org/10.1007/s10107-022-01818-3
A. Barvinok, M. Rudelson, 'When a system of real quadratic equations has a solution', Advances in Mathematics 403:108391 (2022), DOI 10.1016/j.aim.2022.108391 (preprint arXiv:2106.08119), https://doi.org/10.1016/j.aim.2022.108391
A. Barvinok, 'Testing systems of real quadratic equations for approximate solutions', arXiv:2006.09221 (2020), https://arxiv.org/abs/2006.09221
L. Consolini, M. Locatelli, 'Sharp and fast bounds for the Celis–Dennis–Tapia problem', SIAM Journal on Optimization 33(2):868–898 (2023), DOI 10.1137/21M144548X, https://doi.org/10.1137/21M144548X
M. R. Celis, J. E. Dennis, R. A. Tapia, 'A trust region strategy for nonlinear equality constrained optimization', in P. T. Boggs, R. H. Byrd, R. B. Schnabel (eds.), Numerical Optimization, SIAM, Philadelphia (1985), pp. 71–82, zbMATH 0566.65048, https://zbmath.org/0566.65048
P. M. Pardalos, S. A. Vavasis, 'Quadratic programming with one negative eigenvalue is NP-hard', Journal of Global Optimization 1:15–22 (1991), DOI 10.1007/BF00120662, https://doi.org/10.1007/BF00120662
Z. Xu, C. Ma, M. Yang, 'Linear-time algorithm for complex uniform CDT subproblem based on hidden convexity', Mathematics 14(14):2539 (2026), DOI 10.3390/math14142539, https://doi.org/10.3390/math14142539