Fenchel-Rockafellar and Linear Programming

From Optimal Transport Wiki
Jump to navigation Jump to search

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 and be convex, lower semicontinuous and proper functions. Suppose that there exists such that , where is continuous at . Then, it holds that


We provide a sketch of the proof, the reader is referred to Brezis[1] for further reading. Note that, by Young's Inequality, for any and we have

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 , equality must be obtained, and for every the supremum is realized; otherwise assume for all , and let be the value of the infimum.

Let and observe that since is continuous at , the interior of is nonempty. Likewise, let . Both sets are convex, and by construction we have . So a geometric Hahn-Banach Theorem implies that there is some nonzero and such that

Since is finite at , letting shows that is nonnegative, and if , continuity and joint finiteness imply , a contradiction, so . Thus, we can use the inequalities above with the definitions of and to conclude that
Which implies that
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 ,,, , and and consider the following finite dimensional linear program[2]

where and . Moreover, let us suppose that there exist at least one feasible solution such that and . Then, dual problem of is given by

where and . Furthermore, attains its optimal value and we have .


Note that, the linear program may be equivalently written as

where denotes the characteristic function of . Further, let us define , and . Note that, both and are convex, lower semicontinuous and proper functions, where we have . Moreover, since we have , we observe that is continuous at . Therefore, by the Fenchel-Rockafellar Theorem we obtain

In terms of convex conjugate of we have

Furthermore, for the convex conjugate of we observe

Notice that, is finite if and only if we have and for some . Therefore, as , by combining these two results with the Fenchel-Rockafellar Theorem we obtain the dual linear program as follows.