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


Thanks!



Minimize a strictly convex quadratic function subject to linearly equality and nonnegativity constraints in finite time?
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>).


