6
$\begingroup$

Why so much effort spent for solving convex programs? For me (I am a newbie) all convex methods (complex maybe) look like a variations of derivative based methods which are not fundamentally better than dull gradient descent. In the same time there are plenty of real life non-convex tasks which actually don't have (in my opinion) so well developed mathematical theory (genetic algorithms, branch and bound, annealing etc.). Why? Are there methods to cast non-convex tasks to convex? Or it is manifestation of weakness of modern mathematics on non-convex tasks?

Please clarify...

$\endgroup$
  • 3
    $\begingroup$ I think you are oversimplifying things: 1. Quasi-Newton methods offer a genuine advancement to "dull gradient descent" in terms of speed. 2. MCMC methods (what I suspect you mean by "annealing") and "branch and bound" methods have well-founded mathematical frameworks behind them and they are areas of very active research (check for example Manifold MCMCs and Mixed-integer programming respectively). 3. Do not confuse "hard to solve" with a "manifestation of weakness". Some problems take much more effort to solve than others. $\endgroup$ – usεr11852 Sep 9 '15 at 11:01
  • 3
    $\begingroup$ Just to clear up a minor misconception: convexity is only distantly related to differentiability. The concept of convexity also comprises regions and objective functions that are not differentiable. $\endgroup$ – whuber Sep 9 '15 at 13:05
  • 1
    $\begingroup$ LASSO: convex yet not differentiable. $\endgroup$ – Firebug Sep 23 '16 at 13:27
4
$\begingroup$

To get started I recommend reading the introduction to this book by Stephen Boyd. He is doing a lot of cutting edge research in convex optimization, and is one of the biggest names in the field.

Often the issue of "making" your problem convex is reparameterization of the problem formulation. But sometimes the function your are trying to optimize is not convex and thus you can optimize a convex approximation which often agrees on the same global optimum. Still there are functions which are highly non-convex, e.g. deep neural networks, where one needs to resort to other methods, (back propagation).

The fact why this subject is important relates to the history of optimization. People managed to solve linear programs, where the simplex method is one of the first widely used methods to solve those kind of problems. Then they started to solve quadratic programs and other kinds of problems, but there was no obvious generalization. What these problems had in common was the convexity. It turns out that you can put the convex optimization problems in a canonical form, which is just a linear program. Thus making it a possibility to attack a huge class of problems. This is the best generalization we have so far, and I do not think we can generalize much further than this. Continues relaxations of discrete problems often also yields problems that are convex.

Most basic optimization problems are convex, a lot of statistics rely on convex optimization. In some cases you can get a closed form solution for the optimum (e.g. linear regression), but it is easy to define problems that do not have a closed form solution, (e.g. the lasso). If you are working on such a problem it is nice to have a tool to verify if your objective function is convex and to optimize it. This is possible in the software CVX developed by Boyd and others. This is very nice for prototyping, but if you need faster solvers sometimes you need to exploit the intricacies of the problem that you have to create a solver that works faster.

The newton method, the simplex method and others have in common that they are deterministic. They always yield the same results. Genetic algorithms do not give you this guarantee. They usually run much slower and are more suitable for when you have a noisy objective function or potentially a highly multi modal objective function.

It is entirely dependent on the problem that you are solving what method you would like to use. Read the introduction to the book and it will take you far!

$\endgroup$
  • $\begingroup$ >>> Often the issue of "making" your problem convex is reparameterization of the problem formulation. Could you please enumerate some examples? $\endgroup$ – Marat Zakirov Sep 9 '15 at 12:16
  • $\begingroup$ Here is an example from the math stackexchange. $\endgroup$ – Gumeo Sep 9 '15 at 12:45
  • 2
    $\begingroup$ I can second the Boyd reference! $\endgroup$ – Andrew Wagner Sep 26 '16 at 12:43
2
$\begingroup$

The reason so much time is spent developing convex programming is that it already works so well for so many problems, so improving it further is worthwhile.

Also, simple gradient descent does not work on many large non-smooth (but convex) problems that are very interesting. Stuff that is easy to deal efficiently with in 1-2 dimensions can become difficult in 1000 dimensions.

$\endgroup$
  • $\begingroup$ Do the tildes in front of "already" and "not" mean something? If so, what? $\endgroup$ – whuber Sep 23 '16 at 14:15
  • $\begingroup$ An old habit to add emphasis without formatting. Removed them. $\endgroup$ – Andrew Wagner Sep 26 '16 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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