Prove that the function is convex

Solution 1:

The solution follows the suggestion by Rodrigo de Azevedo.

Firstly, observe that

$$ A(v) = \dfrac{k-1}{-\displaystyle\sum_{i=1}^k \frac{1}{v_i}},$$

is composition $A(v)=h \circ g=h(g(v))$ where:

$$g(v)= -\sum_{i=1}^k \frac{1}{v_i}, $$

and

$$h(x)=\frac{k-1}{x}.$$

Now observe that $h(x)$ is a convex decreasing function on the positive reals. Moreover, its extended-value extension $\tilde{h}(x)$ is nonincreasing. Given that g(v) is concave for any $1 \leq v_i\leq k-1$, it then follows that $A(v)$ is convex.

The conclusion follows from the statement that can be found on page 84 of Boyd & Vandenberghe.


enter image description here

Solution 2:

Let $(x_1, \ldots, x_n) \in \mathbb R_{>0}^n$ and $(v_1, \ldots, v_n) \in \mathbb R_{>0}^n$. By Schwarz’ inequality $$\begin{eqnarray} \frac1{x_1}+ \ldots + \frac1{x_n} &=& \left(\frac{\sqrt{v_1}}{x_1}, \ldots, \frac{\sqrt{v_n}}{x_n} \right) \cdot \left(\frac1{\sqrt{v_1}}, \ldots, \frac1{\sqrt{v_n}} \right) \\ & \leq & \left(\frac{v_1}{x_1^2} + \ldots + \frac{v_n}{x_n^2} \right)^{\frac12} \left(\frac1{v_1} + \ldots + \frac1{v_n} \right)^{\frac12}. \end{eqnarray}$$

Rewrite this as $$\left(\frac1{v_1} + \ldots + \frac1{v_n}\right)^{-1} \leq \left(\frac{v_1}{x_1^2} + \ldots + \frac{v_n}{x_n^2}\right) \left(\frac1{x_1} + \ldots + \frac1{x_n}\right)^{-2}.$$

Now the right hand side is exactly the tangent plane of the left hand side at the point $(x_1, \ldots, x_n)$. Since this holds for any such point $(x_1, \ldots, x_n)$ the left hand side is a concave function.

Solution 3:

Let $$g(v) = \frac{1}{\sum_{i=1}^k \frac{1}{v_i}}.$$ It is known that $g(v)$ is concave on $\mathbb{R}_{> 0}^k$. This result is given in Page 116, 3.17, [1].

In general, suppose $p < 1, p\ne 0$, the function $$f(x) = \left(\sum_{i=1}^n x_i^p\right)^{1/p}$$ is concave on $\mathbb{R}_{> 0}^n$. The proof is given in the solutions manual of the book [1]. (I put that proof at the end.)

Reference:

[1] Boyd and Vandenberghe, "Convex optimization". http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf


Proof of concavity of $f(x)$:

The first derivatives of $f$ are given by $$\frac{\partial f(x)}{\partial x_i} = \left(\sum_{i=1}^n x_i^p\right)^{1/p - 1}x_i^{p - 1} = \left(\frac{f(x)}{x_i}\right)^{1 - p}, \quad \forall i.$$ The second derivatives are $$\frac{\partial^2 f(x)}{\partial x_i \partial x_j} = \frac{1 - p}{x_i}\left(\frac{f(x)}{x_i}\right)^{ - p} \left(\frac{f(x)}{x_j}\right)^{1 - p} = \frac{1 - p}{f(x)}\left(\frac{f(x)^2}{x_ix_j}\right)^{1 - p}, \quad i\ne j,$$ and $$\frac{\partial^2 f(x)}{\partial x_i^2} = \frac{1 - p}{f(x)}\left(\frac{f(x)^2}{x_i^2}\right)^{1 - p} - \frac{1 - p}{x_i}\left(\frac{f(x)}{x_i}\right)^{1 - p}.$$ It suffices to prove that, for all $y \in \mathbb{R}^n$, $$y^\mathsf{T}\nabla^2 f(x) y = \frac{1 - p}{f(x)} \left[\left(\sum_{i=1}^n \frac{y_i f(x)^{1 - p}}{x_i^{1 - p}}\right)^2 - \sum_{i=1}^n \frac{y_i^2f(x)^{2 - p}}{x_i^{2 - p}}\right] \le 0.$$ This follows by applying the Cauchy-Bunyakovsky-Schwarz inequality $(a^\mathsf{T}b)^2 \le \|a\|_2^2\|b\|_2^2$ with $$a_i = \left(\frac{f(x)}{x_i}\right)^{-p/2}, \quad b_i = y_i \left(\frac{f(x)}{x_i}\right)^{1 - p/2},$$ and noting that $\sum_{i=1}^n a_i^2 = 1$.

We are done.