To tylko jedna z 10 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Metody i algorytmy optymalizacji dr Helena Spyra Wykład 10
Zadania dualne w programowaniu nieliniowym f ( X) → min
przy ograniczeniach gi(X) ≤ 0 i € In={1,…,r} X€ S
funkcja Lagrange'a: U ≥ 0 , Funkcję określoną dla X€S nazywamy funkcją prymalną
Funkcję określoną dla U ≥ 0 nazywamy funkcją dualną
Obsz. określ. zm X dla funkcji prymalnej jest obszar D.
Dla funkcji dualnej: Niech V ={ U: U ≥ 0 i istnieje min L(X,U) , X € S}
Dla U € V określmy zbiór
Ӿ (U) = { X : X minimalizuje L(X,U) na S }
Zbiór V jest obsz. określ. zmiennej U dla f. dualnej.
Funkcja dualna LD(U) jest wklęsła nad każdym wypukłym podzbiorem Przykład
f (X) = (x1 - 2)2 + (x2 - 1)2 → min
przy warunkach:
gi (X) = 2x1+ x2 - 2 ≤ 0
X € S = { X : X ≥ 0 }
L(X,U) = (x1 - 2)2 + (x2 - 1)2 + u (2x1 + x2 - 2) u ≥ 0
LD(U) = minX€S [(x1 -2)2 + (x2 -1)2 + u (2x1+x2 - 2)]=
= Traktując u jako parametr,
znajdujemy optymalne wartości zmiennych x1 i x2 na rys. F*(U)=LD(U)
Zadanie prymalne szukamy wektora X* € S dla którego
Zadanie dualne
poszukiwany jest wektor U* € V dla którego
LP(X*) = f (X*)
Dla dowolnych X € D U€ V
LD(U) ≤ LD(U*) ≤ LP(X*) ≤ LP(X)
Wykorzystanie otrzymanych nierówności w procedurach iteracyjnych
Ustalamy ε 0. Przyjmijmy, że po k-iteracjach wyznaczyliśmy pewien punkt Xk € D . Jeżeli następnie wyznaczymy Uk ≥ 0 taki, że: i dla tak określonych Xk, Uk będzie spełniona nierówność
Punkt Xk możemy traktować jako dostatecznie dobre przybliżenie punktu X*.
Jeżeli istnieją X*€ D i U* € V takie, że LP(X*) = LD(U*) to X* jest rozwiązaniem zadania prymalnego, a U* rozwiązaniem zadania dualnego.
(…)
…, że po k-iteracjach wyznaczyliśmy pewien punkt Xk € D . Jeżeli następnie wyznaczymy Uk ≥ 0 taki, że: i dla tak określonych Xk, Uk będzie spełniona nierówność
Punkt Xk możemy traktować jako dostatecznie dobre przybliżenie punktu X*.
Jeżeli istnieją X*€ D i U* € V takie, że LP(X*) = LD(U*) to X* jest rozwiązaniem zadania prymalnego, a U* rozwiązaniem zadania dualnego.
Punkt (X*,U*) jest punktem siodłowym…
… C1 i nie ma ograniczeń postaci X ≥ 0, czyli S = Rn L(X,U) = f (X)+ dla U ≥ 0 LD(U) = min X [f(x) + ui gi(x)] dla U≥ 0
Minimum to jest osiągnięte w punkcie, w którym
Zadanie dualne L(X,U) → max
przy ograniczeniach
Dualne zadania optymalizacji W punkcie siodłowym (X, U) funkcja F (X, U) osiąga minimum względem X oraz maksimum względem U. Punkt siodłowy (X, U) można wyznaczyć w dwojaki sposób, najpierw…
… taki dopuszczalny punkt X0, że gj(X0) < 0 j=1,...,J , zadanie to ma rozwiązanie X* to istnieje taki wektor U* ≥ 0, że para (X*, U*) jest rozwiązaniem zadania dualnego i f(X*)=fmin = Lmax = L(X*,U*) Odwrotnie, jeżeli para (X*, U*) jest rozwiązaniem zadania dualnego oraz L (X, U) ma ciągłe pochodne rzędu drugiego, a hesjan jest nieosobliwy, to X* jest rozwiązaniem zadania pierwotnego .
Przykład: f (X) = x12 + x22…
... zobacz całą notatkę
Komentarze użytkowników (0)