9
$\begingroup$

I understand that a convex function is a great object function since a local minimum is the global minimum. However, there are non-convex functions that also carry this property. For example, enter image description here

this figure shows a non-convex function that carries the above property.

It seems to me that, as long as the local minimum is the global minimum, we should be able to use gradient-decent (or similar methods) to find the global minimum. So, my question is, why do convex functions get more attention, compared to other functions that also carry the above property? Thanks!

[UPDATE] Thanks for many of the great comments and answers. I self-learned concepts of optimization and I admit many of my wording are imprecise. Do you have any suggested references for more practical aspects of convex optimization? Boyd's book is probably too intense for me.

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ Although not all functions with unique minima are convex, all convex functions have unique minima. Often one can check that a function is convex much, much more easily than whether it has a unique minimum. That alone merits the attention. In what sense, though, are all ML researchers interested "mostly" in convex functions? Do you have some support for this, or is it just a personal impression? $\endgroup$
    – whuber ♦
    Commented Jun 21, 2016 at 3:03
  • 5
    $\begingroup$ Note that the function you show actually has a related property: It is quasiconvex (its sublevel sets are convex). That said, convexity admits a rich calculus that, itself, yields many useful algorithms with verifiable optimality (sometimes referred to as certificates of $\epsilon$-optimality) through primal-dual relationships. As Rockafellar said: "(...)in fact, the great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity". $\endgroup$
    – cardinal
    Commented Jun 21, 2016 at 5:23
  • 3
    $\begingroup$ A very minor quibble with @whuber's comment: He implicitly is referring to strictly convex functions. (Many convex functions have multiple minima, e.g, $f(x) = 0$.) $\endgroup$
    – cardinal
    Commented Jun 21, 2016 at 5:25
  • 1
    $\begingroup$ If you find Boyd's book too intense you might find Kelley's Iterative Methods for Optimization more palpable. Nocedal's and Wright's Numerical Optimization is considered pretty standard too (but I don't know if it is free). These books do not focus on convex optimisation exclusively. $\endgroup$
    – usεr11852
    Commented Jun 21, 2016 at 6:00
  • 3
    $\begingroup$ Neural nets are perhaps best known case of ML model with non convex objective function, and currently it feels like all ML researchers are doing Neural nets! $\endgroup$
    – seanv507
    Commented Jun 21, 2016 at 6:05

1 Answer 1

Reset to default
5
$\begingroup$

First of all as @whuber mentioned many people are involved in non-convex optimisation. Having said, your definition of "as long as the local minimum is the global minimum" is rather... lax. See for instance the Easom function ($f(x,y) = -\cos(x)\cos(y)\exp(-(x-\pi)^2 - (y-\pi)^2)$. It has a single minimum if that is your concern but if your even remotely away from it you are... staffed. Standard gradient-based methods like BFGS (BFGS in R's optim )and Conjugate Gradient (CG in R's optim) will suffer greatly. You will have to essentially make an "educated guess" about your answer (eg. Simulated Annealing - SANN in R's optim), which a very computationally expensive routine. enter image description here

In R:

easom <- function(x){ 
  -cos(x[1]) * cos(x[2]) * exp( -(x[1] -pi)^2 - (x[2] - pi)^2)
}
optim(easom,par=c(0,0), method='BFGS')$par # 1.664149e-06 1.664149e-06 # Junk
optim(easom,par=c(0,0), method='CG')$par # 0 0 # Insulting Junk
optim(easom,par=c(0,0), method='SANN')$par # 3.382556 2.052309 # Some success!

There are other even worse surfaces to optimise against. See for example Michalewicz's or Schwefel's functions where you might have multiple local minima and/or flat regions.

This flatness is a real problem. For example in generalised as well as standard linear mixed effects model as the number of estimation parameters increases, the log-likelihood function, even after profiling out the residual variance and the fixed-effects parameters can still be very flat. This will lead the model to converge on the boundary of the parameter space or simply to a suboptimal solution (this is actually one of the reason some people myself included are skeptical with the 'keep it maximal' idea for LME's). Therefore "how much convex" your objective function might have big impact to your model as well as your later inference.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ +1 I am glad you finished with the thoughts about "how much convex," because I couldn't help thinking that even when a function is convex, finding an optimum numerically can be problematic. The thread at stats.stackexchange.com/questions/7308 presents an example of that in a real statistical application. (Do note that this function is not globally convex; but I believe it is convex within a neighborhood of the two "solutions" that were found numerically, which is what matters.) $\endgroup$
    – whuber ♦
    Commented Jun 21, 2016 at 13:06
  • $\begingroup$ I assume you meant to say "stuffed"! In any case, I would disagree. All it means is that you have a poor starting point, so choose another one, possibly at random. This is common practice (or I am a complete genius) in the optimization world. I am not a mathematician, but I have been studying optimization using my own code. Trust me, you can easily solve an 8-D version of Easom (see arxiv.org/abs/1008.0549) with nelder-mead if you take enough tries ;) $\endgroup$
    – m4r35n357
    Commented Mar 16 at 10:09
  • $\begingroup$ OK I went a bit OTT on the flippancy scale there, but I was trying to make a point. There is a seeming obsession in the optimization "scene" with being able to find the global minimum of an arbitrary "black box" model in a single attempt. This is clearly fantasy - either you know enough about the function (the global minimum!) that it is no longer a black box, or you need to keep trying (many times) because you can't be sure. $\endgroup$
    – m4r35n357
    Commented Mar 16 at 11:56

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.