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.
Let and be dual pairs. Given a primal problem (minimize f(x)) and a related perturbation function (F(x,y)) then the Lagrangian is the negative conjugate of F with respect to y (i.e. the concave conjugate). That is the Lagrangian is defined by
In particular the weak duality minmax equation can be shown to be
If the primal problem is given by
where . Then if the perturbation is given by
then the perturbation function is
Thus the connection to Lagrangian duality can be seen, as L can be trivially seen to be
Let and be dual pairs. Assume there exists a linear map with adjoint operator. Assume the primal objective function (including the constraints by way of the indicator function) can be written as such that . Then the perturbation function is given by
In particular if the primal objective is then the perturbation function is given by , which is the traditional definition of Fenchel duality.
^ abcRadu Ioan Boţ; Gert Wanka; Sorin-Mihai Grad (2009). Duality in Vector Optimization. Springer. ISBN978-3-642-02885-4.
^J. P. Ponstein (2004). Approaches to the Theory of Optimization. Cambridge University Press. ISBN978-0-521-60491-8.
^ abcZălinescu, C. (2002). Convex analysis in general vector spaces. River Edge, NJ,: World Scientific Publishing Co., Inc. pp. 106–113. ISBN981-238-067-1. MR1921556.
^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. ISBN978-3-8325-2503-3.