Metoda zestawu aktywnego

W optymalizacji matematycznej metoda aktywnego zestawu jest algorytmem używanym do identyfikacji aktywnych ograniczeń w zbiorze ograniczeń nierówności . Aktywne ograniczenia są następnie wyrażane jako ograniczenia równości, przekształcając w ten sposób problem ograniczony nierównością w prostszy podproblem ograniczony równością.

Problem optymalizacyjny definiuje się za pomocą funkcji celu minimalizującej lub maksymalizującej oraz zestawu ograniczeń

{\ Displaystyle g_ {1} (x) \ geq 0, \ kropki, g_ {k} (x) \ geq 0}

które definiują możliwy region , czyli zbiór wszystkich x do poszukiwania optymalnego rozwiązania. Biorąc $możliwym$ uwagę punkt w regionie, ograniczenie

{\ Displaystyle g_ {i} (x) \ geq 0}

, and inactive at $x$ if nazywa się aktywnym , jeśli ${\ Displaystyle g_ {i} (x_ {0}$ $)$ $g_{i}(x_{0})>0.$ Equality constraints are always active. The active set at $x_{0}$ is made up of those constraints $g_{i}(x_{0})$ that are active at the current point (Nocedal & Wright 2006, p. 308).

Zbiór aktywny jest szczególnie ważny w teorii optymalizacji, ponieważ określa, które ograniczenia będą miały wpływ na końcowy wynik optymalizacji. Na przykład, rozwiązując programowania liniowego , zbiór aktywny daje hiperpłaszczyzny , które przecinają się w punkcie rozwiązania. W programowaniu kwadratowym , ponieważ rozwiązanie niekoniecznie znajduje się na jednej z krawędzi wielokąta ograniczającego, oszacowanie aktywnego zbioru daje nam podzbiór nierówności do obserwowania podczas wyszukiwania rozwiązania, co zmniejsza złożoność wyszukiwania.

Metody zestawu aktywnego

Ogólnie algorytm zbioru aktywnego ma następującą strukturę:

Znajdź wykonalny punkt startowy

powtarzaj, aż „wystarczająco optymalny”

rozwiąż problem równości zdefiniowany przez aktywny zbiór (w przybliżeniu)

oblicz mnożniki Lagrange'a aktywnego zbioru

usuń podzbiór ograniczeń z ujemnymi mnożnikami Lagrange'a

wyszukaj niewykonalne ograniczenia

zakończ powtórzenie

Metody, które można opisać jako metody zestawu aktywnego, obejmują:

Sukcesywne programowanie liniowe (SLP)
Sekwencyjne programowanie kwadratowe (SQP)
Sekwencyjne programowanie liniowo-kwadratowe (SLQP)
Metoda zredukowanego gradientu (RG)
Uogólniona metoda zredukowanego gradientu (GRG)

Bibliografia

Murty, KG (1988). Komplementarność liniowa, programowanie liniowe i nieliniowe . Seria Sigma w matematyce stosowanej. Tom. 3. Berlin: Heldermann Verlag. s. xlviii + 629 s. ISBN 3-88538-403-5 . MR 0949214 . Zarchiwizowane od oryginału w dniu 2010-04-01 . Źródło 2010-04-03 .
Nocedal, Jorge; Wright, Stephen J. (2006). Optymalizacja numeryczna (wyd. 2). Berlin, Nowy Jork: Springer-Verlag . ISBN 978-0-387-30303-1 .