Newtonova metóda a kvázi-Newtonove metódy diskutované v predchádzajúcom odseku sú veľmi účinné ako prostriedok na riešenie neobmedzených problémov minimalizácie. Predstavujú však celkom vysoké požiadavky na množstvo použitej pamäte počítača. Je to spôsobené tým, že výber smeru vyhľadávania si vyžaduje systémy riešenia lineárne rovnice, ako aj so vznikajúcou potrebou ukladať matice typu Preto pre veľké môže byť použitie týchto metód nemožné. Vo významnej miere sú metódy konjugovaného smeru zbavené tejto nevýhody.
Zvážte problém minimalizácie kvadratickej funkcie
so symetrickou kladne definitívnou 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 smerovania vám tiež neumožňujú nájsť minimálny bod funkcie (10.33). ako kroky. To sa dá dosiahnuť š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 vám umožňuje nájsť minimálny bod kvadratickej funkcie (10 33) v maximálne 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 použijeme metódu konjugovaného gradientu - z príkladu 10.1. Napíšeme to v tvare 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. Poďme počítať
Keďže riešenie sa ukázalo byť nájdené v dvoch krokoch.
Aby sa táto metóda použila na minimalizáciu ľubovoľného hladká funkcia Vzorec (10.35) na výpočet koeficientu sa prevedie do formulára
alebo do výhľadu
Výhodou vzorcov (10 36), (10.37) je, že explicitne neobsahujú maticu A.
Funkcia je minimalizovaná metódou konjugovaného gradientu v súlade so vzorcami
Koeficienty sa vypočítajú pomocou jedného zo vzorcov (10.36), (10.37).
Iteračný proces tu už nekončí po konečnom počte krokov a smery, všeobecne povedané, nie sú konjugované s ohľadom na nejakú maticu.
Jednorozmerné úlohy minimalizácie (10.40) je potrebné riešiť numericky. Poznamenávame tiež, že v metóde konjugovaného gradientu sa koeficient často nevypočítava pomocou vzorcov (10.36), (10.37), ale predpokladá sa, že sa rovná nule. V tomto prípade sa ďalší krok skutočne vykonáva metódou najstrmšieho zostupu. Táto „aktualizácia“ metódy nám umožňuje znížiť vplyv výpočtovej chyby.
Pre silne konvexnú hladkú funkciu pre niektorých dodatočné podmienky Metóda konjugovaného gradientu má vysokú mieru superlineárnej konvergencie. Zároveň je jeho pracovná náročnosť nízka a je porovnateľná so zložitosťou metódy najstrmšieho zostupu. Ako ukazuje výpočtová prax, má o niečo nižšiu účinnosť ako kvázi-newtonovské metódy, ale kladie podstatne nižšie nároky na použitú pamäť počítača. V prípade, že problém minimalizácie funkcie s veľmi Vysoké číslo premenných, metóda konjugovaného gradientu sa javí ako jediná vhodná univerzálna metóda.
Gradientové metódy založené len na výpočte gradientu R(X), sú metódy prvého rádu, keďže na intervale krokov nahrádzajú nelineárnu funkciu R(X) lineárne.
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 vlastné ťažko riešiteľné problémy - výpočet druhých derivácií v určitom bode a 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ód prvého a druhého rádu a zároveň odstrániť ich nevýhody. 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šie kroky sa vyberajú zakaždým v smere, ktorý je vytvorený 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 = x 0 – h grad R(x 0),
x i+1 = x i – h .
Hodnota α sa dá 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 (použitím metódy 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 úpravy kroku skenovania pri prechode minima, takže presnosť dosiahnutia minima v smere závisí od veľkosti kroku h.
Pre kvadratickú funkciu R(X) riešenie sa dá nájsť v P kroky (P– rozmer problému). Pri iný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í na hľadanie minima dvojrozmernej funkcie pomocou metódy konjugovaného gradientu je znázornená na obr. 1.
Prvé štádium. Vykonanie gradientovej metódy.
Nastavte počiatočnú aproximáciu X 1 0 ,X 20. Určenie hodnoty kritéria R(X 1 0 ,X 20). Nastavte k = 0 a prejdite na krok 1 počiatočnej fázy.
Krok 1. 
A 
.
Krok 2. Ak je gradientový modul 
Krok 3.
X k+1 = X k – h grad R(X k)).
Krok 4. R(X 1 tis. + 1 , X 2 k + 1). Ak R(X 1 tis. + 1 , X 2 tis. + 1)< R(X 1k, X 2 k), potom nastavte k = k+1 a prejdite na krok 3. Ak R(X 1 tis. + 1 , X 2k +1) ≥ R(X 1k, X 2 k), potom prejdite na hlavnú scénu.
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 vypočítajte z centrálnej alebo párovej vzorky hodnotu parciálnych derivácií 
A 
. Vypočítajte hodnotu gradientu modulu 
.
Krok 2. Ak je gradientový modul 
, potom zastavte výpočet a bod (x 1 k, x 2 k) považujte za optimálny bod. V opačnom prípade prejdite na krok 3.
Krok 3. Vypočítajte koeficient α podľa vzorca:
Krok 4. Vykonajte pracovný krok výpočtom pomocou vzorca
x k+1 = x k – h .
Krok 5. Určte hodnotu kritéria R(X 1 tis. + 1 , X 2 k + 1). Nastavte k = k+1 a prejdite na krok 1.
Príklad.
Pre porovnanie zvážte riešenie predchádzajúceho príkladu. Prvý krok urobíme metódou najstrmšieho zostupu (tabuľka 5).
Tabuľka 5
Najlepší bod sa našiel. 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. Potom sa všetko opakuje rovnakým spôsobom. Nižšie v tabuľke. 6 zobrazuje aktuálne súradnice vyhľadávania pre ďalšie kroky.
Tabuľka 6
Pravidlá pre zadávanie 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 . Volajú sa dva n-rozmerné vektory x a y konjugovaný vzhľadom na matricu A (alebo A-konjugát), ak skalárny produkt(x, Au) = 0. Tu je A symetrická pozitívne definitná matica veľkosti n x n.
.
,
.
sú zvolené tak, že smer dk je A-konjugovaný so všetkými predtým skonštruovaný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.
Riešenie. Ako smer vyhľadávania vyberte vektor prechodu 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ý bod priblíženia, parameter dĺžky kroku , presnosť riešenia a vypočíta sa počiatočný smer vyhľadávania.
Krok k. Zapnuté k-tý krok, minimum (maximum) účelovej funkcie sa nachádza na priamke vedenej z bodu v smere . Nájdený minimálny (maximálny) bod určuje ďalší k aproximácia, po ktorej sa určí smer hľadania
Vzorec (5.4) je možné prepísať do ekvivalentnej formy
.
Algoritmus dokončí svoju prácu hneď, ako je splnená podmienka; hodnota poslednej získanej aproximácie sa berie ako riešenie.
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 cieľovej funkcie a na skutočnosti, že v extrémnom bode je gradient funkcie nulový, tzn.
Vskutku, nech nejaký bod leží dostatočne blízko k bodu požadovaného extrému. Uvažujme i zložku gradientu účelovej funkcie a rozviňte ju v bode pomocou Taylorovho vzorca s presnosťou na 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 nesingulárna. Potom má inverzná matica. Vynásobením oboch strán rovnice (5.6) ľavou získame , z čoho
. (5.7)
Vzorec (5.7) definuje algoritmus Newtonovej metódy: prepočet aproximácií k
Algoritmus ukončí svoju prácu hneď, ako je splnená podmienka
,
kde je daná presnosť riešenia; hodnota poslednej získanej aproximácie sa berie ako riešenie.
Newton-Raphsonova metóda
Metóda je metódou prvého poriadku 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 nech sa bod nachádza blízko . Rozšírenie funkcie v bode pomocou Taylorovho vzorca máme
odkiaľ (podľa podmienky) vyplýva
, (5.11)
kde je Jacobiánska matica vektorovej funkcie. Predpokladajme, že Jacobiánska matica nie je singulárna. 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í na 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. Obrázok 5.2 znázorňuje schému 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ť Hessovu a Jacobiho maticu).
Poznámka 5.3. Pri použití metód je potrebné brať do úvahy možnosť prítomnosti mnohých extrémov v objektívnej funkcii (vlastnosti multimodalita).
LITERATÚRA
1. Afanasyev 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: Trans. z angličtiny – M.: Mir, 1982 – 583 s.
3. Berman G.N. 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. Ventzel E. C. Operačný výskum. Ciele, princípy, 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. Nurejev R.M. Zbierka úloh z mikroekonómie. – M.: NORM, 2006. – 432 s.
9. Solodovnikov A. S., Babaytsev V.A., Brailov A.V. Matematika v ekonómii: Učebnica: V 2 častiach - M.: Financie a štatistika, 1999. - 224 s.
10. Taha H.Úvod do operačného výskumu, 6. vyd.: Trans. z angličtiny – M.: Williams Publishing House, 2001. – 912 s.
11. Himmelblau D. Aplikované nelineárne programovanie: Transl. z angličtiny – M.: Mir, 1975 – 534 s.
12. Shikin E. IN., 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. manuál pre univerzity / N.Sh., B.A. Ed. Prednášal prof. N.Sh. – M.: Banky a burzy, UNITY, 1997. – 407 s.
14. Matice a vektory: Učebnica. príspevok / Ryumkin V.I. – Tomsk: TSU, 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. Druhy ZMP ............................................................................................ ... | |
| 1.3. Základné pojmy matematického programovania................................................ | |
| 1.4. Smerová derivácia. Prechod ............................................................ | |
| 1.5. Dotykové nadroviny a normály............................................................ .......... | |
| 1.6. Taylorov rozklad ................................................................................................ ........................ | |
| 1.7. ZNLP a podmienky existencie jeho riešenia............................................ ........... | |
| 1.8. Úlohy ............................................................................................ ............................................. | |
| 2. RIEŠENIE PROBLÉMU NELINEÁRNEHO PROGRAMOVANIA BEZ OBMEDZENÍ......................................... ............................................................. ................................................................. .. | |
| 2.1. Nevyhnutné podmienky pre riešenie neobmedzujúceho neobmedzujúceho zákona...................................... ............... | |
| 2.2. Dostatočné podmienky Riešenia ZNLP bez obmedzení ...................................... | |
| 2.3. Klasická metóda riešenia ZNLP bez obmedzení................................... | |
| 2.4. Úlohy ………………………………………………………… ...................................................... ...... | |
| 3. RIEŠENIE PROBLÉMU NELINEÁRNEHO PROGRAMOVANIA S OBMEDZENIAMI ROVNOSTI...................................... ............................................................ ... | |
| 3.1. Metóda Lagrangeovho multiplikátora ................................................ ...................... | |
| 3.1.1. Účel a zdôvodnenie metódy Lagrangeovho multiplikátora ………………… | |
| 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 ZA OBMEDZENÍ NEROVNOSTI……………………………………………………………………….. | |
| 4.1. Zovšeobecnená Lagrangeova multiplikačná metóda ………………………………………… | |
| 4.2. Kuhn-Tuckerove podmienky………………………………………………………………. | |
| 4.2.1. Nevyhnutnosť podmienok Kuhn-Tucker……………………………………………… | |
| 4.2.2. Dostatočnosť Kuhn-Tuckerových podmienok……………………………………….. | |
| 4.2.3. Kuhn-Tuckerova metóda ................................................................................. ......... | |
| 4.3. Úlohy ………………………………………………………………………… ................................... | |
| 5. NUMERICKÉ METÓDY RIEŠENIA PROBLÉMU NELINEÁRNEHO PROGRAMOVANIA…………………………………………………………………………………………… | |
| 5.1. Pojem 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……………………………………………………………………… ........................ |
Definície lineárnych a nelineárnych funkcií nájdete v časti 1.2
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 skutočnej doméne.
V súlade s uvažovanou metódou sa zisťuje extrém (maximum alebo minimum) účelovej funkcie v smere najrýchlejšieho nárastu (zníženia) funkcie, t. 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 určiť hodnoty váhových koeficientov (premenných), ktoré sa používajú na určenie konjugovaného smeru.
Prvou metódou je určiť koeficient hmotnosti pomocou vzorca Fletcher-Reeves:
- gradientový modul určuje rýchlosť nárastu alebo poklesu funkcie v smere gradientu, resp. antigradientu.
Druhou metódou je určenie hmotnostného koeficientu pomocou Polak-Ribiereho vzorca:
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 generuje smer vyhľadávania smerom k optimálnej hodnote pomocou vyhľadávacích informácií získaných v predchádzajúcich štádiách 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 (hľadanie minima)
Geometrický význam metódy konjugovaného gradientu je nasledovný: z daného počiatočného bodu x sa uskutoční zostup v smere p (gradient alebo antigradient) do nového bodu x, v ktorom sa určí gradientový vektor funkcie. Keďže x je minimálny bod funkcie v smere p, gradientový vektor funkcie v bode 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 dôsledku toho sa zostup uskutoční v nájdenom smere do nového bodu x.
Trajektória pohybu do extrémneho bodu pomocou metódy najstrmšieho zostupu (zelená prerušovaná čiara) a metódy konjugovaného gradientu (červená prerušovaná č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 vyhľadávania a algoritmus sa znova spustil v smere najstrmšieho klesania.
Veľkosť kroku sa volí z podmienky minima účelovej 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čí 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 cieľovej funkcie v lokálnom minimálnom bode je nulový:
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 mnohými jej modifikáciami je rozšírená a efektívna metóda hľadanie optima skúmaných objektov. Nevýhodou gradientového vyhľadávania (ako aj vyššie diskutovaných metód) je, že pri jeho použití je možné zistiť len 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.
Metóda výpočtu
Krok 1: Definícia analytických výrazov (v symbolickej forme) na výpočet gradientu funkcie
Krok 2: Nastavte počiatočnú aproximáciu
Krok 3: 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 zostupu.
Krok 4: 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 v závislosti od kroku výpočtu.
Výpočet váhového koeficientu a jednotkového vektora konjugovaných smerov v aktuálnom kroku výpočtu (Fletcher-Reevesov vzorec):
Pre prvý krok výpočtu sa nevypočítava váhový koeficient (alebo v prípade reštartu algoritmu) a jednotkový vektor konjugovaných smerov sa určí nasledovne.
