3
$\begingroup$

Prove convexity of $$f(x_1,x_2,x_3)=\frac{x_1^2+x_1+1}{x_2+x_3}$$ over $\{(x_1,x_2,x_3) : x_2,x_3\gt0\}$

I am looking for an easy (or relatively easy) way to show $f$ is convex. I tried to split the function into: $$\frac{x_1^2}{x_2+x_3}+\frac{1}{x_2+x_3}+\frac{x_1}{x_2+x_3}$$ The first and the second functions are convex:

  • The first is convex because it's quadratic-over-linear which is convex;
  • The second is convex because it's linear change of variables of $\frac{1}{x}$ which is convex over $x>0$.

I stuck proving the third one. I found it's Hessian matrix. Let $g(x)=\frac{x_1}{x_2+x_3}$.

$$\nabla ^2g(x)= \begin{bmatrix} 0 & \frac{-1}{(x_2+x_3)^2} & \frac{-1}{(x_2+x_3)^2} \\ \frac{-1}{(x_2+x_3)^2} & \frac{2x_1}{(x_2+x_3)^3} & \frac{2x_1}{(x_2+x_3)^3} \\ \frac{-1}{(x_2+x_3)^2} & \frac{2x_1}{(x_2+x_3)^3} & \frac{2x_1}{(x_2+x_3)^3} \end{bmatrix} $$

It suffices to show $\nabla g(x)\succeq0$, but I failed to do so. Last hope is calculating eigenvalues, but it seems too difficult. By the way, I can't use level-sets. Maybe there's an eaier way to show its convexity.

Please advise.

Thank you.

$\endgroup$
2
  • 1
    $\begingroup$ Maybe you can write $x_1^2+x_1+1=(x_1+1/2)^2+3/4$, and split it this way to get rid of the problematic $x_1$ term. $\endgroup$
    – Momo
    May 8, 2021 at 20:28
  • $\begingroup$ @Momo Yes! Then it's just affine change of variables over quad-over-linear $\frac{x_1^2}{x_2}$ which is convex! Thank you! $\endgroup$
    – Dennis
    May 8, 2021 at 20:39

2 Answers 2

2
$\begingroup$

Here is an easy approach:

We need that $g(x,y) = x^2/y$ is convex on $\mathbb R \times \mathbb R^+$, this follows e.g. from the theory of the 'perspective function'.

Then, we write \begin{align*} f(x_1, x_2, x_3) &= \frac{(x_1+1/2)^2 + 3/4}{x_2 + x_3} \\&= g(x_1 + 1/2, x_2 + x_3) + \frac{3/4}{x_2 + x_3}. \end{align*} Now, convexity follows easily.

$\endgroup$
1
$\begingroup$

$g$ is not convex, as $(2,2)$-entry of $\nabla^2 g(x)$ is negative when $x_1$ is negative.

We have $\nabla f(x) = \begin{bmatrix} \frac{2x_1+1}{x_2+x_3} \\ - \frac{x_1^2+x_1+1}{(x_2+x_3)^2} \\ - \frac{x_1^2+x_1+1}{(x_2+x_3)^2}\end{bmatrix}$.

$$\nabla^2 f(x) = \begin{bmatrix} \frac{2}{x_2+x_3} & - \frac{2x_1+1}{(x_2+x_3)^2} & - \frac{2x_1+1}{(x_2+x_3)^2} \\ - \frac{2x_1+1}{(x_2+x_3)^2} & \frac{2(x_1^2+x_1+1)}{(x_2+x_3)^3} & \frac{2(x_1^2+x_1+1)}{(x_2+x_3)^3}\\ - \frac{2x_1+1}{(x_2+x_3)^2} & \frac{2(x_1^2+x_1+1)}{(x_2+x_3)^3} & \frac{2(x_1^2+x_1+1)}{(x_2+x_3)^3}\end{bmatrix}$$

One possible way to check positive semidefiniteness is by examine the determinant of each principal minor is nonnegative.

Since the second row and the third row is identitcal, the determinant is $0$. Also $|a_{23}|=0$.

Notice that $|a_{11}|>0$. Since $x_1^2+x_1+1 \ge \frac34> 0$, we have $|a_{22}|=|a_{33}|>0$.

$$|a_{12}|=|a_{13}|=\frac1{(x_2+x_3)^4}[4(x_1^2+x_1+1)-(2x_1+1)^2]=\frac{3}{(x_2+x_3)^4}>0.$$

Hence, it is convex.

$\endgroup$
5
  • $\begingroup$ You are right, the third-degree in the Hessian was a typo. I know that positive principal minors imply positive definiteness, but I am not sure it works for positive semi-definiteness (with non-negative minors). Are you sure about that? Thank you for the detailed answer. $\endgroup$
    – Dennis
    May 9, 2021 at 9:25
  • $\begingroup$ I checked a little bit and it seems that for telling anything about positive semi-definiteness, all the minors need to be nonnegative (and not only the principal minors). $\endgroup$
    – Dennis
    May 9, 2021 at 10:11
  • 1
    $\begingroup$ Refers to theorem $6$ in here. To check for positive definiteness, we check for all positive leading principal minors. To check for positive semidefiniteness, we check for all nonnegative principal minors. $\endgroup$ May 9, 2021 at 10:31
  • $\begingroup$ Thank you very much! $\endgroup$
    – Dennis
    May 9, 2021 at 20:37
  • $\begingroup$ Perhaps the first $n-1$ leading principal minors being positive and the determinant being nonnegative are enough to guarantee positive semidefiniteness. I don't know. $\endgroup$ Feb 25 at 1:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .