5
$\begingroup$

Consider the following optimization problem:

Given $n\leq 10^3$ vectors $v_i\in\mathbb{R}^2$, all of which are small, i.e., $\|v_i\| \leq 1$, find a subset $S$ of them that minimizes $ \| w + \sum_{i\in S} v_i \|^2$, where $w$ is a fixed known vector.

I know that this can be reduced to an unconstrained 0-1 quadratic program (with unknowns $x_i\in\{0,1\}$, $x_i=1$ whenever $i\in S$), but that is a hard problem in general.

However, since the constraints are so specific, is there a way to get a reasonably simple efficient approximation algorithm for it? One that doesn't involve integer programming? It's not even clear to me how to efficiently implement a greedy algorithm for it.

Are there special cases of this problem that are easier? For example, would it help if all the vectors were unit length, $\|v_i\|=1$?

Improve this question
$\endgroup$
6
  • $\begingroup$ Related: cs.stackexchange.com/q/45718/755, cs.stackexchange.com/q/33788/755. And maybe: cs.stackexchange.com/q/56158/755 $\endgroup$
    – D.W. ♦
    May 24, 2017 at 23:33
  • $\begingroup$ Your problem is the Closest Vector Problem (CVP) in an integer lattice. In general, the CVP is fairly hard. However, you are working in only 2 dimensions, so the problem might become tractable. It's known that the 2D SVP can be solved in polynomial time (algorithm due to Gauss) if you start with only 2 vectors. I don't know if it is solvable if you start with $n>2$ vectors, or if it extends to the CVP. $\endgroup$
    – D.W. ♦
    May 24, 2017 at 23:50
  • $\begingroup$ @D.W. I don't follow you: in a lattice, the coefficients are just arbitrary integers. How do you reduce the 0-1 problem to a lattice problem? $\endgroup$
    – Kirill
    May 25, 2017 at 0:22
  • $\begingroup$ You are absolutely right; my mistake. I overlooked that we need the coefficients to be not just integers, but either zero or one. To try to save my idea: I think we still might be able to formulate as a lattice problem by replacing the vector $(x_i,y_i)$ with a vector of the form $(x_i,y_i,0,0,\dots,0,K,0,\dots,0)$ where $K$ is a sufficiently large constant, but then we're not in a lattice of dimension two. That might lead to an approximation algorithm using LLL lattice reduction, but I haven't thought about it carefully. $\endgroup$
    – D.W. ♦
    May 25, 2017 at 16:42
  • $\begingroup$ Why isn't the objective function to be minimized the following? $$ \left\| \left( \sum_{i\in S} v_i \right) - w \right\|_2^2$$ $\endgroup$
    – Rodrigo de Azevedo
    Jun 4, 2017 at 2:45

2 Answers 2

Reset to default
2
$\begingroup$

Let $\rm V$ be the $2 \times n$ matrix whose $i$-th column is vector $\rm v_i$. We have the Boolean optimization problem in $\mathrm z \in \{0,1\}^n$

$$\min_{\mathrm z \in \{0,1\}^n} \| \mathrm V \mathrm z + \mathrm w \|_2^2$$

Let

$$\rm z = \frac 12 (x + 1_n)$$

where $\mathrm x \in \{\pm 1\}^n$. Hence, we have an instance of the Boolean least-squares (BLS) problem

$$\min_{\mathrm x \in \{\pm 1\}^n} \| \mathrm A \mathrm x - \mathrm b \|_2^2$$

where

$$\rm A = \frac 12 V \qquad \qquad \qquad b = - \left( \frac 12 V 1_n + w \right)$$

Since $\{\pm 1\}$ is the solution set of the quadratic equation $x_i^2 = 1$, we have the following (non-convex) quadratically constrained quadratic program (QCQP) in $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} & x_i^2 = 1 \quad \forall i \in \{1,2,\dots,n\}\end{array}$$

Exhaustive evaluation of the objective function at all $2^n$ points is only feasible for small $n$.

SDP relaxation

Note that

$$\begin{array}{rl} \| \mathrm A \mathrm x - \mathrm b \|_2^2 &= (\mathrm A \mathrm x - \mathrm b)^{\top} (\mathrm A \mathrm x - \mathrm b)\\ &= \mbox{tr} \left( (\mathrm A \mathrm x - \mathrm b) (\mathrm A \mathrm x - \mathrm b)^{\top} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix}^{\top} \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix}^{\top} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \mathrm A^{\top}\\ -\mathrm b^{\top}\end{bmatrix} \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x^{\top} & 1\end{bmatrix} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \,\,\,\, \mathrm A^{\top} \mathrm A & -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A & \,\,\,\, \mathrm b^{\top}\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x \mathrm x^{\top} & \mathrm x\\ \mathrm x^{\top} & 1\end{bmatrix} \right)\end{array}$$

Since $\mathrm x \in \{\pm 1\}^n$, all $n$ entries on the main diagonal of $\mathrm x \mathrm x^{\top}$ are equal to $1$. Thus,

$$\begin{bmatrix} \mathrm x \mathrm x^{\top} & \mathrm x\\ \mathrm x^{\top} & 1\end{bmatrix}$$

is symmetric, positive semidefinite and has only ones on its main diagonal, i.e., it is a correlation matrix. Its rank is $1$. Let

$$\mathrm C := \begin{bmatrix} \,\,\,\, \mathrm A^{\top} \mathrm A & -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A & \,\,\,\, \mathrm b^{\top}\mathrm b\end{bmatrix}$$

Hence, the BLS problem can be written as the following rank-constrained optimization problem in $(n+1) \times (n+1)$ symmetric matrix $\rm Y$

$$\begin{array}{ll} \text{minimize} & \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} & y_{ii} = 1, \quad \forall i \in \{1,2,\dots,n+1\}\\ & \mathrm Y \succeq \mathrm O_{n+1}\\ & \mbox{rank} (\mathrm Y) = 1\end{array}$$

which is a hard problem due to the rank constraint. Relaxing the optimization problem above by discarding the rank constraint, we then obtain the following semidefinite program (SDP) in $\rm Y$

$$\boxed{\begin{array}{ll} \text{minimize} & \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} & y_{ii} = 1, \quad \forall i \in \{1,2,\dots,n+1\}\\ & \mathrm Y \succeq \mathrm O_{n+1}\end{array}}$$

which is convex and computationally tractable. This SDP relaxation provides a lower bound on the minimum of the original BLS problem. In the very, very fortunate case where the optimal solution of the SDP happens to be rank-$1$, we have solved the BLS problem.

References

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for the answer. Do you know if size-$n=10^3$ SDP problems should be considered feasible? It seems like it might be too big. $\endgroup$
    – Kirill
    May 26, 2017 at 20:41
  • $\begingroup$ @Kirill That should be feasible. Take a look at Do they use semidefinite programming in industry?. $\endgroup$
    – Rodrigo de Azevedo
    May 27, 2017 at 15:58
0
$\begingroup$

Consider the following approach to approximate this problem.

First, construct an efficient data structure using your vectors that can perform Nearest Neighbor related searching, such as a KD Tree. Then, formulate your problem as an optimization that's a function of $N$, the number of nearest neighbors you will compute. To get there, we can do the following with the cost function:

\begin{align} J &= \left\lVert w + \sum_{i \in S} v_i\right\Vert^2 \\ &= \frac{N^2}{N^2}\left\lVert w + \sum_{i \in S_N} v_i\right\Vert^2 \\ &= N^2\left\lVert \frac{w}{N} + \frac{1}{N}\sum_{i \in S_N} v_i\right\Vert^2 \end{align}

Note that $S_N$ is then an approximate solution for $S$. We can then approximate this problem by choosing $N$ such that we generate a set of vectors, which can be represented by the index set $S_N$, that are the $N$ nearest neighbors to $\frac{-w}{N}$. The logic is that selecting $N$ nearest neighbors from $\lbrace v_i \rbrace$ about $\frac{-w}{N}$ will produce a value for $\frac{1}{N}\sum_{i \in S_N} v_i$ close to $\frac{-w}{N}$ and in turn help minimize the norm.

The resulting optimization then ends up being:

\begin{align} N^{*} = \arg \min_{N} N^2 \left\lVert \frac{w}{N} + \frac{1}{N}\sum_{i \in S_N} v_i\right\Vert^2 \end{align}

How you go about tackling the above optimization is then up to you.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for the answer. Does this assume that the vectors are uniformly distributed? I don't want to assume that, so I'm not sure about the step where the average of $N$ nearest neighbours should be close to $\frac{-w}{N}$. $\endgroup$
    – Kirill
    May 26, 2017 at 20:46
  • $\begingroup$ @Kirill This approximation scheme does not depend on that, though I expect it would perform better if a subset of the vectors were at least uniformly distributed near $\frac{-w}{N}$. The level of accuracy this might achieve certainly is dependent on the distribution of the vectors. $\endgroup$
    – spektr
    May 26, 2017 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.