Why is this QCQP non-convex?

Question

Why is the following QCQP non-convex?

$$\begin{array}{ll} \underset{x,y \in \Bbb R}{\text{minimize}} & (x+2)^2 + (y+2)^2\\ \text{subject to} & x y \ge 4\\ & x \le 4\\ & y \ge 2\end{array}$$

The objective function is convex and the set of feasible solutions is also convex (follows from the graph).

Answer 1

The problem is not convex because it is not written as $\min \{ f(x) : g_i(x) \leq 0, i=1,2,\ldots,m \}$ where $f$ and $g_i$ are convex functions.

The feasible region is convex as you point out. You can obtain a convex formulation by applying a logarithmic transformation to the nonconvex constraint: $\log x + \log y \geq \log 4$. This constraint implicitly restricts $x$ and $y$ to positive reals, which looking at the other constraints does not reduce the feasible region.

Answer 2

Obviously, the objective function and the last two constraints are convex (quadratic, linear, linear respectively). If we look at the first constraint and transform it into the standard form as $-xy+4\leq0.$

The Hessian is

$\begin{bmatrix}0 & -1\\-1 & 0\end{bmatrix},$

which gives eigenvalues of -1 and 1, thus the Hessian is not positive semi-definite and the constraint is not convex. Combining all these facts, the optimization problem is not convex.

Answer 3

I agree with you that a convex optimization problem is an optimization problem in which the objective function is a convex function and the feasible set is a convex set (https://en.wikipedia.org/wiki/Convex_optimization). The point is that this convex problem is not in standard form. We may express this convex problem in standard form as follows: \begin{align*} &\min_{x, y \in \mathbb{R}} ~ (x + 2)^2 + (y + 2)^2\\ &\mathrm{s.t.} \quad 0 \le x \le 4,\\ &\qquad\,\, y \ge 2,\\ &\qquad \sqrt{xy} \ge 2. \end{align*} Note: We did not change the feasible set.