Find a concept
Start typing to search the mathematical index.
An inequality relating a function and its Fenchel conjugate via the dual pairing.
Fenchel–Young inequality. Let be a proper function, and let be its Fenchel conjugate. Then, for all ,
If is convex, equality holds if and only if , where is the subdifferential. If is also lower semicontinuous, this is equivalent to .
The inequality follows immediately from the definition, since . It is the basic mechanism behind weak duality in convex primal-dual pairs.
A Fenchel conjugate of an extended-real-valued function is the function defined by
where is the Euclidean inner product.
A subdifferential of a convex function at a point in its effective domain is the set
Any is called a subgradient of at .
Geometrically, encodes a supporting hyperplane to the epigraph of at , with normal determined by (compare hyperplane). If is differentiable at (in the sense of the derivative / differentiable map), then .
A primal-dual pair in convex optimization is a pair of problems built from convex objectives so that the dual objective gives a universal lower bound on the primal optimal value. A common (Fenchel) form starts from convex functions and and a linear map , and defines
where and are Fenchel conjugates and use infimum and supremum. The inequality (weak duality) follows from the Fenchel-Young inequality, and under suitable regularity conditions one has strong duality , often certified by subgradient conditions.