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]

## Contents

* 1 Definition
* 2 Use in duality
* 3 Examples
* 3.1 Lagrangian
* 3.2 Fenchel duality
* 4 References

## Definition

Given two dual pairs of separated locally convex spaces (X,X*) and (Y,Y*). Then given the function f:X->ℝ∪{+∞}, we can define the primal problem by

infx∈Xf(x).

If there are constraint conditions, these can be built into the function f by letting f<-f+Iconstraints where I is the characteristic function. Then F:X×Y->ℝ∪{+∞} is a perturbation function if and only if F(x,0)=f(x).[1][3]

## Use in duality

The duality gap is the difference of the right and left hand side of the inequality

supy*∈Y*−F*(0,y*)≤infx∈XF(x,0),

where F* 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 0∈core⁡(PrY(dom⁡F)) (where core is the algebraic interior and PrY is the projection onto Y defined by PrY(x,y)=y) and X, Y are Fréchet spaces then strong duality holds.[1]

## Examples

### Lagrangian

Let (X,X*) and (Y,Y*) be dual pairs. Given a primal problem (minimize f(x)) and a related perturbation function (F(x,y)) then the Lagrangian L:X×Y*->ℝ∪{+∞} is the negative conjugate of F with respect to y (i.e. the concave conjugate). That is the Lagrangian is defined by

L(x,y*)=infy∈Y{F(x,y)−y*(y)}.

In particular the weak duality minmax equation can be shown to be

supy*∈Y*−F*(0,y*)=supy*∈Y*infx∈XL(x,y*)≤infx∈Xsupy*∈Y*L(x,y*)=infx∈XF(x,0).

If the primal problem is given by

infx:g(x)≤0f(x)=infx∈Xf~(x)

where f~(x)=f(x)+Iℝ+d(−g(x)). Then if the perturbation is given by

infx:g(x)≤yf(x)

then the perturbation function is

F(x,y)=f(x)+Iℝ+d(y−g(x)).

Thus the connection to Lagrangian duality can be seen, as L can be trivially seen to be

L(x,y*)={f(x)−y*(g(x))if y*∈ℝ−d,−∞else.

### Fenchel duality

Let (X,X*) and (Y,Y*) be dual pairs. Assume there exists a linear map T:X->Y with adjoint operator T*:Y*->X*. Assume the primal objective function f(x) (including the constraints by way of the indicator function) can be written as f(x)=J(x,Tx) such that J:X×Y->ℝ∪{+∞}. Then the perturbation function is given by

F(x,y)=J(x,Tx−y).

In particular if the primal objective is f(x)+g(Tx) then the perturbation function is given by F(x,y)=f(x)+g(Tx−y), which is the traditional definition of Fenchel duality.[5]

## References

1. ↑ 1.0 1.1 1.2 Radu Ioan Boţ; Gert Wanka; Sorin-Mihai Grad (2009). Duality in Vector Optimization. Springer. ISBN 978-3-642-02885-4.
2. ↑ J. P. Ponstein (2004). Approaches to the Theory of Optimization. Cambridge University Press. ISBN 978-0-521-60491-8.
3. ↑ 3.0 3.1 3.2 Zălinescu, C. (2002). Convex analysis in general vector spaces. River Edge, NJ: World Scientific Publishing Co., Inc. pp. 106–113. ISBN 981-238-067-1.
4. ↑ Ernö Robert Csetnek (2010). Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3.
5. ↑ Radu Ioan Boţ (2010). Conjugate Duality in Convex Optimization. Springer. p. 68. ISBN 978-3-642-04899-9.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Perturbation function. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Perturbation_function&oldid=277562"