3.2 Linear Programming

DATA 442/642 · Week 3 · PDF · Slides

A linear cost, linear inequalities, and a dual that is also an LP.

These notes walk through the lecture slides. The original deck is unchanged; use (slides) on the course hub if you want that PDF.

The figures follow Deisenroth, Faisal, and Ong, Mathematics for Machine Learning.

1. Linear cost, linear inequalities

A linear program is the special case where $J$ and the constraints are linear. In machine learning that is how you optimize a linear model under linear limits, and how you write some feature-selection and dimension-reduction tasks so a solver can hit the feasible set.

Level sets of a linear cost are parallel hyperplanes. Inequality constraints are half-spaces. The feasible set is a polyhedron (shaded). The min, if it exists, sits at a vertex or on a face.

2. The primal

with $A\in {ℝ}^{m\times d}$ and $𝐛\in {ℝ}^m$. That is $d$ variables and $m$ linear constraints.

3. Dual of an LP

Lagrangian, with $\mathit{\lambda }\ge \mathbf{0}$,

Collect terms in $\mathit{\theta }$:

Stationarity in $\mathit{\theta }$ forces

Then $D(\mathit{\lambda })=-{\mathit{\lambda }}^{\top }𝐛$, and the dual is itself an LP with $m$ variables:

Solve the primal if $d$ is small. Solve the dual if $m$ is small. Same optimal value when the LP is feasible and bounded.

4. Practice

1. In the figure, why is the minimizer of a feasible bounded LP at a vertex (or on a face), not in the interior of the polyhedron?

2. After forming the Lagrangian, what equation knocks $\mathit{\theta }$ out and leaves a dual only in $\mathit{\lambda }$?

3. You have few variables and many constraints. Do you prefer the primal or the dual, and why?