4
$\begingroup$

Is it possible for a linear programming model to be non-convex ? If it is, please, provide a simple 2 variables example and explain why it is non-convex.

EDIT 1: I have been wondering, maybe the following constraints are non-convex: \begin{align}x+y&\ge3\\0.5x+y&\le3.\end{align}

$\endgroup$
8
$\begingroup$

A linear problem is always convex, because anything linear is convex.

As pointed out by @Marco Lübbecke, any linear function is also concave. But polygons (feasible sets of linear programs) are only convex (and not concave).

Check out this link, it is well explained, or this one for an algeabraic proof.

Your example has only one feasible point (assuming $x$ and $y$ are positive) : $(0,3)$. I suspect you were maybe thinking of an example such as $y\le 1$ OR $y\ge 2$. This indeed is not convex. Both constraints are linear, but the OR operations kills the convexity.

| improve this answer | |
$\endgroup$
  • $\begingroup$ if you talk about the feasible set, it is convex, yes, but it is not concave (you probably refer to linear functions, which are both, convex and concave) $\endgroup$ – Marco Lübbecke May 16 at 16:22
  • 1
    $\begingroup$ Yes you are right I got mixed up ! Thanks @Marco Lübbecke! fixed it. $\endgroup$ – Kuifje May 16 at 16:27
7
$\begingroup$

No, linear programming is convex, which you can prove directly from the definition. If $A x \le b$ and $A y \le b$, then for arbitrary $\alpha\in[0,1]$, we have $$A (\alpha x+(1-\alpha)y) = \alpha A x+(1-\alpha)Ay \le \alpha b+(1-\alpha)b = b.$$

| improve this answer | |
$\endgroup$
3
$\begingroup$

The others have already given nice answers, but perhaps you posted your edit after their answers, so I'd like to address that. Your constraints are still convex. To see this, first note that any halfspace is convex; next, note that the intersection of any two convex sets is also convex. Since your feasible set is made up of the intersection of two halfspaces (each of your inequalities represents a halfspace regardless of the direction of the inquality), the overall set is also convex. See Boyd and Vandenberghe's textbook, Chapter 2, for more details (the pdf is available for free online).

| improve this answer | |
$\endgroup$

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.