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)\geq \langle x,-u\rangle +\langle x,u\rangle =0$, so the infimum on the left is greater than or equal to the supremum on the right. If the infimum is $-\infty$, equality must be obtained and every $u\in X^{*}$ must realize the supremum; otherwise assume $\phi (x)+\psi (x)>-\infty$ everywhere, and put $m$ for the value of the infimum.

Let

$$A:=\left\{(x,t):\phi (x)\leq t\right\},$$

and observe that since $\phi$ is continuous at $x_{0}$, the interior of $C$ is nonempty. Likewise, let

$$B:=\left\{(x,t):t\leq m-\psi (x)\right\}.$$

Both sets are convex, and $B\cap {\text{int}}A=\emptyset$ by construction, so a geometric Hahn-Banach Theorem gives that there is some $(f,k)\in X^{*}\times \mathbb {R}$ nonzero and $\alpha \in \mathbb {R}$ such that

$${\begin{cases}\langle x,f\rangle +kt\geq \alpha ,&(x,t)\in A,\\\langle x,f\rangle +kt\leq \alpha ,&(x,t)\in B.\end{cases}}$$

Since $\phi$ is finite at $x_{0}$, letting $t\to +\infty$ shows that $k$ is nonnegative, and if $k=0$, continuity and joint finiteness imply $\lVert f\rVert =0$, a contradiction, so $k>0$.

Thus, we can use the inequalities above with the definitions of $\phi ^{*}$ and $\psi ^{*}$ to conclude that

$${\begin{cases}\phi ^{*}\left(-{\frac {f}{k}}\right)&\leq -{\frac {\alpha }{k}},\\\psi ^{*}\left({\frac {f}{k}}\right)&\leq {\frac {\alpha }{k}}-m.\end{cases}}$$

This shows that

$$-\phi ^{*}\left(-{\frac {f}{k}}\right)-\psi ^{*}\left({\frac {f}{k}}\right)\geq m.$$

Since the supremum includes this term, it must also be greater than or equal to the infimum, yielding equality.

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 for $\phi$ 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}$ and onto $b_{2}$ by $A$, 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 .$$

If some point in the interior of $Y$ is mapped strictly less than $c_{1}$ and onto $c_{2}$ by $A^{*}$, then reversing the roles of primal and dual problems by taking negatives gives that the infimum is achieved as well.