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 on a set in an -dimensional Euclidean space. A penalty function, or penalty (for violating the restrictions , ), is a function depending on and a numerical parameter with the following properties: if and if . Let be any point where the function takes an unconstrained (global) minimum, and let be the set of solutions of the original problem. The function is chosen such that the distance between the points and the set tends to zero for , or, if it is not possible to ensure this condition, such that the following relation holds:

For one often chooses the function

(frequently ).

The choice of a particular form for the function is connected both with the problem of convergence of the method of penalty functions, and with problems arising in the unconstrained minimization of .

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

The following well-known general result shows that the method of penalty functions is universal. Let and be reflexive Banach spaces (cf. Reflexive space); let be the extended real line; let be a function defined on with values in that is weakly lower semi-continuous (cf. Semi-continuous function); let , , be functions defined on with values in that are continuous in the weak topology of ; let , , be functions defined on , with values in , that are continuous in the weak topologies of the spaces and (cf. Weak topology); and let the set be non-empty. Consider the problem of finding those for which

(*)

For the function

with , , , , consider the problem of finding those and , , for which

for all , , . If

then any weak limit point of an arbitrary sequence , , , is a solution of the problem (*) and, moreover,

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)