Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The problem is the following

Given $v_1, \, v_2, \, \ldots, \, v_n \in \mathbb R^m$; find $\epsilon_1, \, \epsilon_2, \, \ldots, \, \epsilon_n \in \{0,1\}$ such that $$\left\vert \sum_{i=1}^n (-1)^{\epsilon_i} v_i \right\vert = \max$$ where $\vert \cdot\vert $ denotes the Euclidean norm.

I.e. we want to maximize the length of a sum of vectors, under the restriction that for every vector we must use either the vector itself or $(-1)$ times this vector.

This came from some application and I was asked whether I knew how to obtain a solution some time ago. I didn't see an efficient algorithm and since the number of vectors typically was sufficiently small, it could be solved by simply going through all possibilities.

I thought about it again, today. And the problem really looks like there might be a nice efficient algorithm to solve it - at least better than $\Theta(2^n)$.

Still not being able to find one, I wanted to ask whether someone here could figure out a neat solution!


Something that doesn't work:

  • Order the vectors by length: $|v_1|\ge |v_2|\ge \dots \ge |v_n|$
  • Having found a maximal vector-combination $v = \sum \pm v_i$ from $v_1, \, v_2, \, \ldots, \, v_k$, choose the sign of $v_{k+1}$ so that it maximizes the length of $v \pm v_{k+1}$.

A counterexample is given by $\begin{pmatrix} 3\\ 2\end{pmatrix},\, \begin{pmatrix} -2\\ 3\end{pmatrix},\, \begin{pmatrix} 2\\ 3\end{pmatrix}$. Combining the first two vectors we get $$\begin{pmatrix} 1\\ 5\end{pmatrix} \quad \text{or}\quad \begin{pmatrix} 5\\ -1\end{pmatrix}$$ both of which have the same length. However, if we choose the first combination we can get $\begin{pmatrix} 3\\ 8\end{pmatrix}$ whereas for the second combination $\begin{pmatrix} 7\\ 2\end{pmatrix}$ is the best we can do.

Feel free to share your thoughts! Thanks. =)

share|improve this question
2  
In the solution, all the vectors will point into the same half-space, so the problem reduces to finding that half-space. In two dimensions you can just sort them according to their angles in $O(n\log n)$ time, then walk through the array with two pointers pointing to opposite angles to get the length of all candidates in linear time. I'm not sure whether there's a similarly efficient approach in higher dimensions. –  joriki Jan 11 '12 at 20:35
    
That's basically my suggestion, except you formulated it in a way that would take $O(n^2)$ time. –  joriki Jan 11 '12 at 20:36
    
Could principal component analysis be useful? –  Peter Taylor Jan 11 '12 at 21:04
    
@joriki: Thanks for your comment! I don't think I understand the idea of considering angles. For my example: We get angles $56.31°, 123.69°, 33.69°$ when measured from the x-axis. So according to your idea, I would just add all vectors together to obtain $(3,8)^T$, which is right. But if we turn all three vectors by $90°$ (measure from y-axis), we have angles $146.31°, 213.69°, 123.69°$. So that - if I understand it right - we should take the sum $$\begin{pmatrix} 3\\ 2\end{pmatrix}-\begin{pmatrix} -2\\ 3\end{pmatrix} + \begin{pmatrix} 2\\ 3\end{pmatrix} = \begin{pmatrix} 7\\ 2\end{pmatrix}$$ –  Sam Jan 12 '12 at 19:39
2  
@Sam: That's not what I meant. Sort the angles, set $\phi=0$ and initialize one pointer to point to the beginning of the array, the other to the boundary between angles $\lt\pi$ and $\gt\pi$. These pointers define two ranges; add up all the vectors, with $+$ in one range and $-$ in the other. Now set $\phi$ to $\min(\phi_1,\phi_2-\pi)$, where $\phi_i$ is the angle behind pointer $i$, increment the corresponding pointer and flip the sign of the vector the pointer moved over. Continue like this until the pointers have swapped places. The maximal length you encounter is globally optimal. –  joriki Jan 12 '12 at 20:00

3 Answers 3

up vote 2 down vote accepted

A cool terminology (which is not directly related to the answer): Letting A be an m×n matrix whose columns are given by vectors v1, …, vn, your problem is concisely stated as computing the “subordinate (∞,2)-norm” of matrix A.

This problem is NP-hard, which implies that there is no polynomial-time algorithm unless P=NP. I do not know what the best reference for it is, but one place where it is proved to be NP-hard is [GK89]. Check the problem called ZonMax in [GK89], which is a slight variation of your problem which is easily seen to be equivalent to yours. I think that part of the reduction in [GK89] can be simplified by using the NP-completeness of the subset sum as is done in [MK87].

[GK89] Peter Gritzmann and Victor Klee. On the 0-1 maximization of positive definite quadratic forms. IMA Preprint Series #522, April 1989. http://www.ima.umn.edu/preprints/Jan89Dec89/522.pdf

[MK87] Katta G. Murty and Santosh N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):117–129, June 1987. DOI: 10.1007/BF02592948. (I checked only the technical report version.)

share|improve this answer
    
Thank you for your answer! –  Sam Jan 20 '12 at 17:47

This can be formulated as a quadratically constrained quadratic program.

Maximising $$\left\vert \sum_{i=1}^n (-1)^{\epsilon_i} v_i \right\vert$$ is equivalent to maximising $$\begin{eqnarray} \left\vert \sum_{i=1}^n (-1)^{\epsilon_i} v_i \right\vert^2 & = & \left( \sum_{i=1}^n (-1)^{\epsilon_i} v_i \right).\left( \sum_{j=1}^n (-1)^{\epsilon_j} v_j \right) \\ & = & \sum_{i=1}^n \sum_{j=1}^n (1 - 2\epsilon_i) (1 - 2\epsilon_j) v_i . v_j \end{eqnarray}$$ (where the $-1^\epsilon$ to $(1-2\epsilon)$ transformation is valid because of the constaint $\epsilon\in{0,1}$) and since the constant term is irrelevant, this is in turn equivalent to maximising $$\sum_{i=1}^n \sum_{j=1}^n (4 \epsilon_i \epsilon_j - 2 \epsilon_i - 2 \epsilon_j) v_i . v_j$$

This objective function is convex, as Sam points out in a comment. As mentioned in the Wikipedia article, $\epsilon\in\{0,1\}$ can be converted to quadratic constraints as $\epsilon(\epsilon - 1) \le 0$ and $\epsilon(\epsilon - 1) \ge 0$, and these constraints are also convex, although not semi-definite.

I'm not sure which algorithms for QCQP are applicable and efficient in this convex-but-not-semi-definite case, but it does look hopeful that this might not be NP-hard, and the reduction to a known problem gives a line of investigation.

share|improve this answer
    
Thank you very much Peter! =) Note that a matrix $P$ with coefficients $P_{ij} = v_i^Tv_j$ must necessarily be positive semidefinite. Indeed, if we are given a vector $x = (x_1, \ldots, x_n)^T$, then $$x^TPx = \sum_{i,j} x_i v_i^Tv_j x_j = \left(\sum_i x_i v_i\right)^T\left(\sum_i x_i v_i\right) \ge 0$$ So the objective function will be convex, right? –  Sam Jan 14 '12 at 0:29
    
@Sam, I seem to have been too hasty. You're right, it is convex. Will update. –  Peter Taylor Jan 14 '12 at 9:05
    
Maximization of a convex quadratic function over [0,1]^n (or {0,1}^n, which is equivalent) is NP-hard, e.g. by a reduction from the subset sum problem. –  Tsuyoshi Ito Jan 17 '12 at 7:08
    
@TsuyoshiIto, I can see how to reduce subset sum to minimisation of a positive semi-definite quadratic function or maximisation of a negative semi-definite quadratic function. But, on the offchance, do you have any references to hand for which special cases of QCQP are known to be in P and which are known to be NP-hard? –  Peter Taylor Jan 17 '12 at 11:54
    
@PeterTaylor: Minimization of a convex quadratic function over a polytope is solvable in polynomial time by using ellipsoid or interior-point method. Therefore, probably the reduction you are thinking of does not work. –  Tsuyoshi Ito Jan 17 '12 at 14:54

I don't think there is a deterministic polynomial time algorithm for this. I remember seeing problems like this in my randomized algorithms course, and I would recommend trying the conditional expectation derandomization technique described here (and other places).

share|improve this answer
    
In those lecture notes, $\Phi$ on page $1$ should be $\emptyset$ and "total number of vertices" on page $3$ at the top should be "total number of edges". –  joriki Jan 11 '12 at 20:51
    
Thank you for your answer! I will make sure to have a look at it. –  Sam Jan 12 '12 at 19:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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