1

I'm just learning about optimization, and having trouble understanding the difference between convex and non-convex optimization. From my understanding, a convex function is one where "the line segment between any two points on the graph of the function lies above or on the graph". In this case, a gradient descent algorithm could be used, because there is a single minimum and the gradients will always take you to that minimum.

However, what about the function in this figure:

enter image description here

Here, the blue line segment crosses below the red function. However, the function still has a single minimum, and so gradient descent would still take you to this minimum.

So my questions are:

1) Is the function in this figure convex, or non-convex?

2) If it is non-convex, then can convex optimization methods (gradient descent) still be applied?

Thanks!

Karnivaurus
  • 827
  • Gradient descent leads to a minimum, which is local or global depending on the nature of the function, the position of the starting point, and the direction. – f10w Sep 17 '15 at 12:57

3 Answers3

2

  1. Non-Convex

  2. Gradient descent is an unconstrained optimization method, but it's success depends on various conditions over the functions, like differentiability of the function, Lipschitz condition etc. If a function is not convex, then you can not guarantee about the global optima.

Rajat
  • 2,442
2

In convex functions, all chords lie above the function values.

You can apply gradient descent to non-convex problems provided that they are smooth, but the solutions you get may be only local. Use global optimization techniques in that case such simulated annealing, genetic algorithms etc.

Rubi Shnol
  • 1,125
  • 8
  • 28
0

Yes. The function you have is non-convex. Nevertheless, gradient descent will still take you to the global optimum as you have correctly pointed out "the function still has a single minimum". This function is quasi-convex. Gradient descent almost always work for quasi convex functions but we do not have convergence guarantees. I used almost always because you can be unlucky and end up on a saddle point.

Shiv Tavker
  • 1,612
  • 7
  • 19