1
$\begingroup$

A set $X \subseteq \mathbb{R}^n$ is said to be convex if $tx + (1-t)y \in X$ for all $x,y \in X$ and $t \in (0,1)$. Given a convex set $X \subseteq \mathbb{R}^n$, a function $f: X \to \mathbb R$ is said to be concave if $f(tx + (1-t)y) \ge tf(x) + (1-t)f(y)$ for all $x,y \in X$ and $t \in (0,1)$.

1) Show that $f: \mathbb{R}^n \to \mathbb R$ is concave iff $\sum_{i=1}^r t_if(x_i) \le f\left(\sum_{i=1}^r t_ix_i\right)$

for every positive integer r, for all $x_1, \dots, x_r \in \mathbb R^n$, and all $t_1,\dots,t_r \in (0,1)$ with $\sum_{i=1}^r t_i = 1$

2) Use (1) to show that $\prod_{i=1}^r x_i^{t_i} \le \sum_{i=1}^r t_ix_i$ for all non negative $x_1, \dots, x_r \in \mathbb R$ and all $t_1,\dots,t_r \in (0,1)$ with $\sum_{i=1}^r t_i = 1$

3) Show that the function $f: \mathbb{R}^n \to \mathbb{R}$ is convex iff the set $\{(x,r) \in \mathbb{R}^n \times \mathbb{R} \mid f(x) \le r \}$ is convex.

$\endgroup$
  • $\begingroup$ why isnt my text getting formatted? :O $\endgroup$ – Mathy Jun 21 '13 at 14:12
  • 1
    $\begingroup$ You have to put your LaTeX commands between \$ \$ $\endgroup$ – math Jun 21 '13 at 14:13
  • $\begingroup$ I followed the MathJax basic tutorial. Not even a single one is working. or do we need to add something extra to activate these formats? check \ge $\endgroup$ – Mathy Jun 21 '13 at 14:16
  • $\begingroup$ please yous \to for $\to$ and \mathbb{R} for $\mathbb{R}$ $\endgroup$ – math Jun 21 '13 at 14:20
  • $\begingroup$ Please, see my edits to your code for (1) and (2). $\endgroup$ – Nick Peterson Jun 21 '13 at 14:21
2
$\begingroup$

For part 1), try induction on $r$. For 2), think about log. For 3) think about the pairs $(x, f(x)), (y, f(y))$.

I'm being somewhat mysterious because I think these are healthy exercises to solve for oneself.

EDIT:

Hey sorry for the delay. For the first part, the second condition implies concavity so we only need to prove the first condition implies the second. For the base case, this is easy. Suppose it holds for k and pick $x_1, ..., x_k, x_{k+1} \in \mathbb{R}^n $ and $t_1, ..., t_{k+1} \in (0, 1)$ such that $\sum\limits_{i=1}^{k+1} t_i=1$. Now, let $x'_k=\frac{t_kx_k+t_{k+1}x_{k+1}}{t_k+t_{k+1}}$ and $t'_k= t_k+t_{k+1}$. Then $\sum\limits_{i=1}^{k-1} t_i + t'_k=1$ and by inductive assumption we therefore have $t'_kf(x'_k)+\sum\limits_{i=1}^{k-1} t_if(x_i)$ $ \leq f( t'_kx'_k+\sum\limits_{i=1}^{k-1} t_ix_i)=f(\sum\limits_{i=1}^{k+1} t_ix_i)$. To finish up, we need to show that $t_kf(x_k)+t_{k+1}f(x_{k+1}) \leq t'_kf(x'_k)$. Now, $0<t_k+t_{k+1}<1$ so there is some $r \in \mathbb{R}$ so that $rt_k+rt_{k+1}=1$. Then by the base case, $rt_kf(x_k)+rt_{k+1}f(x_{k+1}) \leq f(rt_kx_k+rt_{k+1}x_{k+1})=f(rt'_kx'_k)=f(x'_k)$. But by definition, $r= \frac{1}{t_k+t_{k+1}}$ and so dividing by $r$, this gives what we want.

$\endgroup$
  • $\begingroup$ thanx for your answer. I am trying it right now. As far as you being mysterious is concerned: I can give you the link, from where these questions are taken. This question was asked in an exam in the year 2004. $\endgroup$ – Mathy Jun 21 '13 at 15:20
  • $\begingroup$ Cool. Also, if anything I wrote is too vague, I can definitely clarify. $\endgroup$ – Alexander Jun 21 '13 at 15:24
  • $\begingroup$ First part: I am not able to prove it via induction. Base case: it is obvious because r=1 so $t_1f(x_1) \le f(t_1x_1)$ and $t_1$ = 1. but I got stuck when proving it for r=k+1 assuming the inequality to hold good for r=k;i.e. $t_1f(x_1) + ... +t_kf(x_k)$ + $t_{k+1}x_{k+1}$ $\le f(t_1x_1 + ... t_kx_k$ + $t_{k+1}x_{k+1}$) . how to prove this?? $\endgroup$ – Mathy Jun 21 '13 at 16:21
  • $\begingroup$ Alexander I am still waiting for you to clarify more. thanx $\endgroup$ – Mathy Jun 22 '13 at 12:15
  • $\begingroup$ Sorry, I was away from my computer for a day. I have updated my answer to give a more thorough solution to part 1. $\endgroup$ – Alexander Jun 22 '13 at 14:44

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.