In
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 of shifting the constraints.
[1]
In some texts the value function is called the perturbation function, and the perturbation function is called the bifunction.[2]
Definition
Given two
locally convex spaces
and
. Then given the function
, we can define the primal problem by
If there are constraint conditions, these can be built into the function by letting where is the characteristic function. Then is a perturbation function if and only if .[1][3]
Use in duality
The duality gap is the difference of the right and left hand side of the inequality
where is the convex conjugate in both variables.[3][4]
For any choice of perturbation function F
lower semi-continuous
with
(where
is the
algebraic interior and
is the
projection onto
Y defined by
) and
X,
Y are
Fréchet spaces then strong duality holds.
[1]
Examples
Lagrangian
Let and be dual pairs. Given a primal problem (minimize f(x)) and a related perturbation function (F(x,y)) then the Lagrangian is the negative conjugate of F with respect to y (i.e. the concave conjugate). That is the Lagrangian is defined by
In particular the weak duality minmax equation can be shown to be
If the primal problem is given by
where . Then if the perturbation is given by
then the perturbation function is
Thus the connection to Lagrangian duality can be seen, as L can be trivially seen to be
Fenchel duality
Main article:
Fenchel duality
Let and be dual pairs. Assume there exists a linear map with
adjoint operator
. Assume the primal
objective function
(including the constraints by way of the indicator function) can be written as
such that
. Then the perturbation function is given by
In particular if the primal objective is then the perturbation function is given by , which is the traditional definition of
References