In mathematics, Fenchel's duality theorem is a result in the theory of convex functions named after
Werner Fenchel
Moritz Werner Fenchel (; 3 May 1905 – 24 January 1988) was a mathematician known for his contributions to geometry and to optimization theory. Fenchel established the basic results of convex analysis and nonlinear optimization theor ...
.
Let ''ƒ'' be a
proper convex function
In mathematical analysis, in particular the subfields of convex analysis and optimization, a proper convex function is an extended real-valued convex function with a non-empty domain, that never takes on the value -\infty and also is not identic ...
on R
''n'' and let ''g'' be a proper concave function on R
''n''. Then, if regularity conditions are satisfied,
:
where ''ƒ''
* is the
convex conjugate
In mathematics and mathematical optimization, the convex conjugate of a function is a generalization of the Legendre transformation which applies to non-convex functions. It is also known as Legendre–Fenchel transformation, Fenchel transformatio ...
of ''ƒ'' (also referred to as the Fenchel–Legendre transform) and ''g''
* is the
concave conjugate of ''g''. That is,
:
:
Mathematical theorem
Let ''X'' and ''Y'' be
Banach spaces
In mathematics, more specifically in functional analysis, a Banach space (pronounced ) is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vector ...
,
and
be convex functions and
be a
bounded linear map
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pr ...
. Then the Fenchel problems:
:
:
satisfy
weak duality In applied mathematics, weak duality is a concept in optimization which states that the duality gap is always greater than or equal to 0. That means the solution to the dual (minimization) problem is ''always'' greater than or equal to the solution ...
, i.e.
. Note that
are the convex conjugates of ''f'',''g'' respectively, and
is the
adjoint operator
In mathematics, specifically in operator theory, each linear operator A on a Euclidean vector space defines a Hermitian adjoint (or adjoint) operator A^* on that space according to the rule
:\langle Ax,y \rangle = \langle x,A^*y \rangle,
where ...
. The
perturbation function In mathematical optimization, the perturbation function is any function which relates to primal and dual problems. The name comes from the fact that any such function defines a perturbation of the initial problem. In many cases this takes the form ...
for this
dual problem
In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then t ...
is given by
.
Suppose that ''f'',''g'', and ''A'' satisfy either
# ''f'' and ''g'' are
lower semi-continuous
In mathematical analysis, semicontinuity (or semi-continuity) is a property of extended real-valued functions that is weaker than continuity. An extended real-valued function f is upper (respectively, lower) semicontinuous at a point x_0 if, ro ...
and
where
is the
algebraic interior
In functional analysis, a branch of mathematics, the algebraic interior or radial kernel of a subset of a vector space is a refinement of the concept of the interior.
Definition
Assume that A is a subset of a vector space X.
The ''algebraic i ...
and
, where ''h'' is some function, is the set
, or
#
where
are the points where the function is
continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous ...
.
Then
strong duality holds, i.e.
. If
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
*
Legendre transformation
In mathematics, the Legendre transformation (or Legendre transform), named after Adrien-Marie Legendre, is an involutive transformation on real-valued convex functions of one real variable. In physical problems, it is used to convert functions ...
*
Convex conjugate
In mathematics and mathematical optimization, the convex conjugate of a function is a generalization of the Legendre transformation which applies to non-convex functions. It is also known as Legendre–Fenchel transformation, Fenchel transformatio ...
*
Moreau's theorem In mathematics, Moreau's theorem is a result in convex analysis named after French mathematician Jean-Jacques Moreau. It shows that sufficiently well-behaved convex functionals on Hilbert spaces are differentiable and the derivative is well-approxim ...
*
Wolfe duality
In mathematical optimization, Wolfe duality, named after Philip Wolfe, is type of dual problem in which the objective function and constraints are all differentiable functions. Using this concept a lower bound for a minimization problem can be f ...
*
Werner Fenchel
Moritz Werner Fenchel (; 3 May 1905 – 24 January 1988) was a mathematician known for his contributions to geometry and to optimization theory. Fenchel established the basic results of convex analysis and nonlinear optimization theor ...
References
*
* {{cite book , author-link=R. Tyrrell Rockafellar, last=Rockafellar, first=Ralph Tyrrell , title=Convex Analysis , url=https://archive.org/details/convexanalysis00rock, url-access=limited, publisher=Princeton University Press , year=1996 , isbn=0-691-01586-4 , pag
327
Theorems in analysis
Convex optimization