Penalty method

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.

Example

Let us say we are solving the following constrained problem:

subject to

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

where

In the above equations, is the penalty function while are the penalty coefficients. In each iteration k of the method, we increase the penalty coefficient (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 eventually converge to the solution of the original constrained problem.

Practical application

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

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.

See also

• Barrier function
• Interior point method
• Augmented Lagrangian method

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.

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

v t e Optimization: Algorithms, methods, and heuristics   Unconstrained nonlinear: Methods calling ... ... functions Golden section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation ... and gradients Convergence Trust region Wolfe conditions Quasi–Newton BFGS and L-BFGS DFP Symmetric rank-one (SR1) Other methods Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient ... and Hessians Newton's method   Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming   Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-Exchange Simplex algorithm of Dantzig Criss-cross algorithm Principal pivoting algorithm of Lemke   Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch & bound or cut Graph algorithms Minimum spanning tree Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal Network flows Dinic Edmonds–Karp Ford–Fulkerson Push-relabel maximum flow   Metaheuristics Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search Categories Algorithms and methods Heuristics Software