<p>Based on posts from <a href="http://or-exchange.com" rel="nofollow noreferrer">or-exchange</a> and some internet reading, the following algorithm works. We adapt the cutting plane method to binary search for variable $y$. For my problem, the upper and lower bounds for all variables are known (but if these are not known, one can find a bound on $y$ by solving the LP by removing the first constraint). Let $l \leq y \leq u$.</p>

<p>Fix $y = (l+u)/2$. This converts the program to a linear program. If the resulting constraints are feasible, update $u(l) = (l+u)/2$. Keep performing the binary search until we reach the optimal solution with an additive $\epsilon_0$. The running time of the algorithm is $O(PTIME)\log\frac{u-l}{\epsilon_0}$. </p>

<p>While this algorithm can find the optimal solution within a small additive constant, I am still not sure about the hardness of the problem for solving exactly. Any comments regarding complexity are welcome!</p>

CC BY-SA 3.0
2017-09-18T16:39:25.167Z
As I said in the answer on math.stackechange, you can solve it analytically (empirically you will see that every second $x_i$ will be zero and all other elements equal to the same value, call it $\mu$, hence $z$ will be equal to $\mu$ at optimality, plug into first constraint and minimize left-hand side analytically). All you have to do is to prove that this solution actually is the optimal choice
Johan Löfberg
CC BY-SA 3.0
2017-09-18T16:55:13.753Z
but unfortunately, you will see that the problem does not have any minimizer, as the optimal cost tends to $c_1\lfloor n/2 \rfloor$ for $\mu \rightarrow \infty$
Johan Löfberg
CC BY-SA 3.0
2017-09-18T15:26:07.787Z
2017-09-18T16:42:43.153Z
2017-09-18T16:42:43.153Z
karmanaut
<p>Consider the following linear program,</p>

<p>$$\min y \\
xc_1 \leq c_2 + yz,\\
x = x_1 + \dots + x_n,\\
z \leq x_1 + x_2, \\
z \leq x_2 + x_3, \\
\vdots\\
z \leq x_{n-1} + x_n, \\
x,x_1, \dots, x_n,y,z \geq 0
$$ 
where $c_1, c_2$ are constants. This is an example of quadratically constrained linear program where I have 1 quadratic constraint. I wish to find out if this problem is NP-Hard or not. The quadratic constraint can be expressed in the form $\vec{y}M\vec{y}^T$ where $M$ for my problem is not positive semidefinite (and thus, non-convex) which is perhaps evidence of hardness</p>

<p>Listing specific questions below:</p>

<ol>
<li>Can this problem be transformed into a linear program by taking logarithms?</li>
<li>Is there any literature reference or reduction showing that linear programs with non-convex quadratic constraints is an NP-Hard problem? </li>
</ol>

<p>Edit : Cross posted question at <a href="https://math.stackexchange.com/questions/2433177/solving-linear-program-with-1-quadratic-constraint-complexity/2433348#2433348">math.stackexchange</a></p>

CC BY-SA 3.0
2017-09-21T21:48:26.907Z
Cross-posted: https://math.stackexchange.com/q/2433177/14578, https://cstheory.stackexchange.com/q/39108/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.   Our site policy prohibits simultaneous cross-posting.
D.W.
<np-hardness><optimization><linear-programming>
Solving linear program with 1 quadratic constraint complexity
karmanaut
# Solving linear program with 1 quadratic constraint complexity

(Asked by: username_0 on 2017-09-17)

Consider the following linear program,

$$\min y \\
xc\_1 \leq c\_2 + yz,\\
x = x\_1 + \dots + x\_n,\\
z \leq x\_1 + x\_2, \\
z \leq x\_2 + x\_3, \\
\vdots\\
z \leq x\_{n-1} + x\_n, \\
x,x\_1, \dots, x\_n,y,z \geq 0
$$
where $c\_1, c\_2$ are constants. This is an example of quadratically constrained linear program where I have 1 quadratic constraint. I wish to find out if this problem is NP-Hard or not. The quadratic constraint can be expressed in the form $\vec{y}M\vec{y}^T$ where $M$ for my problem is not positive semidefinite (and thus, non-convex) which is perhaps evidence of hardness

Listing specific questions below:

1. Can this problem be transformed into a linear program by taking logarithms?
2. Is there any literature reference or reduction showing that linear programs with non-convex quadratic constraints is an NP-Hard problem?

Edit : Cross posted question at [math.stackexchange](https://math.stackexchange.com/questions/2433177/solving-linear-program-with-1-quadratic-constraint-complexity/2433348#2433348)

**Tags:** np-hardness, optimization, linear-programming
> **Comments:**
> **username_1**: Cross-posted: https://math.stackexchange.com/q/2433177/14578, https://cstheory.stackexchange.com/q/39108/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.   Our site policy prohibits simultaneous cross-posting.  

---

## 1 answers

### Answer by username_0 on 2017-09-18. Score: 1

Based on posts from [or-exchange](http://or-exchange.com) and some internet reading, the following algorithm works. We adapt the cutting plane method to binary search for variable $y$. For my problem, the upper and lower bounds for all variables are known (but if these are not known, one can find a bound on $y$ by solving the LP by removing the first constraint). Let $l \leq y \leq u$.

Fix $y = (l+u)/2$. This converts the program to a linear program. If the resulting constraints are feasible, update $u(l) = (l+u)/2$. Keep performing the binary search until we reach the optimal solution with an additive $\epsilon\_0$. The running time of the algorithm is $O(PTIME)\log\frac{u-l}{\epsilon\_0}$.

While this algorithm can find the optimal solution within a small additive constant, I am still not sure about the hardness of the problem for solving exactly. Any comments regarding complexity are welcome!

> **Comments:**
> **username_2**: As I said in the answer on math.stackechange, you can solve it analytically (empirically you will see that every second $x_i$ will be zero and all other elements equal to the same value, call it $\mu$, hence $z$ will be equal to $\mu$ at optimality, plug into first constraint and minimize left-hand side analytically). All you have to do is to prove that this solution actually is the optimal choice  
> **username_2**: but unfortunately, you will see that the problem does not have any minimizer, as the optimal cost tends to $c_1\lfloor n/2 \rfloor$ for $\mu \rightarrow \infty$  

---

