2

Can someone give an example of a convex function $f$ on a path-connected compact nonconvex set where some point $c$ is a local minimum with $\nabla f(c)=0$ but not a global minimum. Thus showing that the set being not convex makes finding global minimums harder.

user782220
  • 3,195
  • 1
    Consider the blue region in this image... –  Mar 11 '12 at 06:09
  • Regarding your edit, if $f$ is convex and $\nabla f(c)=0$, then $c$ has to be the global minimum. But $\nabla f(c)=0$ is not necessary for $c$ to be a local or global minimum when the domain is compact: often, $\nabla f$ is zero nowhere, and the local and global minima lie on the boundary of the domain, as my example shows. –  Mar 11 '12 at 07:16
  • @RahulNarain: if $f$ is convex and $\nabla f(c)=0$, then $c$ has to be the global minimum if the set on which $f$ is defined on is convex. But if the set is not convex then I don't see why $c$ would be the global minimum. – user782220 Mar 11 '12 at 09:00
  • I was implicitly assuming $f$ to be defined on a convex superset of your nonconvex set, in which case the result is immediate. If not, how do you define a convex function on a nonconvex set? –  Mar 11 '12 at 09:21
  • $f(t x_1+ (1-t)x_2) \le t f(x_1) + (1-t)f(x_2)$ if the line connecting $x_1$ and $x_2$ lies in the nonconvex set. – user782220 Mar 11 '12 at 09:57
  • 1
    ...So, by your definition, any function on the circle $x^2+y^2 = 1$ is convex? I wouldn't call that a very useful definition. Is it part of some standard reference, or did you make it up? –  Mar 11 '12 at 10:07
  • Well presumably the focus would be on set with interior having some meat to it. – user782220 Mar 11 '12 at 10:26

2 Answers2

3

For example the function $f(x,y) = x^2+y^2$ restricted to the square with vertices $(-1,-2)$, $(5,-2)$, $(5,4)$ and $(-1,4)$ has four local minima but only one global minimum.

WimC
  • 32,192
  • 2
  • 48
  • 88
3

Consider the set $$A:=[-1,3]\times[-3,3]\ \setminus\ \{(x,y)\ |\ 0<|y|<x\leq3\}$$ (a rectangle minus an isosceles triangle) and define $$f(x,y):=\cases{(x-2)^2 & $(x\leq 0 \ \vee\ y<0)$ \cr 2(x-1)^2+2 & $(x>0\ \wedge \ y>0)$\cr}\ .$$ This $f$ is $C^1$ on $A$, convex, and has local minima at $c:=(2,-{5\over2})$, $c':=(1,2)$ with $f(c)=0$, $f(c')=2$.

Christian Blatter
  • 226,825