1
$\begingroup$

Is the following problem convex?

$$\begin{array}{ll} \text{minimize} & x+y^2\\ \text{subject to} & x + y \leq 2\\ & \frac{x+y^2}{x^2+2} \leq 3\\ & x^2 = 1\end{array}$$

The problem is, in fact, not convex, but I'm having problems showing that the constraint $$\frac{x+y^2}{x^2+2} \leq3$$ is not convex. Is there a way to do so without calculating the Hessian?

$\endgroup$
  • $\begingroup$ Why not pick the 3rd constraint, which is clearly non-convex? $\endgroup$ – Rodrigo de Azevedo Apr 30 '18 at 10:30
1
$\begingroup$

$$\frac{x+y^2}{x^2+2}\le 3$$

$$y^2 \le 3x^2-x+6$$

Hence if $y$ is fixed, and $x$ is large enough in magnitude, then this construct will be satisfied.

Let $y=3$, then $(2,3)$ and $(-2,3)$ both satisfies the inequality, but $(0,3)$ doesn't.

Remark:

For this question, we know that $x=1$ or $x=-1$.

If $x=1$, $y \le 1$ and $y^2 \le 8$, hence $-\sqrt{8} \le y \le 1.$

If $x=-1$, $y \le 3$ and $y^2 \le 10$, hence $-\sqrt{10} \le y \le 3.$

In particular $(1,0)$ and $(-1,0)$ are both feasible but $(0,0)$ is not feasible.

$\endgroup$
0
$\begingroup$

The curve $x+y^2 = 3 (x^2 + 2)$ is a hyperbola; $x+y^2 \ge 3 (x^2 + 2)$ is the region between the two branches, so is obviously not convex. More explicitly, for $y=-3$, your second constraint says $x \le (1-\sqrt{37})/6$ or $x \ge (1+\sqrt{37})/6$.

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