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 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 dual pairs separated 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 indicator 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 weak duality holds. There are a number of conditions which if satisfied imply strong duality.[3] For instance, if F is proper, jointly convex, 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
- Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): L(x,y^*) = \begin{cases} f(x) + y^*(g(x)) & \text{if } y^* \in \mathbb{R}^d_+\\ -\infty & \text{else} \end{cases}
.
Fenchel duality
<templatestyles src="Module:Hatnote/styles.css"></templatestyles>
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 Fenchel duality.[5]
References
- ↑ 1.0 1.1 1.2 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ 3.0 3.1 3.2 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.