Prove that the function is convex

Question

_{Question is reopened due to the problem found in the original solution.}

---

I have the following function:

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

where $k\geq 2$ is some integer constant and $1 \leq v_i \leq k-1$.

I am trying to prove that the function $A(v)$ is convex. According to Wolfram's FunctionConvexity, it is. Therefore, the function is somehow passes the following condition:

$$ f(t x +(1-t)y)\leq t f(x)+(1-t)f(y) ,$$

where $0\leq t\leq 1.$

However, when I have tried to prove this inequality myself I have bumped into a very messy inequality, which looks intractable to me. I have also tried to prove the positive semidefiniteness of the Hessian matrix following Sylvester's criterion, but it seems that the last leading principal minor equals zero. How could I approach this problem?

---

Update 1: I reopen the question due to the problem found in the solution. The proposed solution is possibly wrong. $h$ is convex decreasing on positive reals, but $g$ assumes negative real values. I am not sure how to resolve it.

Update 2: Here you can find additional information on how FunctionConvexity works. It was well explained in the first answer.

Answer 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.

---

Answer 2

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.

Answer 3

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.

Answer 4

Consider the Hessian matrix of $D(v)$:

$$ H= \begin{bmatrix} \frac{\partial^2 D(v)}{\partial v_1^2} & \frac{\partial^2 D(v)}{\partial v_1 \partial v_2}& \dots & \frac{\partial^2 D(v)}{\partial v_1 \partial v_k} \\ \frac{\partial^2 D(v)}{\partial v_2 \partial v_1}&\frac{\partial^2 D(v)}{\partial v_2^2} & \dots & \frac{\partial^2 D(v)}{\partial v_2 \partial v_k} \\ \vdots & \vdots & \ddots & \vdots\\ \frac{\partial^2 D(v)}{\partial v_k \partial v_1} & \frac{\partial^2 D(v)}{\partial v_k \partial v_2} & \dots & \frac{\partial^2 D(v)}{\partial v_k^2} \end{bmatrix} $$ Observe that the diagonal of the matrix consists of positive elements of the form: $$\frac{ \partial^2 D(v)}{\partial v_i^2} = \frac{2 \left(k-1 \right) \prod^k_{j\neq i}v_i^2 \left( \sum_{j \in (1,k]} \prod_{p\neq j} v_p \right) }{\left( \sum^k_{j=1} \prod_{i\neq j}^k v_i \right)^3 }.$$

Off-diagonal elements are represented by negative mixed partial derivatives of the form: $$ \frac{ \partial^2 D(v)}{\partial v_i \partial v_j} =-\frac{2 \left(k-1 \right) v_i^2 v_j^2 \prod_{p=1}^k v_i }{\left( \sum^k_{j=1} \prod_{i\neq j}^k v_i \right)^3 }. $$

Now, the first leading principal minor is:

$$ \Delta_1 = \frac{2 \left(k-1 \right) \prod_{j\neq 1}^k v_j^2 \left( \sum_{j \in (1,k]} \prod_{p\neq j} v_p \right) }{\left( \sum^k_{j=1} \prod_{i\neq j}^k v_i \right)^3 } > 0. $$

The second leading principal is:

$$ \Delta_2 =\Delta_1 \frac{2(k-1)\prod_{j\neq 2}^k v_j^2 \left( \sum_{j \in (2,k]} \prod_{p\neq j} v_p \right)}{ \left( \sum^k_{j=1} \prod_{i\neq j}^k v_j \right)^2 \left( \sum_{j \in (1,k]} \prod_{p\neq j} v_p \right) } >0 .$$

Assume that $m<k$ leading principal minor $\Delta_m>0$. Now I verify that $\Delta_{m+1}$ is also positive:

\begin{equation} \label{m plus one} \Delta_{m+1} = \Delta_m \frac{2(k-1)\prod_{j\neq m}^k v_j^2 \left( \overbrace{\sum_{j \in (m+1,k]} \prod_{p\neq j} v_p }^{n_1}\right)}{ \left( \sum^k_{j=1} \prod_{i\neq j}^k v_j \right)^2 \left( \sum_{j \in (m,k]} \prod_{p\neq j} v_p \right) }>0, \end{equation}

which is always positive too.

Therefore, the first $m<k$ leading principal minors are positive by induction.

Also observe that term in $\Delta_{m+1}$ term $ n_1=0$ if $m+1=k$ and the last leading principal minor is $\Delta_k=0$.

Given that matrix, $H$ enjoys leading implies all (LIA) properties and all leading principal minors are positive, it immediately follows that $H$ is positive semi-definite and $D(v)$ is convex.