Penalty functions, method of

A method for reducing constrained extremum problems to problems of unconstrained optimization. The method of penalty functions may be illustrated for problems in mathematical programming. Consider the problem of minimizing a function $ \phi ( x) $ on a set $ X = \{ {x } : {f _ {i} ( x) \geq 0, i = 1 \dots m } \} $ in an $ n $- dimensional Euclidean space. A penalty function, or penalty (for violating the restrictions $ f _ {i} ( x) \geq 0 $, $ i = 1 \dots m $), is a function $ \psi ( x, \alpha ) $ depending on $ x $ and a numerical parameter $ \alpha $ with the following properties: $ \psi ( x, \alpha ) = 0 $ if $ x \in X $ and $ \psi ( x, \alpha ) > 0 $ if $ x \notin X $. Let $ x( \alpha ) $ be any point where the function $ M( x, \alpha ) = \phi ( x) + \psi ( x, \alpha ) $ takes an unconstrained (global) minimum, and let $ X ^ \star $ be the set of solutions of the original problem. The function $ \psi ( x, \alpha ) $ is chosen such that the distance between the points $ x( \alpha ) $ and the set $ X ^ \star $ tends to zero for $ \alpha \rightarrow \infty $, or, if it is not possible to ensure this condition, such that the following relation holds:

$$ \lim\limits _ {\alpha \rightarrow \infty } \phi ( x( \alpha )) = \ \inf _ {x \in X } \phi ( x). $$

For $ \psi ( x, \alpha ) $ one often chooses the function

$$ \psi ( x, \alpha ) = \alpha \sum _ { i= } 1 ^ { m } | \min \{ f _ {i} ( x), 0 \} | ^ {q} ,\ \ q \geq 1 $$

(frequently $ q = 2 $).

The choice of a particular form for the function $ \psi ( x, \alpha ) $ is connected both with the problem of convergence of the method of penalty functions, and with problems arising in the unconstrained minimization of $ M( x, \alpha ) $.

A more general statement of the method of penalty functions is based on reducing the problem of minimization of $ \phi ( x) $ on a set $ X $ to the problem of minimizing some parametric function $ M( x, \alpha ) $ on a set of simpler structure (from the point of view of efficiency of applying numerical minimization methods) than the initial set $ X $.

The following well-known general result shows that the method of penalty functions is universal. Let $ U $ and $ V $ be reflexive Banach spaces (cf. Reflexive space); let $ \overline{\mathbf R}\; $ be the extended real line; let $ \phi $ be a function defined on $ U $ with values in $ \overline{\mathbf R}\; $ that is weakly lower semi-continuous (cf. Semi-continuous function); let $ f _ {i} $, $ i = 1 \dots m $, be functions defined on $ U $ with values in $ \overline{\mathbf R}\; $ that are continuous in the weak topology of $ U $; let $ h _ {j} $, $ j = 1 \dots n $, be functions defined on $ U $, with values in $ V $, that are continuous in the weak topologies of the spaces $ U $ and $ V $( cf. Weak topology); and let the set $ X = \{ {x } : {f _ {i} ( x) \geq 0, i = 1 \dots m, h _ {j} ( x) = 0, j = 1 \dots n, x \in U } \} $ be non-empty. Consider the problem of finding those $ x ^ \star \in U $ for which

$$ \tag{* } \phi ( x ^ \star ) \leq \phi ( x) \ \textrm{ for } \textrm{ all } x \in X. $$

For the function

$$ M( x, y _ {1} \dots y _ {m} , \alpha ) = \phi ( x) + $$

$$ + \alpha \left \{ \sum _ { i= } 1 ^ { m } | f _ {i} ( x) - y _ {i} | ^ {2} + \sum _ { j= } 1 ^ { n } \| h _ {j} ( x) \| _ {V} ^ {2} \right \} $$

with $ \alpha > 0 $, $ x \in U $, $ y _ {i} \in \mathbf R $, $ i = 1 \dots m $, consider the problem of finding those $ x( \alpha ) \in U $ and $ y _ {i} ( \alpha ) \geq 0 $, $ i = 1 \dots m $, for which

$$ M( x( \alpha ), y _ {1} ( \alpha ) \dots y _ {m} ( \alpha ), \alpha ) \leq $$

$$ \leq \ M( x, y _ {1} \dots y _ {m} , \alpha ) $$

for all $ x \in U $, $ y _ {i} \geq 0 $, $ i = 1 \dots m $. If

$$ \lim\limits _ {\| x \| \rightarrow \infty } \phi ( x) = + \infty , $$

then any weak limit point of an arbitrary sequence $ \{ x( \alpha _ {k} ) \} $, $ \alpha _ {k} \rightarrow \infty $, $ k \rightarrow \infty $, is a solution of the problem (*) and, moreover,

$$ \lim\limits \phi ( x( \alpha )) = \phi ( x ^ \star ),\ \ \alpha \rightarrow \infty . $$

References

[1]	N.N. Moiseev, Yu.P. Ivanilov, E.M. Stolyarova, "Methods of optimization" , Moscow (1978) (In Russian)
[2]	F.P. Vasil'ev, "Numerical methods for the solution of extremum problems" , Moscow (1980) (In Russian)
[3]	A.V. Fiacco, G.P. MacCormick, "Nonlinear programming: Sequential unconstrained minimization techniques" , Wiley (1968)
[4]	J. Cea, "Lectures on optimization: theory and algorithms" , Springer (1978)

Comments

In the last two decades, new developments in the area of penalty function methods, namely multiplier penalty function methods (or augmented Lagrangian methods) and exact penalty function methods, have replaced for the most part the use of pure penalty function methods. See [a1].

References

[a1]	R. Fletcher, "Practical methods of optimization" , Wiley (1987)
[a2]	D.C. Luenberger, "Optimization by vector space methods" , Wiley (1969)
[a3]	A.L. Peressini, F.E. Sullivan, J.J. Uhl, "The mathematics of nonlinear programming" , Springer (1988)