Materiały pomocnicze do ćwiczeń
z  Nowoczesnych metod sterowania
część 1. Zadania optymalizacji
ĆW.1 . Dobór optymalnej wartości jednej zmiennej przy zakłóceniach
pomiarów wskaz
nika. Sterowanie na ekstremum.
ĆW.2*. Przegląd algorytmów programowania nieliniowego.
ĆW.3. Optymalizacja statyczna w obecności zakłóceń.
Jan Leszczyński
Katedra Automatyki i Elektroniki
Politechnika Białostocka.
BIAA
YSTOK, 2002
2
ĆW.1. Dobór optymalnej wartości jednej zmiennej przy zakłóceniach
pomiarów wskaz
nika. Sterowanie na ekstremum.
W trakcie ćwiczenia badane są (program   ) iteracyjne algorytmy optymaliza-
cji jednowymiarowej w których po każdym nowym komplecie pomiarów następuje obliczenie
i ustawienie nowej wartości oddziaływania wejściowego. Z założenia dostępne są jedynie
bezpośrednio pomiary optymalizowanego wskaz
nika jakości, zakłócane realizacjami wielko-
ści losowej o rozkładzie normalnym.
Modelowany i badany jest także (plik   w ) układ regulacji ekstre-
malnej o charakterze ciągłym. W odróżnieniu od problemu stacjonarnego, wartość optymalna
sterowania w takim układzie regulacji może zmieniać się nieprzerwanie, a proces optymaliza-
cji odbywa się w czasie rzeczywistym. W modelu uwzględniana jest także dynamika sterowa-
nego procesu.
PRZED ĆWICZENIEM należy zapoznać się, na podstawie zestawienia A, z podstawowy-
mi typami algorytmów rozwiązywania zadania programowania nieliniowego jednej zmiennej,
a także na podstawie zestawienia B ze specyfiką rozwiązywania zadania optymalnego doboru
zmiennej (lub optymalizowanego parametru) w obecności zakłóceń pomiarowych. Wskaza-
nym jest także uzupełnienie wiedzy teoretycznej w trybie studiów literaturowych (uwagi bi-
bliograficzne z wykazem literatury zamieszczono na końcu instrukcji).
Pytania kontrolne:
Co nazywamy zbiorem wypukłym i funkcją wypukłą - podaj ścisłe definicje.
W jakiej sytuacji zadanie znalezienia ekstremum funkcji ma jednoznaczne rozwiązanie?
Jak formułuje się warunek zakończenia obliczeń przy posługiwaniu się algorytmem itera-
cyjnym optymalizacji?
Objaśnij na wybranym przykładzie działanie układu regulacji ekstremalnej.
PROGRAMOWANIE BADAC
SYMULACYJNYCH w trakcie ćwiczenia wspomagane
jest przez programy Matlaba umieszczone w plikach:   i   . Zaleca
się przeanalizowanie   . Program ten zamieszczono na następnej stronie. Wyzna-
czany jest w nim przebieg minimalizacji funkcji kwadratowej jednej zmiennej:
3
przy pomocy dwu algorytmów iteracyjnych przytoczonych w zestawieniu A: algorytmu po-
chodnej (1) i algorytmu  kroczącego z ustaloną wielkością potencjalnej poprawki (2).
% Przekazanie wyników:
Przytoczymy kilka komentarzy ułatwiających analizę programu.
4
1. Na początku ustalane są wartości wszystkich występujących w programie stałych. Wyraz
-
ne wydzielenie tego fragmentu programu ułatwia ich modyfikację w trakcie badań symu-
lacyjnych. Wartości początkowe parametrów badanych algorytmów są tu ustalone
przypadkowo.
2. Fragmenty programów, w których badane są skutki stosowania obu algorytmów są także
wyraz
nie wydzielone. Wydaje się, że z punktu widzenia eksperymentatora zmienić tu
można przede wszystkim ( de gustibus non est disputandum ) instrukcje związane
z przekazaniem otrzymanych rezultatów. Umieszczone są one na końcu obliczeń iteracyj-
nych związanych z każdą z reprezentowanych tu metod.
3. Każdą z występujących w programie stałych możemy także uczynić funkcją czasu (tj.
numeru iteracji). W tym przypadku powinniśmy jednak, oczywiście, umieścić określoną
instrukcję wewnątrz instrukcji cyklu. Np. możemy w instrukcji  for wprowadzić sinuso-
idalne przemieszczanie się punktu optymalnego charakterystyki zgodnie z równaniem:
umożliwiając w ten sposób symulację procesu śledzenia za przesuwającym się ekstremum.
4. Dostępna jest również modyfikacja tego programu w postaci m-pliku   po-
zwalająca jednocześnie uzyskać i porównać wyniki symulacji (przy optymalizacji algo-
rytmem (1)) dla określonego zbioru wartości analizowanego parametru.
Modelowanie jednej z wersji UKA
ADU REGULACJI EKSTREMALNEJ pozwala zbadać
wpływ dynamiki sterowanego obiektu na przebiegi procesów poszukiwania ekstremum na
jego charakterystyce statycznej. Sterowany obiekt stanowi szeregowe połączenie dwuwej-
ściowego statycznego elementu nieliniowego o charakterystyce kwadratowej:
połączonego szeregowo z liniowym elementem dynamicznym o transmitancji:
G0
Z założenia jest wielkością niesterowalna. Zmiany jej wywołują zmiany położenia
ekstremum na charakterystyce statycznej obiektu sterowania. W układzie (przedstawionym na
rys.1) stosowany jest ciągły proces poszukiwania aktualnego położenia ekstremum ze stałą
prędkością zmian wielkości sterującej . Kierunek zmian zależy od aktualnego znaku iloczy-
nu jej pochodnej i pochodnej wielkości wyjściowej.
5
Po doprowadzeniu do sterowanego obiektu zakłóceń o charakterze probabilistycznym
sytuacja się komplikuje. Należy wprowadzić dodatkowo do układu filtr dolnoprzepustowy
w celu wygładzenia przebiegu pochodnej wielkości wyjściowej.
__________________________________________________________________________
Mux
Generator
Rys.1. Model układu regulacji na ekstr emum.
f(u)
Rys.2. Model sterowanego obiektu z unimodalną charak-
terystyka statyczną.
PRZEBIEG ĆWICZENIA 1:
1. Należy przeprowadzić badania symulacyjne mające na celu dobór parametrów: " ą
w algorytmie poszukiwania minimum na kwadratowej charakterystyce procesu:
gdzie stała
Założenia (stałe � precyzuje wykładowca) przyjmowane w trakcie badań symula-
cyjnych:
6
 Pomiary wielkości wyjściowej y badanego procesu (lub jej pochodnej) obarczone są
losowymi zakłóceniami o rozkładzie normalnym: " �
Stosowany jest algorytm skończonych przyrostów:
ą " "
Badania możemy przeprowadzić przy pomocy  nms_1_a1 , lub analogicznego pro-
gramu opracowanego samodzielnie. W trakcie doświadczeń symulacyjnych należy dobie-
rać racjonalny poziom współczynnika wzmocnienia, określany przy pomocy
współczynnika ą i wartość " testującego przyrostu argumentu. Parametry dobieramy
w procesie minimalizacji (uśrednionych z wielu powtórzeń)  strat w trakcie procesu po-
szukiwania ekstremum przy pomocy algorytmów startujących z jednakowych warunków
początkowych. Straty można wyrazić najprościej poprzez sumę wartości wyjściowych ba-
danej funkcji (w ramach zadanej z góry, ograniczonej do liczby iteracji).
2. Należy przeprowadzić badania symulacyjne mające na celu dobór kroku " w algorytmie
poszukiwania minimum w postaci:
u(k+1) = u(k) - " sign["f(u)]|u(k) , k=0,1,2,...
Badania możemy przeprowadzić przy pomocy programu  nms_1 lub przy pomocy sa-
modzielnie opracowanych programów analogicznych do  nms_1_a1 .
Po doborze wielkości kroku ", należy porównać efekty działania algorytmu tego typu z
punktu widzenia strat na poszukiwanie ekstremum z algorytmem stosowanym uprzednio.
3. Sprawdzić jakościowo (rejestracja typowych przebiegów) proces śledzenia za wolno zmie-
niającym się położeniem punktu optymalnego. wprowadzanego np przy pomocy
Stosujemy przy tym algorytm z parametrami wybranymi
w trakcie dotychczasowej realizacji ćwiczenia.
4. Należy zamodelować układ regulacji ekstremalnej z rys. 1. Po zamodelowaniu zareje-
strować typowe przebiegi wielkości wejściowej i wyjściowej a także trajektorię fazową
7
w procesie sterowania. Jakie zmiany przebiegów obserwujemy przy zmianach stałej cza-
sowej (i wielkości opóz
nienia) w modelu sterowanego obiektu?
ZADANIE UZUPEA
NIAJ
CE:
Jaki program badań symulacyjnych należałoby przeprowadzić mając na celu ustalenie
zasady doboru parametrów ą i " w zależności od drugiej pochodnej i od wa-
riancji zakłóceń � ) pomiarów funkcji kryterialnej w danym zadaniu optymalizacji?
Rezultatem badań symulacyjnych powinno być wypracowanie i zwięzłe przekazanie zaleceń
na temat doboru parametrów " i ą przy rozwiązywaniu zadań optymalizacji analogicz-
nych do symulowanych w trakcie badań w ćwiczeniu. Zalecenia mogą przyjąć postać jako-
ściową, np. mogą być przekazane w formie odpowiedzi na pytania typu:
Czy ze wzrostem drugiej pochodnej parametry ą , " powinny raczej rosnąć,
czy maleć?
Czy ze wzrost poziomu zakłóceń pomiarowych � powinien być sprzężony ze wzrostem,
czy też spadkiem parametrów ą , " ? Czy należałoby zmienić wówczas taktykę wy-
znaczania realizacji pochodnej?
SPRAWOZDANIE POWINNO ZAWIERAĆ:
Ilustratywne przekazanie wyników  m.in. w postaci tabel z uśrednionymi wskaz
nikami
jakości procesów optymalizacji w zależności od wyboru parametrów algorytmu, a także
w postaci graficznego porównania typowych realizacji procesów optymalizacji.
Wnioski i komentarze na temat przeprowadzonych badań, m.in. wypowiedz
na następują-
ce temat:
Która ze badanych w p.1, 2 metod optymalizacji okazała się skuteczniejszą?
Odpowiedz
należy uzasadnić posługując się argumentami opartymi na ścisłych wskaz
ni-
kach (efekt końcowy, liczba iteracji, itp.).
8
ĆW.2. Przegląd algorytmów programowania nieliniowego.
Główne składową danego ćwiczenia stanowią programowane badania symulacyjne
wybranych algorytmów programowania nieliniowego W badaniach tych, prowadzo-
nych przy pomocy przygotowanego programu ( plik  , przestrzeń poszukiwa-
nia ekstremum jest dwuwymiarowa, a pomiary funkcji kryterialnej niezakłócone. W celu
zilustrowania problematyki uwzględnienia ograniczeń w przestrzeni poszukiwania,
w programie wprowadzono możliwość modyfikacji funkcji kryterialnej.
Zadaniem dodatkowym jest rozwiązywanie innych, wybranych zadań optymalizacji
w środowisku programowym
PRZED ĆWICZENIEM należy zapoznać się z podstawowymi rodzajami zadań programo-
wania nieliniowego, a także z przeglądem deterministycznych algorytmów programowania
nieliniowego z zestawienia C.
Pytania kontrolne:
Przedstaw sformułowanie zadania programowania nieliniowego z ograniczeniami.
Jaką cechę posiadają elementy zbioru Pareto definiowanego w ramach teorii optymaliza-
cji wielo-wskaz
nikowej?
W jaki sposób można uzyskać eksperymentalnie przybliżoną wartość gradientu badanej
funkcji przy możliwości bezpośredniego pomiaru jedynie jej wartości?
Wymień podstawowe typy algorytmów stosowanych przy rozwiązywaniu zadania progra-
mowania nieliniowego.
PROGRAMOWANIE OBLICZEC
w trakcie ćwiczenia wymaga zapoznania się z techniką
odnajdywania minimum funkcji wielu zmiennych przy pomocy matlabowskich m-funkcji
  i   z pakietu: , a także zapoznania się z przytoczonym
niżej programem  nms2 . Należy zapoznać się także z techniką przygotowywania danych do
rozwiązywania innych podstawowych zadań optymalizacji statycznej reprezentowanych
w tym pakiecie programowym: zadanie programowania liniowego, zadanie programowania
kwadratowego i zadanie programowania nieliniowego z ograniczeniami.
Pytania kontrolne:
" W jaki sposób wprowadzamy przy stosowaniu programów  i   informa-
cję o postaci analitycznej optymalizowanej funkcji?
" Kiedy wprowadzenie wyrażenia analitycznego gradientu optymalizowanej funkcji nie jest
konieczne?
9
" W jaki sposób ustala się maksymalną liczbę iteracji w procesie optymalizacji?
" W jaki sposób można uzyskać pośrednie wyniki procesu optymalizacji ?
Główny program badań obliczeniowych algorytmów optymalizacji funkcji wielu zmien-
nych umieszczono w pliku:  nms_2.m . Przekazuje on (w postaci liczbowej i analitycznej)
przebieg minimalizacji badanej funkcji przy zastosowaniu podstawowych metod programo-
wania nieliniowego. Pełny tekst programu  nms_2.m umieszczono na końcu instrukcji.
W tym miejscu zamieszczamy jedynie jego początek.
Przy analizie programu widocznym jest, że można podzielić go na kilka części.
Na początku zawarto instrukcje sporządzania wykresy funkcji dwu zmiennych na której
testowane są metody programowania nieliniowego. Przedstawiany jest zarówno jej wykres
w przestrzeni trójwymiarowej (  ) jak i warstwice (  ) na płaszczyz
nie
argumentów.
W dalszej części programu  nms_2.m (patrz Dodatek) widoczne jest menu i związane
z nim instrukcje sterujące dalszym przebiegiem programu. W zależności od wybranej me-
tody ustawiane są parametry robocze procedur z wektora  OPTIONS , a następnie wywo-
ływana jest m-funkcja   lub   . Równolegle do obliczeń iteracyjnych
10
rysowany jest przy pomocy m-funkcji   przebieg wynikającej stąd trajektorii
poszukiwania minimum.
Na końcu programu podaje się główne wyniki optymalizacji i przygotowuje się warstwice
pod następny (potencjalny) rysunek trajektorii.
W trakcie badań przeprowadzanych w ćwiczeniu występuje konieczność samodzielnego
wprowadzania nieznacznych modyfikacji  nms_2.m .
1. Przygotować należy m-funkcję wyznaczania wartości minimalizowanej funkcja 
 o której mówi się w  helpie programu. Określa się ją na bazie wzoru analitycznego
funkcji skonstruowanej na podstawie otrzymanego do rozwiązania układu dwu równań
nieliniowych.
2. Jednym z argumentów m- funkcji   jest analityczne wyrażenie gradientu badanej
funkcji GRAD. Wyrażenie to należy wyznaczyć analitycznie i wpisać na samym początku
programu w wymaganej (patrz przykład przytoczony w  helpie ) konwencji.
3. Pozostałe miejsca modyfikacji programu ( oznaczone: [ ] ) wiążą się z (ewen-
tualnymi) zmianami punktu startowego i punktu stanowiącego rozwiązanie zadania.
PRZEBIEG ĆWICZENIA 2:
1. Rozwiąż, posługując się m- funkcjami  fmins i  fminu , realizującymi algorytmy pro-
gramowania nieliniowego układ dwu nieliniowych równań algebraicznych przydzielony
spośród wymienionych poniżej.





W jaki sposób można ocenić dokładność uzyskanego rozwiązania?
Wskazówka. Należy zdefiniować minimalizowaną funkcję jako sumę kwadratów lewych stron
obu równań. Wartość argumentu funkcji w którym osiąga ona (równe zeru ) minimum jest
jednocześnie rozwiązaniem układu równań.
11
2. Należy, posługując pakietem , rozwiązać przydzielone
przez prowadzącego zadanie z zakresu programowania liniowego, programowania kwa-
dratowego lub problemu optymalizacji nieliniowej z ograniczeniami (np. z jw. z dodat-
kowym warunkiem: .
3. Zbadaj, przy pomocy programu  nms_2.m główne własności (np. liczba wyliczeń
wartości badanej funkcji niezbędnych do wyznaczenia rozwiązania układu z zadaną do-
kładnością) metod programowania nieliniowego reprezentowanych w otrzymanym pro-
gramie. Porównaj jakościowe przebiegi trajektorii poszukiwania ekstremum funkcji
w rozwiązywanym problemie.
Wskazówka. Należy utworzyć m- pliki z badaną funkcją i jej gradientem, lub odpowiednio
zmodyfikować  wyjaśnienia na poprzednich stronach instrukcji - otrzymany program
obliczeń. Podstawowym środkiem stosowanym w trakcie badań obliczeniowych jest od-
notowywanie skutków (wyrażanych zarówno liczbowo jak i na przebiegu uzyskiwanej
trajektorii) stopniowego zwiększania liczby iteracji przeprowadzanych badaną metodą.
SPRAWOZDANIE POWINNO ZAWIERAĆ:
Rozwiązania otrzymanych zadań optymalizacji.
Wyniki przeprowadzonych badań symulacyjnych algorytmów programowania nielinio-
wego przedstawione w ilustratywnej formie, np. porównawczo w układzie tabelaryc z-
nym i graficznie.
Wnioski i komentarze na temat przeprowadzonych badań.
12
ĆW.3. Optymalizacja funkcji wielu zmiennych
w obecności zakłóceń pomiarowych.
W programie badań przebiegów procesów optymalizacji głównym jest problem wy-
znaczenia sterowania zapewniającego osiągnięcie (w sensie statystycznym) ekstremum
wskaz
nika jakości sterowanego procesu. Wersja wielowymiarowa tego zadania jest jed-
nym z głównych składników problematyki sterowania procesem technologicznym, ukie-
runkowanego na osiągnięcie możliwie najlepszych (średnio rzecz biorąc) efektów
sterowania.
W programie badań obliczeniowych   główną uwagę zwrócono na dzia-
łanie algorytmów optymalizacji statycznej w sytuacjach niedeterministycznych. Znaj-
dowane jest tu minimum pewnej formy kwadratowej, pomiary (tutaj: obliczenia) której
są addytywnie zakłócane przy zastosowaniu generatora liczb losowych. Ćwiczący ma
możliwość  jednoczesnego przeprowadzenia i analizy wyników określonej serii prze-
biegów optymalizacji.
PRZED ĆWICZENIEM należy zapoznać się na podstawie zestawienia D i studiów litera-
turowych z problematyką rozwiązywania zadania optymalizacji statycznej w obecności za-
kłóceń pomiarowych.
Pytania kontrolne:
Jaki ciąg czasowy nazywamy stacjonarnym?
W jaki sposób szerokość przedziału ufności przy pomiarze danej wielkości fizycznej
w obecności addytywnych zakłóceń o rozkładzie normalnym zależy od ich wariancji i od
liczby wykonanych pomiarów?
PROGRAMOWANIE BADAC
SYMULACYJNYCH w trakcie ćwiczenia znacznie uła-
twia przytoczony na końcowych stronach instrukcji program  nms_3 , początek którego
przedstawiono poniżej:
13
Analiza zawartości programu  nms_3 (patrz Dodatek) nie sprawia, przy znajomości pro-
gramu badań z poprzedniego ćwiczenia, większych trudności. Obie konstrukcje programowe
są bardzo zbliżone. Komentując najogólniej, w programie tym możemy wyraz
nie wyróżnić
trzy części. Pierwsza z nich, przygotowawcza, pozwala na obejrzenie trójwymiarowych wy-
kresów optymalizowanej funkcji ( zarówno w postaci deterministycznej, jak i zniekształconej
zakłóceniami) a także na ustalenie parametrów procesu symulacji poszukiwania minimum.
Wybieramy tu metodę obliczeń, liczbę iteracji, ilość powtórzeń  pomiarów wielkości wyj-
ściowej obiekcie , parametr określający długość pojedynczego kroku, itp. W pozostałych czę-
ściach programu, oddzielonych liniami kreskowanymi, realizowane są obliczenia
optymalizacyjne metodą programu kroczącego, stanowiącego dwuwymiarowy analog pro-
gramu optymizatora z ćwiczenia 1, metodą simpleksów prostych a następnie metodą gra-
dientu stochastycznego.
Wyniki obliczeń przekazywane są w postaci graficznej jako trajektoria poszukiwania
optimum i (niektóre, najbardziej istotne) w postaci liczbowej. Warto pamiętać również o tym,
że wydruk pełnego protokołu obliczeń możemy uzyskać najprościej poprzez zakończenie
instrukcji wyznaczających nowe wartości argumentów badanej funkcji w trakcie optymaliza-
cji przecinkami zamiast średników.
PRZEBIEG ĆWICZENIA 3:
1. Przeprowadz
doświadczenia symulacyjne ilustrujące sekwencyjny proces doboru dwu
oddziaływań wejściowych ( w przypadku kwadratowego modelu statyczne-
go sterowanego procesu:
14
pomiary wyjścia którego są zakłócane addytywnymi oddziaływaniami losowymi o rozkła-
dzie normalnym: z N ( 0, �2 ). Celem doświadczeń jest minimalizacja wartości średniej
wielkości wyjściowej procesu. Posługujemy się przy tym programem  nms_3 ,
z modyfikacją polegającą na wprowadzeniu (na początku programu) zadanej postaci do-
datnio określonej macierzy Aw formie kwadratowej.
W trakcie badań należy porównać efektywność procesu optymalizacji mierzoną suma-
rycznymi stratami na poszukiwanie ekstremum przy zastosowaniu wszystkich, repreze n-
towanych w programie  nms_3 metod, przy zastosowaniu różnych wartości ustalanych
wyjściowo parametrów algorytmów. Punkty startowe w płaszczyz
nie poszukiwania
ustalamy deterministycznie lub losowo.
2. Czy przebieg procesu optymalizacji istotnie zależy od punktu startowego? W celu odpo-
wiedzi na to pytanie przeprowadz
symulację przy pomocy tych samych algorytmów star-
tując z punktów położonych na różnych osiach elipsoidalnych warstwic badanej funkcji
w tej samej odległości od początku układu współrzędnych. Należy także scharakteryzo-
wać stacjonarne procesy losowe, obserwowane przy błądzeniu procesu poszukiwania
w pobliżu optimum.
3. Czy proces optymalizacji istotnie zależy od poziomu zakłóceń? Czy wpływa on na racjo-
nalny dobór parametrów w stosowanych algorytmach? Należy przeprowadzić program
badań symulacyjnych pozwalający na ustalenie zaleceń odnośnie zmiany wartości kroku
w algorytmie przy wzroście / spadku poziomu zakłóceń w analizowanej sytuacji.
W RAMACH ĆWICZENIA UZUPEA
NIAJ
CEGO:
4. Należy zamodelować układ regulacji ekstremalnej z przemiennym dostrajaniem poszcze-
gólnych sterowań (rys.2). Po zamodelowaniu zarejestrować typowe przebiegi sterowania
i wyjścia sterowanego procesu.
15
du/dt
Rys. 2. Optymalizator z przemiennym dostrajaniem sterowań.
SPRAWOZDANIE POWINNO ZAWIERAĆ:
Główne wyniki przeprowadzonych badań symulacyjnych  m.in. przedstawione porów-
nawczo w układzie tabelarycznym i graficznie.
Wnioski i komentarze na temat przeprowadzonych badań i odpowiedzi na pytania posta-
wione w programie ćwiczenia.
Czy zastosowane metody dały zbliżone wyniki? Czy też należy je uznać za istotnie różne?
Która ze stosowanych metod optymalizacji okazała się skuteczniejszą?
Odpowiedz
uzasadnij na tle ścisłych wskaz
ników: efekt końcowy przy zadanej liczbie po-
miarów badanej funkcji, sumaryczne straty w trakcie poszukiwania ekstremum, itp.
16
Zestawienie A.
Algorytmy optymalizacji funkcji jednej zmiennej
Metody iteracyjne są podstawą konstrukcji algorytmów znajdowania ekstremum funkcji.
Podstawowa idea tych metod związana jest z określeniem tzw. funkcji iteracyjnej wy-
znaczającej następną (tj. w następnej iteracji) wartość argumentu badanej funkcji: u(k+1)
na podstawie jego m uprzednich wartości: u(k),u(k-1),...,u(k-m+1)i wartości ba-
danej funkcji: f(u) ( a także czasami jej pochodnych ) w tych punktach. Punkt startowy
wybiera się na podstawie informacji dostępnej przed rozpoczęciem procesu poszukiwania.
Przedstawimy zwięz
le metody iteracyjne, ograniczając się do najprostszych i najczęściej
stosowanych (m.in. bezpośrednie zastosowania w urządzeniach technicznych). Rozważania
będziemy prowadzić je na tle problemu minimalizacji funkcji f(u),równoważnego pro-
blemowi maksymalizacji tejże funkcji z ujemnym znakiem [-f(u)].
Algorytmy pochodnej wynikają ze znanego faktu, że minimum (ciągłej i posiadającej
ciągłą pochodną) funkcji wypukłej w dół znajduje się w punkcie zerowym tej pochodnej, tj.
w takim punkcie u* w którym: df(u)/du|u=u*=0.Typowa postać algorytmu pochodnej:
u(k+1) = u(k) - ą(k) [df(u)/du]|u(k) , k = 0,1,2,...
Warunkiem koniecznym zbieżności danego algorytmu do optymalnego u = u*,nie-
zależnie od wyboru punktu początkowego u(0),jest wybór współczynników szeregu ą(k)
w postaci zapewniającej:
"
( k ) = + " .
"
k = 0
Cechę tę posiadają np. szeregi: (1) ą(k)=ą=const, lub (2) ą(k) =ą/kw, gdzie
wykładnik potęgi w"[0,1].
17
Warunek dostateczny zbieżności wiąże się z koniecznością ograniczenia stałej do po-
ziomu wynikającego z maksymalnej wartości � drugiej pochodnej optymalizowanej funkcji
-1
w obszarze poszukiwań: ą < 2� .
Istotnym, dopuszczalnym uproszczeniem jest algorytm znaku pochodnej, który działa
wyłącznie w oparciu o, jednoznacznie określony kierunek poszukiwań:
u(k+1) = u(k) - ą(k)sign[df(u)/du]|u(k) , k=0,1,2,...
Warunek (punktowej) zbieżności algorytmu w tej wersji wymaga już jednak zdążania,
wraz ze wzrostem numeru iteracji k do ", szeregu (k) do zera. Inaczej, docelowo, otrzymuje
się oscylacje wokół stacjonarnego punktu u*.Podkreślmy, że zjawisko tego typu, przy ogra-
niczonej, dopuszczalnej amplitudzie oscylacji, nie musi być cechą ujemną. Dodatkowo, przy
występującej np. w wielu systemach technicznych zmienności położenia punktu optymalnego
uzyskuje się nawet, przy racjonalnym wyborze stałej ą,cenną własność śledzenia potencjal-
nych zmian. Mówimy wówczas o tzw. sterowaniu na ekstremum.
Algorytm Newtona jest udoskonaloną wersją algorytmu pochodnej wymagającą jednak
również znajomości drugiej pochodnej:
u(k+1)=u(k)-[d 2f(u)/du2] -1|u(k) [df(u)/du]|u(k), k=0,1,2,...
Można wykazać, że jeżeli funkcja kryterialna jest kwadratową, tzn. typu:
f(u)=au2+bu+c; to, działając zgodnie z algorytmem Newtona, minimum jej znajdu-
jemy już po pierwszej iteracji. Znajomość odwrotności drugiej pochodnej pozwala wówczas
ustalić jednoznacznie wartość współczynnika ą.
Algorytm skończonych przyrostów: stosowany jest w sytuacjach w których nie tylko
druga, lecz i pierwsza pochodna funkcji kryterialnej nie jest dostępna. Z założenia możemy
posłużyć się wówczas wyłącznie pomiarami samej funkcji. Prowadzi to do konieczności
przybliżenia wartości pochodnej ilorazem skończonych przyrostów. W rezultacie:
u(k+1) = u(k)- ą(k)[ "f(u) ]|u(k)/ 2"u , k=0,1, 2,...;
18
przy czym:
[ "f(u) ]|u(k) = f(u(k)+"u) - f(u(k)-"u);
gdzie: "u- mały przyrost wartości argumentu. Zbieżność do punktu u*gwarantowana jest tu
poprzez spełnienie następującego dodatkowego ograniczenia:
"
" ( k ) " u ( k ) < + "
k = 0
Wiąże się to z koniecznością zmniejszania, wraz ze wzrostem numeru iteracji k, testują-
cych przyrostów argumentu "u.
W praktyce rozsądny kompromis może stanowić również algorytm znaku skończonych
przyrostów, działający na bazie określenia znaku przyrostu badanej funkcji przy technolo-
gicznie uzasadnionym przyroście argumentu u:
u(k+1) = u(k) - ą(k) sign["f(u)]|u(k) , k=0,1,2,...
Racjonalnym wyrażeniem możliwych tu uproszczeń jest połączenie kroku testującego z
roboczym. Otrzymujemy wówczas prosty i często stosowany w urządzeniach technicznych
algorytm tzw. regulatora kroczącego:
u(k+1) = u(k) - "u sign["f(u)]|u(k) , k=0,1,2,...
Algorytmy związane z redukcją przedziału nieokreśloności w których
znajduje się minimum badanej funkcji unimodalnej (jeden punkt ekstremalny w badanym
przedziale) związane są z nieco inną metodyką. Podstawą ich działania nie jest ruch dopaso-
wany do pochodnej jak poprzednio, lecz idea szybkiego zmniejszania po każdym pomiarze
(lub obliczeniu) funkcji kryterialnej przedziału w którym może znajdować się poszukiwane
minimum. Start następuje z dostatecznie dużego, z założenia znanego przedziału u"[a,b],
w którym znajduje się minimum badanej funkcji.
Przedstawimy dwa efektywne algorytmy tego rodzaju.
19
Algorytm złotego podziału nazwę zawdzięcza charakterystycznej dla tej metody liczbie: ł
=(sqrt(5)-1)/2 = 0,618, wytyczającej zdaniem starożytnych Greków doskonałe
proporcje kształtu prostokąta. Po jego przeanalizowaniu łatwo zauważyć, że szerokość bada-
nego przedziału maleje proporcjonalnie do: łk = 0,618k.
Jeżeli:
" przez ua i ub oznaczymy dwa punkty z wnętrza rozpatrywanego przedziału i ustalimy
początkowe ich wartości poprzez: ua(0)= b - ł(b-a); ub= a + ł(b-a);
" w punktach tych z założenia mamy możliwość wykonania pomiarów, lub wyliczenia
wartości f(ua) i f(ub) ;
to: algorytm złotego podziału sprowadza się do wykonywania na każdym, kolejnym etapie
tych samych działań związanych z nowym jednym pomiarem lub wyliczeniem wartości
badanej funkcji. Przedstawimy go stosując konwencje zapisu przyjęte w Matlabie.
Algorytm Kiefera wywodzi się także z idei redukcji przedziału zawierającego minimum ba-
danej funkcji. Wymienimy główne różnice w stosunku do metody złotego podziału:
20
" Korzysta się z liczb Fibonacciego: Fo,F1,F2 ,..., definiowanych poprzez:
Fi = 1, dla i = 0,1 ; Fi = Fi-1 + Fi-2 , dla i e" 2.
" Kryterium STOP-u określa się z warunku: Fk <|b  a|/� d" Fk+1 ; przy pośrednic-
twie zadanej z góry liczby iteracji k. Fakt ten może być technicznie wygodny w przypadku
konieczności spełnienia warunku związanego z ograniczeniem całkowitego czasu rozwią-
zania zadania optymalizacji w systemach czasu rzeczywistego.
" Na starcie wyznacza się wartości argumentu:
ua = a + Fk-1(b-a)/Fk+1 ; ub = a + b - ua ,
a następnie wartości funkcji: fa = f(ua) i fb = f(ub) w tych punktach.
" Podstawowe działania każdej iteracji są analogiczne do przytoczonych wyżej działań w
algorytmie złotego podziału:
Jeżeli f(ub)>f(ua) to: b =ub ; ub = ua ; fb=fa;
ua = a + b - ua ; fa = f(ua).
Jeżeli f(ub) d" f (ua) to: a = ua ; ua = ub; fa=fb ;
ub = a + b - ub ; fb=f(ub).
Algorytm interpolacji kwadratowej może posłużyć za przykład zastosowania metod z lo-
kalną aproksymacją funkcji w procesie optymalizacji. Opiera się on na spostrzeżeniu, że
szczególnie w otoczeniu minimum badaną funkcję można często z dostateczną dokładnością
przybliżać trójmianem kwadratowym: f(u) = a u2 + b u + c, którego ekstre-
mum, jak wiadomo, znajduje się w punkcie: u* = - b/2a.
Pozwala to, na podstawie znajomości badanej funkcji f(u)w trzech punktach f(u1),
f(u2), f(u3)znalez
ć (za pośrednictwem wielomianu interpolacyjnego Lagrange a) na-
stępną, teoretycznie lepiej położoną wartość argumentu:
21
u(k+1)=(�23 f(u1)+�31f(u2)+�12f(u3))/2(ł23f(u1)+ł31f(u2)+ł12f(u3));
gdzie: �ij = u2i - u2j ; łij = ui - uj ; {i,j}={2,3},{3,1}{1,2}.
W celu zachowania własności interpolacyjnych w algorytmie powinno się dodatkowo za-
dbać o taką kontynuację by: f(u2) < f(u1) i f(u2) < f(u3)przy u1< u2< u3.
Konieczność stosowania (pomocniczo) rozbudowanych zależności logicznych w celu zagwa-
rantowania zbieżności algorytmu jest zresztą cechą charakterystyczną algorytmów działają-
cych na bazie ekstrapolacyjno  interpolacyjnej [2]. Algorytmy te różnią się stopniem
stosowanego wielomianu interpolacyjnego. Stosunkowo popularnym jest również algorytm
interpolacji sześciennej.
Kryterium stopu wiąże się, podobnie jak w poprzednio przedstawionych metodach, z sy-
tuacją w której osiągana poprawa oceny min funkcji na jednym etapie zmaleje poniżej zada-
nego , lub gdy sam przedział zmaleje do: �łu3 - u1�ł< � .
22
Zestawienie B.
Specyfika optymalizacji w obecności zakłóceń pomiarowych
Wyznaczanie optymalnych warunków realizacji procesu technologicznego wymaga
(przy założeniu niestacjonarności lub nieznajomości postaci funkcji kryterialnej) przeprowa-
dzenia określonego programu badań eksperymentalnych bezpośrednio  na obiekcie . W pro-
gramie tego rodzaju często nie odtwarza się pełnej postaci funkcji kryterialnej, a jedynie
znajduje się jej ekstremum. Ściślej rzecz ujmując, z reguły w praktyce za zadawalające roz-
wiązanie zadania uważane jest znalezienie się w dostatecznie bliskim (z punktu widzenia celu
optymalizacji) otoczeniu aktualnego położenia punktu ekstremalnego. W praktyce stosuje się
 ostrożne (zwielokrotnienie pomiaru, wielkość kroku) wersje najprostszych metod determi-
nistycznych.
Rozważmy przydatność do tego celu, przytoczonych w dodatku poprzednim, algorytmów
iteracyjnych optymalizacji jednej zmiennej:
1. Algorytm pochodnej może być stosowany oczywiście jedynie przy dostępności pomiarów
pochodnej funkcji kryterialnej. W warunkach nie skorelowanych realizacji stacjonarnych z a-
kłóceń stochastycznych pomiarów pochodnej zbieżność tego algorytmu w sensie średniokwa-
dratowym, tj. z gwarancją:
E{(u(k)-u*)2} 0, przy k ";
zapewnia odpowiedni dobór ciągu współczynników ą Zgodnie z twierdzeniem Rob-
binsa - Monro o aproksymacji stochastycznej [1] szereg ten powinien spełniać warunki:
"
"
2
( k ) = + " ,
"
" ( k ) = + " ,
k = 0
k = 0
np. ą(k) =ą /kw, gdzie: w" [0 , 1].
23
Podkreślmy także, że skutkiem tego twierdzenia jest także zbieżność średniokwadratowa
procedur opartych na uśrednianiu określonej liczby pomiarów pochodnej. Powtarzanie do-
świadczeń z uśrednieniem wyników prowadzi bowiem jedynie do zmniejszenia wariancji
mierzonej wielkości:
2
Jeżeli: X " �( � ,� ), to: XN " �( � , �2 / N );
przy zachowaniu innych warunków zbieżności algorytmu.
Tą samą uwagę można odnieść również w stosunku do zbieżności algorytmu opartego na
znaku pochodnej.
___________________________________________________________________________
2. Algorytm przyrostów wiąże się już z pomiarami wartości badanej funkcji. Bezpośrednie
pomiary pochodnej bowiem nie zawsze są w praktyce dostępne. Ustalając wartość pochodnej
przy pomocy ilorazu różnicowego, powinniśmy wykonać dwa pomiary wielkości kryterialnej.
Podkreślmy związek parametrów rozkładu prawdopodobieństwa sumy (różnicy ) zmien-
nych losowych z parametrami samych zmiennych:
jeżeli : X1 " �(�1,�12), X2 " �(�2,�22),
to: X1 + X2 " �( �1 + �2, �12 +�22),
a także: X1 - X2 " �( �1 - �2, �12 + �22).
Analogiczne do przedstawionego powyżej twierdzenia aproksymacji stochastycznej,
graniczne twierdzenie o zbieżności algorytmów przyrostowych w warunkach pomiarów obar-
czonych błędami losowymi zostało wykazane przez Kiefera - Wolfowitza [1].
W praktyce, kluczową sprawą jest jednak najczęściej szybkość osiągania w wyniku
działania danego algorytmu bezpośredniego otoczenia ekstremum, lub równoważna cecha
związana ze zdolnością śledzenia za zmieniającym się położeniem tego ekstremum. Skutecz-
ny dobór parametrów w algorytmie przyrostowym aproksymacji stochastycznej w danej,
określonej sytuacji wymaga wiedzy z doświadczenia ( informacji a priori). Problem ten może
być również rozwiązany przy pomocy określonego programu badań.
24
3. Algorytmy redukcji przedziałów nieokre śloności związane z bezpośrednim porówny-
waniem pomiarów badanej funkcji i dokonywaną sekwencyjnie wielokrotną weryfikacją hi-
potez typu H0 ( fa > fb ), przeciwko alternatywnym H1 ( fa < fb ). Ze względu na znacznie
większą z reguły wagę błędów (pierwszego, lub drugiego rodzaju) decydujących o odrzuce-
niu, szczególnie na starcie, znacznych przedziałów dalszych badań.
Zamiast działania deterministycznego w stylu:
po każdym pomiarze redukuj dotychczasowy przedział badań;
działanie powinno przebiegać na podstawie:
jeżeli hipotezę: H0(fa>fb)lub alternatywnąH1 (fa < fb)można przyjąć na
dostatecznie wysokim poziomie istotności [1- ]
to redukuj przedział badań tak jak w odpowiednim algorytmie deterministycznym,
w innej sytuacji wykonaj dodatkowe pomiary.
Podkreślmy jeszcze raz, że weryfikacja hipotezy powinna być przeprowadzana na bardzo
wysokim ( szczególnie w początkowej fazie obliczeń ) poziomie istotności. Poza tym w pro-
cedurze optymalizacji powinno znajdować się działania kontrolne sprawdzające w określo-
nych odstępach również wartości średnie funkcji na krańcach aktualnego przedziału badań.
Występuje tu bowiem konieczność stosowania pomocniczych zależności logicznych w celu
zagwarantowania zbieżności algorytmu mimo występowania z określonym prawdopodobień-
stwem niesprzyjających sekwencji zakłóceń.
25
Zestawienie C.
Algorytmy optymalizacji funkcji wielu zmiennych.
Regularne metody minimalizacji funkcji wielu zmiennych konstruowane są poprzez se-
kwencyjne powtarzanie dwu działań.
1. Określenie aktualnego ( tj. umiejscowionego się w bieżącym punkcie u(k)przestrzeni
poszukiwań) wektora d kierunku poszukiwania punktu minimum;
2. Minimalizacja funkcji w tym kierunku; tj. rozwiązanie zadania minimalizacji funkcji jed-
nej zmiennej: f(ą ) = f ( u(k) + ą d ):
min f( u(k) + ą d ) = f( u(k) + ą* d ).
Problem minimalizacji funkcji jednej zmiennej został przedstawiony w zestawieniu A.
Aktualnie bardzo zwięz
le przedstawimy główne metody rozwiązywania zadania określenia
kierunku.
Metoda Gaussa-Seidla. Wektor kierunku poszukiwań jest równoległy kolejno do każdej
z osi współrzędnych przestrzeni argumentów badanej funkcji: d(k)=[0,...,1,...0],
tj. d(1)=[1,0,...,0]; d(2)=[0,1,...,0];...aż do: d(n)=[0,0,...,1].
Przeznoznaczono tu liczbę argumentów optymalizowanej funkcji.
__________________________________________________________________________________________
Metoda najszybszego spadku. Wektor kierunku poszukiwań:
d(k) = grad f u .
u k
pokrywa się tu z gradientem badanej funkcji. Metoda ta, podobnie jak poprzednia, stosowana
26
jest w stosunkowo nieskomplikowanych sytuacjach.
W praktyce eksperymentalnej, przy niskim poziomie zakłóceń, składowe gradientu mogą
być zastąpione przez doświadczalnie wyznaczone przyrosty, np.
"fi = ( f(u(k)+� u ) - f(u(k) ) / 2� u.
i i
Przy znacznych zakłóceniach pomiarów funkcji kryterialnej f(u) najczęściej stosuje się
wersję Boxa - Wilsona, metody najszybszego spadku. W wersji tej, na podstawie określonej
liczby pomiarów przeprowadzonych zgodnie z planowanym programem badań, zastępuje się
badaną funkcję f(u) jej przybliżeniem liniowym q(u) w otoczeniu aktualnego punktu poszu-
kiwania ekstremum u. Współczynniki ai (i=1,...,n) wyrażeniu przybliżonym:
q(u) = a0 + a1 u1 + a2 u2 + ... + an un;
odgrywają rolę oszacowania składowych gradientu funkcji kryterialnej w danym punkcie
przestrzeni poszukiwania.
__________________________________________________________________________________________
Metoda Newtona-Raphsona. Ustalenie wektora kierunku poszukiwań w punkcie, sta-
nowiącym aktualne przybliżenie rozwiązania w ramach tej metody wymaga wyliczenia gra-
dientu i (odwrotności) hesjanu badanej funkcji:
2
d(k) = - [ " f(u) ]  1ćł u(k) grad(f(u))ćłu(k) .
Przypomnijmy, że hesjan funkcji w danym punkcie jest macierzą kwadratową rozmiaru
zgodnego z liczbą argumentów minimalizowanej funkcji, np. w przypadku funkcji dwu
zmiennych:
2
["2f(u)] = ["2f /"u12, "2f /" u1"u2 ; "2f /" u1"u2 , Łf /"u22]).
Metoda Newtona - Raphsona jest szczególnie skuteczną w bliskim otoczeniu punktu sta-
nowiącego rozwiązanie zadania. Potencjalne zastosowanie jej w praktyce eksperymentalnej
27
wiąże się z przedstawieniem badanej funkcji w otoczeniu aktualnego punktu u(k)przestrze-
ni poszukiwania przybliżeniem kwadratowym q(u).Może to nastąpić np. po wykonaniu
programu badań drugiego rzędu w otoczeniu aktualnego punktu przestrzeni u(k).Z wyni-
kowej postaci formy kwadratowej:
q(u)= a0 + a1u1 +a2u2+...+ amum + a11u12 + 2a12u1u2 +...+am,m um2 =
= a0 + a u + uT Q u ;
pośrednio wynika zarówno oszacowanie hesjanu, jak i oszacowanie gradientu funkcji kryte-
rialnej w danym punkcie.
__________________________________________________________________________________________
Metoda gradientu sprzężonego nazywana jest również metodą Fletcher a-Reevs a.
Wektor kierunku poszukiwań d(k) jest tu liniową kombinacją gradientu minimalizowanej
funkcji w aktualnym punkcie przestrzeni poszukiwań: grad(f(u))u(k) i wektora kierun-
ku z poprzedniej iteracji d(k-1):
d(k)= � (k)d(k-1) - grad(f(u))u(k) ;
Współczynnik wagi związany jest ze stosunkiem dwu norm gradientów:
�(k) = [grad(f(u))u(k)]T grad(f(u))u(k)
/[grad(f(u))u(k -1)]Tgrad (f(u))u(k -1);
a kierunek początkowy d(0)jest definiowany poprzez gradient w punkcie startowym.
Należy podkreślić, że konieczny nakład badań eksperymentalnych  wyznaczenie gra-
dientu badanej funkcji w danym miejscu przestrzeni czynnikowej - jest w danej metodzie taki
sam jak w metodzie gradientu prostego. Efektywność jej jest natomiast z reguły wyższa.
__________________________________________________________________________________________
Metoda Powella; przy stosowaniu której w pierwszym  obiegu (tj. tzw. dużej iteracji)
algorytmu kierunki poszukiwania wyznacza się w ten sam sposób jak w metodzie Gaussa-
Seidla na bazie wersorów: {e(1),e(2),...,e(n)}. Zestawy kierunków w następnych
28
 dużych iteracjach liczone są natomiast z uwzględnieniem przyrostów wektora argumentów
w obiegach bezpośrednio je poprzedzających, np.
" po pierwszym obiegu formuje się zbiór: {e(2),e(3),...,d(0)} ,
w którym: d(0) = u(n+1) - u(1);
" po drugim natomiast: { e(3),e(4),...,d(0),d(1)},
gdzie: d(1)= u(2n+1)-u(n+1),..., itd.
Metody Powella i Fletchera - Reevsa należą do grupy metod opartych na kierunkach
sprzężonych [ 7, 8 ].
__________________________________________________________________________________________
W metodach zmiennej metryki aktualny wektor kierunku liczony jest w sposób analo-
giczny do stosowanego w metodzie Newtona- Raphsona:
d k = -Dk grad f u ,
u k
z tym, że Dk jest tu jedynie aktualnym przybliżeniem odwrotności hesjanu funkcji w punkcie
u(k).Za początkową macierz D0 przyjmuje się z reguły macierz jednostkowąIn .
Przybliżenia hesjanu Dk można konstruować na szereg różnych sposobów. Niektóre z
nich, bazujące na wektorowych przyrostach argumentu:
ck = u(k+1)  u(k) ;
i przyrostach gradientu:
gk = grad(f(u))|u ( k + 1) - grad(f(u))|u ( k ) ;
po każdej iteracji przedstawiono poniżej (wszystkie wektory reprezentowane w przytoczo-
nych wzorach są kolumnowe).
metoda Fletchera-Powella-Davidona:
Dk+1 = Dk + ck ckT / ckT gk - Dk gk gkT DkT / gkT DkT gk ;
metoda I Pearsona:
Dk+1 = Dk - (Dk gk) (Dk gk)T / gkT Dk gk;
metoda McCormicka:
29
Dk+1 = Dk + (ck - Dk gk) ckT / ckT gk ;
metoda Wolfa-Broydena-Davidona:
Dk+1 = Dk + (ck-Dk gk) (ck -Dk gk)T / (ck-Dk gk)T gk ;
Postępowanie w przypadku nieregularnych metod minimalizacji funkcji wielu zmiennych
nie wiąże się z określonym schematem ogólnym. Opracowywano je indywidualnie. W roli
przykładu przedstawimy aktualnie najbardziej popularną metodę simpleksów.
Y
Y Metoda simpleksów jest programem badań typu bezgradientowego. Simpleksem na-
zywany jest regularny wielościan posiadający (n+1)wierzchołków - njest tu liczbą argu-
mentów funkcji kryterialnej, np. w przypadku dwu argumentów simpleksem jest trójk ąt
równoboczny, trzy optymalizowane czynniki prowadzą do czworościanu w przestrzeni trój-
wymiarowej, itd.
Na starcie poszukiwania ekstremum wykonuje się pomiary funkcji w wierzchołkach ra-
cjonalnie wybranego simpleksu początkowego. Następnie, w najprostszej wersji metody, na
każdym kolejnym etapie minimalizacji wierzchołek z najmniej korzystnym położeniem - od-
powiadający największej wartości funkcji - zostaje zamieniony nowym, położonym syme-
trycznie do niego po przeciwstawnej ścianie simpleksu. W wyniku powtarzania tego działania
simpleks przesuwa się stopniowo w przestrzeni czynników wpływających na jakość optyma-
lizowanego procesu. W sytuacji, gdy wynik pomiaru minimalizowanej funkcji w nowym
wierzchołku jest gorszy od poprzedniego możemy zakończyć poszukiwanie lub kontynuować
program po zmniejszeniu rozmiarów simpleksu. Efektywnym zakończeniem może być rów-
nież wykonanie w znalezionym otoczeniu punktu stacjonarnego programu badań drugiego
rzędu.
Znacznie bardziej rozwiniętą wersją metody simpleksów jest, przedstawiona szczegóło-
wo w [2], sieć działań Neldera  Meada. Na tej metodzie oparto m.in. podstawową procedurę
minimalizacji funkcji bez ograniczeń (   ) w środowisku Matlaba.
30
Zestawienie D.
Optymalizacja w obecności zakłóceń pomiarów
funkcji kryterialnej wielu zmiennych.
1. Wyznaczanie optymalnych warunków realizacji procesu technologicznego wymaga
(przy założeniu niestacjonarności lub nieznajomości a priori postaci funkcji kryterialnej)
przeprowadzenia określonego programu badań eksperymentalnych bezpośrednio  na obiek-
cie . W programie tego rodzaju nie odtwarza się całej funkcji kryterialnej, a jedynie znajduje
się jej ekstremum lub, ściślej rzecz ujmując, z reguły celem jest znalezienie się w dostatecznie
bliskim (z punktu widzenia celu optymalizacji) otoczeniu aktualnego położenia punktu eks-
tremalnego. Z założenia bowiem pomiary badanej funkcji obarczone są niepomijalnymi za-
kłóceniami, co istotnie komplikuje problem znalezienia ekstremum w porównaniu z sytuacj ą
deterministyczną.
Teoria gwarantuje jedynie asymptotyczną zbieżność ( tj. zbieżność przy liczbie pomiarów
rosnącej do nieskończoności) algorytmów typu aproksymacji stochastycznej [1]. W praktyce
stosuje się  ostrożne (zwielokrotnienie pomiaru funkcji w danym punkcie, nieznaczna wiel-
kość poprawki na każdym etapie) wersje najprostszych metod deterministycznych. Przedsta-
wimy tu kilka przykładów programów badań tego rodzaju chętnie stosowanych przez
technologów i dyspozytorów systemów sterowania i nadzoru.
__________________________________________________________________________________________
2. Metoda Boxa-Wilsona jest programem typu gradientowego. Realizuje się ją w dwu eta-
pach. W trakcie etapu pierwszego, na podstawie niewielkiej liczby doświadczeń następuje
opisanie przybliżeniem liniowym funkcji kryterialnej Q(x)w otoczeniu aktualnego punktu
przestrzeni czynnikowej x(k); x jest tu wektorem poszukiwanych wielkości sterujących,
lub parametrów.
Zwróćmy uwagę, że w wyrażeniu przybliżonym, znajdowanym w wyniku realizacji pro-
gramu badań pierwszego rzędu:
31
yest = a0 + a1 x1 + a2 x2 + ... + an xn ;
współczynniki ai odgrywają rolę przybliżenia pochodnych funkcji kryterialnej w danym
punkcie.
W etapie drugim na podstawie uzyskanego modelu następuje wyznaczenie kierunku
(dysponujemy oszacowaniem gradientu) i kroku przemieszczenia. Krok ten jest najczęściej
stałym, lub dobieranym proporcjonalnie do gradientu. Skutecznym rozwiązaniem może być
również zrealizowanie programu badań funkcji kryterialnej w kierunku gradientu.
__________________________________________________________________________________________
3. Metoda simpleksów jest programem typu bezgradientowego. Simpleksem nazywany jest
regularny wielościan posiadający (n+1)wierzchołków - njest tu liczbą argumentów funkcji
kryterialnej, np. w przypadku dwu argumentów simpleksem jest trójkąt równoboczny, trzy
optymalizowane czynniki prowadzą do czworościanu w przestrzeni trójwymiarowej, itd. Na
starcie wykonuje się pomiary funkcji w wierzchołkach racjonalnie wybranego simpleksu po-
czątkowego.
W najprostszej wersji metody, na każdym etapie optymalizacji, wierzchołek z najmniej
korzystnym położeniem - odpowiadający przy minimalizacji największej wartości funkcji -
zostaje następnie zamieniony nowym, położonym symetrycznie do niego po przeciwstawnej
ścianie simpleksu. W wyniku powtarzania operacji tego typu simpleks przesuwa się w prze-
strzeni czynników wpływających na jakość optymalizowanego procesu.
Poszukiwanie zostaje zakończone w sytuacji, gdy wynik pomiaru Q(x)w nowym wierz-
chołku jest gorszy od poprzedniego. Oczywiście, w sytuacji tego typu możliwa jest również
kontynuacja badań po zmniejszeniu rozmiarów simpleksu  patrz algorytm deterministyczny
z zestawienia C.
__________________________________________________________________________________________
4. Programowanie ewolucyjne możemy również realizować w wielu wersjach [4]. Istota
rozwiązania problemu optymalizacji w tym przypadku jest dwufazowa.
32
W pierwszej fazie każdego etapu działań przeprowadza się lokalne badania funkcji celu,
np. w postaci programu całkowitego, lub częściowego w otoczeniu punktu przyjmowanego na
podstawie informacji posiadanej a priori ( lub w wyniku poprzednich pomiarów) za dosta-
tecznie dobry punkt centralny.
W fazie drugiej określa się na podstawie tych wyników nowy punkt centralny wokół któ-
rego przeprowadzi się badania w kolejnym etapie. Celowym jest przy tym skorzystanie z
możliwie największej liczby już posiadanych pomiarów. W praktyce postulat ten realizuje się
najczęściej poprzez przesuwanie nowego centrum do najkorzystniejszego z wierzchołków
planu poprzedniego etapu.
Podkreślmy, że działając w ramach metodyki ewolucyjnej możemy po każdym etapie z
mienić nie tylko punkt centralny doświadczeń, lecz także zakresy zmian poszczególnych
czynników, a także obrócić ( np. o 450 ) przestrzeń poszukiwania.
__________________________________________________________________________________________
33
Zestawienie E.
Pakiet oprogramowania : OPTYMALIZACJA.
1. Lista najczęściej rozwiązywanych zadań w ramach OPYMALIZACJI:
Minimalizacja funkcji jednej zmiennej: x = ( 'funkcja ', ...);
Przeprowadzana jest metodami interpolacji kwadratowej i sześciennej z ekstrapolacją.
Minimalizacja funkcji wielu zmiennych można być przeprowadzona przy pomocy m-
funkcji stosującej metodę sympleksu Naldera-Meada: x = ( 'funkcja', ...);
lub opartej na jednej z metod zmiennej metryki BFGS: x = ( ' funkcja',...).
Minimalizacja funkcji przy ograniczeniach: x = ('fg ',...)
bazuje na jednym z wariantów sekwencyjnego programowania kwadratowego (SQP) - w
każdej iteracji aproksymuje się tu hesjan funkcji Lagrange a i linearyzuje ograniczenia.
Programowanie liniowe x = (c,A,b,...);
opiera się na jednej z wersji metody simpleksowej, umożliwiając m.in. znajdowanie
pierwszego rozwiązania bazowego.
Programowanie kwadratowe: x = (H,c,A,b,...);
rozwiązuje zadanie:
min (xT H x /2  cT x); przy A x d" b;
stosując kombinowany, stosowany i w innych funkcjach algorytm w którym kierunek
określany jest w wyniku rzutowania gradientu na ograniczenia a długość kroku poszuki-
wania w tym kierunku określa się m.in. przy pomocy tzw. funkcji kary.
Układ równań nieliniowych f(x) = 0: x = (' funkcje ', ...);
jest rozwiązywany metodami Gaussa-Newtona i Lavenberga - Marquardta.
34
2. Podstawowe zasady stosowania m-funkcji OPTYMALIZACJI:
Wprowadzenie badanej funkcji i ograniczeń następuje poprzez sprecyzowanie odpowied-
niego m-pliku. Np.
" " "
"
"
Gradienty mogą być określane numerycznie, poprzez wektor ilorazów różnicowych (je-
żeli: options(9) = 0) lub (po ustaleniu: options(9) = 1) analitycznie.
Np. gradienty funkcji f i gbędą obliczane analitycznie po uzupełnieniu podanych wyżej
deklaracji   poprzez:
" " ^ " ^ "
" "
Wywoływanie procedur optymalizacyjnych następuje po zadeklarowaniu badanej funk-
cji, ograniczeń i ewentualnie gradientów.
Liczbowe ustalenie wartości wymaganych (patrz  helpy ) argumentów, takich jak: war-
tość startowa znajdowanego wektora (np. x = [1, -1]),ograniczenia zmiennych
vlb, vub, options i parametrów globalnych (p1, p2,...(najwyżej 10)) może
nastąpić w samym tekście wywołania lub przed nim.
Np.1. Rozwiązanie zadania z ograniczeniami możemy uruchomić poprzez:
` '
` '
Np.2. Deklaracja samej funkcji może być również zawarta w jednym z argumentów.
Dopuszczalnym jest wywołanie procedury minimalizacji w postaci:
35
 ` ^ ^ ' ` " '
Y
Y Wektor ustalanych a priori parametrów   w rozwiązywanym zadaniu po-
siada następujące składowe:
1. display (opcjonalnie (1)= 0); kontroluje sposób przekazywanej na monitorze
informacji po każdej iteracji; przy options(1)= 1 wynik obliczeń jest wyświetlany;
2. stop x (opcjonalnie (2) = 10  4 ); dopuszczalna precyzja zmiennej niezależnej x;
3. stop f(opcjonalnie (3) = 10  4 ); dopuszczalna precyzja optymalizowanej funkcji;
4. uchyb g (opcjonalnie (4) = 10  7 ); podaje precyzję uwzględniania ograniczeń;
5. algorytm(opcjonalnie (5) = 0 ); wybór głównego algorytmu w danym zadaniu;
6. d-algorytm (opcjonalnie 0); wybór metody określenia kierunku poszukiwań;
7. ,-algorytm (opcjonalnie 0); wybór metody poszukiwania minimum w kierunku
,
8. specyficzny, stosuje się jedynie dla funkcji i ;
9. gradient (opcjonalnie 0); sposób zadawania gradientu; 0 - różnicowo, 1 - analitycznie
10. licznik obliczeń funkcji;
11. licznik gradientu; liczba obliczeń gradientu funkcji;
12. licznik ograniczeń ogólna liczba wyliczanych funkcji, łącznie z ograniczeniami;
13. ogr. równościowe (opcjonalnie 0) - liczba ograniczeń typu równościowego, wymienia-
nych przy wywołaniu m-funkcji na pierwszych miejscach: g(1), g(2),...;
14. max. iteracji (opcjonalnie (14) = 100n), ogranicza liczbę iteracji; n - jest tu
liczbą niezależnych zmiennych;
15. specyficzny, stosuje się jedynie dla funkcji ;
16. min. przyrostu (opcjonalnie (16) = 10-8); określa minimalny przyrost przy róż-
nicowym wyliczeniu gradientu funkcji;
17. max. przyrostu (opcjonalnie (17) = .1); określa przyrost argumentu przy różni-
cowym wyliczeniu gradientu funkcji;
18. step size (opcjonalnie 1 lub mniej): definiuje wielkość kroku w pierwszej iteracji.
Przykłady deklaracji parametru: (1) = 1; (2) = le-8; (13) = 2;
36
Dodatek.
Tekst niektórych m-plików stosowanych w ćwiczeniach.
1. Tekst m- pliku:   :
37
2. Tekst m- pliku:   :
38
3. Tekst m- pliku:   :
39
40
41
UWAGI BIBLIOGRAFICZNE i LITERATURA.
Wiedza podstawowa w zakresie nieliniowego programowania matematycznego (optymali-
zacji statycznej) jest przekazywana zwięz
le w niektórych podręcznikach z metod numerycz-
nych, np. [3]. Problematyka jednowymiarowej optymalizacji łączy się ściśle (ze względu na
znaną równość: df(u)/du|u=u*= 0)z problem rozwiązywania równania nieliniowego, sta-
nowiącym podstawowy problem analizy numerycznej. Rozwinięcie tej problematyki
w kierunku rozwiązywania zadań optymalizacji w obecności zakłóceń znajdujemy przede
wszystkim w monografiach poświęconych aproksymacji stochastycznej (np. jeden z rozdzia-
łów [1]). Z niektórych podręczników poruszających tematykę optymalizacji w sytuacjach
niedeterministycznych warto polecić systematyzujący wiedzę podstawową [1], lub odwołują-
cy się do badań operacji technologicznych w przemyśle elektromaszynowym (np.[6]).
Specyficznym typem techniki (przybliżonego) rozwiązywania zadań optymalizacji są algo-
rytmy ewolucyjne, zwane też genetycznymi. Technika obliczeń tego rodzaju rozwinęła się w
latach dziewięćdziesiątych. Interesujące (same przez się) wykłady z algorytmów ewolucyj-
nych w podręczniku [4] poprzedzone są zwięzłym, przekazanym w dostępnej formie prze-
glądem podstawowych problemów optymalizacji.
Układy regulacji ekstremalnej przedstawiane są w niektórych podręcznikach teorii regula-
cji. Model układu zbliżonego do badanego w ćw.1 możemy np. znalez
ć w książce na temat
regulatorów [5], zapewne znanej z poprzednich semestrów studiów. Podstawowe m-funkcje
pakietu Optymalizacji na tle stosowanych w nich metod programowania przedstawione s ą w
jednym z rozdziałów [7].
1. J. Seidler, A. Badach, W. Modlisz.: Metody rozwiązywania zadań optymalizacji. WNT,
Warszawa, 1980.
2. W. Findeisen, J. Szymanowski, A. Wierzbicki.: Teoria i metody obliczeniowe optymali-
zacji. PWN, Warszawa, 1980.
3. A. Bjorck, G. Dahlquist.:Metody numeryczne. PWN, Warszawa, 1987.
4. J. Arabas.: Wykłady z algorytmów ewolucyjnych. WNT, Warszawa, 2001.
5. L.Trybus.: Regulatory wielofunkcyjne. WNT, Warszawa, 1992
6. E. Pająk, K. Wieczorkowski.: Podstawy optymalizacji operacji technologicznych w przy-
kładach. PWN, Warszawa - Poznań 1982.
7. A.Zalewski, R.Cegieła.: Matlab  obliczenia numeryczne i ich zastosowania. Wyd. Na-
kom, Poznań, 1996.
42