# Penalty functions, method of

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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)