Misplaced Pages

Fenchel's duality theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

In mathematics, Fenchel's duality theorem is a result in the theory of convex functions named after Werner Fenchel.

Let ƒ be a proper convex function on R and let g be a proper concave function on R. Then, if regularity conditions are satisfied,

inf x ( f ( x ) − g ( x ) ) = sup p ( g ∗ ( p ) − f ∗ ( p ) ) . {\displaystyle \inf _{x}(f(x)-g(x))=\sup _{p}(g_{*}(p)-f^{*}(p)).}

where ƒ is the convex conjugate of ƒ (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 ∈ R n } {\displaystyle f^{*}\left(x^{*}\right):=\sup \left\{\left.\left\langle x^{*},x\right\rangle -f\left(x\right)\right|x\in \mathbb {R} ^{n}\right\}}
g ∗ ( x ∗ ) := inf { ⟨ x ∗ , x ⟩ − g ( x ) | x ∈ R n } {\displaystyle g_{*}\left(x^{*}\right):=\inf \left\{\left.\left\langle x^{*},x\right\rangle -g\left(x\right)\right|x\in \mathbb {R} ^{n}\right\}}

Mathematical theorem

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

p ∗ = inf x ∈ X { f ( x ) + g ( A x ) } {\displaystyle p^{*}=\inf _{x\in X}\{f(x)+g(Ax)\}}
d ∗ = sup y ∗ ∈ Y ∗ { − f ∗ ( A ∗ y ∗ ) − g ∗ ( − y ∗ ) } {\displaystyle d^{*}=\sup _{y^{*}\in Y^{*}}\{-f^{*}(A^{*}y^{*})-g^{*}(-y^{*})\}}

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

Suppose that f,g, and A satisfy either

  1. f and g are lower semi-continuous and 0 ∈ core ⁡ ( dom ⁡ g − A dom ⁡ f ) {\displaystyle 0\in \operatorname {core} (\operatorname {dom} g-A\operatorname {dom} f)} where core {\displaystyle \operatorname {core} } is the algebraic interior and dom ⁡ h {\displaystyle \operatorname {dom} h} , where h is some function, is the set { z : h ( z ) < + ∞ } {\displaystyle \{z:h(z)<+\infty \}} , or
  2. A dom ⁡ f ∩ cont ⁡ g ≠ ∅ {\displaystyle A\operatorname {dom} f\cap \operatorname {cont} g\neq \emptyset } where cont {\displaystyle \operatorname {cont} } are the points where the function is continuous.

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

One-dimensional illustration

In the following figure, the minimization problem on the left side of the equation is illustrated. One seeks to vary x such that the vertical distance between the convex and concave curves at x is as small as possible. The position of the vertical line in the figure is the (approximate) optimum.

The next figure illustrates the maximization problem on the right hand side of the above equation. Tangents are drawn to each of the two curves such that both tangents have the same slope p. The problem is to adjust p in such a way that the two tangents are as far away from each other as possible (more precisely, such that the points where they intersect the y-axis are as far from each other as possible). Imagine the two tangents as metal bars with vertical springs between them that push them apart and against the two parabolas that are fixed in place.

Fenchel's theorem states that the two problems have the same solution. The points having the minimum vertical separation are also the tangency points for the maximally separated parallel tangents.

See also

References

  1. Borwein, Jonathan; Zhu, Qiji (2005). Techniques of Variational Analysis. Springer. pp. 135–137. ISBN 978-1-4419-2026-3.
Categories: