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.<ref name="BWG">{{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}}</ref>
In some texts the value function is called the perturbation function, and the perturbation function is called the '''bifunction'''.<ref>{{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}}</ref>
== Definition == Given two dual pairs of separated locally convex spaces <math>\left(X,X^*\right)</math> and <math>\left(Y,Y^*\right)</math>. Then given the function <math>f: X \to \mathbb{R} \cup \{+\infty\}</math>, we can define the primal problem by
:<math>\inf_{x \in X} f(x). \, </math>
If there are constraint conditions, these can be built into the function <math>f</math> by letting <math>f \leftarrow f + I_\mathrm{constraints}</math> where <math>I</math> is the characteristic function. Then <math>F: X \times Y \to \mathbb{R} \cup \{+\infty\}</math> is a ''perturbation function'' if and only if <math>F(x,0) = f(x)</math>.<ref name="BWG" /><ref name="Zalinescu">{{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}}</ref>
== Use in duality == The duality gap is the difference of the right and left hand side of the inequality :<math>\sup_{y^* \in Y^*} -F^*(0,y^*) \le \inf_{x \in X} F(x,0),</math> where <math>F^*</math> is the convex conjugate in both variables.<ref name="Zalinescu" /><ref>{{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}}</ref>
For any choice of perturbation function ''F'' weak duality holds. There are a number of conditions which if satisfied imply strong duality.<ref name="Zalinescu" /> For instance, if ''F'' is proper, jointly convex, lower semi-continuous with <math>0 \in \operatorname{core}({\Pr}_Y(\operatorname{dom}F))</math> (where <math>\operatorname{core}</math> is the algebraic interior and <math>{\Pr}_Y</math> is the projection onto ''Y'' defined by <math>{\Pr}_Y(x,y) = y</math>) and ''X'', ''Y'' are Fréchet spaces then strong duality holds.<ref name="BWG" />
== Examples ==
=== Lagrangian === Let <math>(X,X^*)</math> and <math>(Y,Y^*)</math> be dual pairs. Given a primal problem (minimize ''f''(''x'')) and a related perturbation function (''F''(''x'',''y'')) then the '''Lagrangian''' <math>L: X \times Y^* \to \mathbb{R} \cup \{+\infty\}</math> is the negative conjugate of ''F'' with respect to ''y'' (i.e. the concave conjugate). That is the Lagrangian is defined by :<math>L(x,y^*) = \inf_{y \in Y} \left\{F(x,y) - y^*(y)\right\}.</math> In particular the weak duality minmax equation can be shown to be :<math>\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).</math>
If the primal problem is given by :<math>\inf_{x: g(x) \leq 0} f(x) = \inf_{x \in X} \tilde{f}(x)</math> where <math>\tilde{f}(x) = f(x) + I_{\mathbb{R}^d_+}(-g(x))</math>. Then if the perturbation is given by :<math>\inf_{x: g(x) \leq y} f(x)</math> then the perturbation function is :<math>F(x,y) = f(x) + I_{\mathbb{R}^d_+}(y - g(x)).</math> Thus the connection to Lagrangian duality can be seen, as ''L'' can be trivially seen to be :<math>L(x,y^*) = \begin{cases} f(x) - y^*(g(x)) & \text{if } y^* \in \mathbb{R}^d_-, \\ -\infty & \text{else}. \end{cases}</math>
=== Fenchel duality === {{main|Fenchel duality}} Let <math>(X,X^*)</math> and <math>(Y,Y^*)</math> be dual pairs. Assume there exists a linear map <math>T: X \to Y</math> with adjoint operator <math>T^*: Y^* \to X^*</math>. Assume the primal objective function <math>f(x)</math> (including the constraints by way of the indicator function) can be written as <math>f(x) = J(x,Tx)</math> such that <math>J: X \times Y \to \mathbb{R} \cup \{+\infty\}</math>. Then the perturbation function is given by : <math>F(x,y) = J(x,Tx - y).</math>
In particular if the primal objective is <math>f(x) + g(Tx)</math> then the perturbation function is given by <math>F(x,y) = f(x) + g(Tx - y)</math>, which is the traditional definition of Fenchel duality.<ref>{{cite book|title=Conjugate Duality in Convex Optimization|author=Radu Ioan Boţ|publisher=Springer|year=2010|isbn=978-3-642-04899-9|page=68}}</ref>
== References == {{Reflist}}
Category:Linear programming Category:Convex optimization