![]() | ||
Concave and convex functions
Convex analysis is the branch of mathematics devoted to the study of properties of convex functions and convex sets, often with applications in convex minimization, a subdomain of optimization theory.
Contents
- Concave and convex functions
- Conferencia convex analysis in the calculus of variations
- Convex sets
- Convex functions
- Convex conjugate
- Biconjugate
- Convex minimization
- Dual problem
- Lagrange duality
- References
Conferencia convex analysis in the calculus of variations
Convex sets
A convex set is a set C ⊆ X, for some vector space X, such that for any x, y ∈ C and λ ∈ [0, 1] then
Convex functions
A convex function is any extended real-valued function f : X → R ∪ {±∞} which satisfies Jensen's inequality, i.e. for any x, y ∈ X and any λ ∈ [0, 1] then
Equivalently, a convex function is any (extended) real valued function such that its epigraph
is a convex set.
Convex conjugate
The convex conjugate of an extended real-valued (not necessarily convex) function f : X → R ∪ {±∞} is f* : X* → R ∪ {±∞} where X* is the dual space of X, and
Biconjugate
The biconjugate of a function f : X → R ∪ {±∞} is the conjugate of the conjugate, typically written as f** : X → R ∪ {±∞}. The biconjugate is useful for showing when strong or weak duality hold (via the perturbation function).
For any x ∈ X the inequality f**(x) ≤ f(x) follows from the Fenchel–Young inequality. For proper functions, f = f** if and only if f is convex and lower semi-continuous by Fenchel–Moreau theorem.
Convex minimization
A convex minimization (primal) problem is one of the form
such that f : X → R ∪ {±∞} is a convex function and M ⊆ X is a convex set.
Dual problem
In optimization theory, the duality principle states that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem.
In general given two dual pairs separated locally convex spaces (X, X*) and (Y, Y*). Then given the function f : X → R ∪ {+∞}, we can define the primal problem as finding x such that
If there are constraint conditions, these can be built into the function f by letting
The dual problem with respect to the chosen perturbation function is given by
where F* is the convex conjugate in both variables of F.
The duality gap is the difference of the right and left hand sides of the inequality
This principle is the same as weak duality. If the two sides are equal to each other, then the problem is said to satisfy strong duality.
There are many conditions for strong duality to hold such as:
Lagrange duality
For a convex minimization problem with inequality constraints,
the Lagrangian dual problem is
where the objective function L(x, u) is the Lagrange dual function defined as follows: