Active set-metoden

Från Wikipedia
Hoppa till: navigering, sök

Active set-metoden är en metod inom optimeringsläran för att hitta en lösning till ett program. I synnerhet behandlar den icke-linjära program med olikhetsbivillkor (eller en blandning av likhetsbivillkor och olikhetsvillkor). För att lösa programmet ansätts en mängd (active set) av olikhetsbivillkoren till att vara likhetsbivillkor, och programmet löses för denna mängd. Sedermera tar man i ett steg i den optimala riktningen med aspekt på hur långt steg samtliga bivillkor tillåter. Det upprepas till dess att en optimal lösning för samtliga bivillkor har hittats.

Pseudoalgorithm[redigera | redigera wikitext]

Givet att \ x_k är en tillåten punkt. Starta med \ k=0.

  • Om \Z^T \nabla f(x_k)
    • Beräkna lagrangemultiplikatorerna \lambda=A^T \nabla f(x_k)
    • Om \lambda \ge 0 avbryt. (Punkten är ett optimum).
    • Annars släpp ett av de bivillkor som har en negativ lagrangemultiplikator.
  • Beräkna den optimala sökriktning \ p (ex.vis. kan Newtonriktningen användas).
  • Beräkna steglängden \ \alpha i sökriktningen sådan att bivillkoren upprätthålls.
  • Beräkna den nya punkten \ x_{k+1}=x_k+p\alpha och starta om från början.

Med A betecknas bivillkorsmatrisen, \ Z dess nollrumsmatris, och \ f(x) är målfunktionen.