Penalty method

In mathematical optimization, penalty methods are a certain class of algorithms for solving constrained optimization problems. 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 a penalty function, to the objective function that consists of a penalty parameter multiplied 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.

In mathematical optimization, penalty methods are a certain class of algorithms for solving constrained optimization problems. 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 a penalty function, to the objective function that consists of a penalty parameter multiplied 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. \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 the exterior penalty function while p is the penalty coefficient. When the penalty coefficient p is 0, f p = f, meaning that we do not take the constraints into account. 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 the quadratic penalty function and the deadzone-linear penalty function.

References

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. [https://www.ams.org/bull/1943-49-01/S0002-9904-1943-07818-4/S0002-9904-1943-07818-4.pdf 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1282620350 under CC BY-SA 4.0; modifications have been made.