5
$\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$

3 Answers 3

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

$\endgroup$
3
  • $\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$ May 16, 2020 at 16:22
  • 1
    $\begingroup$ Yes you are right I got mixed up ! Thanks @Marco Lübbecke! fixed it. $\endgroup$
    – Kuifje
    May 16, 2020 at 16:27
  • $\begingroup$ 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 $\endgroup$ Jan 8 at 0:06
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.$$

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jan 8 at 0:08
  • $\begingroup$ @GregoryMorse The question is about LP, not ILP. $\endgroup$
    – RobPratt
    Jan 8 at 1:48
  • $\begingroup$ 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. $\endgroup$ Jan 8 at 17:00
  • $\begingroup$ @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. $\endgroup$
    – RobPratt
    Jan 8 at 18:21
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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.