Penalty method

Penalty methodsare a certain class ofalgorithmsfor solvingconstrained optimizationproblems.

A penalty method replaces a constrained optimization problem by a series of unconstrained problems whose solutions ideally converge to the solution of the original constrained problem. The unconstrained problems are formed by adding a term, called apenalty function,to theobjective functionthat consists of apenalty parametermultiplied by a measure of violation of the constraints. The measure of violation is nonzero when the constraints are violated and is zero in the region where constraints are not violated.

Description

Let us say we are solving the following constrained problem:

$\min _{x}f(\mathbf {x} )$

subject to

$c_{i}(\mathbf {x} )\leq 0~\forall i\in I.$

This problem can be solved as a series of unconstrained minimization problems

$\min f_{p}(\mathbf {x} ):=f(\mathbf {x} )+p~\sum _{i\in I}~g(c_{i}(\mathbf {x} ))$

where

$g(c_{i}(\mathbf {x} ))=\max(0,c_{i}(\mathbf {x} ))^{2}.$

In the above equations,$g(c_{i}(\mathbf {x} ))$is theexterior penalty functionwhile$p$is thepenalty coefficient.When the penalty coefficient is 0,f_p=f.In each iteration of the method, we increase the penalty coefficient$p$(e.g. by a factor of 10), solve the unconstrained problem and use the solution as the initial guess for the next iteration. Solutions of the successive unconstrained problems will asymptotically converge to the solution of the original constrained problem.

Common penalty functions in constrained optimization are thequadraticpenalty function and the deadzone-linearpenalty function.

Convergence

We first consider the set of global optimizers of the original problem, X*.Assume that the objectivefhas boundedlevel sets,and that the original problem is feasible. Then:

• For every penalty coefficientp,the set of global optimizers of the penalized problem, X_p*, is non-empty.
• For every ε>0, there exists a penalty coefficientpsuch that the set X_p* is contained in an ε-neighborhood of the set X*.

This theorem is helpful mostly whenf_pis convex, since in this case, we can find the global optimizers off_p.

A second theorem considers local optimizers.Let x* be a non-degenerate local optimizer of the original problem ( "nondegenerate" means that the gradients of the active constraints are linearly independent and the second-order sufficient optimality condition is satisfied). Then, there exists a neighborhood V* of x*, and somep₀>0, such that for allp>p₀,the penalized objectivef_phas exactly one critical point in V* (denoted by x*(p)), and x*(p) approaches x* asp→∞. Also, the objective valuef(x*(p)) is weakly-increasing withp.

Practical applications

Image compressionoptimization algorithms can make use of penalty functions for selecting how best to compress zones of colour to single representative values.The penalty method is often used in computational mechanics, especially in theFinite element method,to enforce conditions such as e.g.contact.

The advantage of the penalty method is that, once we have a penalized objective with no constraints, we can use any unconstrained optimization method to solve it. The disadvantage is that, as the penalty coefficientpgrows, the unconstrained problem becomesill-conditioned- the coefficients are very large, and this may cause numeric errors and slow convergence of the unconstrained minimization.

See also

Barrier methodsconstitute an alternative class of algorithms for constrained optimization. These methods also add a penalty-like term to the objective function, but in this case the iterates are forced to remain interior to the feasible domain and the barrier is in place to bias the iterates to remain away from the boundary of the feasible region. They are practically more efficient than penalty methods.

Augmented Lagrangian methodsare alternative penalty methods, which allow to get high-accuracy solutions without pushing the penalty coefficient to infinity. This makes the unconstrained penalized problems easier to solve.

Other nonlinear programming algorithms:

• Sequential quadratic programming
• Successive linear programming
• Sequential linear-quadratic programming
• Interior point method

References

Smith, Alice E.;Coit David W.Penalty functionsHandbook of Evolutionary Computation, Section C 5.2. Oxford University Press and Institute of Physics Publishing, 1996.

Coello, A.C.[1]:Theoretical and Numerical Constraint-Handling Techniques Used with Evolutionary Algorithms: A Survey of the State of the Art. Comput. Methods Appl. Mech. Engrg. 191(11-12), 1245-1287

Courant, R.Variational methods for the solution of problems of equilibrium and vibrations.Bull. Amer. Math. Soc., 49, 1–23, 1943.

Wotao, Y.Optimization Algorithms for constrained optimization.Department of Mathematics, UCLA, 2015.