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?


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.


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.