Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
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.$$
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).
