Encyclopedia

Perturbation function

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated August 2, 2022

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.

In some texts the value function is called the perturbation function, and the perturbation function is called the bifunction.

01Definition

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)$ .

02Use 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.

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.

03Examples

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.

Watch videos about Perturbation functionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Perturbation function”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.