Linear Programming

Convexity

Convex set: A subset $A\subset \mathbb{R}^2$ is convex if it contains the line segment joining any two of its points

• [ ] Points $x_1,x_2 \in A$

⇒ $x_3 := tx_1 + (1-t)x_2, 0\leq t \leq 1$ is in A

• [ ] A is convex

<aside> 💡 The empty set is also convex!

</aside>

Convex function: A function $f: I \rightarrow \mathbb{R}$ is convex if the set $A_f = \{ (x,y)\in \mathbb{R}^2 | y\geq f(x)\} \subset \mathbb{R}^2$ is convex

⇒ So we basically observe the area which is above our function and see if the set would be convex when included all points in the area above

Lemma. Linear functions are convex ⇒ Linear programs are convex

• Formulation
• What does "linear" refer to?
• "States" of LPs

Canonical Form