Metody i algorytmy optymalizacji- wykład 9

Nasza ocena:

5
Pobrań: 210
Wyświetleń: 1148
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Metody i algorytmy optymalizacji- wykład 9 - strona 1 Metody i algorytmy optymalizacji- wykład 9 - strona 2 Metody i algorytmy optymalizacji- wykład 9 - strona 3

Fragment notatki:

Metody i algorytmy optymalizacji dr Helena Spyra Wykład 9
PROGRAMOWANIE WYPUKŁE
f (X) → min
przy warunkach: gi(X) ≤ 0 i€In={1,…,r} funkcja f (X) jest wypukła i obszar rozwiązań dopuszczalnych D jest wypukły.
Zbiór D nazywamy wypukłym, jeżeli dla dowolnych X1, X2 € D i dowolnych również należy do U.
Funkcja f (X) nazywamy wypukłą, jeżeli dla dowolnych X1, X2 € D , dowolnych Jeżeli funkcja wypukła osiąga w punkcie X0 minimum , to jest to minimum globalne. Jeżeli f(x) jest funkcją wypukłą, to zbiór
Q = { X: f (X) ≤ α } jest wypukły dla dowolnego α Iloczyn mnogościowy skończonej ilości zbiorów wypukłych jest zbiorem wypukłym
Jeżeli f (X) jest klasy C2, to następujące zdania są rownoważne:
f (X) jest wypukla
dla dowolnych X1,X2 hesjan jest dodatnio określony w każdym punkcie określoności funkcji.
Funkcja f (X) jest wypukła wtedy iylko wtedy, gdy dla dowolnego X* i R ≠ 0 funkcja h(X) = f (X*+ t∙R) jest wypukła.
Zadania programowania wypukłego postaci:
f (X) = ½ XTCX + PTX → min
przy ograniczeniach: AX = P0 X ≥ 0
tworzą klasę zadań programowania kwadratowego.
Algorytmy dla zadań programowania wypukłego
1. Punktem startowym jest dowolny punkt X0 € D
2. Punkt ciężkości zasady generowania ciągu { Xk } przenosi się na określanie kierunków przemieszczania Rk dopuszczalnych i użytecznych dla minimalizacji i wyznaczanie punktu Xk+1 jako: Xk+1 = Xk + tk*Rk tak, aby 3. Postępowanie zostaje zakończone w punkcie, w którym spełnio­ne są warunki optymalności Kuhna-Tuckera.
(charakterystyczne własności każdego z algorytmów są związane ze sposobem okreś­lania wektorów Rk )
algorytmy kierunków dopuszczalnych Algorytm Beale'a
f (X) = ½ XTCX → min przy graniczeniach AX = P0 X ≥ 0 (należy do procedur wzorujących się na znanej programowaniu liniowym metodzie simpleks) Postępowanie rozpoczynamy w dowolnym punkcie będący


(…)

… której argumentami są zmienne niebazowe. Wartości tej funkcji ozn. ui Dla xs = xs* wartością tej funkcji jest u1 = 0.
W naszym zadaniu równanie jest równaniem liniowym, którego jedynym z rozwiązań jest xs = xs* dla zerowych wartości pozostałych zmiennych, w tym również u1 .
Jeżeli równanie dołączymy do ukła­du równań BXB + NXN = P0 to otrzymamy układ równań liniowych, którego rozwiązaniem bazowym będzie punkt o składowych XB oraz dodatkowej składowej xs z równania Pozostałe zmienne otrzymanego układu będą zmiennymi niebazowymi. Otrzymujemy ponownie sytuację znaną z metody simpleks i możemy wyrazić funkcję kryterium-jako funk­cję nowych zmiennych niebazowych a następnie przeprowadzić analizę optymalności rozwiązania przez badanie wartości pochodnych cząstkowych zmodyfikowanej funkcji kryterium.
Zmienna swobodna u1 może przybie­rać dowolne wartości, tak, aby żadna ze zmiennych xj nie stała się ujemna i aby zmiana wartości u1 prowadziła do zmniejszenia się wartości funkcji kryterium.
Jeżeli pochodna cząstkowa zmodyfikowanej funkcji kryterium ze względu na u1 jest różna od zera, to zmniejszenie wartości funkcji f(X) możemy uzyskać:
-zmniejszając wartości u1 gdy pochodna jest dodatnia
-zwiększając wartości u1 gdy pochodna jest ujemna
Zmienna u1 jest nieograniczoną co do znaku, możemy ją traktować na równi z pozostałymi, w praktyce okazuje się , że korzyst­nie jest stosować regułę preferencji; jeżeli analiza pochodnych cząstkowych wskazuje, że zmienną bazową może stać się zmienna niebazowa xs lub zmienna u, należy preferować zmienną u . Zmienna u1 powinna stać się zmienną bazową, lecz prowadzi to do wyrugowania jej z zadania…
…. Gk -wektor gradientu f (X) w punkcie Xk.
Oznaczmy symbolem Ni (i= 1, ...,m) kolumnowy wektor współczynników lewej strony i-tej nierówności ograniczeń:
Ni/ = [ai1 ... ain]
Przyjmijmy, źe w punkcie Xk nierówności 1, ...,s są spełnione jako równości. Utwórzmy macierz Qk = [N1 ... Ns] i wyznaczmy tzw. macierz rzuto­wania :
Pk=I-Qk(QkTQk)-1QkT I oznacza macierz jednostkową. Jeżeli s = 0, to przyjmujemy…
... zobacz całą notatkę



Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz