2
$\begingroup$

Prove $f$ is a convex function where

$$f(x)=\sum^m_{i=1}e^{-\frac{1}{f_i(x)}}$$ dom$f=\{x|f_i(x)<0, i=1, \dots, m\}$, where the functions $f_i$ are convex and $x \in \mathbb R^n$.

I was trying to prove it by the definition of a convex function:

$f$ is called convex if: $\forall x_1, x_2 \in X, \forall t \in [0, 1]:$

$$f(tx_1+(1-t)x_2)\leq t f(x_1)+(1-t)f(x_2)$$ But when I plug in the vectors the while formula is kind of messy. Any ideas? Thanks a lot~

$\endgroup$
  • $\begingroup$ Sometimes you just have to roll up your sleeves and get messy. $\endgroup$ – Jake Dec 5 '17 at 2:48
  • $\begingroup$ You might be able to build up an answer by showing that convex functions are closed under, for example, sums and exponentials and reciprocals, or exponential-of-negative-reciprocals. $\endgroup$ – user326210 Dec 5 '17 at 2:50
  • $\begingroup$ @Jake as the accepted answer shows, when it comes to proving convexity, "getting messy" (i.e., proving convexity from first principles) is really the last thing you want to do. Composition rules usually get you very far. In fact, in practice, I'd say this: if you don't have a strong reason to believe something is convex, and you find yourself with no other option than to resort to a derivative or secant test---spend some time looking for a counterexample because you're likely looking at a nonconvex function. $\endgroup$ – Michael Grant Dec 5 '17 at 15:09
2
$\begingroup$

Here's the argument:

  1. The function $g(x) = \exp{(-1/x)}$ is convex and nondecreasing on negative numbers.
  2. If $f$ is convex and $g$ is convex and nondecreasing, then $g\circ f$ is convex.
  3. Hence if $f$ is convex and its output is negative, then $\exp{[-1/f(x)]}$ is convex.
  4. Convex functions are closed under sums.
  5. Hence if $f_1,\ldots, f_n$ are functions as described in the question, then $f \equiv \sum_{i} \exp{[-1/f_i]}$ is convex.

Proof of 2: If $f$ is convex, and $g$ is both convex and nondecreasing, then $g\circ f$ is convex.

Proof: Fix $x, y$ in the domain of $f$, and $t\in [0,1]$. Then:

$$ \begin{align*} (g\circ f)(tx + (1-t)y) &= g( f(tx+(1-t)y)\\ &\leq g(tf(x) + (1-t)f(y)) & f\text{ convex}, g\text{ nondecreasing (!)}\\ &\leq tg(f(x)) + (1-t)g(f(y))& g\text{ convex}\\ &= t(g\circ f)(x) + (1-t)(g\circ f)(y) \end{align*}$$

$\endgroup$
  • $\begingroup$ This is exactly how it should be done. Amateur convex analysts around the world are suffering unnecessarily from a lack of comfort with these composition rules! ;-) $\endgroup$ – Michael Grant Dec 5 '17 at 19:20
1
$\begingroup$

Hints:

The projection functions $x \rightarrow x_i$ are convex.

The $1/x$ function is convex.

The $e^{-x}$ function is convex.

The composition of a convex function with an increasing convex function is convex.

The sum of convex functions is convex.

You are done.

You can prove each of the above (proofs can also be easily found by Googling).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.