3
$\begingroup$

I am trying to prove that the following optimization problem is convex.

$$\begin{array}{ll} \text{minimize} & x_1 x_2^2\\ \text{subject to} & x_1=x_2\\ & x_1\geq 0\end{array}$$

I calculated the Hessian matrix

$$H = 2 \begin{bmatrix} 0 & x_2 \\ x_2 & x_1 \end{bmatrix}$$

It must be positive semidefinite over the whole domain for it to be a convex, as least that's what I know, but it's not positive semidefinite. For instance for $x_1=x_2=1$,

$$\det(H)=-4$$

so it's not positive semidefinite and it's not convex. I can't find what I am doing wrong.

$\endgroup$
  • $\begingroup$ You can see that the restriction of $f$ to $\Omega$ is convex by visualizing its graph. This is an interesting example. Suppose that $f:\mathbb R^n \to \mathbb R$ is twice continuously differentiable. If $U$ is a convex set that is open and the restriction of $f$ to $U$ is convex, then the Hessian of $f$ is guaranteed to be positive semidefinite at all points in $U$. However, if $U$ is a convex set that is not open and the restriction of $f$ to $U$ is convex, then the Hessian $\nabla^2 f(x)$ is not guaranteed to be positive semidefinite for all $x \in U$. $\endgroup$ – littleO May 31 '17 at 11:51
  • $\begingroup$ So if I correctly understand, then this example is convex but its Hessian isn't semi-positive. How can I visually show that it's convex? I mean which graph I should have, x1 vs f(x), x2 vs f(x) or how? I couldn't understand. Also if do it for $f(x)=x^{3}$ over the same domain, which is practically same with the previous one, it's obvious that it's convex. I just couldn't find the way. $\endgroup$ – atrlrgn May 31 '17 at 13:16
  • $\begingroup$ Are you sure this problem is even convex? The objective function is non-convex, though its restriction to $\Omega$ is indeed convex. $\endgroup$ – Rodrigo de Azevedo May 31 '17 at 14:15
  • $\begingroup$ Well, I am not sure. I am trying to solve a problem and it says show that the optimization problem is convex, so I assume it's convex. Also I explained in the previous comment that it's $f(x)=x^3$, and it's convex. So I expect it to be convex, however, I have no idea if it's a legit approach or not. I mean I'm quite inexperienced in this topic, just saying. $\endgroup$ – atrlrgn May 31 '17 at 14:35
  • 1
    $\begingroup$ Well, let me revise. This is not a convex optimization problem as written, as the objective function is not convex. However, if you eliminate one of the variables using the equality constraint, and then you make the inequality "implicit" in the objective function, you get something convex. $\endgroup$ – Michael Grant Jun 4 '17 at 4:10
0
$\begingroup$

An equivalent problem is $$ \underset{x}{\text{minimize}}\quad x^3\\ \text{subject to}\quad x\geq0 $$ The Hessian for this problem is $H=\frac{\partial^2 x^3}{\partial x^2}=6x$, which is $H\geq 0$ for all $x\geq 0$.

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