Newtonova metóda a kvázi-Newtonove metódy diskutované v predchádzajúcej časti sú veľmi efektívne ako prostriedky na riešenie problémov neobmedzenej minimalizácie. Avšak prezentujú celkom vysoké požiadavky na množstvo použitej pamäte počítača. Je to spôsobené tým, že voľba smeru hľadania si vyžaduje riešenie systémov lineárne rovnice, ako aj so vznikajúcou potrebou ukladať matice typu Preto pre veľké nemusí byť použitie týchto metód možné. Do značnej miery sú metódy konjugovaných smerov tohto nedostatku ušetrené.
Zvážte problém minimalizácie kvadratickej funkcie
so symetrickou kladne-definitou maticou A Pripomeňme, že jej riešenie vyžaduje jeden krok Newtonovej metódy a nie viac ako kroky kvázi-Newtonovej metódy Metódy konjugovaných smerov nám umožňujú nájsť aj minimálny bod funkcie (10.33) v maximálne krokoch. To sa dosiahne špeciálnym výberom smerov vyhľadávania.
Povieme, že nenulové vektory sú vzájomne konjugované (vzhľadom na maticu A), ak pre všetky
Metódou konjugovaných smerov pre minimalizáciu kvadratickej funkcie (10.33) rozumieme metódu
v ktorých sú smery vzájomne konjugované, a kroky
sa získajú ako riešenie problémov s jednorozmernou minimalizáciou:
Veta 10.4. Metóda konjugovaných smerov umožňuje nájsť minimálny bod kvadratickej funkcie (10 33) maximálne v krokoch.
Metódy konjugovaných smerov sa navzájom líšia v spôsobe konštrukcie konjugovaných smerov. Najznámejšia z nich je metóda konjugovaného gradientu.
Pri tejto metóde pokyny vytvárajú pravidlo
Pretože prvý krok tejto metódy sa zhoduje s krokom metódy najstrmšieho zostupu. Dá sa ukázať (nebudeme to robiť), že pokyny (10.34) skutočne sú
konjugovať vzhľadom na maticu A. Navyše sa ukázalo, že gradienty sú vzájomne ortogonálne.
Príklad 10.5. Na minimalizáciu kvadratickej funkcie aplikujeme metódu konjugovaného gradientu - z príkladu 10.1. Formulár si napíšeme kde
Zoberme si počiatočnú aproximáciu
1. krok metódy sa zhoduje s prvým krokom metódy najstrmšieho zostupu. Preto (pozri príklad 10.1)
2. krok. Vypočítať
Keďže riešenie sa ukázalo byť nájdené v dvoch krokoch.
Aby sa táto metóda dala použiť na minimalizáciu ľubovoľnej hladkej funkcie, vzorec (10.35) na výpočet koeficientu sa prevedie do tvaru
alebo do výhľadu
Výhodou vzorcov (10 36), (10.37) je, že explicitne neobsahujú maticu A.
Minimalizácia funkcie metódou konjugovaného gradientu sa uskutočňuje podľa vzorcov
Koeficienty sa vypočítajú podľa jedného zo vzorcov (10.36), (10.37).
Iteračný proces tu už nekončí po konečnom počte krokov a smery nie sú, všeobecne povedané, konjugované s ohľadom na nejakú maticu.
Jednorozmerné úlohy minimalizácie (10.40) je potrebné riešiť numericky. Poznamenávame tiež, že často v metóde konjugovaného gradientu pri , koeficient sa nevypočítava podľa vzorcov (10.36), (10.37), ale predpokladá sa, že je rovný nule. V tomto prípade sa ďalší krok v skutočnosti vykonáva metódou najstrmšieho zostupu. Táto „aktualizácia“ metódy umožňuje znížiť vplyv výpočtovej chyby.
Pre niektorých silne konvexnú hladkú funkciu dodatočné podmienky metóda konjugovaného gradientu má vysokú superlineárnu rýchlosť konvergencie. Zároveň je jeho náročnosť nízka a porovnateľná s náročnosťou najstrmšieho spôsobu zostupu. Ako ukazuje výpočtová prax, je o niečo menej efektívna ako kvázi-newtonské metódy, ale kladie oveľa nižšie požiadavky na použitú počítačovú pamäť. V prípade, že sa rieši problém minimalizácie funkcie s veľmi veľkým počtom premenných, metóda konjugovaného gradientu sa javí ako jediná vhodná univerzálna metóda.
Gradientové metódy založené len na gradientovom výpočte R(X), sú metódy prvého rádu, keďže na intervale krokov nahrádzajú nelineárnu funkciu R(X) lineárne.
Účinnejšie môžu byť metódy druhého rádu, ktoré využívajú nielen prvé, ale aj druhé deriváty R(X) v aktuálnom bode. Tieto metódy však majú svoje neriešiteľné problémy – výpočet druhých derivácií v určitom bode, navyše ďaleko od optima, matica druhých derivácií môže byť zle podmienená.
Metóda konjugovaného gradientu je pokusom spojiť výhody metódy prvého a druhého rádu a zároveň odstrániť ich nedostatky. V počiatočných štádiách (ďaleko od optima) sa metóda správa ako metóda prvého rádu a v blízkosti optima sa približuje metódam druhého rádu.
Prvý krok je podobný prvému kroku metódy najstrmšieho zostupu, druhý a ďalší krok sa vždy vyberú v smere, ktorý vznikne ako lineárna kombinácia gradientových vektorov v danom bode a v predchádzajúcom smere.
Algoritmus metódy možno napísať nasledovne (vo vektorovej forme):
x 1 \u003d x 0 – hgrad R (x 0),
x i+1 \u003d x i - h.
Hodnotu α možno približne zistiť z výrazu
Algoritmus funguje nasledovne. Z východiskového bodu X 0 hľadám min R(X) v smere sklonu (metódou najstrmšieho klesania), potom od nájdeného bodu a ďalej je druhým výrazom určený smer hľadania min. Hľadanie minima v smere je možné vykonať ľubovoľným spôsobom: môžete použiť metódu sekvenčného skenovania bez korekcie kroku skenovania pri prejdení minima, takže presnosť dosiahnutia minima v smere závisí od veľkosti kroku h.
Pre kvadratickú funkciu R(X) možno nájsť riešenie P kroky (P je rozmer problému). Pri ostatných funkciách bude vyhľadávanie pomalšie a v niektorých prípadoch nemusí vôbec dosiahnuť optimum kvôli silnému vplyvu výpočtových chýb.
Jedna z možných trajektórií hľadania minima dvojrozmernej funkcie metódou konjugovaného gradientu je znázornená na obr. jeden.
Prvé štádium. Vykonanie gradientovej metódy.
Nastavíme počiatočnú aproximáciu X 1 0 ,X 20. Určte hodnotu kritéria R(X 1 0 ,X 20). Zadajte k = 0 a prejdite na krok 1 počiatočnej fázy.
Krok 1. 
a 
.
Krok 2 Ak modul spádu 
Krok 3
X k+1 = X k – h grad R(X k)).
Krok 4 R(X 1k +1, X 2k+1). Ak R(X 1k +1, X 2 000 + 1)< R(X 1 k , X 2 k), potom zadajte k = k+1 a prejdite na krok 3. Ak R(X 1k +1, X 2k+1) ≥ R(X 1 k , X 2 k), potom prejdite na hlavný krok.
Hlavné pódium.
Krok 1. Vypočítajte R(x 1 k + g, x 2 k), R(x 1 k – g, x 2 k), R(x 1 k, x 2 k + g), R(x 1 k, x 2 k) . V súlade s algoritmom z centrálnej alebo párovej vzorky vypočítajte hodnotu parciálnych derivácií 
a 
. Vypočítajte hodnotu modulu gradientu 
.
Krok 2 Ak modul spádu 
, potom zastavte výpočet a považujte bod (x 1 k , x 2 k) za optimálny bod. V opačnom prípade prejdite na krok 3.
Krok 3 Vypočítajte koeficient α podľa vzorca:
Krok 4 Dokončite pracovný krok výpočtom vzorca
x k+1 = x k – h .
Krok 5 Určte hodnotu kritéria R(X 1k +1, X 2k+1). Dajte k = k+1 a prejdite na krok 1.
Príklad.
Pre porovnanie zvážte riešenie z predchádzajúceho príkladu. Prvý krok robíme podľa spôsobu najstrmšieho zostupu (tabuľka 5).
Tabuľka 5
Našiel najlepší bod. V tomto bode vypočítame deriváty: DR/ dx 1 = –2.908; DR/ dx 2 = 1,600; vypočítame koeficient α, ktorý zohľadňuje vplyv gradientu v predchádzajúcom bode: α = 3,31920 ∙ 3,3192/8,3104 2 =0,160. Urobíme pracovný krok v súlade s algoritmom metódy, dostaneme X 1 = 0,502, X 2 = 1,368. Ďalej sa všetko opakuje podobne. Nižšie v tabuľke. 6 zobrazuje aktuálne súradnice vyhľadávania pre ďalšie kroky.
Tabuľka 6
Pravidlá zadávania funkcií:
Napríklad x 1 2 + x 1 x 2 , napíšte ako x1^2+x1*x2Generuje smery vyhľadávania, ktoré sú konzistentnejšie s geometriou minimalizovanej funkcie.
Definícia . Nazývajú sa dva n-rozmerné vektory x a y konjugovaný vzhľadom na maticu A (alebo A-adjoint), ak skalárny produkt(x, Ay) = 0. Tu je A n x n symetrická pozitívne definitná matica.
.
,
.
sú zvolené tak, že smer dk je A-konjugovaný so všetkými predtým zostrojenými smermi. 
Príklad. Nájdite minimum funkcie pomocou metódy konjugovaného gradientu: f(X) = 2x 1 2 +2x 2 2 +2x 1 x 2 +20x 1 +10x 2 +10 .
rozhodnutie. Ako smer vyhľadávania vyberte vektorový gradient v aktuálnom bode:
|
Metóda je určená na riešenie problému (5.1) a patrí do triedy metód prvého rádu. Metóda je modifikáciou metódy najstrmšieho zostupu (výstupu) a automaticky zohľadňuje vlastnosti účelovej funkcie, urýchľujúcu konvergenciu.
Popis algoritmu
Krok 0. Vyberie sa počiatočný aproximačný bod, parameter dĺžky kroku , presnosť riešenia a vypočíta sa počiatočný smer hľadania.
krok k. Na k-tý krok je minimum (maximum) účelovej funkcie na priamke vedenej z bodu v smere . Nájdený minimálny (maximálny) bod určuje ďalší k-tá aproximácia, po ktorej sa určí smer hľadania
Vzorec (5.4) je možné prepísať do ekvivalentnej formy
.
Algoritmus ukončí svoju prácu hneď, ako je splnená podmienka; ako riešenie sa berie hodnota poslednej získanej aproximácie.
Newtonova metóda
Metóda je určená na riešenie problému (5.1) a patrí do triedy metód druhého rádu. Metóda je založená na Taylorovom expanzii účelovej funkcie a skutočnosti, že v extrémnom bode je gradient funkcie rovný nule, t.j.
Vskutku, nech nejaký bod leží dostatočne blízko k bodu požadovaného extrému. Zvážte i zložku gradientu účelovej funkcie a rozvinúť ju v bode podľa Taylorovho vzorca až po derivácie prvého rádu:
. (5.5)
Vzorec (5.5) prepíšeme do maticového tvaru, berúc do úvahy to :
kde je Hessova matica účelovej funkcie v bode .
Predpokladajme, že Hessiánska matica je nedegenerovaná. Potom má inverzná matica. Vynásobením oboch strán rovnice (5.6) vľavo dostaneme , odkiaľ
. (5.7)
Vzorec (5.7) definuje algoritmus Newtonovej metódy: prepočet aproximácií pomocou k
Algoritmus ukončí svoju prácu hneď, ako je splnená podmienka
,
kde je daná presnosť riešenia; ako riešenie sa berie hodnota poslednej získanej aproximácie.
Newton-Raphsonova metóda
Metóda je metódou prvého rádu a je určená na riešenie systémov n nelineárne rovnice c n neznámy:
Túto metódu je možné uplatniť najmä pri hľadaní stacionárnych bodov účelovej funkcie úlohy (5.1), kedy je potrebné riešiť sústavu rovníc z podmienky .
Nech je bod riešením sústavy (5.9) a bod sa nachádza blízko . Rozšírenie funkcie v bode pomocou Taylorovho vzorca, máme
odkiaľ (podľa podmienky) nasleduje
, (5.11)
kde je Jacobiánska matica vektorovej funkcie . Predpokladajme, že Jacobiho matica je nedegenerovaná. Potom má inverznú maticu. Vynásobením oboch strán rovnice (5.11) vľavo dostaneme 
, kde
. (5.12)
Vzorec (5.12) definuje algoritmus Newton-Raphsonovej metódy: prepočet aproximácií pomocou k iterácia sa vykonáva podľa vzorca
V prípade jednej premennej, keď sa systém (5.9) zvrhne do jedinej rovnice , vzorec (5.13) nadobudne tvar
, (5.14)
kde je hodnota derivácie funkcie v bode .
Na obr. 5.2 je znázornená schéma implementácie Newton-Raphsonovej metódy pri hľadaní riešenia rovnice.
Poznámka 5.1. Konvergencia numerických metód spravidla silne závisí od počiatočnej aproximácie.
Poznámka 5.2. Metóda Newton a Newton-Raphson vyžaduje veľké množstvo výpočtov (v každom kroku je potrebné vypočítať a invertovať Hesseho a Jacobiho maticu).
Poznámka 5.3. Pri používaní metód je potrebné brať do úvahy možnosť výskytu mnohých extrémov v cieľovej funkcii (vlastnosti multimodalita).
LITERATÚRA
1. Afanasiev M.Yu., Suvorov B.P. Operačný výskum v ekonómii: Návod. - M.: Ekonomická fakulta Moskovskej štátnej univerzity, TEIS, 2003 - 312 s.
2. Bazara M, Shetty K. Nelineárne programovanie. Teória a algoritmy: Per. z angličtiny. – M.: Mir, 1982 – 583 s.
3. Berman G.H. Zbierka úloh pre kurz matematickej analýzy: Učebnica pre vysoké školy. - Petrohrad: "Špeciálna literatúra", 1998. - 446 s.
4. Wagner G. Základy operačného výskumu: V 3 zväzkoch. Za. z angličtiny. – M.: Mir, 1972. – 336 s.
5. Wentzel E. C. Operačný výskum. Úlohy, zásady, metodika - M.: Nauka, 1988. - 208 s.
6. Demidovič B.P. Zbierka úloh a cvičení z matematickej analýzy . – M.: Nauka, 1977. – 528 s.
7. Degtyarev Yu.I. Operačný výskum. - M .: Vyššie. škola, 1986. - 320 s.
8. Nureev R.M. Zbierka úloh z mikroekonómie. - M.: NORMA, 2006. - 432 s.
9. Solodovnikov A. S., Babaitsev V.A., Brailov A.V. Matematika v ekonómii: Učebnica: Za 2 hodiny - M.: Financie a štatistika, 1999. - 224 s.
10. Taha H.Úvod do operačného výskumu, 6. vyd.: Per. z angličtiny. – M.: Williams Publishing House, 2001. – 912 s.
11. Himmelblau D. Aplikované nelineárne programovanie: Per. z angličtiny. – M.: Mir, 1975 – 534 s.
12. Shikin E. AT., Shikina G.E. Operačný výskum: Učebnica - M.: TK Welby, Vydavateľstvo Prospekt, 2006. - 280 s.
13. Operačný výskum v ekonomike: Učebnica. príručka pre vysoké školy / N. Sh. Kremer, B. A. Putko, I. M. Trishin, M. N. Fridman; Ed. Prednášal prof. N.Sh.Kremer. - M.: Banky a burzy, UNITI, 1997. - 407 s.
14. Matice a vektory: Učebnica. príspevok / Ryumkin V.I. - Tomsk: TGU, 1999. - 40 s.
15. Sústavy lineárnych rovníc: Učebnica. príspevok / Ryumkin V.I. - Tomsk: TSU, 2000. - 45 s.
| ÚVOD ………………………………………………………………………………… ................. | |
| 1. ZÁKLADY MATEMATICKÉHO PROGRAMOVANIA………………... | |
| 1.1. Vyjadrenie problému matematického programovania .................................................. .... | |
| 1.2. Odrody ZMP ……………………………………………………………………… ... ... | |
| 1.3. Základné pojmy matematického programovania ................................................ .. | |
| 1.4. Smerová derivácia. Prechod ............................................................ | |
| 1.5. Dotykové nadroviny a normály……………………………………………………………………….. | |
| 1.6. Taylorova expanzia……………………………………………………………………………………………….. .......... | |
| 1.7. ZNLP a podmienky existencie jeho riešenia ............................................ ........... | |
| 1.8. Úlohy ............................................................................................ ............................................ | |
| 2. RIEŠENIE PROBLÉMU NELINEÁRNEHO PROGRAMOVANIA BEZ LIMITOV ...................................... ............................................................. ............................................. | |
| 2.1. Nevyhnutné podmienky Riešenia ZNLP bez obmedzení ................................................. . | |
| 2.2. Dostatočné podmienky na riešenie neobmedzeného ZNLP.................................................. ...................... | |
| 2.3. Klasická metóda riešenia ZNLP bez obmedzení .................................................. ... | |
| 2.4. Úlohy ................................................................ ................................................. | |
| 3. RIEŠENIE PROBLÉMU NELINEÁRNEHO PROGRAMOVANIA ZA OBMEDZENÍ - ROVNOSŤ...................................... ...................................................................... ............................. | |
| 3.1. Metóda Lagrangeových multiplikátorov ................................................................................ ................. | |
| 3.1.1. Účel a opodstatnenie metódy Lagrangeových multiplikátorov………………… | |
| 3.1.2. Schéma implementácie Lagrangeovej multiplikačnej metódy…………………………... | |
| 3.1.3. Interpretácia Lagrangeových multiplikátorov ………………………………… | |
| 3.2. Metóda nahradenia ……………………………………………………………………………………………………………………………… .. ........... | |
| 3.3. Úlohy ………………………………………………………………………… ................................... | |
| 4. RIEŠENIE PROBLÉMU NELINEÁRNEHO PROGRAMOVANIA V OBMEDZENÍCH-NEROVNOSTI………………………………………………………….. | |
| 4.1. Zovšeobecnená metóda Lagrangeových multiplikátorov ………………………………… | |
| 4.2. Kuhn-Tuckerove podmienky……………………………….................................. .............................. | |
| 4.2.1. Nevyhnutnosť podmienok Kuhn-Tucker……………………………………………… | |
| 4.2.2. Dostatočnosť Kuhn-Tuckerových podmienok……………………………………………….. | |
| 4.2.3. Metóda Kuhn-Tucker………………………………………………………………………………………………………………………………. ......... | |
| 4.3. Úlohy ………………………………………………………………………… ................................... | |
| 5. NUMERICKÉ METÓDY RIEŠENIA PROBLÉMU NELINEÁRNEHO PROGRAMOVANIA ………………………………………………………………………………… | |
| 5.1. Koncept algoritmu ……………………………………………………………………………………………………………………… ………………………………………………… | |
| 5.2. Klasifikácia numerických metód ………………………………………………… | |
| 5.3. Algoritmy numerických metód …………………………………………………... | |
| 5.3.1. Metóda najrýchlejšieho zostupu (výstupu) ………………………………………… | |
| 5.3.2. Metóda konjugovaného gradientu ……………………………………………………………………………………………………………………………… | |
| 5.3.3. Newtonova metóda …………………………………………………………………………………………………. ... | |
| 5.3.4. Newton-Raphsonova metóda………………………………………………………... | |
| LITERATÚRA……………………………………………………………………… ........................ |
Pozrite si časť 1.2 pre definície lineárnych a nelineárnych funkcií
Metóda konjugovaného gradientu (v anglickej literatúre „conjugated gradient method“) je iteratívna numerická metóda(prvého rádu) riešenie optimalizačných problémov, ktoré vám umožňuje určiť extrém (minimum alebo maximum) cieľovej funkcie:
sú hodnoty argumentu funkcie (riadené parametre) na reálnej ploche.
V súlade s uvažovanou metódou sa extrém (maximum alebo minimum) účelovej funkcie určuje v smere najrýchlejšieho nárastu (zníženia) funkcie, t.j. v smere gradientu (antigradientu) funkcie. Gradientová funkcia v bode je vektor, ktorého projekcie na súradnicové osi sú parciálne derivácie funkcie vzhľadom na súradnice:
kde i, j,…, n sú jednotkové vektory rovnobežné so súradnicovými osami.
Gradient v základnom bode 
je striktne ortogonálny k povrchu a jeho smer ukazuje smer najrýchlejšieho nárastu funkcie a opačný smer (antigradient) ukazuje smer najrýchlejšieho poklesu funkcie.
Metóda konjugovaného gradientu je ďalším vývojom metódy najstrmšieho zostupu, ktorá kombinuje dva koncepty: gradient objektívnej funkcie a konjugovaný smer vektorov. Vo všeobecnosti je proces hľadania minima funkcie iteratívny postup, ktorý je napísaný vo vektorovej forme takto:
kde znamienko „+“ sa používa na nájdenie maxima funkcie a znamienko „-“ sa používa na nájdenie minima funkcie.
Jednotkový vektor konjugovaných smerov, ktorý je určený vzorcom:
Existuje niekoľko spôsobov, ako definovať hodnoty hmotnosti (premenné), ktoré sa používajú na určenie smeru konjugácie.
Prvým spôsobom je zvážiť definíciu váhového faktora podľa vzorca Fletcher-Reeves (Fletcher-Reeves):
- modul gradientu určuje rýchlosť nárastu alebo poklesu funkcie v smere gradientu, resp. protispádu.
Ako druhú metódu zvážte definíciu váhového faktora podľa Polak-Riberovho vzorca (Polak-Ribiere):
V súlade s prezentovanými výrazmi sa nový konjugovaný smer získa sčítaním gradientu (antigradientu) v bode obratu a predchádzajúceho smeru pohybu, vynásobeného koeficientom. Metóda konjugovaného gradientu teda formuje smer hľadania na optimálnu hodnotu pomocou informácií o hľadaní získaných v predchádzajúcich fázach zostupu. Treba poznamenať, že konjugované smery P, P, ..., P sú vypočítané pomocou Fletcher-Reevesovho vzorca, ktorý umožňuje zostaviť konjugované vektory vzhľadom na nejakú symetrickú maticu pre ľubovoľne danú funkciu.
Trajektória zostupu v metóde konjugovaného gradientu (minimálne vyhľadávanie)
Geometrický význam metódy konjugovaného gradientu je nasledovný: z daného počiatočného bodu x sa vykoná zostup v smere p (gradient alebo antigradient) do nového bodu x, v ktorom sa určí gradientový vektor funkcie. Pretože x je minimum funkcie v smere p, gradientový vektor funkcie v x je ortogonálny k vektoru p. Potom sa určí vektor p, ktorý je ortogonálny vzhľadom na nejakú symetrickú maticu k vektoru p. Výsledkom je zostup v nájdenom smere do nového bodu x.
Trajektória pohybu do extrémneho bodu pomocou metódy najstrmšieho zostupu (zelená čiara) a metódy konjugovaného gradientu (červená čiara).
Treba poznamenať, že každých n + 1 krokov je potrebné reštartovať algoritmickú procedúru (n je rozmer vyhľadávacieho priestoru). Opätovné spustenie algoritmu je potrebné, aby sa zabudlo na posledný smer hľadania a algoritmus sa začal znova v smere najrýchlejšieho zostupu.
Hodnota kroku sa volí z podmienky minimálnej cieľovej funkcie f(x) v smere pohybu, t.j. ako výsledok riešenia úlohy jednorozmernej optimalizácie v smere gradientu alebo antigradientu:
Inými slovami, veľkosť kroku je určená riešením tejto rovnice:
Hľadanie optimálneho riešenia končí, keď v kroku iteračného výpočtu (niekoľko kritérií):
Trajektória vyhľadávania zostáva v malom susedstve aktuálneho bodu vyhľadávania:
Prírastok účelovej funkcie sa nemení:
Gradient účelovej funkcie v bode lokálneho minima zmizne:
Metóda konjugovaného gradientu je metódou prvého rádu, ale má kvadratickú rýchlosť konvergencie, podobne ako newtonovské metódy výpočtu. Gradientová metóda spolu s jej mnohými modifikáciami je bežnou a efektívna metóda hľadanie optima skúmaných objektov. Nevýhodou gradientového vyhľadávania (ako aj metód diskutovaných vyššie) je, že pri jeho použití možno nájsť iba lokálny extrém funkcie. Aby ste našli iných lokálne extrémy je potrebné hľadať z iných východísk.
Spôsob výpočtu
1 krok: Definícia analytických výrazov (v symbolickej forme) na výpočet gradientu funkcie
2 krok: Nastavte počiatočnú aproximáciu
3 krok: Je určená potreba reštartovať algoritmickú procedúru na resetovanie posledného smeru vyhľadávania. V dôsledku reštartu sa vyhľadávanie opäť vykoná v smere najrýchlejšieho klesania.
4 krok: Vypočítajte súradnice jednotkového vektora pomocou vzorca získaného v kroku 1 a určte súradnice nový bod pri pohybe v smere jednotkového vektora ako funkcie vzorkovacieho času.
Výpočet váhového koeficientu a jednotkového vektora konjugovaných smerov v aktuálnom čase vzorky (Fletcher-Reevesov vzorec):
Pre prvý krok výpočtu sa váhový koeficient nevypočíta (alebo v prípade reštartu algoritmu) a jednotkový vektor konjugovaných smerov sa určí nasledovne.
