Penalty method

Penalty method

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.

Example

Let us say we are solving the following constrained problem:: min f(old x) subject to: c_i(old x) ge 0 ~forall i in I. .

This problem can be solved as a series of unconstrained minimization problems: min Phi_i (old x) = f (old x) + sigma_i ~ sum_{iin I} ~ g(c_i(old x)) where: g(c_i(old x))=min(0,~c_i(old x))^2.

In the above equations, "g"("c"(x)) is the "penalty function" while sigma_k are the "penalty coefficients". In each iteration "k" of the method, we increase the penalty coefficient sigma_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.

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.

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.

Courant, R. [http://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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Penalty shootout (association football) — Penalty shootouts, properly named kicks from the penalty mark, are a method sometimes used to decide which team progresses to the next stage of a tournament (or wins the tournament) following a draw in a game of football. Kicks during a shootout… …   Wikipedia

  • Penalty shot (ice hockey) — In ice hockey, a penalty shot is a type of penalty awarded when a team loses a clear scoring opportunity on a breakaway because of a foul committed by an opposing player. A player from the non offending team is given an attempt to score a goal… …   Wikipedia

  • Penalty shootout — A penalty shootout or simply shootout is a method of determining a winner in sports matches that would have otherwise been drawn or tied. The rules for penalty shootouts vary between sports and even different competitions; however, the usual form …   Wikipedia

  • Penalty — A penalty is generally a punishment, and may refer to:In law: * Penalty, a sentence (decree of punishment) issued by a court or judge * Penalty, sanctions imposed by a court or judgeIn sports: * Penalty, used to refer to any of various fouls in… …   Wikipedia

  • penalty shootout — /pɛnəlti ˈʃutaʊt/ (say penuhltee shoohtowt) noun Hockey, etc., Soccer a method of deciding a match after a tied game, in which each team is given equal opportunity to score penalty goals, the team scoring the greatest number being declared the… …  

  • Capital Punishment (Death Penalty) —     Capital Punishment     † Catholic Encyclopedia ► Capital Punishment     The infliction by due legal process of the penalty of death as a punishment for crime.     The Latins use the word capitalis (from caput, head) to describe that which… …   Catholic encyclopedia

  • Fixed Amortization Method — One of three methods by which early retirees of any age can access their retirement funds without penalty before turning 50.5. The fixed amortization method amortizes the retiree s account balance over his/her remaining life expectancy as… …   Investment dictionary

  • Fixed Annuitization Method — One of three methods by which early retirees of any age can access their retirement funds without penalty before turning 50.5. The fixed annuitization method divides the retiree s account balance by an annuity factor taken from IRS tables to… …   Investment dictionary

  • Required Minimum Distribution Method — One of three methods by which early retirees of any age can access their retirement funds without penalty before turning 59 ½. Normally, funds withdrawn before age 59 ½ are assessed a 10% early withdrawal penalty. Funds must be… …   Investment dictionary

  • Gap penalty — Gap penalties are used during sequence alignment. Gap penalties contribute to the overall score of alignments, and therefore, the size of the gap penalty relative to the entries in the similarity matrix affects the alignment that is finally… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”