Convex analysis


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.

Background

A subset of some vector space is if it satisfies any of the following equivalent conditions:
  1. If is real and then
  2. If is real and with then
[Image:ConvexFunction.svg|thumb|300px|right|Convex function on an interval.]
Throughout, will be a map valued in the extended real numbers with a domain that is a convex subset of some vector space.
The map is a if
holds for any real and any with If this remains true of when the defining inequality is replaced by the strict inequality
then is called.
Convex functions are related to convex sets. Specifically, the function is convex if and only if its [Epigraph (mathematics)|]
Image:Epigraph convex.svg|right|thumb|300px|A function is convex if and only if its epigraph, which is the region above its graph, is a convex set.
[Image:Grafico 3d x2+xy+y2.png|right|300px|thumb|A graph of the bivariate convex function ]
is a convex set. The epigraphs of extended real-valued functions play a role in convex analysis that is analogous to the role played by graphs of real-valued function in real analysis. Specifically, the epigraph of an extended real-valued function provides geometric intuition that can be used to help formula or prove conjectures.
The domain of a function is denoted by while its is the set
The function is called if and for Alternatively, this means that there exists some in the domain of at which and is also equal to In words, a function is if its domain is not empty, it never takes on the value and it also is not identically equal to If is a proper convex function then there exist some vector and some such that
where denotes the dot product of these vectors.

Convex conjugate

The of an extended real-valued function is the function from the (continuous) dual space of and
where the brackets denote the canonical duality
If denotes the set of -valued functions on then the map defined by is called the.

Subdifferential set and the Fenchel-Young inequality

If and then the is
For example, in the important special case where is a norm on, it can be shown
that if then this definition reduces down to:
For any and which is called the. This inequality is an equality if and only if It is in this way that the subdifferential set is directly related to the convex conjugate

Biconjugate

The of a function, typically written as, is the conjugate of the conjugate; for every. The biconjugate is useful for showing when strong or weak duality hold.
For any the inequality follows from the. For proper functions, if and only if is convex and lower semi-continuous by Fenchel–Moreau theorem.

Convex minimization

A is one of the form

Dual problem

In optimization theory, the 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 and Then given the function we can define the primal problem as finding such that
If there are constraint conditions, these can be built into the function by letting where is the indicator function. Then let be a perturbation function such that
The with respect to the chosen perturbation function is given by
where is the convex conjugate in both variables of
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 is the Lagrange dual function defined as follows: