METODE DE CALCUL PENTRU OPTIMIZAREA FĂRĂ RESTRICŢII

 

 

 

1. Principalele categorii de metode de calcul

 

 

După cum se ştie, în cazul funcţiilor f(x) de o singură variabilă – x fiind deci un scalar – condiţiile necesare şi suficiente de extrem se stabilesc prin intermediul primei derivate şi a celei de-a doua derivate

 

Condiţia necesară pentru a avea un extrem (maxim sau minim) este anularea primei derivate

 

f’(x)=0                                                                               (1)

 

reprezentând condiţia de staţionaritate.

 

Pentru un maxim, condiţiile necesare şi suficiente sunt  (1) împreună cu condiţia de convexitate

 

f’’(x) < 0,                                                                           (2)

 

iar pentru un minim condiţiile necesare şi suficiente sunt (1) împreună cu condiţia de convexitate

 

f’’(x) > 0.                                                                           (3)

 

 Condiţia de staţionaritate este îndeplinită în punctual de optim x^*, iar condiţia de convexitate este îndeplinită în jurul acestui punct.

 Relaţiile menţionate sunt valabile pentru funcţii f(x) de cel puţin gradul doi, respectiv nu sunt valabile pentru funcţii  de gradul întâi, liniare, de forma f(x) = ax + b, întrucât la acestea rezultă f’(x) = a şi deci prima derivată nu depinde de variabila x. Datorită acestui fapt, metodele de programare neliniară  - folosite pentru optimizarea funcţiilor criteriu neliniare f(x), unde x este un vector – nu pot fi folosite pentru rezolvarea problemelor de programare liniară, cu funcţii criteriu şi restricţii liniare.

 

În cazul optimizării funcţiilor criteriu f(x) de variabilă vectorială, principalele categorii de metode se disting după faptul că unele fac apel la primele derivate, altele necesită derivatele prime şi secunde, iar o a treia categorie nu necesită nici determinarea primelor derivate, nici a derivatelor secunde; cele trei categorii de metode aproximează deci dezvoltarea în serie Taylor a funcţiei f(x) prin reţinerea unui număr diferit de termeni.

 

Metodele din prima categorie pot fi denumite metode de gradient, sau metode bazate pe prima variaţie, metodele din a doua categorie pot fi numite metode Newton, sau metode bazate pe a doua variaţie, iar metodele din a treia categorie sunt denumite metode de căutare directă, sau metode directe, întrucât asigură optimizarea apelând numai la valorile funcţiei criteriu.

 

Pentru o funcţie scalară derivabilă f(x) de variabilă vectorială x, vectorul gradient, care constituie o direcţie şi are o importanţă esenţială în optimizare, reprezintă prima derivată şi se poate nota prin f’(x), f_x sau prin , fiind definit prin derivatele parţiale ale funcţiei, respectiv:

 

                                              (4)

 

 Întru-un punct x¹, gradientul f ’(x¹) indică direcţia în care – din punctual x¹ – are loc cea mai abruptă creştere a funcţiei criteriu f(x).

 

De fapt, orice vector n-dimensional p poate servi ca direcţie în . Astfel, dacă se dă punctul şi direcţia p (cu ), atunci punctul

 

y = x + α p                                                                         (5)

 

pentru variaţii ale scalarului α între 0 şi ∞, descrie o rază care porneşte din punctual x pe direcţia p, iar pentru valori ale scalarului α între - ∞ şi +∞ descrie toată dreapta  care trece prin x şi coincide cu direcţia p.

 

Importanţa gradientului pentru optimizare rezidă în faptul că pentru o anumită direcţie p, produsul scalar

 

                                                                    (6)

 

exprimă viteza de variaţie a funcţiei f de-a lungul direcţiei p. Astfel, în analiza matematică, se demonstrează că pentru o funcţie f(x) derivabilă în punctul x are loc relaţia

 

                                            (7)

 

expresia (7) fiind denumită derivată Gateaux.

 

Presupunând că optimizarea urmăreşte maximizarea unei funcţii criteriu concave f(x), relaţia (7) permite să se demonstreze că dacă f(x) este derivabilă în punctual x şi există o direcţie pentru care

 

                                                                (8)

 

atunci există τ > 0 astfel încât pentru orice valoare se obţine

 

                                                                   (9)

 

Deci, pe direcţia p, are loc creşterea funcţiei criteriu şi apropierea de maxim.

 

Astfel, din (7) şi (8) se obţine

 

                                                     (10)

 

şi, din definiţia limitei, rezultă că trebuie să existe τ > 0 astfel încât pentru orice şi cuprins între -τ şi +τ să se obţină

 

                                                           (11)

 

 Se constată că dacă se aleg valori pozitive care verifică inegalitatea (11), relaţia (9) este demonstrată. Toate direcţiile care satisfac condiţia (8) asigură creşterea funcţiei f(x) şi deci apropierea de maxim.

 

Expresiile (8) şi (9) atestă faptul că gradientul indică totdeauna către maxim; în punctul maxim x^*, gradientul este nul, deci

 

     .                                                         (12)

 

 

 Relaţia (8) arată că unghiul dintre vectorii f_x şi p trebuie să fie mai mic de 90^o.

 

Dacă în locul maximizării unei funcţii concave, optimizarea urmăreşte minimizarea unei funcţii convexe f(x), atunci direcţiile p trebuie alese dintre direcţiile care asigură condiţia

 

                                                                    (13)

 

întrucât, în acest caz, se va obţine

 

     ,                                                           (14)

 

deci pe direcţia p are loc descreştera funcţiei f(x) şi apropierea de minim.

 

 Relaţia (13) aratǎ cǎ unghiul dintre vectorii f_x şi p trebuie sǎ fie mai mare de 90^o, pentru ase asigura descreşterea funcţiei f(x).

 

 Rezultǎ astfel cǎ direcţia gradientului f_x indicǎ totdeauna spre minimul unei funcţii convexe.

 

 Din considerentele expuse, rezultǎ deosebita importanţǎ a gradientului pentru desfǎşurarea procesului iterativ descris de relaţiile de forma

 

                                                                   (15)

 

 Astfel, presupunând cǎ iteraţia se gǎseşte în punctul x^k, atunci, în cazul maximizǎrii unei funcţii concave, direcţia p a urmǎtoarei deplasǎri – spre punctul x^k+1 – trebuie aleasǎ dintre direcţiile care satisfac condiţia (13) în raport cu gradientul f_x .

 

 Derivatele secunde intervin în expresia matricei  Hessian, care se obţine din gradient printr-o nouǎ derivare în raport cu vectorul x; notând matricea Hessian cu H(x), f’’(x) sau f_xx, rezultǎ

 

                            (16)

 

 Calculul matricei - la fiecare iteraţie a procesului de cǎutare a optimului – este deosebit de laborios şi, de aceea, cele mai multe dintre metodele folosite în practicǎ evitǎ acest calcul.

 În anumite probleme, chiar determinarea gradientului poate fi sensibil mai complicatǎ decât determinarea valorii funcţiei (uneori gradientul nici nu poate fi exprimat analitic); în asemenea cazuri, se preferǎ metodele de cǎutare directǎ, ilustrate ulterior.

2. Metode de gradient

 

 

Ideea metodei gradientului, emisă de A.L.Cauchy în secolul trecut se bazează pe o aproximaţie de ordinul I liniară, f(x)_L a dezvoltării în serie Taylor pentru funcţia criteriu f(x).

 

O asemenea aproximaţie pentru dezvoltarea în jurul unui punct de maxim x^* are aspectul

 

                                     (17)

 

unde s-a folosit notaţia f’(x) pentru gradient.

 

 Dezvoltarea completă în serie Taylor conduce la expresia

 

            (18)

 

unde prin f’’(x) s-a notat matricea Hessian din (16), iar restul O[(x-x^*)³] grupează ceilalţi termeni ai dezvoltării.

 

 Definind diferenţa

 

                                                           (19)

 

ca variaţia funcţiei criteriu şi notând prin

 

                                                                       (20)

 

variaţia variabilei vectoriale, din (17) se obţine

 

                    (21)

 

 Adoptând aproximaţia liniară din (17), se obţine prima variaţie

 

.                                                            (22)

 

 În punctele de minim sau maxim prima variaţie este nulă – având în vedere condiţia de staţionaritate (12) – şi (21) devine

 

,                                      (23)

 

termenul preponderent în această expresie reprezentând a doua variaţie

 

                                                     (24)

 

Pentru ca punctul x^* să asigure un maxim al funcţiei criteriu, este necesar ca a doua variaţie să fie negativă – întrucât,conform cu (19), asigură relaţia  f(x) < f(x^*)  care defineşte un maxim în punctul x^* - deci este necesară condiţia

 

.                                              (25)

 

 Ca urmare, valorile proprii ale matricii Hesian trebuie să fie negative.

 

 În practică se folosesc diferite variante de metode de gradient. Una din cele mai utilizate este aşa zisa metodă a celei mai mari pante, sau a celei mai abrupte coborâri, în ipoteza că optimul căutat este un minim. Această metodă porneşte de la ideea de a adopta în (15)

 

                                                             (26)

 

întrucât astfel se asigură în  mod simplu satisfacerea condiţiei  (13) de deplasare spre minim, deoarece rezultă

 

                                             (27)

 

având în vedere şi definiţia produsului intern.

 

 Din (15) şi (26) rezultă că procesul iterativ de căutare a minimului este definit de relaţia

 

                                                            (28)

 

unde .

 

 Diversele subvariante ale metodei celei mai mari pante se deosebesc prin tehnica alegerii valorii pasului .

 

Pe lângǎ metoda celei mai mari pante se folosesc şi alte variante de metode de gradient, la unele dintre aceste variante procentul iterativ de cǎutare a minimului fiind descris de relaţii de forma

 

                                                       (29)

 

 Comparând (15) cu (29), se constatǎ cǎ vectorul direcţiei are expresia

 

                                                                    (30)

 

deci, pentru a obţine din (30)  relaţia (26), -definind metoda celei mai mari pante – este necesar ca pentru sǎ se adopte matricea unitate.

 

 Pentru asigurarea relaţiei (13), matricea simetricǎ - determinatǎ la fiecare iteraţie – trebuie  sǎ satisfacǎ anumite condiţii.

 

 Compararea diverselor variante de metode de gradient, din punct de vedere al eficienţei – ca şi compararea diferitelor categorii de metode de calcul – reprezintǎ o problemǎ dificilǎ. În primul rând, compararea se poate efectua numai pe baza unuia sau mai multor criterii, iar în practicǎ este necesarǎ considerarea simultanǎ a mai multor criterii, dintre care unele conduc la rezultate contradictorii.

 

 Criteriile cele mai frecvent utilizate pentru aprecierea unei metode de calcul se referǎ la precizia rezultatelor, viteza de convergenţǎ a procedeului iterativ, timpul de calcul, volumul necesar de memorie a calculatorului.

 

 Primele douǎ criterii – precizia şi viteza de convergenţǎ – sunt cele mai importante, dar ele nu pot permite o ordonare univocǎ a tuturor metodelor de calcul, întrucât estimarea vitezei de convergenţǎ a unei metode rǎmâne valabilǎ numai pentru o clasǎ de probleme, dar nu şi pentru altele. De aceea, este indicat ca proiectantul de optimizǎri sǎ dispunǎ de un bagaj cât mai vast de metode calcul şi de rezultate concrete obţinute în aplicarea fiecǎrei metode la anumite clase de probleme.

 

 În cadrul procesului iterativ (15), alegerea direcţiei determinǎ viteza de convergenţǎ, iar alegerea pasului influenţeazǎ puternic volumul de calcul la fiecare iteraţie.

3. Metode Newton

 

Metoda gradientului se bazeazǎ pe aprximarea linarǎ f(x)_L – din (17) – a dezvoltǎrii în serie Taylor a funcţiei criteriu f(x), deci pe cea mai grosierǎ aproximaţie.

 

Metoda Newton foloseşte o aproximaţie  pǎtraticǎ  f(x)­_P, rezultând pentru dezvoltarea în jurul unui punct x^k expresia

 

              (31)

 

conform cu o relaţie analoagǎ cu (18) (relaţia (18) a fost scrisǎ pentru dezvoltarea în jurul punctului de optim x^*, iar relaţia (31) pentru dezvoltarea în jurul punctului x^k, considerat apropiat de punctul optim x^*).

Pentru ca punctul de optim  x^* sǎ asigure extremul aproximaţiei pǎtratice f(x)_p este necesarǎ anularea gradientului acestei expresii pentru x = x^*, condiţie de tipul (12).

 

Calculînd gradientul expresiei (31) se obţine

 

                                      (32)

 

şi anulând valoarea gradientului pentru x = x^* rezultǎ

 

                                                (33)

 

 Considerând cǎ matricea Hessian este inversabilǎ, din (33) se obţine

 

                                                  (34)

 

 Aceastǎ relaţie atestǎ faptul cǎ, adoptând  în procesul de iteraţie un vector de direcţie definit de relaţia

 

                                                        (35) 

 

se obţine o deplasare cǎtre punctul optim x^*. 

 

 Astfel, presupunând deocamdatǎ cǎ în (15) se adoptǎ

 

     ,                                                                             (36)

 

relaţia (15) devine

 

                                                                      (37)

 

iar din (34) şi (35) rezultǎ

 

     ,                                                                   (38)

 

înlocuirea expresiei p^k din (38) în (37) conducînd la relaţia

 

      .                                                (39)

 

 Evident, rezultatul din (39) nu este exact, întrucât toate expresile anterioare au fost obţinute pe baza aproximaţiei pǎtratice f(x)_p, dar el atestǎ cǎ deplasarea din x^k pe direcţia p^k din (35) se efectueazǎ cǎtre punctul optim x^*.

 

 Înlocuind (35) în (37), se obţine metoda Newton clasicǎ de calcul:

 

     ,                                            (40)

 

corespunzǎtoare valorii din (36).

 

 Dacǎ extremul este un maxim, direcţia p^k din (35) va satisface condiţia (8), iar dacǎ extremul este un minim va satisface condiţia (13).

 Astfel, fǎcând abstracţie de indicele superior k al itreaţiei, cu expresia lui p din (35) se obţine

 

     .                        (41)

 

 În apropierea unui maxim, valorile proprii ale matricei Hessian f’’(x) sunt negative – cum a rezultat din (25) – şi deci condiţia (8) este satisfǎcutǎ, iar în cazul unui minim valorile proprii sunt pozitive si, ca urmare, este satisfǎcutǎ condiţia (13).

 

 Dacǎ se adoptǎ

 

                                                                                   (42)

 

-          spre deoseire de (36) – (cu respectarea condiţiei ) şi se pǎstreazǎ direcţia p^k din (35), atunci procesul iterativ este descris de relaţia

 

                                      (43)

 

care reprezintǎ metoda Newton cu pas variabil (sau metoda Newton generalizatǎ).

 

 Metodele Newton au avantajul cǎ aproximeazǎ funcţia criteriu mult mai exact decât metodele de gradient, asigurǎ o aproximare mai bunǎ a soluţiilor prin deplasǎrile pe direcţia p^k din (35) şi deci permit obţinerea unei convergenţe mai rapide a procesului iterativ decât în cazul metodelor de gradient.

 

 În schimb, dupǎ cum s-a mai menţionat, calculul matricei Hessian – la fiecare iteraţie – este foarte laborios şi necesitǎ un mare numǎr de operaţiii aritmetice, ceea de face ca, la metodele Neweton, numǎrul de operaţii aritmetice pe iteraţiie sǎ fie mult mai ridicat decât la metodele de gradient, reducându-se astfel eficienţa metodelor Newton.

 De aceea au fost cǎutate metode de calcul care sǎ conveargǎ aproape ca metodele Newton, fǎrǎ a necesita numǎrul mare de operaţii pe iteraţie pe care îl implicǎ metodele Newton.               Unele dintre metodele respective, care au în prezent o utilizare cin ce în ce mai largǎ, sunt prezentate în paragraful urmǎtor.

4.    Metodele direcţiilor conjugate

 

 

Aceste metode folosesc o aproximaţie pǎtraticǎ a funcţiei criteriu, fǎrǎ sǎ implice calculul explicit al matricei Hessian la fiecare iteraţie, iar informaţia necesarǎ aferentǎ acestei matrice este obţinutǎ în decursul câtorva iteraţii, ceea ce micşoreazǎ mult efortul de calcul la fiecare iteraţie, fǎrǎ ca precizia aproximǎrii funcţiei criteriu sǎ scadǎ sensibil.

 

Fiind datǎ o matrice simetricǎ A n × n, direcţiile reprezentate de vectorii n-dimensionali

p¹, p², ..., p^m – cu - se numesc A-conjugate dacǎ vectorii pⁱ (i = 1, 2, …, m) sunt liniar independenţi şi dacǎ satisfac relaţia

 

                                                                           (44)

 

pentru

 

                                                                                     (45)

 

cu .

 

 Sistemul vectorilor p¹, p², ..., p^m este liniar independent – fiind un sistem ortogonal în metrica definitǎ de matricea A – şi, ca urmare, punctul

 

                                                                           (46)

 

descrie un subspaţiu m-dimensional atunci când scalarii iau valori de la la .

 

 Pornind de la un punct x¹ dat şi cu valoarea  catǎ – cu - se considerǎ punctul

 

     ;                                                                 (47)

 

pentru variaţii arbitrare ale scalarilor se obţine o varietate liniarǎ m-dimensionalǎ, rezultatǎ din translarea susbspaţiului m-dimensional.

 Dacǎ m = n  - şi acesta este cazul care prezintǎ cel mai mare interes – atunci punctul x¹ şi cele n direcţii A-conjugate genereazǎ o varietate n-dimensionalǎ care coincide cu , întrucât vectorii celor n-direcţii A-conjugate sunt liniari independenţi.

 

 Se poate demonstra cǎ, dacǎ se adoptǎ o funcţie criteriu pǎtraticǎ, atunci maximul (sau minimul) funcţiei pe varietatea menţioatǎ – care coincide cu - poate fi determinat în numai n paşi, verificând câte o singurǎ datǎ fiecare din cele n direcţii A- conjugate, ordinenea verificǎrii fiind indiferentǎ.

 

 Construirea direcţiiilor conjugate pentru minimizarea unei funcţii pǎtratice a fost propusǎ de W.C.Davidon, care a elaborat “algoritmul cu metricǎ variabilǎ”, ideea fiind dezvoltatǎ de R.Fletcher şi M.J.D.Powel, rezultând metoda de calcul “algoritmul Davidon-Fletcher-Powell” (DFP).

 

 Algoritmul propus de Davidon a introdus o metricǎ variabilǎ în relaţiile iterative ale metodei celei mai mari pante, în locul expresiei (28) fiind folositǎ relaţia

 

                                                          (48)

 

unde matricea S_k, de dimensiuni n × n, este actualizatǎ la fiecare iteraţie printr-o relaţie recursivǎ. Se constatǎ cǎ, dacǎ în locul matricei S_k din (48) s-ar introduce matricea unitate, se obţine (28).

 

 De fapt, în algoritmul lui Davidon se noteazǎ

 

                                                      (50)

 

unde .

 

 În calitate de matrice iniţialǎ S₀ se alege, de regulǎ, matricea unitate.

 

 Din (43), (48), (49) şi (50) se constatǎ cǎ algoritmul DFP construieşte la fiecare iteraţie o aproximaţie a matricei Hessian, bazatǎ pe informaţia obţinutǎ prin intermediul gradientului.

 

 La fiecare iteraţie, se alege pentru valoarea care minimizeazǎ funcţia

 

     ,                                                           (51)

 

consideratǎ ca funcţie de o singurǎ variabilǎ , f(x) fiind funcţia criteriu.

 

Metoda direcţiilor conjugate poate fi utilizatǎ şi la minimizǎri de funcţii criteriu care nu sunt pǎtratice, întrucât, pentru funcţiile convexe, aproximarea pǎtraticǎ este bunǎ, îndeosebi în apropierea punctului de minim.

 

Rezultatele teoretice ale algoritmului DFP au fost generalizate la o clasǎ de algoritmi cu metricǎ variabilǎ.

 

O variantǎ interesantǎ de construire a direcţiilor conjugate sunt generate prin intermediul relaţiei

 

                                 (52)

 

pentru direcţia iniţialǎ (care porneşte din punctul x⁰) adopotându-se

 

     .                                                                   (53)

 

 O altǎ caracteristicǎ a metodei gradientului conjugat constǎ în faptul cǎ gradienţii la diverse iteraţii sunt ortogonali, respectiv

 

                                                            (53)

pentru .

 

 Întrucât la algoritmul DFP apare necesitatea memorǎrii matricei S_k, n × n, pentru problemele de dimensiuni mari, metoda gradientului conjugat apare mai indicatǎ, necesitând numai memorarea gradientului curent şi a direcţiei curente p^k pentru generarea noii direcţii p^k+1, conform cu (52). O variantǎ a metodei gradientului conjugat este reprezentatǎ de metoda gradientului conjugat scalat.

 

5.    Metode de căutare directă

 

Metodele de căutare directă (sau metodele directe) pot oferi numai soluţii aproximative ale problemelor de optimizare, dar, în schimb, asigură convergenţa pentru orice punct ales iniţial, în timp ce metodele care folosesc gradientul, matricea Hessian, sau o aproximaţie a acesteia  (asemenea metode sunt denumite uneori metode indirecte) pot oferi soluţii exacte, dar necesită un punct iniţial bine ales.

 

În cazul metodelor, folosirea indicaţiilor date de gradient (sau de gradient şi de matricea Hessian), de exemplu pentru determinarea unui maxim, poate fi comparată cu o ascensiune spre un vârf de munte care este vizibil în timpul urcuşului, iar folosirea metodelor directe poate fi considerată analogă cu o ascensiune în condiţii de lipsă de vizibilitate a vârfului (de exemplu pe ceaţă), când singurele informaţii de care dispune cel care caută vârful se referă la sesizarea faptului că urcă sau coboară.

 

Ilustrarea metodelor directe poate fi uşor fǎcutǎ prin intermediul unei funcţii de o singurǎ variabilǎ f(x), variabila x fiind deci scalarǎ; o asemenea cǎutare a extremului este denumitǎ “de-a lungul unei drepte” (în limba englezǎ “along a line”), deoarece variabila x ia valori în R¹, deci pe o dreaptǎ.

 

Presupunând cǎ se cunoaşte intervalul de variaţie al mǎrimii x în care se gǎseşte extremul – de exemplu se ştie cǎ între 0 şi 1 existǎ un maxim, funcţia f(x) fiind concavǎ – cǎutarea directǎ poate fi efectuatǎ prin mai multe metode. În figura  este ilustratǎ aplicarea metodei dichotomiei (înjumǎtǎţirii intervalului).

 

Metoda prevede alegerea a douǎ valori x = x₁ şi x = x₂ în jurul centrului intervalului – respectiv în jurul valorii x = 0,5 – cele douǎ valori fiind apropiate între ele, deci diferind cu o valoare micǎ ε; se comparǎ valorile funcţiei f(x₁) şi f(x₂) şi dacǎ rezultǎ, de exemplu

   f(x₁) > f(x₂)                                                                                  (54)

 

 ca în figura 1  , atunci poate fi eliminat intervalul x > x₂ (haşurat în figura  ), întrucât funcţia este concavǎ şi maximul se va gǎsi între 0 şi x₂.

 

 

 

 

Fig.1

 

 

 Se aleg apoi alte douǎ valori x = x₃ şi x = x₄ în jurul centrului intervalului rǎmas (dintre 0 şi x₂), separate tot prin ε, şi se comparǎ valorile f(x_3­) şi f(x₄) ale funcţiei criteriu; dacǎ rezultǎ, de exemplu,

 

    f(x₄) > f(x₃)                                                                                  (55)

 

ca în figura 1 , atunci poate fi eliminat şi intervalul (haşurat) x < x₃, întrucât maximul se va gǎsi în domeniul x > x₃, respectiv în intervalul rǎmas nehaşurat

 

    x₃ < x < x₂                                                                                    (56)

 

 Se continuǎ succesiv cu centrǎri de perechi de valori x, comparaţii ale valorilor funcţiei şi înjumǎtǎţiri de interval, pânǎ la obţinerea unui interval foarte mic în care se gǎseşte punctul de optim x^*, deci pânǎ la obţinerea soluţiei aproximative cu o toleranţǎ admisǎ.

 

 Neglijând valoarea ε a distanţei dintre perechile de puncte şi având în vedere cǎ prin douǎ testǎri ale valorilor funcţiei criteriu se asigurǎ o înjumǎtǎţire a fiecǎrui interval, rezultǎ cǎ, dupǎ n testǎri, intervalul I_n care rǎmâne de explorat are valoarea aproximativǎ

 

                                                                                        (57)

 

Alte metode de căutare de-a lungul unei drepte (de exemplu, metoda Fibonacci şi metoda secţiunii de aur) au o eficienţă sensibil superioară, reducerea intervalului iniţial fiind mai rapidă.

 

 Metodele de căutare de-a lungul unei drepte au o importanţă deosebită şi în căutarea extremului unei funcţii criteriu de variabilă vectorială, întrucât, după alegerea direcţiei p^k din cadrul procesului iterativ (15), determinarea valorii _k se efectuează prin găsirea extremului unei funcţii de variabilă scalară   de-a lungul direcţiei p^k, după cum s-a ilustrat şi prin (51).

 

 Încercări de a organiza căutarea directă a punctului de optim, fără determinarea gradientului, au fost făcute şi în cazul funcţiilor criteriu de variabilă vectorială, fiind elaborate diferite strategii de explorare. În cele mai simple strategii, fiecare variabilă (componentă a vectorului x) este succesiv modificată până se obţine un extrem – de exemplu un maxim – al funcţiei criteriu pe direcţia variabilei respective, trecându-se apoi la modificarea variabilei următoare; procesul este oprit când nu se mai obţin creşteri ale funcţiei criteriu pe direcţiile niciunei variabile.

 

 O strategie elaborată de Hooke, Jeeve şi Wood prevede executarea dintr-un punct a unui “pas de explorare”, reprezentând modificarea variabilelor cu o mică variaţie pozitivă prestabilită; dacă se constată o apropiere de optimul funcţiei criteriu, de exemplu de un maxim, atunci punctul obţinut devine o nouă “bază” – spre deosebire de punctul de plecare reprezentând “vechea bază” – din care se efectuează paşi de lucru pe direcţiile tuturor variabilelor (constituind un pas n-dimensional), pe fiecare direcţie paşii fiind proporţionali cu diferenţele valorilor variabilei respective în noua şi vechea bază.

 

 Dacă pasul n-dimensional de lucru asigură apropierea de maxim, urmează un nou pas de explorare ş.a.m.d. Dacă pasul de lucru nu asigură creşterea funcţiei criteriu, are loc anularea lui şi executarea unui nou pas de explorare.

 Dacă în direcţia unei variabile pasul iniţial de explorare nu determină o apropiere de maxim, atunci se efectueză un pas negativ de explorare pe aceeaşi direcţie; în cazul când se obţine o apropiere de maxim, acest pas rămâne valabil, dar dacă nici pasul negativ nu marchează creşterea funcţiei criteriu, atunci pe direcţia respectivă nu se mai execută nici un pas de explorare.

 

 O altă strategie, elaborată de Powell, foloseşte direcţii conjugate şi converge în n iteraţii spre optimul unei funcţii criteriu pătratice.

 

 Strategia elaborată de Nedler şi Mead a fost numită “metoda simplex”, într-un spaţiu n-dimensional un număr de n+1 puncte formând un “simplex”. Pentru ilustrare, se consideră cazul minimizării unei funcţii criteriu f(x) în care variabila vectorială x are două componente, x₁ şi x₂, deci dependenţa f(x₁, x₂) poate fi reprezentată într-un spaţiu R . Întrucât asemenea reprezentări sunt dificile, se preferă intersecţia corpului care reprezintă dependenţa f(x₁, x₂) cu o serie de plane paralele cu planul (x₁, x₂), prin intersecţie rezultând, în fiecare plan, câte o curbă de nivel de valori constante ale funcţiei criteriu, numită şi “curbă de nivel”.

 Proiectând diferitele curbe de nivel în planul variabilelor (x₁, x₂), se obţine o imagine de tipul celei din figura 2, în care punctul M (de coordonate x₁x₂ ) corespunde minimului, deci

 

                                                            (58)

 

iar valorile constante C₁, C₂, C₃, C₄ – ale funcţiei criteriu pe diferitele curbe de nivel – sunt din ce în ce mai mici, pe măsura apropierii de punctul M, deci

    

C₁ > C₂ > C₃ > C₄                                                                        (59)

 

 

 

 

 

Fig.2

 

 

 

 Întrucât în R un “simplex” se realizează cu n+1 puncte, în planul R din figura  2, un simplex va fi realizat cu 3 puncte, având forma unui triunghi. Se porneşte de la un simplex iniţial, de exemplu I₁, J­₁, K₁ din figură şi apoi se caută înlocuirea punctului cu cea mai mare valoare a funcţiei criteriu f(x) – deci cel mai depărtat de minim – de exemplu punctul I₁, cu un alt punct de pe direcţia I₁O₁, unde O₁ se găseşte la jumătatea distanţei dintre J₁ şi K₁; în cazul unui număr mai mare de dimensiuni, punctul O₁ este centroidul tuturor vârfurilor rămase ale simplexului, după eliminarea vârfului I₁.

 

 Stabilind, printr-un algoritm adecvat de verificare a valorilor funcţiei criteriu, punctul de pe direcţia I₁O₁ care urmeză să înlocuiască punctul I₁ – de exemplu punctul L₁ – se formează un nou simplex cu punctele J₁, K₁, L₁, continuându-se operaţiile de construire a unei noi direcţii pentru înlocuirea punctului cel mai  depărtat de minim (din cadrul noului simplex) printr-un punct de pe noua direcţie.

 

 Când ajunge în apropierea minimului M, simplexul are aspectul  definit de punctele I_f, J_f, K_f, cu direcţia I_fO pentru înlocuirea punctului I_f printr-un nou punct; în figura 2, punctul O coincide cu M, ceea ce, evident, nu este obligatoriu.

 

 Unele metode de căutare directă nu realizează o explorare prin stabilirea unui algoritm de elaborare a traseului, ca în cazurile menţionate anterior, ci selectează în mod aleator punctele în care se determină valoarea funcţiei criteriu.

 Dacă punctele respective acoperă complet gamele de variaţie estimate pentru toate variabilele de care depinde funcţia criteriu; asemenea metode de căutare directă cu selectare aleatoare a punctelor de exploatare sunt încadrate în clasa metodelor denumite “Monte Carlo”. În cadrul acestor metode, punctul în care a rezultat valoarea extremă funcţiei criteriu este considerat ca localizat într-o anumită zonă restrânsă din cadrul celei considerate iniţial şi se poate calcula probabilitatea apropierii de optim, urmând apoi succesiv noi explorări aleatoare alternând cu noi reduceri ale zonei.

 Elemente de calcul statistic intervin şi în alte aspecte ale rezolvării problemelor de optimizare, nu numai în selectarea aleatoare a punctelor explorate.

 

 Astfel, în unele cazuri, însăşi alegerea direcţiilor de căutare p^k din (15) are un caracter aleator, rezultând metode aleatoare de căutare – prin procedee iterative – a optimului.

 

 În alte cazuri, variabilele înseşi (de care depinde funcţia criteriu sau unii parametri care intervin în această funcţie) sunt variabile aleatoare. În asemenea cazuri, optimizarea urmăreşte găsirea unui extrem al valorii medii a funcţiei criteriu, iar metodele de calcul folosite în acest scop sunt uneori denumite metode de programare stochastică.