View source for Fenchel-Moreau and Primal/Dual Optimization Problems

The Fenchel-Moreau Theorem<ref name="Brezis" /> 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 the equivalence of ''primal'' and ''dual'' optimization problems.

==Fenchel-Moreau Theorem==
Given a normed vector space ''X'' and <math> f: X \to \mathbb{R} \cup \{+\infty\} </math>, then

:<math> f \text{ is convex and lower semicontinuous} \iff f^{**} = f. </math>

==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 <math> f: X \to \mathbb{R} \cup \{+\infty\} </math>, its ''convex conjugate'' <math>f^*:X^* \to \mathbb{R} \cup \{+\infty\}</math> is defined by 

:<math> f^*(y):=\sup_{x \in X} \{ \langle y,x \rangle - f(x) \} \quad \forall y \in X^*. </math>

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

:<math> f^*(y) +f(x) \geq \langle y,x \rangle \quad \forall x \in X, y \in X^* . </math>

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 <math>f^{**}:X \to \mathbb{R} \cup \{+\infty\} </math> is defined by 

:<math> f^{**}(x):=\sup_{y \in X^*} \{ \langle y,x \rangle - f^*(y) \} \quad \forall y \in X^*. </math>

As above, for any function ''f'', its biconjugate function ''f**'' is convex and lower semicontinuous. Furthermore, by Young's inequality, we always have

:<math> f^{**}(x) \leq f(x) \quad \forall x \in X. </math>

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

 
==Application to Primal/Dual Optimization Problems==
An important consequence of the Fenchel-Moreau Theorem is characterizing the equivalence of the primal and dual optimization problems.<ref name="Rockafellar" /> Given a normed vector space ''X'' and a proper, lower semicontinuous, convex function <math>f: X \to \mathbb{R}\cup \{+\infty\}</math>, the ''primal'' optimization problem is given by

:<math> \inf_{x \in X} f(x). </math>

The corresponding dual problem arises from a suitable ``perturbation" of the primal problem, subject to a parameter ''u'' ∈ ''U'', where ''U'' is also a normed vector space. In particular, let <math> F:X \times U \to \mathbb{R} \cup \{+\infty\} </math> be a proper convex function so that <math> f(x) = F(x,0) </math>. Then the corresponding ''primal'' and ''dual'' problems may be written as

:<math> P_0 := \inf_{x \in X} F(x,0) </math>
:<math> D_0 := \sup_{v \in U^*} -F^*(0,v) </math>

The formulation of these problems becomes even simpler from the perspective of the ''inf projection'' <math> P(u) := \inf_{x} F(x,u) </math>. With this notation, the primal and dual problems are given by

:<math> P_0 = P(0)</math>
:<math> D_0 =P^{**}(0) </math>

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==
<references>
<ref name="Brezis">H. Brezis, ''Functional Analysis'', Chapter 1.</ref>
<ref name="Rockafellar">Rockafellar, ''Convex Analysis''.</ref>
</references>