# Proof Verification: Showing a function is affine if its convex and concave

I know this question has been asked several times but the answers don't really make sense to me (I'll explain misunderstandings:)

Question: Suppose that a function $$f: \mathbb R^n \rightarrow \mathbb{R}$$ is both concave and convex. Prove that $$f$$ is an affine function. My solution uses: How to prove convex+concave=affine? as inspiration. However, I'm not sure if I did it correctly especially for the negative cases and I'm not exactly sure if I have showed that $$g$$ is linear in all cases.

et $$g(x)=f(x)-a$$, where $$a=f(0)$$. Thus $$g(0)=0$$. Also since $$f$$ is convex and concave, $$g$$ is convex and concave as well. Thus for $$x,y \in \mathbb R^n$$, $$0 \leq \lambda \leq 1$$, by inequalities resulting from convexity and concavity we have: $$g(\lambda x +(1-\lambda) y)$$=$$\lambda g(x) +(1-\lambda)g(y)$$. Does this mean $$g$$ is linear (why?, I don't get this from looking at the other stack-exchange posts) and hence $$f$$ is affine.

Case 2: $$\lambda >1$$. Note $$x = (1/\lambda ) (\lambda x) + (1 - 1/\lambda) (0)$$. Note then $$1/ \lambda \in [0,1]$$. Thus $$g(x)=g((1/\lambda) (\lambda x) + (1 - 1/\lambda) (0))$$=$$1/\lambda \cdot g(\lambda x)+(1- 1/\lambda) \cdot g(0)$$. This means $$g(x)=1/\lambda * g(\lambda x)$$. Hence $$g(\lambda x)=\lambda g(x)$$.

Case 3: $$\lambda <0$$. Not sure what to do now....

Perhaps I could do :

Case : $$\lambda \leq -1$$.

$$x=(-1/\lambda)(-\lambda x)+(1+1/\lambda)(0)$$ Note that $$-1/\lambda \in [0,1]$$

$$g(x)=g((-1/\lambda)(-\lambda x) + (1 + 1/\lambda) (0))$$=$$-1/\lambda \cdot g(-\lambda x)+(1+1/\lambda) \cdot g(0)$$. This means $$g(x)=-1/\lambda * g(-\lambda x)$$. Hence $$g(-\lambda x)=-\lambda g(x)$$.

Case: $$-1< \lambda <0$$ Note $$-\lambda \in [0,1]$$. Thus $$x=(-\lambda)(-1/\lambda \cdot x)+(1+\lambda)(0)$$

$$g(x)=g((-\lambda) (-1/\lambda \cdot x) + (1 + \lambda) (0))$$=$$-\lambda \cdot g(-1/\lambda \cdot x)+(1+\lambda) \cdot g(0)$$. This means $$g(x)=-\lambda * g(-1/\lambda \cdot x)$$. Hence $$g(-1/\lambda \cdot x)=-1/ \lambda \cdot g(x)$$.

Any help would much appreciated. Thanks.

Thus, linear in all cases...not exactly sure if this is correct at all.

• Possible duplicate of How to prove convex+concave=affine? – wnoise Sep 10 '19 at 1:36
• @wnoise my question is different because I'm trying to verify whether my proof is correct and whether I successfully accomplished the recommendations given in that question. i tried to do what Robert Israel recommended. Did I accomplish this correctly? Please let me know as I've been very frustrated with this problem. thanks! – Boy Wonder Sep 10 '19 at 1:39
• Hi @wnoise if you can, can you remove that the question is a duplicate. I've updated my question with several edits and I have now noted in the title that my question is a proof verification one. I would like to know if I did the proof right, that is all using the hints from the one you tagged – Boy Wonder Sep 10 '19 at 1:45
• any ideas/corrections/suggestions/things to fix? thanks – Boy Wonder Sep 10 '19 at 2:12

Your proof is (mostly) finished after your case $$0\leq \lambda \leq 1$$! In other words, the other cases you consider for $$\lambda$$ are not required.

I will go into more detail as to why this is the case and hopefully alleviate some confusions. First of all I will mention the very important definition:

A function $$g:\mathbb{R}^n\rightarrow \mathbb{R}$$ is linear if for all scalars $$\gamma \in \mathbb{R}$$ and $$x\in\mathbb{R}^n$$ we have $$g(\gamma x) = \gamma g(x)$$ and for all $$x,y \in \mathbb{R}^n$$ we have $$g(x+y) = g(x) + g(y)$$.

So in order to prove a function is linear we need to show that both these conditions hold. Returning to your problem:

You have shown that if a function $$g$$ (such that $$g(0) = 0$$) is both convex and concave then for every $$\lambda\in[0,1]$$ and for every $$x,y\in \mathbb{R}^n$$ we have $$\begin{equation} g(\lambda x + (1-\lambda)y) = \lambda g(x) + (1-\lambda)g(y). \end{equation}$$ I claim that this enough to show that $$g$$ is linear. Note that in the above equation this holds for any choice of $$\lambda \in[0,1]$$ (and $$x,y\in\mathbb{R}^n$$) and so we are free to pick $$\lambda$$ (and $$x$$ and $$y$$) as we please! We will first show that $$g(\gamma x) = \gamma g(x)$$ for every $$\gamma \in \mathbb{R}$$ and $$x\in\mathbb{R}^n$$:

Note that if $$\gamma = 0$$ or $$\gamma = 1$$ then our claim is trivially true (since $$g(1\cdot x) = 1\cdot g(x)$$ and $$0 = g(0\cdot x) = 0\cdot g(x)$$ by definition of $$g$$). Consider $$\gamma\in(0,1)$$ then, using our above equation (which we are allowed to do since $$\gamma\in(0,1)$$ with $$\lambda = \gamma$$ and $$y=0$$, $$\begin{equation} g(\gamma x) = g(\gamma x + (1-\gamma)\cdot0) = \gamma g(x). \end{equation}$$ If $$\gamma > 1$$ then $$0<\frac{1}{\gamma} < 1$$ and we can use our above equation again. Using the equation with $$\lambda = 1/\gamma$$, $$x = \gamma X$$ and $$y=0$$ we obtain $$\begin{equation} \gamma g(X) = \gamma g\left(\frac{1}{\gamma} (\gamma X) + (1-\frac{1}{\gamma})\cdot0\right) = \gamma\cdot 1/\gamma\cdot g(\gamma X) = g(\gamma X), \end{equation}$$ by our previous proof. Thus we have shown that $$g(\gamma x) = \gamma g(x)$$ for $$\gamma\geq 0.$$ To show that this holds for $$\gamma < 0$$ too, we will use the equation above again with $$\lambda = 1/2$$, $$x = 2X$$ and $$y = -2X$$. Then $$\begin{equation} 0 = g(0) = g\left(\frac{1}{2}\cdot 2X - \frac{1}{2}\cdot2X)\right) = \frac{1}{2}g(2X) + \frac{1}{2}g(-2X) = g(X) + g(-X), \end{equation}$$ where in the last step we used our previously proven result that $$g(\gamma x) = \gamma g(x)$$ for $$\gamma \geq 0$$. This implies that $$g(-x) = -g(x).$$ Thus for $$\gamma < 0$$ we have (since $$-\gamma > 0$$), $$-\gamma g(x) = g(-\gamma x) = -g(\gamma x)$$ by our previous arguments. And so $$\gamma g(x) = g(\gamma x)$$.

We now only need to prove that $$g(x + y) = g(x) +g(y)$$ for every $$x,y\in\mathbb{R}^n$$. Similar tricks to before can be used, but I will leave the details for you. (Hint: Use $$\lambda =1/2$$ and a tactical choice of $$x$$ and $$y$$).

We are now finished.

• @BoyWonder Sure. To prove $g(x+y) = g(x) + g(y)$ we don't really want to set $x$ or $y$ to be $0$. This is because if we did, when using the equation we would eliminate one of the $g(x)$ or $g(y)$ which we don't want to do! The clue is just to look at the original equation and force it to look like what we want it to. We picked $\lambda = 0.5$ for a reason (since $\lambda = 1-\lambda$). – Timothy Hedgeworth Sep 10 '19 at 3:07
• should I write $x$ and $y$ in terms of $X$ and $\gamma$. not sure exactly how to start. ive been trying a few things – Boy Wonder Sep 10 '19 at 3:08
• @BoyWonder We can set both $x$ and $y$ in terms of $X$ and $Y$ respectively. – Timothy Hedgeworth Sep 10 '19 at 3:10
• let me try something in 10 minutes and I'll be back to ask if you if I'm on the right track, thanks – Boy Wonder Sep 10 '19 at 3:14
• so why I can't I take $x=-\gamma X$ and $y=0$. I don't get why this doesn't work: – Boy Wonder Sep 10 '19 at 4:01