3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What about $h(x,y)=(x-2y)^2$? $\endgroup$ – Michael Grant Jan 15 '18 at 6:03
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ I'll ask you the same question I asked Redeldio below: what if $h(x,y)=(x-2y)^2$? It is not necessary for $h(x)$ to be affine for the equality constraint $h(x)=0$ to describe a convex set. The same is true for inequality constraints: it is not necessary for $g(x)$ to be convex for $g(x)\leq 0$ to describe a convex set---consider, for instance, $\sqrt{|x|}-1$. $\endgroup$ – Michael Grant Jan 15 '18 at 6:06
  • $\begingroup$ You have to consider always irreducible constraints. In your example, $(x-2y) = 0$ can be readily reduced to $x-2y = 0$, which is an affine function. The same holds for inequality constraints. $\endgroup$ – TheDon Jan 15 '18 at 9:36
  • 2
    $\begingroup$ Yes, but the OP is asking if the constraint function must be affine for the constraint set to be convex, so the answer is no. Here’s another: $\lceil x \rceil = 1$. $\endgroup$ – Michael Grant Jan 15 '18 at 13:31
  • $\begingroup$ Of course a convex constraint see can be described by a set of linear equations and nonlinear inequalities. But thats a one way implication. $\endgroup$ – Michael Grant Jan 15 '18 at 13:33
  • $\begingroup$ In fact, it is sufficient for $h_i$ to be quasilinear and $g_j$ to be quasicomvex, but even that is not necessary. $\endgroup$ – Michael Grant Jan 15 '18 at 13:41

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.