430 2

430

10. Optymalizacja

W zasadzie te metody można by uogólnić na zadania optymalizacji z dowolny^ funkcjami i dowolnymi warunkami, aproksymując je lokalnie zadaniami liniowo* -kwadratowymi. Trzeba przy tym dołączać dcdaikowe warunki aby zapewnić, jfc nie opuści obszaru, gdzie aproksymacja ma sens.

Należy zbadać możliwość redukcji liczby zmiennych i równań przez eliminaci w warunkach będących równaniami. Warunki będące nierównościami można niekiedy wyeliminować przez podstawienie; np. dla spełnienia warunku Xj2>Q możemy zmien-ć Xj na xf.

Dla poniższego zadania z warunkami typu równań istnieją też inne metody.

Znaleźć minimum funkcji

(10.5.18)    ę(x) (xeR_n) przy warunkach

»(x)=0    («(x)eR_m).

Metoda mnożników Laoranęe^!a sprowadza takie zadanie do znalezienia punktu stacjonarnego funkcji n + m zmiennych

ę>*(x,^)=xę>(x)+ż^T»(x)    (AeR„).

Niestety w tym punkcie funkcja w* nie osiąga ani minimum, ani maksimum, więc typowe techniki minimalizacji nie są dla niego skuteczne. Metoda Newtona nie rozróżnia jednak poszczególnych rodzajów punktów stacjonarnych i można w zasadzie z niej korzystać, jeśli uda się znaleźć zadowalający punkt początkowy.

Innym ciekawym pomysłem jest zastąpienie ograniczeń funkcją kary, tj. zmiana zadania na bezwarunkową minimalizację funkcji

(10.5.19)    p(x)=^*)+*"¹*^T(x)ii(x),

gdzie k jest bardzo małą liczbą. To nowe zadanie jest jednak źle uwarunkowane dla małych k.

Przy pewnych warunkach jego rozwiązanie można rozwinąć względem potęg parametru k:

(10.5.20)    x(*)*=<r₀+Arc,+**«*+...,

gdzie c₀ jest rozwiązaniem zadania z warunkami typu równań. Można więc minimalizować y(x) dla kilku niezbyt małych wartości k i stosować ekstrapolację Richardsona. Uź>o^c funkcji kary można interpretować jako technikę zanurzania; zob. $ 6.9.3. Początku** przybliżenia można obliczać za pomocą wzorów (6.9.11) i (6.9.12).

Przykład 10.5.1. Zminimalizować sumę x\ą-x\ przy warunku

u(x)==Xi+2XjX₂-r 3x2— 1 =0.

Inaczej mówiąc, znaleźć kierunek i długość mniejszej osi elipsy określonej przez ten *** runek. Dokładnym rozwiązaniem jest =2''^,,2—0.5 = 0.207107, x₂=0.5. StflffijjgM