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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} , letting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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\}$$