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.

The use of negative penalty parameters was introduced in 1999 (see references below) in modelling the constraints of structural systems for the purpose of calculating natural frequencies using the Rayleigh-Ritz method. For such problems, the sign of the error due to violation of the constraint condtions(s) depends on the sign of the penalty coefficient. From this, it has now been shown that the error due to the violation of the constraint by using the penalty method can be determined and controlled by using a combination of positive and negative penalty parameters.

[edit] Example

Let us say we are solving the following constrained problem:

\min f(\bold x)

subject to

c_i(\bold x) \ge 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.

[edit] References

Ilanko. S., Asymptotic modelling theorems for the static analysis of linear elastic structures, Royal Society Proceedings A (Mathematical, Physical and Engineering Sciences) v 461, No. 2063, 2005: 3525–3542

Ilanko. S., Introducing the Use of Positive and Negative Inertial Functions in asymptotic modeling, Royal Society Proceedings A (Mathematical, Physical and Engineering Sciences) v461, No.2060, 2005: 2524-2562

Ilanko, S. and Dickinson, S.M., Asymptotic modelling of rigid boundaries and connections in the Rayleigh-Ritz Method. Journal of Sound and Vibration, v219, 1999:370-378.