3
$\begingroup$

I've got a convex program of the form:

Choose $v \in \mathbb{R}^n$ to minimize $vAv^T$ subject to $O(n)$ linear contraints (including $v \ge 0$). $A$ is a square binary matrix.

What algorithm gives me the best asymptotic solution?

$\endgroup$
  • $\begingroup$ Your program is not convex unless $A$ is positive semidefinite, or at least $v^TAv \ge 0$ over all feasible $v$ $\endgroup$ – Sasho Nikolov Jan 24 '14 at 2:01
  • $\begingroup$ @SashoNikolov : Thanks, I should have mentioned that one of my linear inequalities is $v \ge 0$, so the condition $v^T A v \ge 0$ is satisfied. $\endgroup$ – GMB Jan 24 '14 at 2:45
  • $\begingroup$ @GMB So, the number of inequalities is not $O(1)$, but rather $n+O(1)$? $\endgroup$ – Austin Buchanan Jan 24 '14 at 3:44
  • $\begingroup$ @AustinBuchanan : Yes, sorry - I guess I have even more than that. My linear inequalities are $0 \le v_i \le 1$ and $\sum_i v_i = k$, so I have $2n + 1$ in total. My fault for expressing myself poorly in the OP. $\endgroup$ – GMB Jan 24 '14 at 4:12
  • 2
    $\begingroup$ how much precision do you want? in general, solutions can be irrational. if you are ok with a $1+\epsilon$ approximation and convergence rate $\frac{1}{\epsilon}$, the Frank-Wolfe algorithm can be very efficient and is very simple. check Ken Clarkson's analysis: kenclarkson.org/sga/p.pdf. if you want faster convergence, you'd have to go for more sophisticated techniques $\endgroup$ – Sasho Nikolov Jan 24 '14 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.