Tell me more ×
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.
up vote 0 down vote favorite

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.

share|improve this question
1  
Consider the blue region in this image... – Rahul Narain Mar 11 '12 at 6: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. – Rahul Narain Mar 11 '12 at 7: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 9: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? – Rahul Narain Mar 11 '12 at 9:21
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? – Rahul Narain Mar 11 '12 at 10:07
show 2 more comments

2 Answers

up vote 1 down vote accepted

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$.

share|improve this answer
@Rahul Narain: There was a typo in the definition of the isosceles triangle. Thank you. – Christian Blatter Mar 11 '12 at 13:19
up vote 1 down vote

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.

share|improve this answer
A square is not a non-convex set. – user782220 Mar 11 '12 at 9:01
@user782220, I believe WimC means the boundary of the square, not its interior. – Rahul Narain Mar 11 '12 at 10:23
@user782220 As Rahul Narain commented: The boundary of the square. (Otherwise $f$ would clearly only have a single local minimum.) – WimC Mar 11 '12 at 12:50

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.