# Is the minimum of a parametric convex function convex again?

Let $I$ and $J$ be compact intervals. Let $f:I\times J\to\mathbb R$ be differentiable and strictly convex. Is the function $g:I\to\mathbb R$ defined by $$g(x) = \min_{y\in J} f(x,y)$$ convex?

Remarks:

• I know that minimum of convex functions is in general not convex. However, I can't find a counter example in which $f$ is convex.

• The regularity ensures that the minimizer $y^*(x)$ of $f(x, \cdot)$ is unique.

• Assume $y^*$ as function is convex, $y^*$ maps $I$ into an interval $J^*$, and $f(x, \cdot)$ is increasing on $J^*$ for every $x\in I$. Then, $g$ is convex.

Thanks for any input :)

It is convex!

Your first statement that the minimum of convex functions is in general not convex is true, but here you have a lot more structure! In a sense you are projecting onto $x$. In fact, $g$ is also called the inf-projection of $f$. Let $\lambda \in (0,1)$ and $y_1, y_2 \in J$ arbitrary:

\begin{aligned} g(\lambda x_1 + (1-\lambda) x_2) &= \min_{y} f(\lambda x_1 + (1-\lambda)x_2, y) \\ &\leq f(\lambda x_1 + (1-\lambda)x_2, \lambda y_1 + (1-\lambda)y_2)\\ &\leq \lambda f(x_1, y_1) + (1-\lambda) f(x_2,y_2)\\ \end{aligned}

Now first minimize with respect to $y_1$, then with respect to $y_2$ to finally get: $$g(\lambda x_1 + (1-\lambda) x_2) \leq \lambda g(x_1) + (1-\lambda) g(x_2)$$

Also notice that you do not need the regularity conditions you imposed onto $f$.

Theorem: Let $X,Y$ be real linear spaces and $f\colon X\times Y\to [-\infty,+\infty]$ be convex. Then $$\phi(x)=\inf_{y\in Y}f(x,y)$$ is convex.

Proof: Let $E$ be the image of $\text{epi}(f)$ under the projection $(x,y,\alpha)\to (x,\alpha)$. Then by definition of infimum $$\text{epi}(\phi)=\{(x,\alpha)\in X\times\mathbb{R}\colon \ (x,\beta)\in E,\ \forall\beta>\alpha\}.\tag1$$ The epigraph of $f$ is convex, then $E$ is convex (as a linear image of the convex set), and $(1)$ yields then that $\text{epi}(\phi)$ is convex as an intersection of convex sets $E_\epsilon=E-(0,\epsilon)$, i.e. $$\text{epi}(\phi)=\bigcap_{\epsilon>0}E_\epsilon.$$

P.S. Since a convex function $f$ on any set $S\subset X\times Y$ can be extended to the whole space by (re)defining $f=+\infty$ outside $S$, the generality is not lost by assuming that $f$ is defined on $X\times Y$.

• Irrespective of whether your answer is correct or wrong, here you're talking about linear spaces; how does it link back to the user's question where $X$ and $Y$ are compact sets ? Aug 24, 2015 at 2:43
• @dohmatob I am talking about functions to the extended real line. One can always (re)define $f=+\infty$ outside a set of one's particular interest, so no generality is lost to replace it with the whole space.
– A.Γ.
Aug 24, 2015 at 3:07
• I'm a fan of extended real treatment myself. But yes, I'd agree this doesn't quite answer the question without that clarification. Aug 24, 2015 at 3:43
• @A.G.: Indeed you can always do thusly. I was worried about pedagogy for the user. Still concerning pedagogy, there is a significant amount of non-trivial detail buried in your answer, for example: $\alpha \ge \phi(x) \iff \exists y_0 \in Y | \beta \ge f(x, y_0) \forall \beta > \alpha$, etc. Also, your extension to linear spaces does no good to the remainder of the problem. Aug 24, 2015 at 3:46
• @user251257: Proposition A.22 of the PhD thesis of Bertsekas web.mit.edu/dimitrib/www/phdthesis.pdf provides a extenstion to Danskin's Theorem, which establishes the first parts of your result, plus much more. Think of Danskin's Theorem (and generalizations thereof) whenever you see problems like yours :) Aug 24, 2015 at 4:33