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 $\left(X,X^{*}\right)$ and $\left(Y,Y^{*}\right)$ . Then given the function $f:X\to \mathbb {R} \cup \{+\infty \}$ , we can define the primal problem by

\inf _{{x\in X}}f(x).\,

If there are constraint conditions, these can be built into the function $f$ by letting $f\leftarrow f+I_{\mathrm {constraints} }$ where $I$ is the indicator function. Then $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ 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

\sup _{{y^{*}\in Y^{*}}}-F^{*}(0,y^{*})\leq \inf _{{x\in X}}F(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\in \operatorname {core}(\operatorname {Pr}_{Y}(\operatorname {dom}F))$ (where $\operatorname {core}$ is the algebraic interior and $\operatorname {Pr}_{Y}$ is the projection onto Y defined by $\operatorname {Pr}_{Y}(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\times Y^{*}\to {\mathbb {R}}\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\in Y}}\left\{F(x,y)-y^{*}(y)\right\}.

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

\sup _{{y^{*}\in Y^{*}}}-F^{*}(0,y^{*})=\sup _{{y^{*}\in Y^{*}}}\inf _{{x\in X}}L(x,y^{*})\leq \inf _{{x\in X}}\sup _{{y^{*}\in Y^{*}}}L(x,y^{*})=\inf _{{x\in X}}F(x,0).

If the primal problem is given by

\inf _{{x:g(x)\leq 0}}f(x)=\inf _{{x\in X}}{\tilde {f}}(x)

where ${\tilde {f}}(x)=f(x)+I_{{{\mathbb {R}}_{+}^{d}}}(-g(x))$ . Then if the perturbation is given by

\inf _{{x:g(x)\leq y}}f(x)

then the perturbation function is

F(x,y)=f(x)+I_{{{\mathbb {R}}_{+}^{d}}}(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))&{\text{if }}y^{*}\in {\mathbb {R}}_{+}^{d}\\-\infty &{\text{else}}\end{cases}}

Fenchel duality

Main article: Fenchel duality

Let $(X,X^{*})$ and $(Y,Y^{*})$ be dual pairs. Assume there exists a linear map $T:X\to Y$ with adjoint operator $T^{*}:Y^{*}\to 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\times Y\to {\mathbb {R}}\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]

References

1 2 3 Radu Ioan Boţ; Gert Wanka; Sorin-Mihai Grad (2009). Duality in Vector Optimization. Springer. ISBN 978-3-642-02885-4.
↑ J. P. Ponstein (2004). Approaches to the Theory of Optimization. Cambridge University Press. ISBN 978-0-521-60491-8.
1 2 3 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. MR 1921556.
↑ 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.
↑ Radu Ioan Boţ (2010). Conjugate Duality in Convex Optimization. Springer. p. 68. ISBN 978-3-642-04899-9.

This article is issued from Wikipedia - version of the 5/30/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.