<p>I've got a convex program of the form:</p>

<p>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.</p>

<p>What algorithm gives me the best asymptotic solution?</p>

CC BY-SA 3.0
2014-01-24T02:01:11.503Z
Your program is not convex unless $A$ is positive semidefinite, or at least $v^TAv \ge 0$ over all feasible $v$
Sasho Nikolov
CC BY-SA 3.0
2014-01-24T02:45:05.323Z
@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
CC BY-SA 3.0
2014-01-24T03:44:42.697Z
@GMB So, the number of inequalities is not $O(1)$, but rather $n+O(1)$?
Austin Buchanan
CC BY-SA 3.0
2014-01-24T04:12:51.850Z
@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
CC BY-SA 3.0
2014-01-24T05:50:10.903Z
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: http://kenclarkson.org/sga/p.pdf. if you want faster convergence, you'd have to go for more sophisticated techniques
Sasho Nikolov
CC BY-SA 3.0
2014-01-24T08:53:17.070Z
Thanks, that is very helpful.  It would be neat if I could guarantee termination in any polynomial number of steps, but - looking at other convex optimization resources - I'm not so sure that's going to be feasible.  Quick question: when you say $(1+\epsilon)$ approximation, I assume you mean my answer $a \le (1 + \epsilon)opt$.  But if $opt = 0$, what does that mean for $a$?
GMB
<convex-optimization><asymptotics>
What is the state-of-the-art asymptotics for convex optimization?
GMB
# What is the state-of-the-art asymptotics for convex optimization?

(Asked by: username_0 on 2014-01-24)

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?

**Tags:** convex-optimization, asymptotics

> **Comments:**
> **username_1**: Your program is not convex unless $A$ is positive semidefinite, or at least $v^TAv \ge 0$ over all feasible $v$  
> **username_0**: @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.  
> **username_2**: @username_0 So, the number of inequalities is not $O(1)$, but rather $n+O(1)$?  
> **username_0**: @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.  
> **username_1**: 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: http://kenclarkson.org/sga/p.pdf. if you want faster convergence, you'd have to go for more sophisticated techniques  
> **username_0**: Thanks, that is very helpful.  It would be neat if I could guarantee termination in any polynomial number of steps, but - looking at other convex optimization resources - I'm not so sure that's going to be feasible.  Quick question: when you say $(1+\epsilon)$ approximation, I assume you mean my answer $a \le (1 + \epsilon)opt$.  But if $opt = 0$, what does that mean for $a$?  

---

## 0 answers

