1 

 

MINIMALIZACJA FUNKCJI WIELU ZMIENNYCH  

METODY SPRZĘŻONYCH KIERUNKÓW POPRAWY 

 
 
Wprowadzenie 
 
 

Celem  dwiczenia  jest  zapoznanie  się  z  niektórymi  metodami  minimalizacji  funkcji  wielu 

zmiennych bez ograniczeo. Metody te można podzielid na następujące klasy: 

- 

metody poszukiwao prostych; 

- 

metody kierunków poprawy, wśród których możemy wyróżnid następujące grupy: 
1.  metody bezgradientowe,  w  przypadku  których  do  znalezienia  minimum potrzebne 

jest wyznaczenie jedynie wartości wskaźnika jakości 

 

f x

; 

2.  metody  gradientowe,  dla  w  których  procesie  poszukiwao  minimum  korzystamy  z 

wyznaczanych  wartości  minimalizowanego  wskaźnika  jakości 

 

f x

  oraz  jego 

gradientu 

 

x

f



x

; 

3.  metody  newtonowskie,  gdzie  poszukiwanie  minimum  przeprowadzamy  z 

wyznaczeniem  w  kolejnych  punktach  wartości  wskaźnika  jakości,  jego  gradientu 

oraz hesjanu 

 

T

x

x

f

 









x

. 

Dokładnie  zostaną  omówione  dwie  metody  wykorzystujące  w  procesie  minimalizacji  kierunki 
sprzężone. 
 

Dla  wszystkich  typów  metod  należących  do  klasy  metod  kierunków  poprawy 

wykorzystujemy  wspólny  schemat  prowadzenia  obliczeo  iteracyjnych.  Polega  on  na  tym,  że  do 
punktu  odpowiadającego  minimum  wskaźnika  jakości, 

 

f x

,  dochodzimy  w  kolejnych  krokach 

poszukiwania  minimum  wzdłuż  odpowiednio  wyznaczonych  kierunków 

d

  w  przestrzeni  

n

-wymiarowej, zwanych kierunkami poszukiwao.  

Jeżeli po 

1

k



 krokach optymalizacji osiągnięto punkt poszukiwao 

1

ˆ

k



x

 to w kolejnym 

k

-tym kroku 

przeprowadza  się  minimalizację  wzdłuż  prostej  wyznaczonej  przez  punkt 

1

ˆ

k



x

  i  wektor  kierunku 

k

d

, tj. znajdujemy taką optymalna wartośd  ˆ

k



, że 

 





1

ˆ

ˆ

: min

k

k

k

k

k

f











x

d

, 

 
a więc rozwiązujemy zagadnienie minimalizacji funkcji jednej zmiennej - tą zmienną jest 

k



. 

Kierunki te mogą byd stałe w trakcie całego iteracyjnego procesu poszukiwao minimum bądź też 
mogą ulegad zmianie na kolejnych etapach w zależności od wartości minimalizowanej funkcji, jej 
gradientu lub również hesjanu. 
 

W  algorytmie  poszukiwao  można  wyróżnid  następujące,  wspólne  dla  wszystkich  metod, 

fazy: 

- 

wybór punktu początkowego poszukiwao 

0

x

; 

- 

wyznaczenie kolejnego punktu  ˆ

k

x

, stanowiącego przybliżenie punktu  ˆx  odpowiadającego 

minimum  wskaźnika  jakości;  punkt  ten  wyznaczamy  przez  poszukiwania  wzdłuż  kierunku 

k

d

, którego określenie, jak i również odległośd przesunięcia w tym kierunku są zależne od 

 

2 

wybranej  metody  optymalizacji;  kolejny  punkt,  będący  nowym  (lepszym)  przybliżeniem 
punktu minimalizującego funkcję 

 

f x

, jest wyznaczany z zależności 

 

1

ˆ

ˆ

ˆ

;

k

k

k

k









x

x

d

 

 

 

- 

sprawdzenie  warunków  zbieżności  (kryterium  osiągnięcia  punktu  minimalnego  wskaźnika 
jakości)  i  –  w  zależności  od  wyniku  –  kontynuowanie  poszukiwao  iteracyjnych  albo  ich 
zakooczenie. 

Punkt  początkowy  poszukiwao  wybieramy  na  podstawie  posiadanych  informacji  dotyczących 

położenia  punktu  minimalnego  wskaźnika  jakości.  Należy  podkreślid,  że  w  przypadku  zadania 
minimalizacji  nieliniowego  wskaźnika  jakości  wielu  zmiennych  dobór  punktu  początkowego 
poszukiwao  może  w  znaczący  sposób  przyspieszyd  lub  opóźnid  znalezienie  minimum  wskaźnika 
jakości albo wręcz zdecydowad o możliwości znalezienia minimum globalnego wskaźnika jakości. 
 
 
Metoda Powella (metoda bezgradientowa) 
 

Metoda Powella należy do bezgradientowych metod poprawy, w których minimum, funkcji 

celu, 

 

f x

,  znajdujemy  poprzez  przeszukiwanie  przestrzeni 

n



  w  odpowiednio  dobranych 

kierunkach  stanowiących  bazę  tej  przestrzeni.  W  metodzie  Powella  poszukiwao  dokonujemy  w 
kolejnych  iteracjach,  z  których  każda  polega  na  kolejno  wykonanych  minimalizacjach  wzdłuż  n  
kierunków, gdzie  n  jest liczbą zmiennych decyzyjnych. 
Na  zakooczenie  każdej  iteracji  dokonujemy  minimalizacji  wzdłuż  nowo  wyznaczonego  (

1

n



)-go 

kierunku  poszukiwao 

1

k



d

.  Kierunki  poszukiwao  nie  są  w  metodzie  Powella  stałe:  w  pierwszej 

iteracji  jako  kierunki  poszukiwao  wykorzystujemy  zwykle  kierunki  osi  współrzędnych  (wersory),  
a  w  koocowej  fazie  każdej  iteracji  dodawany  jest  do  zbioru  kierunków  poszukiwao  nowo 
wyznaczony kierunek 

1

k



d

, a usuwany jest zeo 

1

d

. 

 

Na  wstępie  wyznaczamy  kierunki  w  przestrzeni 

n



  n   liniowo  niezależnych  wektorów 

1

,...,

n

d

d

, będących początkowymi kierunkami poszukiwao i stanowiących tzw. bazę podstawową. 

Kierunki początkowe mogą byd wybrane dowolnie (przy spełnieniu liniowej niezależności), zwykle 
dla  uproszczenia  przyjmujemy  jako  początkowe  kierunki  poszukiwao  kierunki  osi  układu 
współrzędnych. W koocowej fazie etapu wstępnego dokonujemy minimalizacji wzdłuż ostatniego 
z  początkowych  kierunków  poszukiwao,  startując  z  punktu  początkowego, 

0

x

,  i  osiągając  punkt 

startowy dla pierwszej iteracji metody Powella, 

1,0

x

.  

 

Minimalizacja  funkcji  celu  za  pomącą  metody  Powella  przebiega  w  kolejnych  iteracjach.  

W każdej iteracji realizowane są 4 etapy (oznaczenia dotyczą  i -tej iteracji): 

1.  Startując  z  początkowego  punktu  poszukiwao  dla  iteracji  i -tej, 

,0

i

x

,  dokonujemy  n  

kolejnych  minimalizacji  wzdłuż  kierunków  poszukiwao  dla  i -tej  iteracji: 

,1

,

,...,

i

i n

d

d

.  Jako 

wynik tych minimalizacji otrzymujemy punkty 

,1

,2

,

ˆ

ˆ

ˆ

,

,...,

i

i

i n

x

x

x

. 

Kolejny punkt, będący  nowym  przybliżeniem  punktu  minimalizującego funkcję 

 

f x

,  jest 

wyznaczany z zależności 
 
 

,

,

1

,

,

ˆ

ˆ

ˆ

.

i k

i k

i k

i k









x

x

d

 

 

2.  Wyznaczamy nowy kierunek poszukiwao zgodnie z zależnością 

 

 

3 

,

1

,

,0

ˆ

ˆ

i n

i n

i







d

x

x

 

 

 
a następnie dokonujemy wzdłuż nowo wyznaczonego kierunku, 

,

1

i n



d

, minimalizacji funkcji 

celu – osiągając punkt 

,

1

ˆ

i n



x

. 

3.  Sprawdzamy warunek zakooczenia obliczeo (kryterium stopu): 

 

,

1

,0

ˆ

ˆ

i n

i









x

x

 

 
(możliwe jest również wykorzystanie innych kryteriów stopu lub ich kombinacji: 

 



  

,

1

,0

ˆ

ˆ

i n

i

f

f









x

x

 

lub 

 



  

,

1

,0

,

1

,0

ˆ

ˆ

ˆ

ˆ

i n

i

i n

i

f

f













x

x

x

x

 

lub 
 

max

i

It



) 

 

 
gdzie 



  jest  pewną,  zadaną  z  góry  dokładnością  przeprowadzania  minimalizacji.  Jeśli 

kryterium  stopu  jest  spełnione,  następuje  zakooczenie  procesu  minimalizacji  i  przyjęcie 
punktu 

,

1

ˆ

i n



x

 za punkt optymalny,  ˆx . 

4.  Jeśli  warunek  zakooczenia  obliczeo  nie  jest  spełniony  dokonujemy  przedefiniowania 

(zmiany)  kierunków  poszukiwao  dla  kolejnej  (

1

i



)-szej  iteracji  według  następującego 

algorytmu: 

 

1,1

,2

1,2

,3

1,

,

1

          

.

i

i

i

i

i

n

i n















d

d

d

d

d

d

 

 

 
Nowy  kierunek  wyznaczamy  ostatnim  kierunkiem  poszukiwao  w  kolejnej  iteracji,  a  ze 
zbioru  kierunków  poszukiwao  usuwamy  kierunek  będący  na  pierwszej  pozycji  w  iteracji  

i

-tej. 

 

Teoria metody Powella dotyczy funkcji kwadratowych. Metodę tę można jednak stosowad 

do  innych  funkcji  celu.  Oczywiście  trudno  się  wtedy  spodziewad  osiągnięcia  minimum  w  n  
iteracjach dla funkcji celu  n  zmiennych. Proces obliczeniowy trwa w tym przypadku tym dłużej, im 
mniej dokładnie można funkcje celu aproksymowad za pomocą funkcji kwadratowej. 
 
 
Metoda gradientu sprzężonego (metoda gradientowa) 
 
 

Metoda  gradientu  sprzężonego  należy  do  mieszanych  metod  kierunków  poprawy, 

stanowiących połączenie metod poszukiwania minimum funkcji celu 

 

f x

 w kierunku przeciwnym 

do kierunku gradientu funkcji (metody gradientowe) i bezgradientowych metod wykorzystujących 
własności  sprzężonych  kierunków  poszukiwania  minimum.  Metoda  gradientu  sprzężonego  ma 
charakter  iteracyjny:  każda  iteracja  polega  w  tym  przypadku  na  przeprowadzeniu  minimalizacji 

 

4 

kierunkowej wzdłuż obowiązującego kierunku poszukiwao, 

d

, oraz wyznaczenia nowego kierunku 

poszukiwao dla kolejnej iteracji. 
 

Pierwszym  kierunkiem  poszukiwao  jest  kierunek  przeciwny  do  kierunku  gradientu 

minimalizowanej  funkcji  w  punkcie  startowym 

0

x

,  co  czyni  wynik  pierwszej  iteracji  tożsamy  z 

metodą najszybszego spadku: 
 
 

 

0

1

x

f

 

x

d

x

 

 
W każdej iteracji metody gradientu sprzężonego nowy kierunek poszukiwao, dla  i -tej iteracji, jest 
wyznaczany wg następującej zależności: 
 
 

 

1

ˆ

i

i

i

i

x

f





 



x

d

x

d

 

 
Współczynnik 

i



  występujący  w  powyższej  zależności  jest  dobierany  w  taki  sposób,  aby  nowo 

wyznaczony  kierunek 

1

i



d

  był  A-sprzężony  z  poprzednim  kierunkiem  poszukiwao 

i

d

  względem 

kwadratowego przybliżenia minimalizowanej funkcji celu 

 

f x

. Spełnienie podanego wymagania 

zapewni,  że  kierunki  poszukiwao  w  metodzie  gradientu  sprzężonego  będą  z  jednej  strony  w 
korzystny sposób „zawierały” kierunek przeciwny do wektora gradientu minimalizowanej funkcji, a 
z  drugiej  –  będą  kierunkami  sprzężonymi  względem  macierzy  A  przybliżenia  kwadratowego 
minimalizowanej funkcji. Algorytm doboru współczynnika funkcji 

i



, zapewniający A-sprzężonośd 

generowanych kierunków poszukiwao, jest następujący:  
 
algorytm Fletchera-Reevesa 
 

 

 

 

 

 

 

1

1

1

2

ˆ

ˆ

ˆ

2

ˆ

ˆ

ˆ

i

i

i

i

i

i

T

x

x

x

i

FR

T

x

x

x

f

f

f

f

f

f

























x

x

x

x

x

x

x

x

x

x

x

x

, 

 
algorytm Polaka-Ribiére’a 
 

 

 

 





 

 

 

 

1

1

1

1

ˆ

ˆ

ˆ

ˆ

2

ˆ

ˆ

ˆ

i

i

i

i

i

i

i

T

T

i

x

x

x

x

i

PR

T

x

x

x

f

f

f

f

f

f

f















 















x

x

x

x

x

x

x

x

x

x

x

g

x

x

x

 

gdzie wektor 

i



g

 określony jest jako różnica wektorów gradientu w odpowiednich punktach: 

 

 

 

1

ˆ

ˆ

i

i

i

x

x

f

f



  



x

x

g

x

x

. 

 
 

Dla  funkcji  kwadratowej  n   zmiennych  algorytm  gradientu  sprzężonego  powinien 

doprowadzid  do  punktu  globalnie  minimalnego  po  najwyżej  n   iteracjach,  jako  że  w  metodzie 
gradientu  sprzężonego  po  n   kolejnych  iteracjach  dysponujemy  n   kierunkami  sprzężonymi  dla 
kwadratowej  funkcji  celu.  W  związku  z  powyższym  w  metodzie  gradientu  sprzężonego  po  n  
kolejnych  iteracjach  oraz  zawsze  wtedy,  gdy  nowo  wyznaczony  kierunek  nie  jest  kierunkiem 
poprawy,  dokonuje  się  tzw.  odnowy  kierunków  poszukiwao,  poprzez  przyjęcie  jako  kierunku 
poszukiwao  dla  kolejnej  iteracji  kierunku  przeciwnego  do  wektora  gradientu  minimalizowanej 
funkcji w ostatnio osiągniętym punkcie poszukiwao. 

 

5 

 

Iteracyjne poszukiwanie minimum za pomocą metody gradientu sprzężonego kooczymy w 

przypadku,  gdy  norma  wektora  gradientu  minimalizowanej  funkcji  dla  ostatniego  przybliżenia 
punktu minimalnego jest mniejsza od założonej dokładności obliczeo 



: 

 

 

 

ˆ

i

x

f







x

x

 

 
(możliwe jest również wykorzystanie innych kryteriów stopu lub ich kombinacji: 

 

2

ˆ

i

x

f







x

x

 

lub 

1

ˆ

ˆ

i

i









x

x

 

lub 

   

1

ˆ

ˆ

i

i

f

f









x

x

 

lub 

   

1

1

ˆ

ˆ

ˆ

ˆ

i

i

i

i

f

f













x

x

x

x

 

lub 

max

i

It



). 

Jako punkt minimalizujący,  ˆx , daną funkcję przyjmuje się ostatnie przybliżenie tego punktu  ˆ

i

x

. 

 
 
DODATEK 
 
Definicje: 
Kierunki  sprzężone:  Kierunki 

1

2

,

,...,

0

n



d d

d

  nazywamy  sprzężonymi  względem  dodatnio 

określonej symetrycznej macierzy A o wymiarach  n n



 (A-sprzężonymi), jeżeli zachodzi: 

 
 

,

1,..,

     ¹

 

0

T
i

j

i j

n

i j







d Ad

 

 
Uwaga:  

1. Kierunki A-sprzężone są liniowo niezależne. 
2. Relacja A-sprzężoności nie jest przechodnia tj. z faktu 

0

T
i

j



d Ad

 oraz 

0

T

j

k



d Ad

 

nie wynika, że 

0

T
i

k



d Ad

, czyli nie wynika, że kierunki 

i

d

,

j

d

 i 

k

d

 są A-sprzężone. 

 
Rozmaitość liniowa: 

r

-wymiarową rozmaitością liniowa w przestrzeni  n -wymiarowej nazywamy 

zbiór: 
 

 

0

1

:

r

n

i

i

i













x

x

x

d

 

 
przy czym: 





,

,  

1,..., ,

i

i

r



  



 

n

i



d

 - kierunek w  n -wymiarowej przestrzeni poszukiwao, 

 

1,...,

i

i

r



d

 - kierunki liniowo niezależne, 

 

6 

0

n



x

 - dowolny punkt w  n -wymiarowej przestrzeni poszukiwao. 

 
Twierdzenie: 
Jeżeli 

1

2

,

,...,

n

d d

d

 są kierunkami A-sprzężonymi, to minimum funkcji kwadratowej  n  zmiennych 

 

 

 

1

2

T

T

f

c

 



x

b x

x Ax

 

 
w rozmaitości liniowej określonej przez te kierunki i dowolny punkt 

0

x

 może byd wyznaczone w  n  

krokach poprzez minimalizację funkcji 

 

f x

 na każdym z tych kierunków tylko jeden raz. 

 
Program dwiczenia 
 

1.  Dla  podanych  przez  prowadzącego  funkcji  wielu  zmiennych  zaimplementowad  algorytm 

poszukiwania  punktu  minimalizującego  z  zastosowaniem  metody  Powella  oraz  metody 
gradientu sprzężonego

1

. 

2.  Przedstawid  w  postaci  schematu  blokowego  algorytm  działania  badanej  metody 

minimalizacji funkcji wielu zmiennych. 

3.  Dla jednego przykładowego zestawu parametrów 

0



x

0

 i 

0, 0001





 (punktu startowego  

i  zadanej  dokładności  obliczeo)  przedstawid  wyniki  działania  metody  dla  podanej  funkcji 
celu. Wyniki przedstawid w postaci tabelarycznej: 

 

Nr iteracji 

Punkt osiągnięty 

w danej iteracji 

Wartośd funkcji celu 

w danej iteracji 

Wartośd kryterium 

stopu (przy danym 



) 

0 

 

 

 

1 

 

 

 

 

 

 

 

 

4.  Zbadad eksperymentalnie czy zbieżnośd badanej metody, dla podanej przez prowadzącego 

funkcji,  jest  zależna  od  wyboru  punktu  początkowego 

0

x

.  Odpowiedź  uzasadnid  oraz 

poprzed wynikami eksperymentów. 

5.  Zbadad eksperymentalnie czy zbieżnośd badanej metody, dla podanej przez prowadzącego 

funkcji, jest zależna od wyboru wartości parametru 



. Odpowiedź uzasadnid oraz poprzed 

wynikami eksperymentów. 

6.  W  sprawozdaniu  zamieścid  wydruki  procedur  realizujących  opisywane  metody 

minimalizacji funkcji wielu zmiennych. 

7.  Porównad wyniki działania analizowanej metody z wynikami działania metody analizowanej 

na  dwiczeniu:  „MINIMALIZACJA  FUNKCJI  WIELU  ZMIENNYCH  -  METODA  PROSTYCH 
KIERUNKÓW  POPRAWY”  (odpowiednio  met.  Powella  z  met.  Gaussa-Seidla  oraz  met. 
gradientu sprzężonego z met. najszybszego spadku). 

 
Literatura: 
 

J. Figwer, J. Mościoski, Z. Ogonowski: Laboratorium metod optymalizacji statycznej, skrypt 
uczelniany nr 2114, Wydawnictwo Politechniki Śląskiej, Gliwice 1998 

                                                 

1

 O wyborze metody decyduje prowadzący zajęcia