In convex optimization, must equality constraints be linear or affine?

8.4k Views Asked by At

In convex optimization, the feasible region is convex if equality constraints $h(x)$ are linear or affine, and inequality constraints $g(x) \leq 0$ are convex. Does this mean that if $h(x)$ is nonlinear, then the optimization problem is non-convex? Is there any special case where $h(x)$ is nonlinear and the feasible region is still convex?

2

There are 2 best solutions below

1
On

If the equality constraints are nonlinear the feasible region is not a convex set (even if the non-linear equality constraints are convex functions). Consider for example $h(x, y)=\left(x-\frac{3}{2}\right)^2+(y-5)^2=10$,$\ \ \ $$g_1(x, y)=2x^2+3y^2\leq 35$,$\ \ \ $ $g_2(x, y), g_3(x, y)\geq0$.

5
On

You can see the equality constraint $h(x)=0$ as two inequality constraints, i.e., $h(x) \leq 0$ and $h(x) \geq 0$. If $h$ is not linear, then there is no way for both $h(x) \leq 0$ and $h(x) \geq 0$ to be convex and, therefore, the problem is always non-convex. See also [Boyd, Ch. 2.1].