Fenchel-Moreau and Primal/Dual Optimization Problems

The Fenchel-Moreau Theorem 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.

Theorem Statement

Given a normed vector space X and $f:X\to \mathbb {R} \cup \{+\infty \}$, then

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

$f^{*}(u):=\sup _{x\in X}\{\langle u,x\rangle -f(x)\}\quad \forall u\in X^{*}.$

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

$f^{*}(u)+f(x)\geq \langle u,x\rangle \quad \forall x\in X,u\in X^{*}.$

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

$f^{**}(x):=\sup _{u\in X^{*}}\{\langle u,x\rangle -f^{*}(u)\}\quad \forall u\in X^{*}.$

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

$f^{**}(x)\leq f(x)\quad \forall x\in X.$

In this way, it is clear that, 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 is also sufficient.