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) May 16, 2020 at 16:22
• Yes you are right I got mixed up ! Thanks @Marco Lübbecke! fixed it. May 16, 2020 at 16:27
• This answer is wrong as it failed to specify problem domain. Integer programs or which integer linear programming is a subset introduce non convexity. As the blanket term linear programming includes integer cases and no qualification specifying continuous domain was made, it is safe to assume the answer is unsound without clarification Jan 8 at 0:06

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

• Wrong. Integer linear programming is non convex and therefore to say something broadly about a superset of ILP and giving a proof where variable domains are neglected is insufficient. Jan 8 at 0:08
• @GregoryMorse The question is about LP, not ILP. Jan 8 at 1:48
• ILP (Integer Linear Programming) is a subset of LP (Linear Programming). Integer Linear Programming is a specific case of linear programming where the decision variables are required to take on integer values. This adds an additional level of complexity to the optimization problem, as the solutions must satisfy both linear constraints and the requirement that the decision variables are integers. In summary, all Integer Linear Programming problems can be considered as Linear Programming problems, but not all Linear Programming problems are Integer Linear Programming problems. Jan 8 at 17:00
• @GregoryMorse Welcome to ORSE. You'll find that, at least in this forum, the convention is that LP implies that there are no integer restrictions. Jan 8 at 18:21