Penalty method

Penalty methods are a certain class of algorithms for solving constrained optimization problems.

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.

(e.g. by a factor of 10), solve the unconstrained problem and use the solution as the initial guess for the next iteration.

[2]: Thm.9.2.1 Assume that the objective f has bounded level sets, and that the original problem is feasible.

Then, there exists a neighborhood V* of x*, and some p0>0, such that for all p>p0, the penalized objective fp has exactly one critical point in V* (denoted by x*(p)), and x*(p) approaches x* as p→∞.

Also, the objective value f(x*(p)) is weakly-increasing with p. Image compression optimization algorithms can make use of penalty functions for selecting how best to compress zones of colour to single representative values.

[2]: Sub.9.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: Smith, Alice E.; Coit David W. Penalty functions Handbook of Evolutionary Computation, Section C 5.2.

Coello, A.C.[1]: Theoretical and Numerical Constraint-Handling Techniques Used with Evolutionary Algorithms: A Survey of the State of the Art.