# Fenchel-Rockafellar and Linear Programming

The Fenchel-Rockafellar Theorem is a well-known result from convex analysis that establishes a minimax principle between convex functions and their convex conjugates under some regularity conditions. One fundamental application of this theorem is the characterization of the dual problem of a finite dimensional linear program.

## The Fenchel-Rockafellar Theorem

Let $\phi :X\to \mathbb {R} \cup \left\{+\infty \right\}$ and $\psi :X\to \mathbb {R} \cup \left\{+\infty \right\}$ be convex, lower semicontinuous and proper functions. Suppose that there exists $x_{0}\in X$ such that $\phi (x_{0}),\varphi (x_{0})<\infty$ , where $\phi$ is continuous at $x_{0}$ . Then, it holds that

${\underset {x\in X}{\inf }}\left\{\phi (x)+\psi (x)\right\}={\underset {u\in X^{*}}{\max }}\left\{-\phi ^{*}(-u)-\psi ^{*}(u)\right\}.$ ### Proof

We provide a sketch of the proof, the reader is referred to Brezis for further reading. Note that, 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.$ Hence, the infimum of the left hand side is greater than or equal to the supremum of the right hand side. If the infimum is $-\infty$ , equality must be obtained, and for every $u\in X^{*}$ the supremum is realized; otherwise assume $\phi (x)+\psi (x)>-\infty$ for all $x\in X$ , and let $m$ be 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 by construction we have $B\cap {\text{int}}A=\emptyset$ . So a geometric Hahn-Banach Theorem implies that there is some nonzero $(f,k)\in X^{*}\times \mathbb {R}$ 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
$\phi ^{*}\left(-{\frac {f}{k}}\right)\leq -{\frac {\alpha }{k}},\quad {\text{and}}\quad \psi ^{*}\left({\frac {f}{k}}\right)\leq {\frac {\alpha }{k}}-m.$ Which implies that
$-\phi ^{*}\left(-{\frac {f}{k}}\right)-\psi ^{*}\left({\frac {f}{k}}\right)\geq m.$ Finally, since the supremum includes this term, it must also be greater than or equal to the infimum, which yields their equality.

## Application to Linear Programs

Let $A_{1}\in \mathbb {R} ^{p\times m}$ ,$A_{2}\in \mathbb {R} ^{q\times n}$ ,$b_{1}\in \mathbb {R} ^{p}$ , $b_{2}\in \mathbb {R} ^{q}$ ,$c_{1}\in \mathbb {R} ^{m}$ and $c_{2}\in \mathbb {R} ^{m}$ and consider the following finite dimensional linear program

{\mathcal {P}}=\quad {\begin{aligned}&{{\text{ }}\inf }&&\langle c_{1},x\rangle +\langle c_{2},y\rangle \\&{\text{subject to}}&&A_{1}x\geq b_{1}\\&&&A_{2}y=b_{2}\\&&&x\geq 0\\\end{aligned}} where $x\in \mathbb {R} ^{m}$ and $y\in \mathbb {R} ^{n}$ . Moreover, let us suppose that there exist at least one feasible solution ${\tilde {x}}\in \mathbb {R} ^{m},{\tilde {y}}\in \mathbb {R} ^{n}$ such that $A_{1}{\tilde {x}}>b_{1}$ $A_{2}{\tilde {y}}=b_{2}$ and ${\tilde {x}}>0$ . Then, dual problem of ${\mathcal {P}}$ is given by

{\mathcal {D}}=\quad {\begin{aligned}&{{\text{ }}\max }&&\langle b_{1},\alpha \rangle +\langle b_{2},\beta \rangle \\&{\text{subject to}}&&A_{1}^{T}\alpha \leq c_{1}\\&&&A_{2}^{T}\beta =c_{2}\\&&&\alpha \geq 0\\\end{aligned}} where $\alpha \in \mathbb {R} ^{p}$ and $\beta \in \mathbb {R} ^{q}$ . Furthermore, ${\mathcal {D}}$ attains its optimal value and we have ${\mathcal {P}}={\mathcal {D}}$ .

### Proof

Note that, the linear program may be equivalently written as

${\underset {x\in \mathbb {R} ^{m},y\in \mathbb {R} ^{n}}{\inf }}\left\{\langle c_{1},x\rangle +\langle c_{2},y\rangle +\mathrm {X} _{\mathbb {R} _{+}}(x)+\mathrm {X} _{\mathbb {R} _{+}}(b_{1}-A_{1}x)+\mathrm {X} _{\{0\}}(b_{2}-A_{2}y)\right\}$ where $\mathrm {X} _{A}$ denotes the characteristic function of $A\subseteq \mathbb {R} ^{n}$ . Further, let us define $\phi (x,y)=\langle c_{1},x\rangle +\langle c_{2},y\rangle +\mathrm {X} _{\mathbb {R} _{+}}(x)$ , and $\varphi (x,y)=\mathrm {X} _{\mathbb {R} _{+}}(b_{1}-A_{1}x)+\mathrm {X} _{\{0\}}(b_{2}-A_{2}y)$ . Note that, both $\phi$ and $\varphi$ are convex, lower semicontinuous and proper functions, where we have $\phi ({\tilde {x}},{\tilde {y}}),\varphi ({\tilde {x}},{\tilde {y}})<\infty$ . Moreover, since we have ${\tilde {x}}>0$ , we observe that $\phi$ is continuous at $({\tilde {x}},{\tilde {y}})$ . Therefore, by the Fenchel-Rockafellar Theorem we obtain

${\underset {w\in \mathbb {R} ^{m},t\in \mathbb {R} ^{n}}{\max }}\left\{-\phi ^{\star }(-w,-t)-\varphi ^{\star }(w,t)\right\}={\underset {x\in \mathbb {R} ^{m},y\in \mathbb {R} ^{n}}{\inf }}\left\{\langle c_{1},x\rangle +\langle c_{2},y\rangle +\mathrm {X} _{\mathbb {R} _{+}}(x)+\mathrm {X} _{\mathbb {R} _{+}}(b_{1}-A_{1}x)+\mathrm {X} _{\{0\}}(b_{2}-A_{2}y)\right\}.$ In terms of convex conjugate of $\phi$ we have

{\begin{aligned}\phi ^{\star }(-w,-t)&={\underset {x\in \mathbb {R} ^{m},y\in \mathbb {R} ^{n}}{\sup }}\left\{-\langle x,w+c_{1}\rangle -\langle y,t+c_{2}\rangle -\mathrm {X} _{\mathbb {R} _{+}}(x)\right\}\\&={\underset {x\in \mathbb {R} _{-}^{m},y\in \mathbb {R} ^{n}}{\sup }}\left\{-\langle x,w+c_{1}\rangle -\langle y,t+c_{2}\rangle \right\}\\&=\mathrm {X} _{\mathbb {R} _{+}}(w+c_{1})+\mathrm {X} _{\{0\}}(t+c_{2}).\end{aligned}} Furthermore, for the convex conjugate of $\varphi$ we observe

{\begin{aligned}\varphi ^{\star }(w,t)&={\underset {x\in \mathbb {R} ^{m},y\in \mathbb {R} ^{n}}{\sup }}\left\{\langle x,w\rangle +\langle y,t\rangle -\mathrm {X} _{\mathbb {R} _{+}}(b_{1}-A_{1}x)-\mathrm {X} _{\{0\}}(b_{2}-A_{2}y)\right\}\\&={\underset {x\in \mathbb {R} ^{m},y\in \mathbb {R} ^{n}}{\sup }}\left\{\langle x,w\rangle +\langle y,t\rangle -{\underset {\alpha \in \mathbb {R} _{+}^{p},\beta \in \mathbb {R} ^{q}}{\sup }}\left\{\langle b_{1}-A_{1}x,\alpha \rangle +\langle b_{2}-A_{2}y,\beta \rangle \right\}\right\}\\&={\underset {x\in \mathbb {R} ^{m},y\in \mathbb {R} ^{n}}{\sup }}\left\{{\underset {\alpha \in \mathbb {R} _{+}^{p},\beta \in \mathbb {R} ^{q}}{\inf }}\left\{\langle x,w\rangle +\langle y,t\rangle +\langle A_{1}x-b_{1},\alpha \rangle +\langle A_{2}y-b2,\beta \rangle \right\}\right\}\\&={\underset {x\in \mathbb {R} ^{m},y\in \mathbb {R} ^{n}}{\sup }}\left\{{\underset {\alpha \in \mathbb {R} _{+}^{p},\beta \in \mathbb {R} ^{q}}{\inf }}\left\{\langle x,w+A_{1}^{T}\alpha \rangle +\langle y,t+A_{2}^{T}\beta \rangle -\langle b_{1},\alpha \rangle -\langle b_{2},\beta \rangle \right\}\right\}\end{aligned}} Notice that, $\varphi ^{\star }$ is finite if and only if we have $w=A_{1}^{T}\alpha$ and $t=A_{2}^{T}\beta$ for some $\alpha \in \mathbb {R} _{+}^{p},\beta \in \mathbb {R} ^{q}$ . Therefore, as $\phi ^{\star }=\mathrm {X} _{\mathbb {R} _{+}}(w+c_{1})+\mathrm {X} _{\{0\}}(t+c_{2})$ , by combining these two results with the Fenchel-Rockafellar Theorem we obtain the dual linear program as follows.

${\underset {\alpha \in \mathbb {R} _{+}^{p},\beta \in \mathbb {R} ^{q}}{\max }}\left\{\langle b_{1},\alpha \rangle +\langle b_{2},\beta \rangle -\mathrm {X} _{\mathbb {R} _{+}}(c_{1}-A_{1}^{T}\alpha )-\mathrm {X} _{\{0\}}(A_{2}^{T}\beta -c_{2})\right\}$ 