Penalty method

Let us say we are solving the following constrained problem:

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

subject to

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

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

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+\sigma _{k}~\sum _{i\in I}~g(c_{i}(\mathbf {x} ))}$

where

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

In the above equations, ${\displaystyle g(c_{i}(\mathbf {x} ))}$ is the exterior penalty function while ${\displaystyle \sigma _{k}}$ are the penalty coefficients. In each iteration k of the method, we increase the penalty coefficient ${\displaystyle \sigma _{k}}$ (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.

Image compression optimization algorithms can make use of penalty functions for selecting how best to compress zones of colour to single representative values.[1][2]

Barrier methods constitute 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.

Other nonlinear programming algorithms:

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

Other links:

• Barrier function

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

Coello, A.C.: 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.