0
$\begingroup$

Let $p_i \in [0,1], 1 \leq i \leq n$ so that $p_1+p_2 +...+p_n=1$.

Define $f(p)= \sum_{j \neq i}p_ip_j=1-\sum_{i}p_i^2$. Prove that $f(p)$ is concave.


My effort:

Let $a,b \geq 0, a+b=1$. I try to show that $f(ap+bp') \geq af(p)+bf(p')$.

Then:

$$f(ap+bp')= \sum_{j \neq i}(ap_i+bp'_i)(ap_j+bp'_j) = \sum_{j \neq i}(a^2p_ip_j+b^2p'_ip'_j+abp_ip'_j+abp'_ip_j)$$

$$ = a^2f(p)+b^2f(p')+ab\sum_{j \neq i}(p_ip'_j+p'_ip_j)$$

But I don't know where to go from here...

Thanks!

$\endgroup$
  • $\begingroup$ Did you try to form the second derivative of $f(tp+(1-t)p')$? I haven't tried it myself, so I don't know if it gets you anywhere, but it could be wroth a try. $\endgroup$ – Harald Hanche-Olsen Jan 11 '14 at 11:01
0
$\begingroup$

I think maybe you know this theorem. just for reminding you can use this one: A continuously differentiable function $f:D\subset\mathbb{R^{n}} \rightarrow \mathbb{R} $ is concave if and only if $f(y)- f(x) <= Df(x)(y-x)$ for $x,y\in D$.

i.e. that is , $f(y)- f(x)<=$ $ \dfrac{\partial f}{\partial x_{1}}(x)(y_{1}-x_{1})+...+\dfrac{\partial f}{\partial x_{n}}(x)(y_{n}-x_{n}) $

$\endgroup$
0
$\begingroup$

Write your function as $$ f(p) = \sum_{j \not=i} p_i p_j = (\sum p_i)^2 - \sum p_i^2. $$ Then the gradient vector becomes $$ 2(\sum_{j\not =1}p_j, \sum_{j\not=2}p_j, \dots, \sum_{j\not=n}p_j) $$ and the Hessian matrix becomes $$ 2 \begin{pmatrix} 0 & 1 & 1 &\dots 1 \\ 1 & 0 & 1 &\dots 1 \\ \vdots \\ 1 & 1 & 1 \dots 0 \\ \end{pmatrix} = 2H $$ Note that $H$ has one eigenvalue $n-1$ with eigenvector the vector with all component equal to 1, the rest of the eigenvalues is negative. So the function cannot be neither convex nor concave: It has a saddle point. This becomes clear in the case $n=2$ where the function is $f(x,y)=xy$. EDIT sorry, I didnt see your condition that $\sum p_i =1$! That condition annihilates the eigenspace with a positive eigenvalue, so then the function clearly becomes convex. But the expression you give:$ f(p) = 1 - \sum p_i^2$, the second term is the negative of a convex function, which gives the result immediately.

$\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.