Convex optimization problem has to include only convex constraint functions?

Question

It is well-known that convex optimization problem is defined as a problem of minimizing convex function (or maximizing concave function) over a convex feasible set which is usually written as (in standard form)

$\min_x \; f(x)$

s.t. $g_i(x) \leq 0, \; i = 1, \cdots, m$

where $f(x)$ is convex, and $g_i(x)$ is convex. Here, I wonder if $g_i(x)$ should be always convex for convex optimization problems. For instance, only quasi-convexity of $g_i(x)$ seems to be sufficient for generating convex set.

For example, consider an optimization problem

$\min_{x \geq 0} \; x^2$

s.t. $ \sqrt{x} \leq 2$

It can be seen that $\sqrt{x}$ is not convex, but the feasible set of above problem is convex. Is the above problem convex or not? Also, can I apply standard convex optimization techniques such as KKT conditions or duality to find its global optimal solution?

Answer 1

A problem of minimizing convex function over a convex feasible set always can be rewritten into such standard form.

The problem \begin{equation} \begin{array}{cl} {\min_{x \ge 0}} & {x^2} \\ {\text{s.t.}} & {\sqrt{x} \leq 2} \end{array} \end{equation} is actually a convex optimization problem. And we can reformulate it into standard form \begin{equation} \begin{array}{cl} {\min_{x \ge 0}} & {x^2} \\ {\text{s.t.}} & {x^2 \leq 4} \end{array} \end{equation}

Convex optimization techniques often study standard form. For example, the KKT conditions actually can be applied as necessary property of optimal solution even though the problem is non-convex. However, if the $f$ and $g_i$ in KKT conditions are convex, the dual gap of optimal solution will be zero. One can refer to Boyd's book ``Convex Optimization'' (Page 244) for more details.