Penalty method

From Wikipedia, the free encyclopedia

Penalty methods are a certain class of algorithms to solve constraint optimization problems.

The penalty method replaces a constraint optimization problem by a series of unconstrained problems whose solutions must converge to the solution of the original constrained problem. E.g. in the case of minimization with inequality constraints, the corresponding minimization problems are formed by adding a penalty term to the objective function. The penalty term grows when the constraints are violated and is 0 in the region where constraints are not violated. The penalty term is usually a product of a positive penalty coefficient and a penalty function.

[edit] Example

Let us say we are solving the following constrained problem:

\min f(\bold x)

subject to

c_i(\bold x) \le 0 ~\forall i \in I..

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

\min \Phi_i (\bold x) = f (\bold x) + \sigma_i ~ \sum_{i\in I} ~ g(c_i(\bold x))

where

g(c_i(\bold x))=\min(0,~c_i(\bold x)^2).

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

[edit] Barrier methods

Barrier methods are based on a similar idea. These methods also add a penalty term to the objective function, but with barrier methods, the penalty term grows without bound as one approaches the constraint.

Retrieved from "http://en.wikipedia.org../../../p/e/n/Penalty_method.html"