# Perturbation function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Perturbation_function
> Markdown URL: https://mediated.wiki/source/Perturbation_function.md
> Source: https://en.wikipedia.org/wiki/Perturbation_function
> Source revision: 1101960764
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [mathematical optimization](/source/mathematical_optimization), the '''perturbation function''' is any [function](/source/function_(mathematics)) which relates to primal and [dual problem](/source/dual_problem)s.  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](/source/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 pair](/source/dual_pair)s of [separated](/source/separated_space) [locally convex space](/source/locally_convex_space)s <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](/source/Characteristic_function_(convex_analysis)).  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&nbsp; Co.,&nbsp;Inc|location = River Edge,&nbsp;NJ |year=2002|pages=106–113|isbn=981-238-067-1|mr=1921556}}</ref>

== Use in duality ==
The [duality gap](/source/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](/source/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](/source/weak_duality) holds.  There are a number of conditions which if satisfied imply [strong duality](/source/strong_duality).<ref name="Zalinescu" />  For instance, if ''F'' is [proper](/source/proper_convex_function), jointly [convex](/source/convex_function), [lower semi-continuous](/source/lower_semi-continuous) with <math>0 \in \operatorname{core}({\Pr}_Y(\operatorname{dom}F))</math> (where <math>\operatorname{core}</math> is the [algebraic interior](/source/algebraic_interior) and <math>{\Pr}_Y</math> is the [projection](/source/projection_(set_theory)) onto ''Y'' defined by <math>{\Pr}_Y(x,y) = y</math>) and ''X'', ''Y'' are [Fréchet space](/source/Fr%C3%A9chet_space)s 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](/source/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](/source/linear_map) <math>T: X \to Y</math> with [adjoint operator](/source/adjoint_operator) <math>T^*: Y^* \to X^*</math>. Assume the primal [objective function](/source/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](/source/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

---
Adapted from the Wikipedia article [Perturbation function](https://en.wikipedia.org/wiki/Perturbation_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Perturbation_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.