Take the 2-minute tour ×
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.

I am given the following problem, but can't figure it out.

Let $f\colon\mathcal{C}\rightarrow\mathbb{R}$ denote a convex function defined on the convex set $\mathcal{C}$. A (global) minimum of $f$ is an $x^*\in\mathcal{C}$ with $f(x^*)\leq f(x)$ for all $x\in\mathcal{C}$. Show that the set $\mathcal{S}$ of all minimum points of $f$ is convex.

I have tried the following but am unable to "finish" the solution (maybe I'm not even close and working in the wrong direction?):

$$\mathcal{S} = \left\{x^*~\middle|~f(x^*)\leq f(x),\, x\in\mathcal{C}\right\}$$

Let $u, v \in\mathcal{C}$, $\lambda\in(0,1)$. Then

$$\lambda u + (1-\lambda)v \overset{!}{\in} \mathcal{S}\\ \Leftrightarrow f(\lambda u + (1-\lambda)v) \overset{!}{\leq} f(x),\quad\forall x\in\mathcal{C}$$

  • $f$ is strict convex: the set S has only one element and the set is convex
  • $f$ is convex: because $f$ is defined over a convex set the line of points between $u$ and $v$ are in the set. At this point I'm lost.
share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Let $x,y\in\mathcal{S}$. Since both are minimizers, $f(x)=f(y)$. Let $\lambda\in(0,1)$. Since $f$ is convex, $f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)=\lambda f(x)+(1-\lambda)f(x)=f(x)$. Since $x$ minimizes $f$, also $f(x)\leq f(\lambda x+(1-\lambda)y)$. So every convex combination in $\mathcal{C}$ gives the same value of $f$ and that is the smallest one. So $\mathcal{S}$ is convex.

share|improve this answer
    
Thank you. Should the right side in $f(x)\leq (\lambda x+(1-\lambda)y)$ not be $f(\cdot)$? I.e. $f$ missing? –  emuso May 12 '12 at 15:33
    
@mrothe: You are right, I edited it. –  Michael Greinecker May 12 '12 at 15:36
add comment

Let $x_1$ and $x_2$ be two minimum points. If $0 \leq \lambda \leq 1$, then $$f (\lambda x_1 + (1-\lambda)x_2)\leq \lambda f(x_1)+(1-\lambda)f(x_2) = \lambda \min f + (1-\lambda) \min f = \min f.$$ Hence $\lambda x_1 + (1-\lambda) x_2$ is a minimum point.

share|improve this answer
add comment

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.