Exercise 1.1* (Concave convex functions are affine)

Proof. Our goal is to demonstrate that $f$ is representable in the form

for some $a_0\in \Re ,𝐚\in {\Re }^n$ (see the definition on page 15).

The trick is to notice that $f=f(0)+f^{\ast }$ for a linear function $f^{\ast }$; thus, consider

We demonstrate that $f^{\ast }$ is indeed linear.

• (convexity and concavity) We have $f^{\ast }\left(\lambda 𝐱+(1-\lambda )𝐲\right)=\lambda f^{\ast }\left(𝐱\right)+(1-\lambda )f^{\ast }\left(𝐲\right).$
  Proof. By theorem assumption, $f$ is convex. By Definition 1.1.,

  $$f\left(\lambda 𝐱+(1-\lambda )𝐲\right)\le \mathit{𝜆𝑓}\left(𝐱\right)+(1-\lambda )f\left(𝐲\right).$$

  Similarly, since $f$ is concave, we have

  $$f\left(\lambda 𝐱+(1-\lambda )𝐲\right)\ge \mathit{𝜆𝑓}\left(𝐱\right)+(1-\lambda )f\left(𝐲\right).$$

  Combining both of these facts, we see that

  $$f\left(\lambda 𝐱+(1-\lambda )𝐲\right)=\mathit{𝜆𝑓}\left(𝐱\right)+(1-\lambda )f\left(𝐲\right).$$

  The same property must then also hold for $f^{\ast }$:

  $$\begin{array}{llll}\hfill f^{\ast }\left(\lambda 𝐱+(1-\lambda )𝐲\right)& =f\left(\lambda 𝐱+(1-\lambda )𝐲\right)-f\left(0\right)& \hfill & \\ \hfill & =\mathit{𝜆𝑓}\left(𝐱\right)+(1-\lambda )f\left(𝐲\right)-\mathit{𝜆𝑓}\left(0\right)-(1-\lambda )f\left(0\right)& \hfill & \\ \hfill & =\lambda f^{\ast }\left(𝐱\right)+(1-\lambda )f^{\ast }\left(𝐲\right).& \hfill & \end{array}$$

• (homogeneity) We have $f^{\ast }(c𝐱)=c{f}^{\ast }(𝐱)$for any $c\ge 0$.
  Proof. We break up this assertion into cases. The case when $c=0$ or $c=1$ follows trivially from convexity-concavity condition (also notice that $f^{\ast }(0)=0$). If $c\in (0,1)$ then

  $$f^{\ast }(c𝐱)=f^{\ast }(c𝐱+(1-c)0)=c{f}^{\ast }(𝐱)+(1-c)f^{\ast }(0)=\mathit{𝑐𝑓}(𝐱).$$

  Finally, if $c\in (1,+\infty )$, then $\frac{1}{c}\in (0,1)$ and so,

  $$f^{\ast }\left(𝐱\right)=f^{\ast }\left(\frac{1}{c}c𝐱+\left(1-\frac{1}{c}\right)0\right)=\frac{1}{c}{f}^{\ast }\left(𝐱\right).$$

  Multiplying both sides by $c$ yields the desired result.

• (additivity) We have $f^{\ast }(𝐱+𝐲)=f^{\ast }(𝐱)+f^{\ast }(𝐲)$for any $𝐱,𝐲\in {\Re }^n$.
  Proof. This is simply a matter of setting $\lambda =\frac{1}{2}$ and following the convexity-concavity equation:

  $$\begin{array}{llll}\hfill f^{\ast }\left(𝐱+𝐲\right)& =f^{\ast }\left(\frac{1}{2}\cdot 2𝐱+\frac{1}{2}\cdot 2𝐲\right)& \hfill & \\ \hfill & =\frac{1}{2}{f}^{\ast }\left(2𝐱\right)+\frac{1}{2}{f}^{\ast }\left(2𝐲\right)& \hfill & \\ \hfill & =f^{\ast }\left(𝐱\right)+f^{\ast }\left(𝐲\right)& \hfill & \end{array}$$

  where the last equality comes from the previous claim on homogeneity of $f^{\ast }$.

• (homogeneity II) We have $f^{\ast }(c𝐱)=c{f}^{\ast }(𝐱)$for any $c<0$.
  Proof. To prove the result for the negative numbers, we consider the special case $c=-1$. By homogeneity for non-negative scalars and by the additivity, we obtain

  $$f(𝐱)=f(2𝐱-𝐱)=f(2𝐱)+f(-𝐱)=2f(𝐱)+f(-𝐱)⟹-f(𝐱)=f(-𝐱).$$

  Using this, we see that for any $c\in (-\infty ,0)$ it is true that $f(-c𝐱)=-\mathit{𝑐𝑓}(𝐱)$.

• (linearity) We have

  $$f^{\ast }\left(\underset{i=1}{\overset{k}{\sum }}{a}_i{𝐱}_i\right)=\underset{i=1}{\overset{n}{\sum }}{a}_i{f}^{\ast }\left({𝐱}_i\right)$$

  for any $a_1,\dots ,a_n\in [0,+\infty )$and ${𝐱}_1,\dots ,{𝐱}_k\in {\Re }^n$.
  Proof. This follows from homogeneity and pairwise additivity using induction on $k$.

Now we make use of these properties of $f^{\ast }$. For any $𝐱\in {\Re }^n$ we make use of linearity to obtain:

where ${𝐞}_1,\dots ,{𝐞}_n$ denote the basis vectors of ${\Re }^n$. Setting $a_0:=f\left(0\right)$ and $a_i:=f^{\ast }({𝐞}_i)$, we obtain the desired result. □