Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have globally optimal solutions, so one can use methods such as gradient (steepest) descent to find such solutions, but I am not convinced.

For example, the function $|x|^{0.001}$ is not convex (see the yellow-shaded area in the picture below) but it has a single global minimizer.

                      enter image description here

Update:

From the comments and answers I learned/recalled that the function above is quasiconvex. If my understanding is correct, and quasiconvex functions such as the one above have a single minimizer:

  • Why is convexity more important than quasiconvexity in optimization? Why do all optimization texts focus on convexity and not on quasiconvexity?
share|improve this question
    
From what I understand, convex functions are "easier" to minimize from a computational complexity point of view. That is, you can find the solution in polynomial time up to a pre-specified accuracy. You might want to look at the book "Introductory Lectures on Convex Optimization: A Basic Course" by Yurii Nesterov. I guess it is available partially in Google books. (I suggest looking at the first chapter of that book.) Or go to his website and look at some of his slides. –  passerby51 May 17 '12 at 21:01
1  
The function above is amenable to convex optimization after the transformation $x \mapsto 1/x$. –  Emre May 17 '12 at 23:34
1  
In a few words, convexity implies that a local minimum is a global minimum. –  Yuval Filmus May 18 '12 at 0:18
1  
Your example function is quasiconvex. –  cardinal May 18 '12 at 15:06
4  
Fromthe Wikipedia article on quasiconvex functions one can infer the advantages and disadvantages of this class of functions relative to convex ones. One I find particularly striking is that the sum of two quasiconvex functions need not be quasiconvex. –  Rahul May 18 '12 at 15:57
show 5 more comments

5 Answers

There are many reasons why convexity is more important than quasi-convexity in optimization theory. I'd like to mention one that the other answers so far haven't covered in detail. It is related to Rahul Narain's comment that the class of quasi-convex functions is not closed under addition.

Duality theory makes heavy use of optimizing functions of the form $f+L$ over all linear functions $L$. If a function $f$ is convex, then for any linear $L$ the function $f+L$ is convex, and hence quasi-convex. I recommend proving the converse as an exercise: $f+L$ is quasi-convex for all linear functions $L$ if and only if $f$ is convex.

Thus, for every quasi-convex but non-convex function $f$ there is a linear function $L$ such that $f+L$ is not quasi-convex. I encourage you to construct an example of a quasi-convex function $f$ and a linear function $L$ such that $f+L$ has local minima which are not global minima.

Thus, in some sense convex functions are the class of functions for which the techniques used in duality theory apply.

share|improve this answer
add comment

Sophisticated optimization methods are developed to deal with problems where it is not obvious what the solution is. In general, we may not know much about the behavior of the cost function, so we cannot decide on an a-priori base whether there is a unique minimum or not. We need optimization methods to find the or a minimum.

For convex problems, the global behavior is determined by purely local properties. If a function is everywhere locally convex, it is globally convex too. So for such problems, local solutions are sufficient, which make them a lot easier to deal with.

share|improve this answer
    
Thanks Michael, but when you said: For convex problems, the global behavior is determined by purely local properties. If a function is everywhere locally convex, it is globally convex too. So for such problems, local solutions are sufficient, which make them a lot easier to deal with. Wouldn't all this hold as well if I replace the word convex by quasiconvex? If so, why is convexity more important than quasiconvexity? –  user815423426 May 19 '12 at 18:44
    
Almost. Every monotone function from the reals to the reals is quasiconvex. But a function can be locally monotone without beig globally monotone. I think it works with strictly quasi-convex functions though. –  Michael Greinecker May 19 '12 at 19:44
add comment

For your first question, the answer is basically yes.

Gradient methods are usually descent methods, so the cost function decreases at points that are non-optimal points. Many such methods also have the property that any accumulation point of the sequence generated cannot have a non-zero gradient (call these 'guaranteed' descent methods). (This awkward wording allows the cost function to be non-differentiable at a minimum.)

Here is a sufficient condition that applies to the problem above: Let the initial point be $x_0$, and let $L_{x_0} = \{x | f(x) \leq f(x_0) \}$. Suppose $L_{x_0}$ is compact and the gradient is non-zero at all points other than the minimizer. Then any 'guaranteed' descent methods will converge to the minimizer. (I'm assuming that the cost function $f$ is $C^1$ at non-optimal points.) The problem you have above satifies these conditions.

The second question is more of a discussion topic. Some points to consider:

Duality is another big plus for convex problems. Dual problems are often more amenable to solutions.

Problems can often be transformed into convex problems, posynomials being a good example.

Often convexity of the level sets is the important criterion. Various generalizations (eg, pseudo-, and quasi-convexity) can extend the usefulness of convexity to broader settings.

share|improve this answer
add comment

Like someone else said, convex problems often have a dual, which lets an algorithm solve the problem from two sides and declare the solution when the duality gap is sufficiently close to 0 (when the lower and upper bound on the solution converge). There are also fairly efficient methods and algorithms that can solve canonical convex problems which do not extend easily to general quasiconvex problems.

For strict quasiconvex problems, a gradient descent method should be sufficient, but it's a question of algorithmic efficiency. The algorithms for canonical convex problems are just much more efficient.

At least, that's my impression of why there's so much focus on convexity. However, one could certainly argue that quasiconvexity is often overlooked when it would be useful...

share|improve this answer
add comment

I'm not an expert, but just from eyeballing your function you can see that gradient descent would not converge to the global minimizer. Gradient descent looks for places where the gradient (which is just the derivative for 1-dimensional functions like the one you provide) is zero. In a convex function, as you approach the minimum, the gradient approaches zero (and vice versa). But you can see that, as you approach the minimum in your function, the derivative is getting further and further from zero.

If you try to do gradient descent on that function, you'll actually move further and further away from the minimum, since the gradient is minimized as you approach (positive or negative) infinity.

So at least one reason convexity is so important in optimization is that the global minimum is also the unique critical point (place where the gradient is zero), which allows you to search for one by searching for the other. In some sense, you pick a point, look around a little bit, and move in the direction that makes your gradient smaller. Repeat this enough and you'll get to a really small gradient, which corresponds to being close to the minimum.

share|improve this answer
1  
Generally gradient methods use some form of step size to ensure a descent. –  copper.hat May 18 '12 at 4:09
1  
-1: This is not how gradient descent works. In short, you perform successive line searches along the ray $x_n - \alpha \nabla f(x_n)$ with $\alpha$ positive, so you never go up the gradient, and use sufficient decrease criteria to ensure that $f(x_n-\alpha\nabla f(x_n))$ is (sufficiently) less than $f(x_n)$. So you do approach the minimum even on the nonconvex function in the question. –  Rahul May 18 '12 at 15:45
1  
I wrote that poorly. It should be "use sufficient decrease criteria to ensure that the value at the next iterate $f(x_n−\alpha\nabla f(x_n))$ is (sufficiently) less than the current value $f(x_n)$." –  Rahul May 18 '12 at 16:09
    
MartianInvader, did you mix up gradient descent with the Newton method (en.wikipedia.org/wiki/Newton%27s_method_in_optimization)? The Newton method would have exactly the problem you are describing... (Indeed, there is variant of gradient descent which uses the Newton method to calculate the "ideal" step length. In fact, this would not work here... Of course, this only makes sense for a multi-dimensional function.) –  Hauke Strasdat May 21 '12 at 18:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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