2
$\begingroup$

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

Thanks!

$\endgroup$
6
  • 1
    $\begingroup$ As a practical matter, such problems are relatively easy to solve numerically to within reasonable tolerances. However, it sounds as though you're asking a more theoretical question about exactly solving the problem within some model of computation. What computational model are you interested in? $\endgroup$ Apr 12, 2014 at 20:00
  • $\begingroup$ Thanks Brian. Yes, I am asking this from a theoretical perspective. I am wondering if it is possible to use convex optimization techniques to solve this one in polynomial time or finite time (if polynomial is not achievable). $\endgroup$
    – XiMS
    Apr 12, 2014 at 21:19
  • 1
    $\begingroup$ @XiMS: As Brian asked: "what model of computation are you using?" Complexity analysis depends on the model of computation----the term "polynomial time" too, so it would be good to know what model. But in the commonly used oracle model, the runtimes are polynomial in the problem size for $\epsilon$-accuracy solution (depending on stuff like $1/\epsilon$, $\log(1/\epsilon)$, etc.) $\endgroup$
    – Suvrit
    Apr 13, 2014 at 11:32
  • $\begingroup$ @Suvrit, thank you so much! I see. I think I am talking about the oracle model. I was reading the book "Convex Optimization" by Professor Stephen Boyd yesterday. I think many ϵ-accuracy solutions mentioned (like Newton's step in that book) are actually based on the oracle model. $\endgroup$
    – XiMS
    Apr 13, 2014 at 17:09
  • 1
    $\begingroup$ @Xims: you'll benefit greatly by reading the book: Introductory lectures on convex optimization by Yurii Nesterov --- that books a very nice introduction to oracle based complexity (upper and lower bounds); you can also have a look at Lecture 23 of my course: cs.cmu.edu/~suvrit/teach/aopt.html $\endgroup$
    – Suvrit
    Apr 13, 2014 at 19:40

1 Answer 1

4
$\begingroup$

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).

$\endgroup$
4
  • 1
    $\begingroup$ Cristobal: as far as I can tell, the problem posed by the OP can be solved with a method that converges at a linear rate (by passing to an ADMM procedure to "easily" handle the linear constraints). $\endgroup$
    – Suvrit
    Apr 14, 2014 at 9:58
  • $\begingroup$ Suvrit: that is indeed true, but I wanted to point out that computing Prox-mappings might not even be necessary by the striking result of Garber and Hazan. Also I thought it was necessary to explain that complexity theory would probably not give the ultimate answer (e.g., one needs to incorporate the cost of your oracle as well). $\endgroup$ Apr 14, 2014 at 14:28
  • $\begingroup$ Indeed Cristóbal: I just commented to point out one more small addition to your already nice answer :-) $\endgroup$
    – Suvrit
    Apr 14, 2014 at 22:36
  • $\begingroup$ Thanks, guys. This is quite helpful! I am reading the docs you pointed out. $\endgroup$
    – XiMS
    Apr 15, 2014 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.