<p>An optimal solution lies on some face.  So, we can go through all the faces of the cube, and find all stationary points on each of the faces.</p>

<p>Here is a more concrete procedure.  A face of the cube can be characterized by two disjoint index sets $I_0$ and $I_1$.  For $i \in I_0$, we fix $x_i = 0$, and for $i \in I_1$ we fix $x_i = 1$.  Let $\tilde{x}$ consist of the remaining unfixed entries of $x$.  This fixing turns the objective function into the following form:</p>

<p>$$
\tilde{x}^{\top} \tilde{A} \tilde{x} + \tilde{c}^{\top} \tilde{x} + d,
$$</p>

<p>with appropriate $\tilde{A}$ and $\tilde{c}$, and some constant $d$, and we want to find the stationary points of this function under the condition that $0 &lt; \tilde{x} &lt; 1$.</p>

<p>To this end, we take the differentiation of the objective function to obtain</p>

<p>$$
\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.
$$</p>

<p>Solving this system of linear equations gives you the stationary points, the candidates for optimal solutions.  We go through all of them, check the condition, and choose one with the minimum objective value.</p>

<p>The overall time complexity is something like $O(3^n \text{poly}(n))$ since the number of faces of the $n$-cube is $3^n$ and a system of linear equations can be solved in polynomial time.  The space complexity is polynomial in $n$.</p>

CC BY-SA 3.0
2015-04-15T20:43:52.287Z
Why does an optimal solution lie on some face with a non-convex $f$?
cody
CC BY-SA 3.0
2015-04-21T04:45:40.697Z
@cody: That's because every polytope is the disjoint union of its faces.
Yoshio Okamoto
CC BY-SA 3.0
2015-04-21T12:57:20.347Z
What if $f$ is cubic, or quartic? Does this property still hold?
cody
CC BY-SA 3.0
2015-04-21T14:25:26.010Z
@cody: The property still holds, but we need to solve an algebraic equation of degree more than one. I'm afraid this is not trivial for multivariate cases.
Yoshio Okamoto
CC BY-SA 3.0
2012-12-13T09:05:55.103Z
2012-12-13T09:05:55.103Z
Yoshio Okamoto
<p>This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form</p>

<ul>
<li>minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}$ subject to $\mathbf{x} \in [0,1]^n$.</li>
</ul>

<p>If $A$ was positive semi-definite, then everything would be nice and convex and easy, and we could solve the problem in polynomial time.</p>

<p>On the other hand, if we had the integrality constraint $\mathbf{x} \in \{0,1\}^n$, we could easily solve the problem in time $O(2^n \cdot \mathrm{poly}(n))$ by brute force. For the purposes of this question, this is reasonably fast.</p>

<p>But what about the non-convex continuous case? What is the fastest known algorithm for general box-QPs?</p>

<p>For example, can we solve these in moderately exponential time, e.g., $O(3^n \cdot \mathrm{poly}(n))$, or is the worst-case complexity of the best known algorithms something much worse?</p>

<hr>

<p><strong>Background:</strong> I have some fairly small box-QPs that I would actually like to solve, and I was a bit surprised to see how poorly some commercial software packages perform, even for very small values of $n$. I started to wonder if there is a TCS explanation for this observation.</p>

CC BY-SA 3.0
2012-12-05T22:08:55.323Z
Can you solve exactly even for PSD $A$? The solution can be irrational, no? If you are willing to lose additive $\epsilon$ perhaps one can get an exponential time algorithm by doing brute-force search over a sufficiently fine grid. Just a vague suggestion.
Chandra Chekuri
CC BY-SA 3.0
2012-12-05T22:24:34.683Z
Downside is that the "base" of the exponent would be something like $1/\epsilon$, but maybe clever grid engineering can help for "small" $n$
Suresh Venkat
CC BY-SA 3.0
2012-12-05T23:18:03.530Z
@ChandraChekuri: Approximations are perfectly fine if you can achieve, e.g., $\epsilon = 10^{-9}$. However, brute-forcing over such a fine grid is not feasible.
Jukka Suomela
CC BY-SA 3.0
2012-12-06T18:08:45.843Z
There is work on approximating indefinite quadratic programs with linear inequality constraints by Vavasis which proves that there exists a PTAS: http://link.springer.com/article/10.1007%2FBF01581085?LI=true#page-1
Dimitris
CC BY-SA 3.0
2012-12-08T19:02:37.507Z
If $O(3^n)$ is allowed, you may optimize the function on each of the faces of the cube just by writing down the first-order optimality criteria.
Yoshio Okamoto
CC BY-SA 3.0
2012-12-12T17:28:05.107Z
@YoshioOkamoto: I think this is the best suggestion so far; could you perhaps post it as an answer?
Jukka Suomela
CC BY-SA 3.0
2012-12-13T09:11:07.687Z
@JukkaSuomela: I've posted as an answer, but there should be a more satisfactory answer in the literature.
Yoshio Okamoto
<ds.algorithms><optimization><exp-time-algorithms>
Exact algorithms for non-convex quadratic programming
Jukka Suomela
# Exact algorithms for non-convex quadratic programming

(Asked by: username_0 on 2012-12-05)

This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form

* minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}$ subject to $\mathbf{x} \in [0,1]^n$.

If $A$ was positive semi-definite, then everything would be nice and convex and easy, and we could solve the problem in polynomial time.

On the other hand, if we had the integrality constraint $\mathbf{x} \in \{0,1\}^n$, we could easily solve the problem in time $O(2^n \cdot \mathrm{poly}(n))$ by brute force. For the purposes of this question, this is reasonably fast.

But what about the non-convex continuous case? What is the fastest known algorithm for general box-QPs?

For example, can we solve these in moderately exponential time, e.g., $O(3^n \cdot \mathrm{poly}(n))$, or is the worst-case complexity of the best known algorithms something much worse?

---

**Background:** I have some fairly small box-QPs that I would actually like to solve, and I was a bit surprised to see how poorly some commercial software packages perform, even for very small values of $n$. I started to wonder if there is a TCS explanation for this observation.

**Tags:** ds.algorithms, optimization, exp-time-algorithms

> **Comments:**
> **username_1**: Can you solve exactly even for PSD $A$? The solution can be irrational, no? If you are willing to lose additive $\epsilon$ perhaps one can get an exponential time algorithm by doing brute-force search over a sufficiently fine grid. Just a vague suggestion.  
> **username_2**: Downside is that the "base" of the exponent would be something like $1/\epsilon$, but maybe clever grid engineering can help for "small" $n$  
> **username_0**: @ChandraChekuri: Approximations are perfectly fine if you can achieve, e.g., $\epsilon = 10^{-9}$. However, brute-forcing over such a fine grid is not feasible.  
> **username_3**: There is work on approximating indefinite quadratic programs with linear inequality constraints by Vavasis which proves that there exists a PTAS: http://link.springer.com/article/10.1007%2FBF01581085?LI=true#page-1  
> **username_4**: If $O(3^n)$ is allowed, you may optimize the function on each of the faces of the cube just by writing down the first-order optimality criteria.  
> **username_0**: @YoshioOkamoto: I think this is the best suggestion so far; could you perhaps post it as an answer?  
> **username_4**: @JukkaSuomela: I've posted as an answer, but there should be a more satisfactory answer in the literature.  

---

## 1 answers

### Answer by username_4 on 2012-12-13. Score: 12 | Accepted answer

An optimal solution lies on some face. So, we can go through all the faces of the cube, and find all stationary points on each of the faces.

Here is a more concrete procedure. A face of the cube can be characterized by two disjoint index sets $I\_0$ and $I\_1$. For $i \in I\_0$, we fix $x\_i = 0$, and for $i \in I\_1$ we fix $x\_i = 1$. Let $\tilde{x}$ consist of the remaining unfixed entries of $x$. This fixing turns the objective function into the following form:

$$
\tilde{x}^{\top} \tilde{A} \tilde{x} + \tilde{c}^{\top} \tilde{x} + d,
$$

with appropriate $\tilde{A}$ and $\tilde{c}$, and some constant $d$, and we want to find the stationary points of this function under the condition that $0 < \tilde{x} < 1$.

To this end, we take the differentiation of the objective function to obtain

$$
\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.
$$

Solving this system of linear equations gives you the stationary points, the candidates for optimal solutions. We go through all of them, check the condition, and choose one with the minimum objective value.

The overall time complexity is something like $O(3^n \text{poly}(n))$ since the number of faces of the $n$-cube is $3^n$ and a system of linear equations can be solved in polynomial time. The space complexity is polynomial in $n$.

> **Comments:**
> **username_5**: Why does an optimal solution lie on some face with a non-convex $f$?  
> **username_4**: @username_5: That's because every polytope is the disjoint union of its faces.  
> **username_5**: What if $f$ is cubic, or quartic? Does this property still hold?  
> **username_4**: @username_5: The property still holds, but we need to solve an algebraic equation of degree more than one. I'm afraid this is not trivial for multivariate cases.  

---

