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.{{cite book|title=Duality in Vector Optimization|author1=Radu Ioan Boţ|author2=Gert Wanka|author3=Sorin-Mihai Grad|year=2009|publisher=Springer|isbn=978-3-642-02885-4}}

In some texts the value function is called the perturbation function, and the perturbation function is called the bifunction.{{cite book|title=Approaches to the Theory of Optimization|author=J. P. Ponstein|publisher=Cambridge University Press|year=2004|isbn=978-0-521-60491-8}}

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 \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 characteristic function. Then $F: X \times Y \to \mathbb{R} \cup \{+\infty\}$ is a perturbation function if and only if $F(x,0) = f(x)$ .{{cite book|last=Zălinescu|first=C.|title=Convex analysis in general vector spaces|publisher=World Scientific Publishing Co., Inc|location = River Edge, NJ |year=2002|pages=106–113|isbn=981-238-067-1|mr=1921556}}

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^*) \le \inf_{x \in X} F(x,0),$

where $F^*$ is the convex conjugate in both variables.{{cite book|title=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|author=Ernö Robert Csetnek|year=2010|publisher=Logos Verlag Berlin GmbH|isbn=978-3-8325-2503-3}}

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 \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 =

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.{{cite book|title=Conjugate Duality in Convex Optimization|author=Radu Ioan Boţ|publisher=Springer|year=2010|isbn=978-3-642-04899-9|page=68}}

References

Category:Linear programming

Category:Convex optimization