# Linear programming convexity

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}

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.

• 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) – Marco Lübbecke May 16 at 16:22
• Yes you are right I got mixed up ! Thanks @Marco Lübbecke! fixed it. – Kuifje May 16 at 16:27

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