<p><strong>Warning</strong>: As one of the comments points out, the sum of squares is not necessarily convex, so the hardness reduction suggested below does not work. The problem still lies in <span class="math-container">$\exists\mathbb{R} \subseteq \mathrm{PSPACE}$</span> though.</p>
<p>Deciding whether there is an <span class="math-container">$x \in \mathbb{R}^n$</span> such that <span class="math-container">$f_i(x) = 0$</span> for a family of quadratic polynomials is complete for the existential theory of the reals, <span class="math-container">$\exists\mathbb{R}$</span>. So testing whether <span class="math-container">$f(x) = \sum_i (f_i(x))^2 \leq 0$</span> has a solution is also complete for <span class="math-container">$\exists\mathbb{R}$</span>, and, as a sum of squares, <span class="math-container">$f$</span> is a convex function. So solving the non-emptiness problem of a convex set is as hard as deciding truth in the existential theory of the reals.</p>
<p>The hardness result goes back to <a href="https://www.ams.org/journals/bull/1989-21-01/S0273-0979-1989-15750-9/S0273-0979-1989-15750-9.pdf" rel="nofollow noreferrer">Blum, Shub, and Smale. On a Theory of Complexity over the Real Numbers</a>, it follows from the main theorem, but it's stated in the BSS-model. A statement in the <span class="math-container">$\exists\mathbb{R}$</span>-framework can be found as Lemma 3.2 in <a href="https://link.springer.com/article/10.1007/s00224-015-9662-0" rel="nofollow noreferrer">Schaefer, Stefankovic. Fixed Points, Nash Equilibria, and the Existential Theory of the Reals</a>.</p>

CC BY-SA 4.0
2023-12-14T21:51:12.327Z
Does it mean that it is in PSPACE? So it can be solved in exponential time? By what algorithm?
Erel Segal-Halevi
CC BY-SA 4.0
2023-12-15T06:02:21.867Z
A simple Google search gives this useful description on Wikipedia. https://en.wikipedia.org/wiki/Existential_theory_of_the_reals
Chandra Chekuri
CC BY-SA 4.0
2023-12-15T07:46:44.127Z
@ErelSegal-Halevi The original algorithm is due to Canny, *Some algebraic and geometric computations in PSPACE*, https://doi.org/10.1145/62212.62257 . A follow-up improvement: https://doi.org/10.1093/comjnl/36.5.409
Emil Jeřábek
CC BY-SA 4.0
2023-12-15T16:38:33.457Z
Wait a minute, the sum of squares is not necessarily **convex in $x$**.  Eg. consider $[(1-x)(1+x)]^2$ (here's [a plot](https://www.google.com/search?client=safari&rls=en&q=plot+((1-x)*(1%2Bx))**2+from+-1.5+to+1.5&ie=UTF-8&oe=UTF-8))
Neal Young
CC BY-SA 4.0
2023-12-16T14:34:21.953Z
When you say "the problem still lies in PSPACE", which problem do you mean?  It seems like you mean the problem you discuss in your answer.  But the problem in OP's post doesn't (in general) reduce to the problem you discuss in your answer, so I don't think you can conclude that OP's problem is in PSPACE.
Neal Young
CC BY-SA 4.0
2023-12-16T19:37:37.793Z
@NealYoung The case of “polynomials with rational coefficients” in the OP’s question is solvable in $\exists\mathbb R\subseteq \mathrm{PSPACE}$.
Emil Jeřábek
CC BY-SA 4.0
2023-12-17T13:36:11.940Z
@EmilJeřábek,perhaps, but I don't think the reduction described in the answer shows that (except in the easy case when the given polynomials are linear).
Neal Young
CC BY-SA 4.0
2023-12-17T15:51:52.863Z
For this direction, the trivial reduction works: $\exists\vec x\,\bigwedge_ig_i(\vec x)\le0$ is, literally, an existential statement in the theory of the reals.
Emil Jeřábek
CC BY-SA 4.0
2023-12-17T18:01:50.090Z
I am surprised that the problem can be decided in finite time, since the passage I quoted from the book on convex optimization apparently shows that the run-time might be infinite. Or maybe I did not understand it correctly?
Erel Segal-Halevi
CC BY-SA 4.0
2023-12-18T13:47:26.287Z
@ErelSegal-Halevi The quoted passage doesn't focus on polynomials, does it? The existential theory of the reals does, so this might be were the disconnect lies. Also it says "in practice". I don't think that a PSPACE algorithm is very practical, in general.
Tassle
CC BY-SA 4.0
2023-12-18T14:08:35.477Z
@EmilJeřábek, for that to work don't you need to assume something about the $g_i$'s (beyond the given assumption that they are convex)?
Neal Young
CC BY-SA 4.0
2023-12-18T14:26:06.277Z
@NealYoung I don’t even need that they are convex. I only need that they are polynomials with rational (or: real algebraic, if represented in a suitable way) coefficients, as I wrote above.
Emil Jeřábek
CC BY-SA 4.0
2023-12-19T16:27:17.407Z
@EmilJeřábek, okay, that makes sense.  (I was considering OP's question to be the general one, without the assumption that the functions are polynomials.)
Neal Young
CC BY-SA 4.0
2023-12-14T19:30:54.743Z
2023-12-15T18:18:22.907Z
2023-12-15T18:18:22.907Z
user67422
<p>Let <span class="math-container">$S\subseteq \mathbb{R}^n$</span> be a convex region defined by <span class="math-container">$$g_i(x)\leq 0, ~~i\in 1,\ldots,m,$$</span> where <span class="math-container">$g_i$</span> are convex functions.
The goal is to decide whether <span class="math-container">$S$</span> is empty, and if not - find a point <span class="math-container">$x\in S$</span>.</p>
<p>In the book of <a href="https://web.stanford.edu/%7Eboyd/cvxbook/bv_cvxbook.pdf" rel="nofollow noreferrer">Boyd and Vandenberghe</a> (chapter 11), I found the following algorithm. Solve the following <em>optimization</em> problem:</p>
<p><span class="math-container">$$\text{ mininize } ~~p~~ \text{ subject to }  ~~g_i(x)\leq p, ~~i\in 1,\ldots,m.$$</span></p>
<p>Denote the optimal solution by <span class="math-container">$(p^*,x^*)$</span>.
If <span class="math-container">$p^*&gt;0$</span>, then <span class="math-container">$S$</span> is empty. If <span class="math-container">$p^*\leq 0$</span>, then <span class="math-container">$x^*$</span> is a point in <span class="math-container">$S$</span> (in particular, if <span class="math-container">$p^* &lt; 0$</span> then <span class="math-container">$x^*$</span> is in the interior of <span class="math-container">$S$</span>; if <span class="math-container">$p^*=0$</span> then interior of <span class="math-container">$S$</span> is empty and <span class="math-container">$x^*$</span> is a boundary point).</p>
<p>The problem is that, when <span class="math-container">$p^*$</span> approaches 0, the runtime complexity of solving this auxiliary problem approaches infinity; here is the exact runtime from the book of Boyd and Vandenberghe:</p>
<p><a href="https://i.sstatic.net/ZUJyL.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ZUJyL.png" alt="enter image description here" /></a></p>
<p>As you can see, <span class="math-container">$p^*$</span> is in the denominator. They also say that:</p>
<p><a href="https://i.sstatic.net/lmYE1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lmYE1.png" alt="enter image description here" /></a></p>
<p>I would like to know what is known about the complexity of this decision problem. In particular:</p>
<ul>
<li>Suppose the functions <span class="math-container">$g_i$</span> are given explicitly (e.g. they are all polynomials with rational coefficients; this also means that they are continuously differentiable infinitely many times), and every basic arithmetic operation on real numbers takes unit time. Is there a proof that the decision problem cannot be solved in a finite number of arithmetic operations?</li>
<li>Are there sub-classes of convex functions (except linear functions) for which the decision problem can be solved in finite time? In polynomial time?</li>
</ul>
<p>EDIT: Based on the comments, it seems the question is non-trivial even in the case of <a href="https://en.wikipedia.org/wiki/Quadratic_programming" rel="nofollow noreferrer">quadratic programming</a>, where all functions <span class="math-container">$g_i$</span> are convex quadratic functions. The Wikipedia page mentions that the problem can be solved in weakly-polynomial time using the ellipsoid method, but to use the ellipsoid method we need a lower bound on the volume of the feasible region, which is not always guaranteed.</p>

CC BY-SA 4.0
2023-12-15T08:40:11.333Z
What do you know about the $g_i$? This would be easier if the inequalities stemmed from, say, a linear matrix inequality
Rodrigo de Azevedo
CC BY-SA 4.0
2023-12-15T16:40:52.453Z
There's semi-definite programming...
Neal Young
CC BY-SA 4.0
2023-12-15T16:58:17.633Z
More generally, if you can compute the gradients (derivatives) accurately, then you have a separation oracle, so you can use the [ellipsoid method](https://en.wikipedia.org/wiki/Ellipsoid_method#Theoretical_run-time_complexity_guarantee).. with the caveat that you need (roughly) an initial containing ellipsoid and a lower bound on the volume of your convex set if it is not empty.
Neal Young
CC BY-SA 4.0
2023-12-16T16:55:02.547Z
See https://en.wikipedia.org/wiki/Quadratic_programming#Complexity and https://en.wikipedia.org/wiki/Convex_optimization and https://or.stackexchange.com/questions/989/cubic-programming-and-beyond .
Neal Young
CC BY-SA 4.0
2023-12-16T17:49:23.820Z
@NealYoung  "with the caveat that you need... a lower bound on the volume of your convex set if it is not empty" --- this caveat is quite similar to the caveat with the interior-point method I cited from the book of Boyd and Vandenberghe, which works only if the optimal value of the auxiliary problem is sufficiently far from zero. But what happens if we cannot guarantee a lower bound on the volume of the convex set? Or cannot guarantee that the optimal value is sufficiently far from zero? Is there a hardness result for the general case?
Erel Segal-Halevi
CC BY-SA 4.0
2023-12-16T17:54:23.397Z
@RodrigodeAzevedo If the $g_i$ are linear, then it is known that the problem can be solved in polynomial time. I am interested in the more general case. For example, suppose the $g_i$ are polynomials of a finite degree, with rational coefficients that are given as an input. This also means that they are continuously differentiable infinitely many times.
Erel Segal-Halevi
CC BY-SA 4.0
2023-12-16T18:19:13.667Z
@ErelSegal-Halevi I was thinking along the lines of [Helton & Nie](https://doi.org/10.1137/07070526X)
Rodrigo de Azevedo
CC BY-SA 4.0
2023-12-30T18:00:49.080Z
@NealYoung I wrote in the question: every basic arithmetic operation on real numbers takes unit time (i.e., the real RAM model)
Erel Segal-Halevi
CC BY-SA 4.0
2024-01-04T20:59:27.390Z
In that case, have a look at https://cstheory.stackexchange.com/questions/4053/sum-of-square-roots-hard-problems and https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010 .  There are decision problems that can be solved in linear time in the real RAM model (assuming you can do square roots), for which no known polytime algorithm is known (in the standard model).  So one has to be careful to specify what a hardness result would mean in this model.
Neal Young
CC BY-SA 4.0
2024-01-04T21:24:33.617Z
See also the closely-related questions https://cstheory.stackexchange.com/questions/6833/what-classes-of-mathematical-programs-can-be-solved-exactly-or-approximately-in and https://cstheory.stackexchange.com/questions/44324/is-convex-optimisation-in-p/44333#44333
Neal Young
CC BY-SA 4.0
2024-01-15T15:56:42.383Z
Related: [this article](https://doi.org/10.1007/s10107-011-0499-2) shows that it is NP-hard to decide whether a feasible region defined by quartic polynomials is convex.  [Sorry for so many comments.. I think this question is very interesting!]
Neal Young
<time-complexity><convex-optimization><computing-over-reals>
Deciding whether a convex region is empty
Erel Segal-Halevi
# Deciding whether a convex region is empty

(Asked by: username_0 on 2023-12-14)

Let $S\subseteq \mathbb{R}^n$ be a convex region defined by $$g\_i(x)\leq 0, ~~i\in 1,\ldots,m,$$ where $g\_i$ are convex functions.
The goal is to decide whether $S$ is empty, and if not - find a point $x\in S$.

In the book of [Boyd and Vandenberghe](https://web.stanford.edu/%7Eboyd/cvxbook/bv_cvxbook.pdf) (chapter 11), I found the following algorithm. Solve the following *optimization* problem:

$$\text{ mininize } ~~p~~ \text{ subject to } ~~g\_i(x)\leq p, ~~i\in 1,\ldots,m.$$

Denote the optimal solution by $(p^\*,x^\*)$.
If $p^\*>0$, then $S$ is empty. If $p^\*\leq 0$, then $x^\*$ is a point in $S$ (in particular, if $p^\* < 0$ then $x^\*$ is in the interior of $S$; if $p^\*=0$ then interior of $S$ is empty and $x^\*$ is a boundary point).

The problem is that, when $p^\*$ approaches 0, the runtime complexity of solving this auxiliary problem approaches infinity; here is the exact runtime from the book of Boyd and Vandenberghe:

[![enter image description here](https://i.sstatic.net/ZUJyL.png)](https://i.sstatic.net/ZUJyL.png)

As you can see, $p^\*$ is in the denominator. They also say that:

[![enter image description here](https://i.sstatic.net/lmYE1.png)](https://i.sstatic.net/lmYE1.png)

I would like to know what is known about the complexity of this decision problem. In particular:

* Suppose the functions $g\_i$ are given explicitly (e.g. they are all polynomials with rational coefficients; this also means that they are continuously differentiable infinitely many times), and every basic arithmetic operation on real numbers takes unit time. Is there a proof that the decision problem cannot be solved in a finite number of arithmetic operations?
* Are there sub-classes of convex functions (except linear functions) for which the decision problem can be solved in finite time? In polynomial time?

EDIT: Based on the comments, it seems the question is non-trivial even in the case of [quadratic programming](https://en.wikipedia.org/wiki/Quadratic_programming), where all functions $g\_i$ are convex quadratic functions. The Wikipedia page mentions that the problem can be solved in weakly-polynomial time using the ellipsoid method, but to use the ellipsoid method we need a lower bound on the volume of the feasible region, which is not always guaranteed.

**Tags:** time-complexity, convex-optimization, computing-over-reals
> **Comments:**
> **username_1**: What do you know about the $g_i$? This would be easier if the inequalities stemmed from, say, a linear matrix inequality  
> **username_2**: There's semi-definite programming...  
> **username_2**: More generally, if you can compute the gradients (derivatives) accurately, then you have a separation oracle, so you can use the [ellipsoid method](https://en.wikipedia.org/wiki/Ellipsoid_method#Theoretical_run-time_complexity_guarantee).. with the caveat that you need (roughly) an initial containing ellipsoid and a lower bound on the volume of your convex set if it is not empty.  
> **username_2**: See https://en.wikipedia.org/wiki/Quadratic_programming#Complexity and https://en.wikipedia.org/wiki/Convex_optimization and https://or.stackexchange.com/questions/989/cubic-programming-and-beyond .  
> **username_0**: @NealYoung  "with the caveat that you need... a lower bound on the volume of your convex set if it is not empty" --- this caveat is quite similar to the caveat with the interior-point method I cited from the book of Boyd and Vandenberghe, which works only if the optimal value of the auxiliary problem is sufficiently far from zero. But what happens if we cannot guarantee a lower bound on the volume of the convex set? Or cannot guarantee that the optimal value is sufficiently far from zero? Is there a hardness result for the general case?  
> **username_0**: @RodrigodeAzevedo If the $g_i$ are linear, then it is known that the problem can be solved in polynomial time. I am interested in the more general case. For example, suppose the $g_i$ are polynomials of a finite degree, with rational coefficients that are given as an input. This also means that they are continuously differentiable infinitely many times.  
> **username_1**: @ErelSegal-Halevi I was thinking along the lines of [Helton & Nie](https://doi.org/10.1137/07070526X)  
> **username_0**: @NealYoung I wrote in the question: every basic arithmetic operation on real numbers takes unit time (i.e., the real RAM model)  
> **username_2**: In that case, have a look at https://cstheory.stackexchange.com/questions/4053/sum-of-square-roots-hard-problems and https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010 .  There are decision problems that can be solved in linear time in the real RAM model (assuming you can do square roots), for which no known polytime algorithm is known (in the standard model).  So one has to be careful to specify what a hardness result would mean in this model.  
> **username_2**: See also the closely-related questions https://cstheory.stackexchange.com/questions/6833/what-classes-of-mathematical-programs-can-be-solved-exactly-or-approximately-in and https://cstheory.stackexchange.com/questions/44324/is-convex-optimisation-in-p/44333#44333  
> **username_2**: Related: [this article](https://doi.org/10.1007/s10107-011-0499-2) shows that it is NP-hard to decide whether a feasible region defined by quartic polynomials is convex.  [Sorry for so many comments.. I think this question is very interesting!]  

---

## 1 answers

### Answer by username_3 on 2023-12-14. Score: 4

**Warning**: As one of the comments points out, the sum of squares is not necessarily convex, so the hardness reduction suggested below does not work. The problem still lies in $\exists\mathbb{R} \subseteq \mathrm{PSPACE}$ though.

Deciding whether there is an $x \in \mathbb{R}^n$ such that $f\_i(x) = 0$ for a family of quadratic polynomials is complete for the existential theory of the reals, $\exists\mathbb{R}$. So testing whether $f(x) = \sum\_i (f\_i(x))^2 \leq 0$ has a solution is also complete for $\exists\mathbb{R}$, and, as a sum of squares, $f$ is a convex function. So solving the non-emptiness problem of a convex set is as hard as deciding truth in the existential theory of the reals.

The hardness result goes back to [Blum, Shub, and Smale. On a Theory of Complexity over the Real Numbers](https://www.ams.org/journals/bull/1989-21-01/S0273-0979-1989-15750-9/S0273-0979-1989-15750-9.pdf), it follows from the main theorem, but it's stated in the BSS-model. A statement in the $\exists\mathbb{R}$-framework can be found as Lemma 3.2 in [Schaefer, Stefankovic. Fixed Points, Nash Equilibria, and the Existential Theory of the Reals](https://link.springer.com/article/10.1007/s00224-015-9662-0).

> **Comments:**
> **username_0**: Does it mean that it is in PSPACE? So it can be solved in exponential time? By what algorithm?  
> **username_4**: A simple Google search gives this useful description on Wikipedia. https://en.wikipedia.org/wiki/Existential_theory_of_the_reals  
> **username_5**: @ErelSegal-Halevi The original algorithm is due to Canny, *Some algebraic and geometric computations in PSPACE*, https://doi.org/10.1145/62212.62257 . A follow-up improvement: https://doi.org/10.1093/comjnl/36.5.409  
> **username_2**: Wait a minute, the sum of squares is not necessarily **convex in $x$**.  Eg. consider $[(1-x)(1+x)]^2$ (here's [a plot](https://www.google.com/search?client=safari&rls=en&q=plot+((1-x)*(1%2Bx))**2+from+-1.5+to+1.5&ie=UTF-8&oe=UTF-8))  
> **username_2**: When you say "the problem still lies in PSPACE", which problem do you mean?  It seems like you mean the problem you discuss in your answer.  But the problem in OP's post doesn't (in general) reduce to the problem you discuss in your answer, so I don't think you can conclude that OP's problem is in PSPACE.  
> **username_5**: @NealYoung The case of “polynomials with rational coefficients” in the OP’s question is solvable in $\exists\mathbb R\subseteq \mathrm{PSPACE}$.  
> **username_2**: @EmilJeřábek,perhaps, but I don't think the reduction described in the answer shows that (except in the easy case when the given polynomials are linear).  
> **username_5**: For this direction, the trivial reduction works: $\exists\vec x\,\bigwedge_ig_i(\vec x)\le0$ is, literally, an existential statement in the theory of the reals.  
> **username_0**: I am surprised that the problem can be decided in finite time, since the passage I quoted from the book on convex optimization apparently shows that the run-time might be infinite. Or maybe I did not understand it correctly?  
> **username_6**: @ErelSegal-Halevi The quoted passage doesn't focus on polynomials, does it? The existential theory of the reals does, so this might be were the disconnect lies. Also it says "in practice". I don't think that a PSPACE algorithm is very practical, in general.  
> **username_2**: @EmilJeřábek, for that to work don't you need to assume something about the $g_i$'s (beyond the given assumption that they are convex)?  
> **username_5**: @NealYoung I don’t even need that they are convex. I only need that they are polynomials with rational (or: real algebraic, if represented in a suitable way) coefficients, as I wrote above.  
> **username_2**: @EmilJeřábek, okay, that makes sense.  (I was considering OP's question to be the general one, without the assumption that the functions are polynomials.)  

---

