5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of How to prove convex+concave=affine? $\endgroup$ – wnoise Sep 10 '19 at 1:36
  • $\begingroup$ @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! $\endgroup$ – Boy Wonder Sep 10 '19 at 1:39
  • $\begingroup$ 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 $\endgroup$ – Boy Wonder Sep 10 '19 at 1:45
  • $\begingroup$ any ideas/corrections/suggestions/things to fix? thanks $\endgroup$ – Boy Wonder Sep 10 '19 at 2:12
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @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$). $\endgroup$ – Timothy Hedgeworth Sep 10 '19 at 3:07
  • $\begingroup$ should I write $x$ and $y$ in terms of $X$ and $\gamma$. not sure exactly how to start. ive been trying a few things $\endgroup$ – Boy Wonder Sep 10 '19 at 3:08
  • $\begingroup$ @BoyWonder We can set both $x$ and $y$ in terms of $X$ and $Y$ respectively. $\endgroup$ – Timothy Hedgeworth Sep 10 '19 at 3:10
  • $\begingroup$ let me try something in 10 minutes and I'll be back to ask if you if I'm on the right track, thanks $\endgroup$ – Boy Wonder Sep 10 '19 at 3:14
  • $\begingroup$ so why I can't I take $x=-\gamma X$ and $y=0$. I don't get why this doesn't work: $\endgroup$ – Boy Wonder Sep 10 '19 at 4:01

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.