Linear Programs

Departure from Linear Algebra to Optimization

l2 regularization - Least Square l1

Problem: How to handle something like: $Ax\le b$ OR ${\min }_x\Vert Ax-b{\Vert }_1$

New class of problems: Linear Programs (LPs) Any LP can be written in “Standard Form”: (Linear cost and linear inequality constraints) (Most Popular) $mi{n}_x{c}^{T}x$ $\text{such that }Ax\le b$

Other (Equivalent) Standard Form: $mi{n}_x{c}^{T}x$ $\text{such that }Ax=b,x\ge 0$ “Standard Form” Provides us with a definition of LP = any problem that can be written in “that” form. [Just as with Least squares] Cause it could be written as least squares problem through transformation. Same with Linear Programs. (Can be transformed although it might not be obvious)

what do these constraints mean. In least square, x is not constraint. In LP, x have inequality constraints.

What does the “Feasible Set” of x s.t. $Ax\le b$ looks like?

$Ax\le b\leftrightarrow a_i^{T}x\le b$

$\{x:Ax\le b\}=x:a_i^{T}x\le b_i,i=1,\dots ,n$ $\{x:a_i^{T}x\le b_i\}$

Intersection form.

In the space, → “Half Space ← “Feasible Set”

Intersection of halfspaces is called a “polytope” (basically the feasible region). Higher dimension of polygon. Could be empty if the problem is infeasible problem. Empty Set.

[Picture]

---

Examples:

1. Probability Simplex $\{x\in R^n:x_i>-0,{\sum }_{i=1}^n{x}_i=1\}$ $x_i\ge 0\text{for all i}⟹-x\le 0$ $\sum x_i=1⟹1^{T}x\le \vec{1}\text{and}-1^{T}x\le -1$ Basically Changing from equality to inequality constraints. Ex 2: l1 ball (quite complicated in higher dimension, but nevertheless, an example of Polytope)

---

Generally Speaking, LP is in the form

$mi{n}_{x}f(x)\text{st}x\in P\text{ where P is a polytope = intersection of finite x of }$

Cost function is affine function $c^{T}x+d$

Objective Function $df(x)=c$ points in the direction of max increase. → -c points in the direction of max decrease.

[picturessss]

---

Many problems don’t look like LPs, but can be cast as such.

SVM is an LP.

Ex: $mi{n}_x{c}^{T}x+\lambda \Vert x{\Vert }_1\text{such that}Ax\le b$

The trick is often time Introduce new variables. Slack Variables.