%matplotlib inline
import numpy as np;
from matplotlib import pyplot as plt
$\LaTeX \text{ commands here} \newcommand{\R}{\mathbb{R}} \newcommand{\im}{\text{im}\,} \newcommand{\norm}[1]{||#1||} \newcommand{\inner}[1]{\langle #1 \rangle} \newcommand{\span}{\mathrm{span}} \newcommand{\proj}{\mathrm{proj}} \newcommand{\OPT}{\mathrm{OPT}} $
Georgia Tech, CS 4540
Jake Abernethy & Benjamin Bray
Thursday, October 17, 2019
We will work towards proving the following Lemma:
Hint: Use the separating hyperplane theorem, where one set is $\mathrm{cone}(a_1,\dots,a_k)$.
Imagine you have a directed graph graph $G = (V,E)$ where each edge $e \in E$ has some "travel time" $c_e$ associated with it. You have a source $t \in V$ and a sink $s \in V$. Formulate a linear program that solves the "continuous flow" version of shortest path! Does not need to be in standard form.
If $y = (y_1,\dots,y_m) \geq 0$, then $y^T A$ is a nonnegative linear combination of the constraints (the rows of $A$). Look for combinations of constraints that dominate the objective, $$ y^T A = \sum_{k=1}^m y_k a_k^T \geq c^T \implies c^T x \leq y^T A x \leq y^T b $$
This is an upper bound on the value of the objective function!
Note: People usually write $A^T y \geq c$, which is equivalent.
The dual linear program searches for the best or tightest upper bound by looking at all possible combinations of constraints which dominate the objective:
Using the "tightest upper bound" interpretation of the dual linear program, it is clear that weak duality holds:
Recall that a feasible solution $x \in \R^n$ to Primal is called optimal if no other feasible solution has a higher objective value.
Solution: Assume towards contradiction that $x' \in \R^n$ has a higher objective value, $c^T x' > c^T x$. Then $c^T x' > y^T b$. But since $y$ is dual feasible, this contradicts weak duality!
A company has $m$ different resources which can be used to manufacture $n$ different products.
If it helps, assume the amount of each resource available is measured in kilograms, and our profit is measured in euros €. Maybe we're manufacturing rope, so the amount of each product is measured in meters.