<p>Given the following program, where <span class="math-container">$f, g$</span> are convex functions:
<span class="math-container">$$
\text{minimize}~~ f(x)
\\
\text{subject to}~~ g(x)\leq 0
$$</span>
the problem can be solved by convex programming algorithms, but it would be more efficient if we could solve it using linear programming with integer coefficients.
However, in some cases this is impossible. For example, the program
<span class="math-container">$$
\text{minimize}~~ -x
\\
\text{subject to}~~ x^2 -2\leq 0
$$</span>
cannot be solved exactly by linear programs with integer coefficients, since its solution <span class="math-container">$\sqrt{2}$</span> is irrational.</p>
<p>Let us say that such a problem is &quot;CP hard&quot; if it can be solved by convex programming, but cannot be solved exactly by a polynomial-time algorithm using linear programming with integer coefficients.</p>
<p>I am looking for some additional techniques to prove &quot;CP hardness&quot;. What are some references proving that a given class of convex programs cannot be solved by linear programming?</p>

CC BY-SA 4.0
2022-12-18T21:09:40.430Z
Can you clarify more specifically what you want CP-hard to mean?  E.g., there are programs that are not convex in their given representation, but with an easy change of variables (e.g. replacing a non-negative variable $x$ by $e^{y}$ where $y$ is an unconstrained variable) they become convex, or even linear, programs.  Secondly, as long as the problem of solving your program is in P, it is log-space reducible to solving an LP, as LP is P-complete under log-space reductions.  Thirdly, convex programs (e.g. SDPs) can often be solved as infinite-constraint LPs that admit a separation oracle.
Neal Young
CC BY-SA 4.0
2022-12-19T21:39:30.537Z
@NealYoung can you explain how convex programs can be solved by infinite constraint lp admitting a separation oracle?
Turbo
CC BY-SA 4.0
2022-12-19T22:44:59.280Z
@Turbo, the most well-known (but somewhat complicated) case of this is semi-definite programming.  A matrix $M$ is positive semi-definite if and only if $v^T M v \ge 0$ for all vectors $v$.  This can be interpreted as putting linear constraints on $M$, one for each $v$: $\sum_{ij} v_i v_j M_{ij} \ge 0$, which gives you an LP with infinitely many constraints, but it has a separation oracle.  A simpler example: take, say, $\max\{x+y : x^2 + y^2 \le 1\}$, replace $x^2 + y^2 \le 1$ by "supporting hyperplane" constraints $(x, y) \cdot (a, b) \le 1$ for every $(a, b)$ such that $a^2 + b^2 \le 1$...
Neal Young
CC BY-SA 4.0
2022-12-19T22:54:17.110Z
@NealYoung so uncountable many?
Turbo
CC BY-SA 4.0
2022-12-20T01:16:12.507Z
@Turbo, Yes.  Yet there is a separation oracle: for a given $(x, y)$, if any constraint is violated, the constraint with $(a, b) = (x, y)$ will be.  Generally, for a convex body, for any point not in the body, some supporting hyperplane  separates the body from the point.  (e.g. take the supporting hyperplane perpendicular to the vector from the point to the closest point in the body).
Neal Young
CC BY-SA 4.0
2022-12-20T01:52:18.490Z
@NealYoung I added a clarification: "CP hard" means that it cannot  be solved by a polynomial-time algorithm using linear programming with integer coefficients. For example: "maximize $x$ subject to $x^2\leq 2$" is  a convex program, but it cannot be solved exactly by linear programming with integer coefficients, since its solution is irrational.
Erel Segal-Halevi
CC BY-SA 4.0
2022-12-20T14:20:35.023Z
But what does "solved by" mean, exactly?  Note that any problem that has a poly-time algorithm has a log-space reduction to max flow (and thus linear programing with integer coefficients), just because max flow is complete for P under log-space reductions [1].  So in that sense all problems in P can be solved by linear programming with integer coefficients.  Or, your example via a change of variables is equivalent to $\min \{-y  : y\le 2\}$, so in that sense is solvable by LP with int. coefficients.. [1] https://doi.org/10.1016/0304-3975(82)90092-5
Neal Young
<cc.complexity-theory><optimization><linear-programming><convex-optimization>
How to prove that a given class of convex programs cannot be solved by linear programming?
Erel Segal-Halevi
# How to prove that a given class of convex programs cannot be solved by linear programming?

(Asked by: username_0 on 2022-12-18)

Given the following program, where $f, g$ are convex functions:
$$
\text{minimize}~~ f(x)
\\
\text{subject to}~~ g(x)\leq 0
$$
the problem can be solved by convex programming algorithms, but it would be more efficient if we could solve it using linear programming with integer coefficients.
However, in some cases this is impossible. For example, the program
$$
\text{minimize}~~ -x
\\
\text{subject to}~~ x^2 -2\leq 0
$$
cannot be solved exactly by linear programs with integer coefficients, since its solution $\sqrt{2}$ is irrational.

Let us say that such a problem is "CP hard" if it can be solved by convex programming, but cannot be solved exactly by a polynomial-time algorithm using linear programming with integer coefficients.

I am looking for some additional techniques to prove "CP hardness". What are some references proving that a given class of convex programs cannot be solved by linear programming?

**Tags:** cc.complexity-theory, optimization, linear-programming, convex-optimization

> **Comments:**
> **username_1**: Can you clarify more specifically what you want CP-hard to mean?  E.g., there are programs that are not convex in their given representation, but with an easy change of variables (e.g. replacing a non-negative variable $x$ by $e^{y}$ where $y$ is an unconstrained variable) they become convex, or even linear, programs.  Secondly, as long as the problem of solving your program is in P, it is log-space reducible to solving an LP, as LP is P-complete under log-space reductions.  Thirdly, convex programs (e.g. SDPs) can often be solved as infinite-constraint LPs that admit a separation oracle.  
> **username_2**: @NealYoung can you explain how convex programs can be solved by infinite constraint lp admitting a separation oracle?  
> **username_1**: @username_2, the most well-known (but somewhat complicated) case of this is semi-definite programming.  A matrix $M$ is positive semi-definite if and only if $v^T M v \ge 0$ for all vectors $v$.  This can be interpreted as putting linear constraints on $M$, one for each $v$: $\sum_{ij} v_i v_j M_{ij} \ge 0$, which gives you an LP with infinitely many constraints, but it has a separation oracle.  A simpler example: take, say, $\max\{x+y : x^2 + y^2 \le 1\}$, replace $x^2 + y^2 \le 1$ by "supporting hyperplane" constraints $(x, y) \cdot (a, b) \le 1$ for every $(a, b)$ such that $a^2 + b^2 \le 1$...  
> **username_2**: @NealYoung so uncountable many?  
> **username_1**: @username_2, Yes.  Yet there is a separation oracle: for a given $(x, y)$, if any constraint is violated, the constraint with $(a, b) = (x, y)$ will be.  Generally, for a convex body, for any point not in the body, some supporting hyperplane  separates the body from the point.  (e.g. take the supporting hyperplane perpendicular to the vector from the point to the closest point in the body).  
> **username_0**: @NealYoung I added a clarification: "CP hard" means that it cannot  be solved by a polynomial-time algorithm using linear programming with integer coefficients. For example: "maximize $x$ subject to $x^2\leq 2$" is  a convex program, but it cannot be solved exactly by linear programming with integer coefficients, since its solution is irrational.  
> **username_1**: But what does "solved by" mean, exactly?  Note that any problem that has a poly-time algorithm has a log-space reduction to max flow (and thus linear programing with integer coefficients), just because max flow is complete for P under log-space reductions [1].  So in that sense all problems in P can be solved by linear programming with integer coefficients.  Or, your example via a change of variables is equivalent to $\min \{-y  : y\le 2\}$, so in that sense is solvable by LP with int. coefficients.. [1] https://doi.org/10.1016/0304-3975(82)90092-5  

---

## 0 answers

