Perturbation function explained

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 of separated locally convex spaces

\left(X,X^*\right)

and

\left(Y,Y^*\right)

. Then given the function

f:X\toR\cup\{+infty\}

, we can define the primal problem by

inf_xf(x).

If there are constraint conditions, these can be built into the function

by letting

f\leftarrowf+I_constraints

where

is the characteristic function. Then

F:X x Y\toR\cup\{+infty\}

is a perturbation function if and only if

F(x,0)=f(x)

.^[3]

Use in duality

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

\sup
	y^*\inY^*

-F^*(0,y^*)\leinf_xF(x,0),

where

F^*

is the convex conjugate in both variables.^[4]

For any choice of perturbation function F weak duality holds. There are a number of conditions which if satisfied imply strong duality. For instance, if F is proper, jointly convex, lower semi-continuous with

0\in\operatorname{core}({\Pr}_{Y(\operatorname{dom}F))}

(where

\operatorname{core}

is the algebraic interior and

{\Pr}_Y

is the projection onto Y defined by

{\Pr}_Y(x,y)=y

) and X, Y are Fréchet spaces then strong duality holds.

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 x Y^*\toR\cup\{+infty\}

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^*)=inf_y\left\{F(x,y)-y^{*(y)\right\}.}

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

\sup
	y^*\inY^*

-F^*(0,y^*)=

\sup
	y^*\inY^*

inf_xL(x,y^*)\leqinf_x

\sup
	y^*\inY^*

L(x,y^*)=inf_xF(x,0).

If the primal problem is given by

inf_x:f(x)=inf_x\tilde{f}(x)

where

\tilde{f}(x)=f(x)+

	d
R
	+

(-g(x))

. Then if the perturbation is given by

inf_x:f(x)

then the perturbation function is

F(x,y)=f(x)+

	d
R
	+

(y-g(x)).

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

L(x,y^*)=\begin{cases}f(x)-y^*(g(x))&ify^*\in

	d
R
	-,

\\ -infty&else. \end{cases}

Fenchel duality

See main article: Fenchel duality. Let

(X,X^*)

and

(Y,Y^*)

be dual pairs. Assume there exists a linear map

T:X\toY

with adjoint operator

T^*:Y^*\toX^*

. 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 x Y\toR\cup\{+infty\}

. 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]

Notes and References

Book: Duality in Vector Optimization. Radu Ioan Boţ. Gert Wanka. Sorin-Mihai Grad. 2009. Springer. 978-3-642-02885-4.
Book: Approaches to the Theory of Optimization. J. P. Ponstein. Cambridge University Press. 2004. 978-0-521-60491-8.
Book: Zălinescu, C.. Convex analysis in general vector spaces. World Scientific Publishing Co., Inc. River Edge, NJ . 2002. 106–113. 981-238-067-1. 1921556.
Book: 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. Ernö Robert Csetnek. 2010. Logos Verlag Berlin GmbH. 978-3-8325-2503-3.
Book: Conjugate Duality in Convex Optimization. Radu Ioan Boţ. Springer. 2010. 978-3-642-04899-9. 68.