Minimize a strictly convex quadratic function subject to linearly equality and nonnegativity constraints in finite time?

Question

I am wondering if we can minimize a strictly convex quadratic function in finite time, subject to linearly equality and nonnegativity constraints.

Thanks!

Answer 1

Although complexity analysis can give you some insight on the difficulty of your problem, it is unlikely that will settle your question in full-generality.

For example: in the oracle model, a strongly convex function can be minimized in time $O(\ln(1/\varepsilon))$. However, since your domain is a general polyhedron, it depends on how easy is to solve projections (or computing Prox-mappings) over your polyhedron to obtain good running time.

My advice is: have a look at Nesterov's book (as suggested above) to see if his optimal method is applicable to your problem (this gives you $O(1/T^2)$ convergence rate). If your polyhedral domain is complicated, you might want to try a Frank-Wolfe method, that does not require projection (or proximal) computations, and converges at the rate $O(1/T)$. Finally, since your objective is strongly convex, these methods can be applied with 'restarts' so you can obtain the much better convergence rate $O(e^{-T})$ (e.g. http://arxiv.org/abs/1301.4666).

Finally, I think it is very unlikely that you find good lower bounds for your problem for general polyhedral sets; moreover, this analysis depends crucially on how you access your data. For example, if your oracle is only able to solve LPs, then there are simple lower bounding techniques (http://arxiv.org/abs/1309.5550). If your oracle only is constrained to be 'local', the complexity can have a different behavior (http://arxiv.org/abs/1307.5001).