8
$\begingroup$

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 :)

$\endgroup$

2 Answers 2

10
$\begingroup$

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

$\endgroup$
0
7
$\begingroup$

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

$\endgroup$
15
  • $\begingroup$ 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 ? $\endgroup$
    – dohmatob
    Aug 24, 2015 at 2:43
  • 1
    $\begingroup$ @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. $\endgroup$
    – A.Γ.
    Aug 24, 2015 at 3:07
  • $\begingroup$ I'm a fan of extended real treatment myself. But yes, I'd agree this doesn't quite answer the question without that clarification. $\endgroup$ Aug 24, 2015 at 3:43
  • $\begingroup$ @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. $\endgroup$
    – dohmatob
    Aug 24, 2015 at 3:46
  • $\begingroup$ @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 :) $\endgroup$
    – dohmatob
    Aug 24, 2015 at 4:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .