Fenchel-Rockafellar and Linear Programming

The Fenchel-Rockafellar Theorem is a minimax principle especially suited to converting between primal and dual linear programs.

The Fenchel-Rockafellar Theorem

Suppose $\phi :X\to \mathbb {R} \cup \left\{+\infty \right\}$ and $\psi :X\to \mathbb {R} \cup \left\{+\infty \right\}$ are convex, lower semicontinuous, proper functions which are both finite at some $x_{0}\in X$, and $\phi$ is continuous there. Then

$$\inf \left\{\phi (x)+\psi (x):x\in X\right\}=\max \left\{-\phi ^{*}(-u)-\psi ^{*}(u):u\in X^{*}\right\},$$

where the existence of the minimizer on the right hand side is part of the theorem.

Proof Sketch

Details may be found in Brezis' text, but a sketch of the proof follows.

By Young's Inequality, for any $x\in X$ and $u\in X^{*}$, we have $\phi (x)+\phi ^{*}(-u)+\psi (x)+\psi ^{*}(u)\leq \langle x,-u\rangle +\langle x,u\rangle =0$, so the infimum on the left is less than or equal to the supremum on the right. If the supremum is $-\infty$, equality must be obtained and every $u\in X^{*}$ must realize it; otherwise assume $-\phi (-u)-\psi (u)>-\infty$ everywhere. (INCOMPLETE)

Application to Linear Programs

Consider the linear program

$$\inf \left\{\langle c,x\rangle +\theta _{Y}(b-Ax):x\in X\right\},$$

where $X=\mathbb {R} _{+}^{r}\times \mathbb {R} ^{n-r}$, $Y=\mathbb {R} _{+}^{s}\times \mathbb {R} ^{m-s}$, and $\theta _{Z}(u):=\sup \left\{\langle z,u\rangle :z\in Z\right\}=\chi _{Z}^{*}(u)$. Then if we put

$$\phi (x)+\psi (x):=\left(\langle c,x\rangle +\chi _{X}(x)\right)+\theta _{Y}(b-Ax),$$

(noting that $\langle c,x\rangle +\chi _{X}(x)$ and $\theta _{Y}(b-Ax)$ are both convex lower semicontinuous proper functions), we are interested in computing $\phi ^{*}(u)=\sup \left\{\langle x,u-c\rangle :x\in X\right\}=\theta _{X}(u-c)$ and $\psi ^{*}(u)=\sup \left\{\langle x,u\rangle -\sup \left\{\langle y,b-Ax\rangle :y\in Y\right\}:z\in \mathbb {R} ^{n}\right\}$. By writing the latter as $\psi ^{*}(u)=\sup \left\{\inf \left\{\langle x,u+A^{*}y\rangle -\langle y,b\rangle :y\in Y\right\}:z\in \mathbb {R} ^{n}\right\}$, we can see that we have a finite value of $\psi ^{*}(u)$ if and only if $u=-A^{*}y_{0}$ for some $y_{0}\in Y$, and the value is then the infimum of $-\langle y,b\rangle$ where $A^{*}y=A^{*}y_{0}$. Putting this together, the Fenchel-Rockafellar Theorem gives that

$$\inf \left\{\langle c,x\rangle +\theta _{Y}(b-Ax):x\in X\right\}=\max \left\{\langle y,b\rangle -\theta _{X}(A^{*}y-c):y\in Y\right\},$$

provided we can find a point of continuity and mutual finiteness for $\phi$ and $\psi$.

To do this, we use our knowledge of $X$ and $Y$ to be more precise about the $\theta$ functions. In particular, if we write $(\pi _{1}^{Y},\pi _{2}^{Y}):Y\to \mathbb {R} ^{s}\times \mathbb {R} ^{m-s}$ and $(\pi _{1}^{X},\pi _{2}^{X}):X\to \mathbb {R} ^{r}\times \mathbb {R} ^{n-r}$ for the projections, and put $(b_{1},b_{2})=(\pi _{1}^{Y},\pi _{2}^{Y})b$, $(A_{1},A_{2})=(\pi _{1}^{Y},\pi _{2}^{Y})\circ A$, $(c_{1},c_{2})=(\pi _{1}^{X},\pi _{2}^{X})c$, and $(A_{1}^{*},A_{2}^{*})=(\pi _{1}^{X},\pi _{2}^{X})\circ A^{*}$ (which do satisfy $A_{i}^{*}=(A_{i})^{*}$, justifying the notation) we get (writing inequalities termwise)

$$\theta _{Y}(b-Ax)={\begin{cases}0,&b_{1}\leq A_{1}x\land b_{2}=A_{2}x,\\+\infty ,&{\text{else}},\end{cases}}\qquad \theta _{X}(A^{*}y-c)={\begin{cases}0,&c_{1}\geq A_{1}^{*}y\land c_{2}=A_{2}^{*}y\\+\infty ,&{\text{else}}.\end{cases}}$$

So, if some point in the interior of $X$ is mapped strictly greater than $b_{1}$ by $A_{1}$ and onto $b_{2}$ by $A_{2}$, we may write the duality result in the more customary way,

$$\inf _{x\in X,A_{1}x\geq b_{1},A_{2}x=b_{2}}\langle c,x\rangle =\max _{y\in Y,A_{1}^{*}y\leq c_{1},A_{2}^{*}y=c_{2}}\langle y,b\rangle .$$