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

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?

Solution 1:

Because of the specific way you asked your question, I do consider the other answers provided to be incorrect.

Given a set of equations and inequalities on $x\in\mathbb{R}^n$: $$\begin{array}{ll} h_i(x) = 0 & i=1,2,\dots,M \\ g_j(x) \leq 0 & j=1,2,\dots, N \end{array}$$ As you correctly state, if the equality constraint functions $h_i$ are affine, and the inequality constraint functions $g_j$ are convex, then the feasible region---the set of points that satisfy these constraints---is convex.

But this is a one way implication. It is not necessarily the case that non-affine $h_i$ or non-convex $g_j$ result in a non-convex feasible region. And no, not all examples are contrived.

The notion of quasiconvexity is important here. It offers us a more relaxed set of conditions: if the equality constraint functions $h_i$ are quasilinear, and the inequality constraint functions are quasiconvex, then the feasible region is convex. There are plenty of genuinely useful quasiconvex, quasiconcave, and quasilinear functions out there.

Even that isn't as relaxed as it can be. For instance, quasiconvexity requires that all of the sublevel sets $\{x\,|\,g_j(x)\leq\alpha\}$ are convex. But for the specific case we're considering, we only care about $\alpha=0$. Still, at this point, I'd suggest that relaxing the class of functions even further gets you into the realm of manufactured/contrived cases.

Having said all this: in practice, we define a convex optimization problem as one having only affine equality constraint functions and convex inequality constraint functions. Doing so is necessary both to assist in analysis/proofmaking and building computational methods. Even if you have quasiconvexity/quasilinearity, ultimately you will have to find an equivalent set of constraints that satisfy the stricter condition if you wish to solve the model.

Solution 2:

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