0
$\begingroup$

From Boyd & Vandenburghe, Convex Optimization Problem 3.16(c):

Determine if $f(x_1,x_2) = \frac{1}{x_1x_2}$ is convex, quasiconvex, concave, or quasiconcave on $\mathbb{R}^2_{++}$.

From this post Determining whether $\alpha$ sublevel sets are convex I tried to plot it with mesh in Matlab, and I think it is convex on $\mathbb{R}^2_{++}$. But I'm stuck trying to prove it with the definition. My current attempt:

We have for $(x_1, y_1) \in \mathbb{R}^2_{++}$ and $(x_2, y_2) \in \mathbb{R}^2_{++}$, i.e., $x_1, x_2, y_1, y_2 > 0$, and $0 \leq \theta \leq 1$, \begin{align*} f\left(\theta(x_1,y_1) + (1-\theta)(x_2,y_2)\right) &= f\left(\theta x_1 + (1-\theta)x_2, \theta y_1 + (1-\theta)y_2\right) \\ &= \frac{1}{(\theta x_1 + (1-\theta)x_2)(\theta y_1 + (1-\theta)y_2)} \\ &= \frac{1}{\theta^2 x_1y_1 + \theta(1-\theta)(x_1y_2 + x_2y_1) + (1-\theta)^2x_2y_2} \\ &< \frac{1}{\theta^2 x_1y_1 + (1-\theta)^2x_2y_2} \\ \end{align*} I know ultimately I need to show that $\frac{1}{\theta^2 x_1y_1 + (1-\theta)^2x_2y_2} \leq \frac{\theta}{x_1y_1} + \frac{1-\theta}{x_2y_2}$, but I'm not sure how to proceed or whether my approach is wrong. I don't think partial fraction expansion strategy applies here because we have different variables. Any hints?

$\endgroup$
4
  • 1
    $\begingroup$ Compute the Hessian, and show that it is positive semi-definite will be helpful, since your function is $C^2(\mathbb{R}^2_{++})$. Using definition directly is not quite straightful sometimes in terms of computing. $\endgroup$
    – Mike
    Oct 6 '20 at 4:49
  • 1
    $\begingroup$ If you do not use Hessian, proceeding along your approach, you may prove that $\frac{1}{\theta^2 x_1y_1 + \theta(1-\theta)(x_1y_2 + x_2y_1) + (1-\theta)^2x_2y_2} \le \frac{\theta}{x_1y_1} + \frac{1-\theta}{x_2y_2}$. After some manipulation, blablabla; By the way, $\frac{1}{\theta^2 x_1y_1 + (1-\theta)^2x_2y_2} \leq \frac{\theta}{x_1y_1} + \frac{1-\theta}{x_2y_2}$ is incorrect. $\endgroup$
    – River Li
    Oct 6 '20 at 4:50
  • $\begingroup$ I'm curious what those manipulation steps are... could you elaborate? Although I think I'll go with the Hessian condition approach, it looks cleaner. $\endgroup$
    – user594147
    Oct 6 '20 at 4:55
  • 1
    $\begingroup$ @user594147 Sure. I posted it as an answer. $\endgroup$
    – River Li
    Oct 6 '20 at 7:18
2
$\begingroup$

To show that it is convex, it would be easier if you show that the Hesian of the function is positive semi-definite.

In fact, the hessian is $$\begin{bmatrix} {2 \over x_1^3 x_2} & {1 \over x_1^2 x_2^2} \\ {1 \over x_1^2x_2^2} & {2 \over x_1 x_3^3} \end{bmatrix}$$

The matrix and all of its principal submatrices are positive semi-definite, so it is convex, hence quasiconvex as well.

Or you can show PSD by showing $z^T H z \ge 0$, and we get $$ {2 \over x_1^3 x_2}z_1^2 + {1 \over x_1^2 x_2^2}z_2z_1 {1 \over x_1^2x_2^2}z_1z_2 + {2 \over x_1 x_3^3}z_2^2 \ge 0$$ The above is non-negative since you can complete the square.

$\endgroup$
7
  • $\begingroup$ I'm not familiar with the "all principal submatrices are positive semi-definite so the matrix is positive semi-definite" theorem... I know the other direction is true by setting the corresponding entries of the vectors to 0. Is the proof similar? $\endgroup$
    – user594147
    Oct 6 '20 at 5:07
  • $\begingroup$ Also, not sure if that is actually the case since $\begin{bmatrix}0 & 1\\ 1 & 0\end{bmatrix}$ is clearly indefinite, but its principal submatrices (the $0$ entries, unless I mistook what the principal submatrix means) are technically PSD. $\endgroup$
    – user594147
    Oct 6 '20 at 5:14
  • $\begingroup$ @user594147 I'm not sure what you mean by setting entries to 0. You can show it's positive semi definite by showing that $z^THz \ge 0$ for all $z$, where $H$ is the hessian. Since all entries in your hessian are positive, it is positive semi-definite. $\endgroup$
    – MoneyBall
    Oct 6 '20 at 5:15
  • $\begingroup$ @user594147 $\begin{bmatrix}0 & 1 \\ 1 & 0 \end{bmatrix}$ is not PSD. The matrix has a negative determinant. $\endgroup$
    – MoneyBall
    Oct 6 '20 at 5:16
  • $\begingroup$ Sorry, I meant setting the entries of vector $z$ to be 0 like from this post math.stackexchange.com/questions/1221790/… $\endgroup$
    – user594147
    Oct 6 '20 at 5:16
1
$\begingroup$

Besides using Hessian, there are several approaches:

  1. We have $\frac{1}{x_1x_2} = \mathrm{e}^{-\ln x_1 - \ln x_2}$. Recall that if $g$ is convex, then $\mathrm{e}^g$ is also convex. Since $-\ln x_1 - \ln x_2$ is convex, $\mathrm{e}^{-\ln x_1 - \ln x_2}$ is convex. We are done.

  2. Proceeding along your approach

Let us prove that $$\frac{1}{\theta^2 x_1y_1 + \theta(1-\theta)(x_1y_2 + x_2y_1) + (1-\theta)^2x_2y_2} \le \frac{\theta}{x_1y_1} + \frac{1-\theta}{x_2y_2}.$$ We have \begin{align} &\theta^2 x_1y_1 + \theta(1-\theta)(x_1y_2 + x_2y_1) + (1-\theta)^2x_2y_2\\ =\ & \theta x_1y_1 + (1-\theta)x_2y_2 + \theta(1-\theta)(x_1y_2 + x_2y_1 - x_1y_1-x_2y_2) \end{align} and $$(\theta x_1y_1 + (1-\theta)x_2y_2) \left(\frac{\theta}{x_1y_1} + \frac{1-\theta}{x_2y_2}\right) = 1 + \theta(1-\theta)\left(\frac{x_2y_2}{x_1y_1} + \frac{x_1y_1}{x_2y_2} - 2\right).$$ Thus, it suffices to prove that \begin{align} 1 &\le 1 + \theta(1-\theta)\left(\frac{x_2y_2}{x_1y_1} + \frac{x_1y_1}{x_2y_2} - 2\right)\\ &\qquad + \theta(1-\theta)(x_1y_2 + x_2y_1 - x_1y_1-x_2y_2)\left(\frac{\theta}{x_1y_1} + \frac{1-\theta}{x_2y_2}\right) . \end{align} It suffices to prove that $$0 \le \left(\frac{x_2y_2}{x_1y_1} + \frac{x_1y_1}{x_2y_2} - 2\right) + (x_1y_2 + x_2y_1 - x_1y_1-x_2y_2)\left(\frac{\theta}{x_1y_1} + \frac{1-\theta}{x_2y_2}\right)$$ which is written as \begin{align} 0&\le \left(\frac{x_2y_2}{x_1y_1} + \frac{x_1y_1}{x_2y_2} - 2 + (x_1y_2 + x_2y_1 - x_1y_1-x_2y_2)\frac{1}{x_1y_1}\right)\theta\\ &\qquad +\left(\frac{x_2y_2}{x_1y_1} + \frac{x_1y_1}{x_2y_2} - 2 + (x_1y_2 + x_2y_1 - x_1y_1-x_2y_2)\frac{1}{x_2y_2}\right)(1-\theta)\\ &= \left(\frac{x_1y_1}{x_2y_2} + \frac{y_2}{y_1} + \frac{x_2}{x_1} - 3\right)\theta + \left(\frac{x_2y_2}{x_1y_1} + \frac{x_1}{x_2} + \frac{y_1}{y_2} - 3\right)(1-\theta). \end{align} It is true by AM-GM. We are done.

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