---
abstract: 'Recent research has focused on the complexity of extensions of the classical trust-region subproblem, which addresses the minimization of a quadratic function over a unit ball in ${\mathbb{R}}^n,$ a problem of importance in many applications. Even though the trust-region subproblem can be considered well-solved (both from the perspective of theory and implementation) even minor extensions are NP-hard. The CDT (Celis-Dennis-Tapia) problem is an extension of the trust-region subproblem, involving the minimization of a quadratic function over the intersection of two ellipsoids in ${\mathbb{R}}^n$. In this paper we show how to adapt a construction of Barvinok so as to obtain a polynomial-time algorithm for quadratic programming with a fixed number of quadratic constraints (one of which is ellipsoidal) under the bit model of computing.'
---

0.1cm

Daniel Bienstock, Columbia University, December 2013

Introduction {#intro}
============

The classical trust-region subproblem can be stated as $\min \{ f(x) \, : \, \norm{x} \le 1, \, x \in {\mathbb{R}}^n \}$ where $f \, : \, {\mathbb{R}}^n \rightarrow {\mathbb{R}}$ is a quadratic function, i.e. a polynomial of degree at most two. This problem, which has received a great deal of attention in the literature because of a rich set of applications, can be efficiently solved – it is polynomial-time solvable and effective implementations are available. See @trustbook (and references therein), @yeold. At the same time, seemingly minor extensions of the trust-region subproblem, such as the addition of an arbitrary family of linear constraints, give rise to NP-hard problems, and recent work has focused on understanding which extensions are polynomial-time solvable. See @bureranstreicher, @yangburer0, @danoalex for recent complexity results.

The CDT (Celis-Dennis-Tapia) problem @CDT is of the form $$(CDT) \quad \min \{ f(x) \, : \, g_2(c) \le 0, \ g_2(x) \le 0, \, x \in {\mathbb{R}}^n \}$$ where $f(x)$ is a quadratic and for $i = 1, 2$ the set $\{x \in {\mathbb{R}}^n \, : \, g_i(x) \le 0 \}$ defines an ellipsoid. Thus, the CDT problem can be viewed as an extension of the trust-region subproblem with an added ellipsoidal constraint. The CDT problem has long generated interest, see @bureranstreicher, where it was termed the "two trust-region" problem, @aizhang, @beckeldar, @cy99, @cy09, @pengyuan, @yz, @JeLeeLi, @pengyuan, @yuan; also see @yangburer and @bomzeoverton, as well as their references. Broadly speaking these papers have sought to exploit the connection between CDT and convex optimization, in particular semidefinite programming; this approach is related to the use of the S-Lemma to solve the classical trust-region subproblem (see @polter). The inclusion of a second ellipsoidal constraint dramatically increases the complexity of the underlying geometry, even in low dimension, as demonstrated in particular in the elegant analysis in @yangburer. From our perspective, this analysis highlights an underlying combinatorial (or perhaps, enumerational) behavior of CDT problems as evinced by the local structure of solutions to systems of quadratic inequalities. Recently, an algorithm for quadratic programming with two quadratic constraints, which runs in polynomial time under appropriate assumptions, was presented in @SNTI.

A separate line of work has produced results of a very different flavor in order to address related problems. Barvinok @barvinok ("Problem(1.1)") proved that for each each positive integer $K$ there is a polynomial-time algorithm to decide if a system of the form

\[barv\] $$\begin{aligned}
x^T M_i x & = & 0, \quad 1 \le i \le K, \\
\| x \|^2 & = & 1,\end{aligned}$$

is feasible, where $x \in {\mathbb{R}}^n$ and $M_i$ is an $n \times n$ matrix for $1 \le i \le K$. The construction in @barvinok relies on the model of computing over the reals (e.g., infinite-precision is assumed) however the extension to the standard bit model of computing should be straightforward @barvpersonal.

Related and stronger results were presented by Grigoriev and Pasechnik in @dima. Moreover, it was argued in @dima2 that the results in @dima imply that a polynomial-time algorithm for a generalization of CDT exists. Also see @baspasu. Yet another line of research comes from the algebraic and computational geometry communities, in particular the theory of "roadmaps" of semi-algebraic sets, which was started in @canny. This topic appears related to the work cited above on "sampling" algebraic sets. See @basuetal, and @seldinschost for recent research results and additional citations. These research efforts have produced results with applications to diverse problem domains. It is quite possible that other polynomial-time algorithms for generalizations of CDT can be derived from this work. A nontrivial point concerning such algorithms is whether they would attain polynomial-time complexity under the bit model of computation, as opposed to exact computation over the reals.

In this note we present a simple procedure that uses a weak version of Barvinok's construction to obtain a polynomial-time algorithm for a generalization of CDT under the standard bit model of computing. This algorithm will use a relaxed version of feasibility, as follows.

\[epsfeas\] Let $f_i(x) \le 0$, $1 \le i \le m$ be a system of inequalities where $x \in {\mathbb{R}}^n$.

-   Given $0 \le \epsilon < 1$ a vector $\hat x \in {\mathbb{R}}^n$ is called $\epsilon$-feasible for the system if $f_i(\hat x) \le \epsilon$ for $1 \le i \le m$. If such a vector exists we will say that the system is $\epsilon$-feasible.

-   An algorithm that, given any $0 < \epsilon < 1$ either proves that the system is infeasible, or proves that it is $\epsilon$-feasible will be called a <span>**weak feasibility algorithm**</span>. Note that we insist on $\epsilon > 0$.

The weak version of Barvinok's construction is as follows:

\[weakalgo\]We will assume that for each integer $K$, there is a weak feasibility algorithm for systems of the type (\[barv\]) with running time polynomial in the size of the data and in $\log \epsilon^{-1}$.

Barvinok's method @barvinok clearly fulfills this role, as does Grigoriev and Pasechnik's @dima. It is also possible that faster weak feasibility algorithms exist, as opposed to algorithms for exact feasibility as in (\[barv\]). Also see @barvlinf.\
To describe our main result suppose that for $0 \le i \le p$, $\ g_i(x)$ is a quadratic, over $x \in {\mathbb{R}}^n$. We consider the problem $$\begin{aligned}
&&  \min \, \{ \, g_0(x) \, : \, g_i(x) \le 0, \ 1 \le i \le p \, \}, \label{cdtgen}\end{aligned}$$ and prove:

\[main\] For each fixed integer $p \ge 1$ there is an algorithm with the following properties. Given a problem of the form (\[cdtgen\]) where at least one of the $g_i(x)$ with $i \ge 1$ is strictly convex, and $0 < \epsilon < 1$, the algorithm either

-   proves that problem (\[cdtgen\]) is infeasible,

or

-   computes an $\epsilon$-feasible vector $\hat x$ such that there exists no feasible $x$ with $g_0(x) < g(\hat x) - \epsilon$.

Under Assumption \[weakalgo\] the algorithm runs in polynomial time. More precisely, the algorithm makes a sequence of calls to a weak feasibility algorithm for problems of type (\[barv\]) with $K = O(p)$; the length of the sequence is polynomial in the number of bits in the data and $\log \epsilon^{-1}$, as is the size of the coefficients of the matrices $M_i$, and as is all additional work carried out by the algorithm.

Thus, under Assumption \[weakalgo\], Theorem \[main\] implies that a polynomial-time algorithm for CDT exists. Theorem \[main\] is proved in several steps in Section \[construction\]. Throughout, we assume $n \ge 2$.

The construction {#construction}
================

This section is organized as follows. In Section \[algorithm1\] we describe an algorithm to determine if a system of $m$ quadratic inequalities is $\epsilon$-feasible; this algorithm runs in polynomial time for each fixed $m$ provided that at least one of the quadratics is strictly convex. In Section \[binsearch\] the algorithm in Section \[algorithm1\] is used to compute the value of problem (\[cdtgen\]) within tolerance $\epsilon$, in polynomial time, under the assumptions in Theorem \[main\]. However, this does not yet yield a proof of Theorem \[main\] because the algorithm we describe in Section \[algorithm1\] relies on the weak feasibility algorithm in Assumption \[weakalgo\] as a subroutine. That algorithm (and in the strict sense, Barvinok's) decides if a system of the form (\[barv\]) is $\epsilon$-feasible but without producing an explicit $\epsilon$-feasible vector. In Section \[explicit\] we show how to refine our algorithm from Section \[algorithm1\] so as to produce an $\epsilon$-feasible vector in the case that infeasibility is not proved. This fact, together with the results in Section \[binsearch\] will be used to complete the proof of Theorem \[main\].

Systems of quadratic inequalities {#algorithm1}
---------------------------------

Here we consider a system of quadratic inequalities $$\begin{aligned}
f_i(x) & \le & 0, \quad 1 \le i \le m. \label{manyq}\end{aligned}$$ We write $$\begin{aligned}
f_i(x) & \doteq & x^T A_i x + c^T_i x + d_i \label{quad-def} \end{aligned}$$ where $A_i \in {\mathbb{R}}^{n \times n}$ and symmetric, $c_i \in {\mathbb{R}}^n$ and $d_i \in {\mathbb{R}}$. Such a system describes the feasibility set for a problem of the form (\[cdtgen\]); more generally we will use the solution of systems of the form (\[manyq\]) as steps in our algorithm for problem (\[cdtgen\]). Our main result for this section, proved below, is as follows:

\[punch\] Under Assumption \[weakalgo\], for each fixed $m$ there is a polynomial-time weak feasibility algorithm for any system of type (\[manyq\]) where $A_i \succ 0$ for at least one index $i \ge 1$.

We will first prove two technical results, Lemma \[equiv0\] and \[equiv\], under the assumptions of Theorem \[punch\]. We assume, without loss of generality that $$\begin{aligned}
 f_1(x) & = & \norm{x}^2 - 1. \label{one}\end{aligned}$$ Then, for $2 \le i \le m$, there exists (polynomially computable) $U_i > 0$, such that $$|f_i(x)| \le U_i, \quad \mbox{for each $x \in {\mathbb{R}}^n$ with $\norm{x}^2 \le 2$.}$$ Now consider the following system of quadratic equations on real variables $v_0, x_1, \ldots, x_n, s_1, \ldots, s_m, w_2, \ldots, w_m$:

\[sys2\] $$\begin{aligned}
x^T A_i x + c^T_i v_0 x + d_i v_0^2 + s_i^2 & = & 0 \quad \quad 1 \le i \le m, \label{sys2a} \\
\frac{s_i^2 + w_i^2}{U_i} - v_0^2 & = & 0 \quad \quad 2 \le i \le m,\label{sys2b} \\
\norm{x}^2 + s_1^2 + \sum_{i = 2}^n \frac{s_i^2 + w_i^2}{U_i} + v_0^2 
& = & m + 1. \label{sys2c}\end{aligned}$$

\[equiv0\] Let $0 \le \delta < 1$ and suppose that $$\hat z \ = \ (\hat v_0, \hat x_1, \ldots, \hat x_n, \hat s_1, \ldots, \hat s_m, \hat w_2, \ldots, \hat w_m)^T$$ is a $\delta$-feasible solution to (\[sys2a\])-(\[sys2b\]). Then <span>**(i)**</span> $$\begin{aligned}
&& m \hat v_0^2 - m \delta \ \le \ \norm{\hat x}^2 + \hat s_1^2 + \sum_{i = 2}^n \frac{\hat s_i^2 + \hat w_i^2}{U_i} \ \le \ m \hat v_0^2 + m \delta. \label{thesum}\end{aligned}$$ <span>**(ii)**</span> If $\hat z$ is also $\delta$-feasible for (\[sys2c\]) $$1 - \delta \le \hat v_0^2 \le  1 + \delta.$$

<span>*Proof.*</span> (i) Note that $\delta$-feasibility of $\hat x$ applied to (\[sys2a\]) for $i = 1$ states $$-\delta \ \le \ \norm{\hat x}^2 - \hat v_0^2 + \hat s^2_1 \ \le \ \delta,$$ and applied to (\[sys2b\]) it states $$-\delta \ \le \ \frac{\hat s_i^2 + \hat w_i^2}{U_i} - \hat v_0^2 \ \le \ \delta, \quad 2 \le i \le m.$$ Adding these inequalities yields (\[thesum\]). (ii) Since $\hat x$ is $\delta$-feasible for (\[sys2c\]) $$m+1 - \delta \ \le \ \norm{\hat x}^2 + \hat s_1^2 + \sum_{i = 2}^n \frac{\hat s_i^2 + \hat w_i^2}{U_i} + \hat v_0^2 \ \le \ m+1 + \delta$$ which together with (\[thesum\]) implies the desired result.

------------------------------------------------------------------------

\
Let $M$ denote the largest absolute value of a coefficient in system (\[sys2\]).

\[equiv\] Let $ 0 \le \epsilon < 1/2$. (a) Suppose (\[manyq\]) is $\epsilon$-feasible. Then (\[sys2\]) is $m\epsilon$-feasible. (b) Conversely, if (\[sys2\]) is $\epsilon$-feasible, then (\[manyq\]) is $(2n + 1)M \epsilon$-feasible.

<span>*Proof.*</span> (a) Suppose first that $\tilde x$ is an $\epsilon$-feasible solution to (\[manyq\]). Define: $$\begin{aligned}
\tilde v_0 & \doteq & 1,\\
\tilde s_i & \doteq & \sqrt{ \max\{0, -f_i(\tilde x)\}}, \quad 1 \le i \le m, \label{slack}\\
\tilde w_i & \doteq & \sqrt{ U_i - \tilde s_i^2}, \quad 2 \le i \le m. \label{comp}\end{aligned}$$ In (\[comp\]), the value in the radical is nonnegative since $|\tilde x|^2 \le 1 + \epsilon < 2$. Now we claim that $$\tilde z \doteq (\tilde x_1 , \ldots, \tilde x_n, \tilde v_0, \tilde s_1, \ldots, \tilde s_m, \tilde w_2, \ldots, \tilde w_m)^T$$ is an $\epsilon$-feasible solution to (\[sys2\]). To see this, note that $\tilde v_0 = 1$ and (\[slack\]) imply that $\tilde z$ is $\epsilon$-feasible for (\[sys2a\]). Likewise, $\tilde z$ satisfies (\[sys2b\]) by (\[comp\]) and $\tilde v_0 = 1$. Finally, Lemma \[equiv0\], part (i) (with $\hat x = \tilde x$ and $\delta = \epsilon$), together with $\tilde v_0 = 1$ implies that $\tilde z$ is $m\epsilon$-feasible for (\[sys2c\]), as desired.\
(b) For the converse, suppose $$\hat z \doteq (\hat x_1 , \ldots, \hat x_n, \hat v_0, \hat s_1, \ldots, \hat s_m, \hat w_2, \ldots, \hat w_m)^T$$ is $\epsilon$-feasible for (\[sys2\]). By Lemma \[equiv0\] (ii), $$\begin{aligned}
&& 1 - \epsilon \ \le \ \hat v_0^2 \le 1 + \epsilon. \label{boundonvprev}\end{aligned}$$ This implies $$\begin{aligned}
&& 1 - \epsilon \ \le \ | \hat v_0| \le 1 + \epsilon, \label{boundonv0}\end{aligned}$$ and together with is $\epsilon$-feasibility of $\hat x$ for (\[sys2a\]) with $i = 1$, it implies $ \norm{\hat x}^2 + \hat s_1 ^2 \ \le \ 1 + 2 \epsilon $ and therefore $$\begin{aligned}
&& | \hat x_j | \le 1 + \epsilon, \quad \mbox{for $1 \le j \le n$}.  \label{boundonxj}\end{aligned}$$ Then (\[boundonvprev\])-(\[boundonxj\]) imply that for each $1 \le j \le n$, $|v_0 \hat x_j - \hat x_j| \le \epsilon |\hat x_j| \le \epsilon^2 + 2 \epsilon < 2$. Hence, using "${\mathop{\rm sgn}}$" indicate the sign function, $\epsilon$-feasibility of $\hat x$ for (\[sys2a\]) imply that ${\mathop{\rm sgn}}(\hat v_0) (\hat x_1 , \ldots, \hat x_n)^T$ is $(2n + 1)M \epsilon$-feasible for (\[manyq\]).

------------------------------------------------------------------------

\[approx\] A system (\[manyq\]) is feasible if and only if the corresponding system (\[sys2\]) is feasible.

<span>*Proof.*</span> Use $\epsilon = 0$ in Lemma \[equiv\].

------------------------------------------------------------------------

\
Now we can present the proof of the main result in this section.\
<span>*Proof of Theorem \[punch\].*</span> Consider the corresponding system (\[sys2\]), and let $\delta \doteq \frac{\epsilon}{(2n + 1)M}$. Using the method in Assumption \[weakalgo\], we terminate in polynomial time with a proof that system (\[sys2\]) is infeasible, in which case system (\[manyq\]) is infeasible (by Corollary \[approx\]), or, using part (b) of Lemma \[equiv\], with a proof that (\[manyq\]) is $\epsilon$-feasible.

------------------------------------------------------------------------

Estimating the value of problem (\[cdtgen\]) {#binsearch}
--------------------------------------------

In what follows we will use the following convention.

Consider an optimization problem $$\begin{aligned}
&& H^* \ \doteq \ \min \{ f(x) \, : \, h_i(x) \le 0, \ 1 \le i \le k \}. \label{Hopt}\end{aligned}$$ Given $0 < \epsilon < 1$ a rational $V$ is called an $\epsilon$-estimate for (\[Hopt\]) if $V \le H^*$ and there exists some vector $\bar x$ with $h_i(x) \le \epsilon$ for $1 \le i \le k$ and $f(\bar x) \le V + \epsilon$. We will likewise define $\epsilon$-estimates for maximization problems.

Let $G^*$ be the value of problem (\[cdtgen\]), i.e. $G^* \ \doteq \ \min \{ g_0(x) \, : \, g_i(x) \le 0, \ 1 \le i \le p \}.$ In this section we provide a polynomial-time procedure that produces one of two outcomes, given $0 < \epsilon < 1:$

-   It proves that (\[cdtgen\]) is infeasible.

-   It produces an $\epsilon$-estimate for (\[cdtgen\]).

We stress that in case (ii) the vector $\bar x$ that yields the $\epsilon$-estimate is not explicitly known. The algorithm, which amounts to a modified form of binary search, works as follows. As the initial step we run the weak feasibility problem on the system $\{ x \in {\mathbb{R}}^n : \, g_i(x) \le 0, \ 1 \le i \le p \},$ and if infeasibility is determined, we stop with outcome (i). Otherwise we know some $\epsilon$-feasible point exists. We next compute a rational $U > 1$ such that $ |g_0(x)| \le U $ for every $\epsilon$-feasible $x$. Such a value $U$ exists and is polynomial-time computable since we assume that at least one of the $g_i(x)$, for $i \ge 1$, is positive definite.

In a typical iteration of the modified binary search we solve the weak feasibility problem, with tolerance $\epsilon$, for the system of the form

\[redx\] $$\begin{aligned}
g_i(x) & \le & \ \, 0  \quad \mbox{for} \ 1 \le i \le p, \\
g_0(x) & \le &  \ \, V \end{aligned}$$

If (\[redx\]) is infeasible, then clearly $V \le G^*$ and otherwise there exists an $\epsilon$-feasible $\bar x$ with $g_0(\bar x) \le V + \epsilon$. Clearly, after a number of iterations which is $O(\log U + \log \epsilon^{-1})$ (i.e. is polynomial in the number of bits in the data) we will terminate with one of the two desired outcomes.\
<span>**Remark.**</span> Assume (\[cdtgen\]) is feasible. For a given $\epsilon$ denote by $\bar x(\epsilon)$ the $\bar x$ vector implicit in the final iteration of the modified search. Similarly denote by $V(\epsilon)$ the final value of $V$. Since the feasible region for (\[cdtgen\]) is contained in a compact set, we have that as $\epsilon \rightarrow 0^+$, the sequence of vectors $\bar x(\epsilon)$ will have an accumulation point which must be an optimal solution for (\[cdtgen\]), and the corresponding accumulation point of the values $V(\epsilon)$ is the optimal value for problem (\[cdtgen\]). If on the other hand (\[cdtgen\]) is infeasible then for $\epsilon > 0$ small enough the modified binary search will return infeasibility. An open question is whether exact (i.e., not weak) feasibility of (\[cdtgen\]) can be proved, using a weak feasibility oracle with a choice for $\epsilon$ where $\log \epsilon^{-1}$ is polynomially bounded in the size of the coefficients in (\[cdtgen\]).

Computing explicit solutions in polynomial time {#explicit}
-----------------------------------------------

Here we will show that for each fixed $m$ there is a polynomial-time algorithm that, given a system of the form

\[basic\] $$\begin{aligned}
&& f_i(x) \ \le \ 0, \quad 1 \le i \le q,  \\ \label{mquad}
&& \norm{x}^2 - 1 \ = \ 0, \label{mqnorm}\end{aligned}$$

where the $f_i(x)$ are quadratic polynomials, and $0 < \epsilon < 1$, either proves the system is infeasible, or computes an explicit $\epsilon$-feasible solution. Any system of the form (\[sys2\]) used in the algorithm in Section \[algorithm1\] can be reduced, by scaling, to an equivalent system (\[basic\]) with $q = O(m)$ and $n$ appropriately redefined. For $x \in {\mathbb{R}}^n$ write $$\bm{s(x)} \doteq | \norm{x}^2 - 1|.$$ Algorithm C, given next, sequentially computes values $\hat x_1, \hat x_2, \ldots, \hat x_n $, such that at termination either the system (\[basic\]) is proved infeasible or the vector $\hat x$ is $\epsilon$-feasible. In preparation for the algorithm we introduce some notation.

\[mudef\] Given $0 < \delta $ we let $0 < \mu(\delta) < \delta/4$ be any rational so that whenever $x, y \in {\mathbb{R}}^n$ are such that $\norm{x} < 2$ and $\norm{x - y} < \mu(\delta)$ then $|f_i(y) - f_i(x)| \le \delta$ for $1 \le i \le q$, and $| s(x) - s(y) | \le \delta/2$. Such a value $\mu(\delta)$ can be computed in polynomial time in the number of bits in the data and $\log \delta^{-1}$.

<span style="font-variant:small-caps;"><span>**Algorithm C**</span></span>

\

We now analyze Algorithm C.

\[fast\] Algorithm C runs in polynomial time.

<span>*Proof.*</span> First we note that $\Delta$ and $\rho$ can be computed in polynomial time in the number of bits in the data, and in $\log \epsilon^{-1}$. Thus at each iteration $k$ the size of the description of $Z^k$ is polynomially bounded in the number of bits in the data and $\log \epsilon^{-1}$.

------------------------------------------------------------------------

\[central\] Let $k \le n$. Suppose that the algorithm does not stop at Step 1a of any iteration $k' \le k$, and that $Z^k \neq \emptyset$ . There is a vector $\tilde z$, which is $\rho/2$-feasible for $Z^{k}$ with $|\hat x_k - \tilde z_k| \le \rho$.

<span>*Proof.*</span> Since at iteration $k$ we obtain outcome 1b, there is a vector $$\tilde z \ = \ (\hat x_1, \ldots , \hat x_{k-1}, \tilde z_k, \ldots, \tilde z_n)^T,$$ which is $\rho/2$-feasible for $Z^k$, and such that $$| \tilde z_k - \max\{ P_{k,k} , -M_{k,k} \}| \le \rho/2.$$ The result follows from the rounding step used to obtain $\hat x_k$ in Step 2.

------------------------------------------------------------------------

\[iterative\] Suppose system (\[basic\]) is feasible. Then for any $k \le k^*$, $Z^{k} \neq \emptyset$.

<span>*Proof.*</span> By induction on $k$. For $k = 1$ the result follows since $Z^{1}$ is the set of points feasible for system (\[basic\]). Moreover suppose $Z^{k} \neq \emptyset$ and $k < k^*$. Let $\tilde z$ be the vector produced by Lemma \[central\], and define $$\tilde w \ = \ (\hat x_1, \ldots , \hat x_{k-1}, \hat x_{k}, \tilde z_{k+1}, \ldots, \tilde z_n)^T.$$ By Lemma \[central\] $\tilde z$ is $\rho/2$-feasible for $Z^{k}$ and $\norm{ \tilde w - \tilde z} \, \le \, \rho \, < \, \mu(\Delta/2)$. The definition of the $\mu$ function thus implies that $\tilde w$ is $(\rho + \Delta)/2$-feasible for $Z^{k}$. Since $\rho < \Delta$ this implies $\tilde w \, \in \, Z^{k + 1}$.

------------------------------------------------------------------------

\[terminfeas\] If the algorithm ever stops at Step 1a, system (\[basic\]) is infeasible.

A variation on the proof for Lemma \[iterative\] shows that if the algorithm does stop at Step 1a, then it does so with $k = 1.$

\[final\] Suppose the algorithm does not stop at Step 1a. Then at termination the vector $\hat x$ is $\epsilon$-feasible for system (\[basic\]).

<span>*Proof.*</span> Let $\tilde z$ be the vector obtained by applying Lemma \[central\] at $k = k^*$. Thus

\[sumdiff\] $$\begin{aligned}
&& \sum_{k = 1}^n \tilde z_k^2 \ \le \ 1 + k^* \frac{\Delta}{2} \ < \ 1 + (n-1) \Delta, \quad \mbox{and} \label{zk*} \\
&& \sum_{k = 1}^{k^*} |\hat x_k - \tilde z_k|^2 \ = \ |\hat x_{k^*} - \tilde z_{k^*}|^2 \le \ \rho^2. \label{sumdiff2}\end{aligned}$$

If $k^* < n$ then since $\sum_{k = 1}^{k^*} \hat x_k^2 \ge 1 -  \Delta/2 + \rho^2$, we have that (\[sumdiff2\]) and $\rho \le \mu(\Delta/2)$ imply $$\begin{aligned}
&& \sum_{k = 1}^{k^*} \tilde z_k^2 \ \ge \ 1 - \Delta/2 - \Delta/2 + \rho^2 = 1 - \Delta + \rho^2, \label{sum2z}\end{aligned}$$ and so, by (\[zk\*\]), $$\sum_{k = k^* + 1}^n |\hat x_k - \tilde z_k|^2 \ = \ \sum_{k = k^* + 1}^n \tilde z_k^2 \ \le \ n \Delta - \rho^2.$$ Hence whether $k^* < n$, or not, $$\begin{aligned}
&& \norm{\hat x - \tilde z}^2 \ \le \ n\Delta \ = \ \mu^2(\epsilon/2) \label{phew}\end{aligned}$$ (by definition of $\Delta $). Now $\tilde z$ is $\rho$-feasible for $V^{k^*}$, and so $\tilde z$ is $n \Delta$-feasible for (\[basic\]). Using $\Delta = \frac{\mu(\epsilon/2)}{n} < \epsilon/(2n)$ (Definition \[mudef\]) this implies $\tilde z$ is $\epsilon/2$-feasible for (\[basic\]). This fact, together with (\[phew\]) and the definition of the $\mu$ function now implies that $\hat x$ is $\epsilon$-feasible for (\[basic\]), as desired.

------------------------------------------------------------------------

\
Corollary \[terminfeas\] and Lemma \[final\] complete the proof of Theorem \[main\]. However we can prove an additional result, namely that at termination of the algorithms all entries $\hat x_k$ with $k \le k^*$ are nonzero, and "large."

\[it2\] Let $k \le k^*$. Then $|\hat x_k| \ \ge \ [ \frac{\Delta}{4n}]^{1/2} - \rho/2 \ \ge \ \frac{1}{2}[ \frac{\Delta}{4n}]^{1/2}$.

<span>*Proof.*</span> Since the algorithm has not terminated by iteration $k -1$, we have $\sum_{j = 1}^{k-1} \hat x_j^2 \le 1 - \Delta/2 + \rho^2$. Since at iteration $k$ the algorithm does not stop in Step 1a, there is a vector $\breve z$ that is $\rho/2$-feasible for $Z^k$. Thus $$\begin{aligned}
&& \sum_{j = 1}^{k-1} \hat x_j^2 + \sum_{j = k}^n \breve x_j^2 \ \ge \ 1 - n \rho/2, \label{float}\end{aligned}$$ As a result, $\sum_{j = k}^n \breve x_j^2$ is "large," i.e. $ \sum_{j = k}^n \breve x_j^2 \ > \ \Delta/2 - n \rho/2 - \rho^2 > \Delta/4.$ This concludes the proof, since as per Step 2 of the algorithm $|\breve x_k| \ge (\frac{\Delta}{4n})^{1/2}$ .

------------------------------------------------------------------------

\
<span>**Acknowledgment.**</span> This work was partly supported by ONR award N00014-13-1-0042, LANL award "Grid Science" and DTRA award HDTRA1-13-1-0021.\

<span>99</span> , Strong duality for the CDT subproblem: a necessary and sufficient condition, <span>*SIAM J. Optim.*</span> <span>**19**</span> (2008), 1735-­1756.

, Feasibility Testing for Systems of Real Quadratic Equations, <span>*Disc. Comput. Geometry*</span> <span>**10**</span> (1993), 1 – 13.

, Estimating $L^{\inf}$ norms by $L^{2k}$ norms for functions on orbits, <span>*Found. Comput. Math.*</span> <span>**2**</span> (2002), 393–412.

, personal communication (2014).

, Bounding the Betti numbers and computing the Euler-Poincare characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials, arXiv.org preprint math.AG/0708.3522 (shortened version in <span>*J. European Math. Soc.*</span> <span>**12**</span> (2010), 529 –- 553).

, Algorithms in real algebraic geometry, volume 10 of <span>*Algorithms and Computation in Mathematics*</span>. Springer-Verlag, second edition (2006).

, Strong duality in nonconvex quadratic optimization with two quadratic constraints, <span>*SIAM J. Optim.*</span> <span>**17**</span> (2006), 844­-860.

, Polynomial solvability of variants of the trust-region subproblem. <span>*Proc. 2014 ACM-SIAM Symposium on Discrete Algorithms (SODA '14)*</span>. http://www.optimization-online.org/DB$\_$HTML/2013/07/3951.html.

, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, <span>*Math. Programming*</span> (2014) 1–18.

, Second-order cone constraints for extended trust-region subproblems, <span>*SIAM Journal on Optimization*</span> <span>**23**</span> 917-772-6053.

, The complexity of robot motion planning. PhD thesis, MIT (1987).

, A trust region strategy for nonlinear equality constrained optimization. In P.T. Boggs, R.H. Byrd and R.B. Shnabel, editors, <span>*Numerical Optimization*</span>, 71­-82, SIAM, Philadelphia, PA, 1985.

, On local solutions of the Celis-Dennis-Tapia subproblem, <span>*SIAM J. Opt.*</span> <span>**10**</span> (1999) 359–383.

, Strong duality for the CDT subproblem: a necessary and sufficient condition, <span>*J. Comp. Math.*</span> <span>**19**</span> (2009) 113-­124.

A. R. Conn, N. Gould and Ph. L. Toint, <span>*Trust-Region Methods*</span>, SIAM, Philadelphia (2000).

, A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. http://arxiv.org/abs/1307.7836.

, Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets, <span>*Computational Complexity*</span> <span>**14**</span> (2005), 20–52. , Quadratic optimization subject to a fixed number of quadratic constraints is polynomial-time. Slides for a talk (2002).

, Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization, <span>*Math. Program.*</span> <span>**147**</span> (2014), 171–206.

, Alternative theorems for quadratic inequality systems and global quadratic optimization, <span>*SIAM J. Optim.*</span> <span>**20**</span> (2009) 983-­1001.

, Optimality conditions for the minimization of a quadratic with two quadratic constraints, <span>*SIAM J. Optim.*</span> <span>**7**</span> (1997), 579-­594.

, A survey of the S-lemma, <span>*SIAM Review*</span> <span>**49**</span> (2007), 371 – 418.

, A Polynomial-Time Algorithm for Nonconvex Quadratic Optimization with Two Quadratic Constraints, http://www.keisu.t.u-tokyo.ac.jp/research/techrep/data/2015/METR15-03.pdf.

, The Trust Region Subproblem with Non-Intersecting Linear Constraints. To appear, <span>*Math. Programming*</span>. http://www.optimization-online.org/DB$\_$HTML/2013/02/3789.html. , A Two-Variable Analysis of the Two-Trust-Region Problem. http://www.optimization-online.org/DB$\_$HTML/2013/11/4126.html.

Y. Ye, A new complexity result on minimization of a quadratic function with a sphere constraint, in C. Floudas and P. Pardalos (eds.), <span>*Recent Advances in Global Optimization*</span> (Princeton University Press, NJ, 1992).

, New results on quadratic minimization, <span>*SIAM J. Optim.*</span> <span>**14**</span> (2003), 245 – 267.

On a subproblem of trust region algorithms for constrained optimization, <span>*Math. Programming*</span> <span>**47**</span> (1990) 53-­63.

Mon.Feb.23.083927.2015@littleboy\
Tue.Nov.26.220720.2013\

{'source': 'arXiv_out/1406'}