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

2 Answers 2

up vote 2 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? –  user1058 May 12 '12 at 15:33
    
@mrothe: You are right, I edited it. –  Michael Greinecker May 12 '12 at 15:36

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.