0

When doing linear programming, according to my professor, linear constraints always form a convex set. Why is this true?

Alexander Mills
  • 342
  • 4
    https://math.stackexchange.com/questions/1612887/constraint-set-of-canonical-linear-programming-problem-is-convex – jcneek Sep 13 '22 at 19:16
  • If two points satisfy a linear constraint, so do all points on the line between them. For multiple constraints, this applies to each individually. – eyeballfrog Sep 13 '22 at 19:17
  • 5
    The key idea here is that an intersection of convex sets is a convex set. – Brian Borchers Sep 13 '22 at 19:25
  • 1
    A linear constraint is either a subspace (equality) or a closed half space ($\le$). @BrianBorchers comment is the essence. – copper.hat Sep 13 '22 at 20:51

1 Answers1

1

If $Ax_1 = b, Ax_2 =b$

i.e $x_1,x_2$ belongs to the set then for $0<=k<=1$

$kAx_1 + (1-k)Ax_2 = kb + (1-k)b$

or $A(kx_1 + (1-k)x_2) = b$

i.e $kx_1 + (1-k)x_2 $ also belongs to the set. Therefore the set is convex.

Alexander Mills
  • 342
Anwesha1729
  • 352
  • 2
  • 8