Fenchel's duality theorem

Let $f$ be a proper convex function on $R^{n}$ and let $g$ be a proper concave function on $R^{n}$ . Then, if regularity conditions are satisfied,

inf_{x} (f (x) - g (x)) = sup_{p} (g_{*} (p) - f^{*} (p)) .

where $f^{*}$ is the convex conjugate of $f$ (also referred to as the Fenchel–Legendre transform) and $g_{*}$ is the concave conjugate of $g$ . That is,

f^{*} (x^{*}) := sup {⟨ x^{*}, x ⟩ - f (x) | x \in R^{n}}

g_{*} (x^{*}) := inf {⟨ x^{*}, x ⟩ - g (x) | x \in R^{n}}

Mathematical theorem

Let X and Y be Banach spaces, $f : X \to R \cup {+ \infty}$ and $g : Y \to R \cup {+ \infty}$ be convex functions and $A : X \to Y$ be a bounded linear map. Then the Fenchel problems:

p^{*} = inf_{x \in X} {f (x) + g (A x)}

d^{*} = sup_{y^{*} \in Y^{*}} {- f^{*} (A^{*} y^{*}) - g^{*} (- y^{*})}

satisfy weak duality, i.e. $p^{*} \geq d^{*}$ . Note that $f^{*}$ and $g^{*}$ are the convex conjugates of $f$ and $g$ , respectively, and $A^{*}$ is the adjoint operator. The perturbation function for this dual problem is given by $F (x, y) = f (x) + g (A x - y)$ .

Suppose that $f$ , $g$ , and $A$ satisfy either

$f$ and $g$ are lower semi-continuous and $0 \in core (dom g - A dom f)$ where $core$ is the algebraic interior and $dom h$ , where $h$ is some function, is the set ${z : h (z) < + \infty}$ , or
$A dom f \cap cont g \neq \emptyset$ where $cont$ are the points where the function is continuous.

Then strong duality holds, i.e. $p^{*} = d^{*}$ . If $d^{*} \in R$ then supremum is attained.

One more chapter is free with a Lably account.

Fenchel's duality theorem

Mathematical theorem

One-dimensional illustration

More in Topics in mathematics