Fenchel-Moreau and Primal/Dual Optimization Problems

From Optimal Transport Wiki
Jump to navigation Jump to search

The Fenchel-Moreau Theorem[1] is a fundamental result in convex analysis, characterizing the class of functions for which a function equals its biconjugate. A key consequence of this theorem is that is provides sufficient conditions for the equivalence of primal and dual optimization problems.[2]

Fenchel-Moreau Theorem

Given a normed vector space X and , then

Background on Convex Conjugate Functions

Let X be a normed vector space, and let X* denote its topological dual. Given an extended real-valued function , its convex conjugate is defined by

An immediate consequence of this definition is Young's Inequality,

Furthermore, it follows directly from the definition that, for any function f, its conjugate function f* is convex and lower semicontinuous.

In a similar way, for any function f, its the biconjugate function is defined by

As above, the biconjugate function f** is always convex and lower semicontinuous. Furthermore, by a second application of Young's inequality, we have

Since f** is always convex and lower semicontinuous, in order for equality to hold for all x, it is necessary that f also be convex and lower semicontinuous. The heart of Fenchel-Moreau Theorem is that this condition is not just necessary, but sufficient.

Application to Primal/Dual Optimization Problems

An important consequence of the Fenchel-Moreau Theorem is that it provides sufficient conditions for the equivalence of primal and dual optimization problems. Given a normed vector space X and a proper, lower semicontinuous, convex function , the primal optimization problem is given by

The corresponding dual problem arises from a suitable ``perturbation" of the primal problem, subject to a parameter uU, where U is also a normed vector space. In particular, let be a proper convex function so that . Then the corresponding primal and dual problems may be written as

The formulation of these problems becomes even simpler from the perspective of the inf projection . With this notation, the primal and dual problems are given by

Therefore, by the Fenchel-Moreau theorem, a sufficient condition for equivalence of the primal and dual problems is that the inf projetion function P(u) is convex and lower semicontinuous.

References

  1. H. Brezis, Functional Analysis, Chapter 1.
  2. Rockafellar, Convex Analysis.