# What is the state-of-the-art asymptotics for convex optimization?

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?

• Your program is not convex unless $A$ is positive semidefinite, or at least $v^TAv \ge 0$ over all feasible $v$ – Sasho Nikolov Jan 24 '14 at 2:01
• @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. – GMB Jan 24 '14 at 2:45
• @GMB So, the number of inequalities is not $O(1)$, but rather $n+O(1)$? – Austin Buchanan Jan 24 '14 at 3:44
• @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. – GMB Jan 24 '14 at 4:12
• 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 – Sasho Nikolov Jan 24 '14 at 5:50