0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Khue Sep 17 '15 at 12:57
2
$\begingroup$
  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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.