Informații inițiale despre metodele numerice de optimizare
Uneori este posibil, pe baza condițiilor de optimitate sau pe o interpretare geometrică, să se obțină o soluție la problema optimizării
în mod explicit, dar în cele mai multe cazuri, problema (2.1) trebuie să fie rezolvată numeric, cu ajutorul unui calculator. De exemplu, soluțiile pentru problema de minimizare a R n funcție diferențiabilă f se poate utiliza orice metodă numerică de rezolvare a sistemului de ecuații f „(x) = 0. Cu toate acestea, de obicei, cele mai multe metode tive de eficacitate sunt concepute special pentru soluții problemă de optimizare, deoarece acestea permit o mai bună ia în considerare specificitatea acesteia.
În următoarele capitole, vor fi luate în considerare metode numerice pentru rezolvarea diferitelor tipuri de probleme: probleme unidimensionale și multidimensionale, necondiționate și condiționate, discrete și optime.
În această secțiune vom oferi câteva informații generale legate în primul rând de metodele numerice de minimizare necondiționată și condiționată a unei funcții a unui număr finit de variabile variabile continuu. Astfel de metode sunt esențiale pentru optimizarea numerică; acestea, în special, sunt utilizate în soluționarea problemelor de optimizare discrete și a problemelor de control optime.
Orice metodă numerică (algoritm) pentru rezolvarea problemei de optimizare se bazează pe calcularea exactă sau aproximativă a caracteristicilor sale (valorile funcției obiective, funcțiile care definesc mulțimea admisibilă și, de asemenea, derivatele acestora). Pe baza informațiilor obținute aproximăm soluția problemei - punctul minim necesar x * sau, dacă un astfel de punct nu este unic, la setul de puncte minime. Uneori, dacă este necesar, este construită o aproximare a valorii minime a funcției obiectiv.
Pentru fiecare sarcină specifică, întrebarea cu privire la caracteristicile care trebuie alese pentru calcul este rezolvată în funcție de proprietățile funcției minimizate, constrângerile și opțiunile disponibile pentru stocarea și prelucrarea informațiilor. Astfel, pentru a minimiza funcția nediferențiată, nu se poate folosi un algoritm care să permită calculul gradientului unei funcții la un punct arbitrar. În cazul în care este disponibilă o mică cantitate de memorie a calculatorului, atunci când se rezolvă o problemă de dimensiuni mari, nu se poate folosi un algoritm care necesită calcul la fiecare pas, stocarea matricei de derivate secunde în memorie și așa mai departe.
Algoritmii care utilizează numai informații despre valorile unei funcții minimizate sunt numiți algoritmi de ordin zero; algoritmi care utilizează și informații despre valorile primelor produse derivate, - algoritmi de ordinul întâi; algoritmii care, în plus, utilizează informații despre al doilea derivat, sunt algoritmi de ordinul doi.
În curs, sunt luate în considerare numai algoritmi cu zero, primul și al doilea ordin.
Lucrarea algoritmului constă din două etape. În prima etapă, se calculează caracteristicile sarcinii furnizate de algoritm. În a doua etapă, conform informațiilor primite, se construiește o abordare a soluției. Pentru problemele de optimizare, selectarea în a doua etapă a metodei de construire a aproximării, de regulă, nu cauzează dificultăți. De exemplu, pentru metodele de coborâre în care, la fiecare etapă, se produce o tranziție la un punct cu o valoare mai mică decât cea precedentă, punctul de calcul ultim este ales de obicei pentru a se apropia de punctul minim. Prin urmare, pentru a specifica algoritmul, este suficient să se indice metoda de selectare a punctelor de calcul (desigur, cu condiția să fie calculată problema care caracteristici ale problemei care trebuie rezolvate) a fost deja rezolvată.
Dacă toate punctele sunt selectate în același timp înainte de începerea calculului, algoritmul de minimizare se numește pasiv. Necesitatea de a aplica algoritmi pasivi apare, de exemplu, în legătură cu utilizarea computerelor multiprocesoare, în legătură cu condițiile de setare și efectuare a experimentelor fizice, rezultatul căruia sunt minime valorile funcției etc.
Cu toate acestea, pentru majoritatea sarcinilor de calcul alternativ, adică. E. punctul xi +1 este selectat vybi point-rayutsya, când este selectat în ceea ce privește calculele precedente x 1 x i și fiecare dintre ele a făcut furnizate algoritmul de calcul rezultat Coto ryh va fi notat cu prin y 1. i. Asemenea algo-ritmuri sunt numite secvențiale. Astfel, algoritmul-ing secvență punct determinat x 1 Î X și o colecție de mapări ale formularului
.
În cele ce urmează, pentru a scrie metodele de minimizare, vom folosi o relație a formei
În acest algoritm special este definit prin specificarea unui punct x 0, reguli de selecție vector h k și ak numere pe baza informațiilor obținute rezultate de calcul și starea de oprire. Astfel, cantitățile ak. hk în formula (2.3), în același mod ca și xi +1 în ecuația (2.2) sunt determinate de diferite tipuri de puncte-funcție ționale și în funcție de rezultatele tuturor calculelor anterioare dennyh VERIFICARE, practica frecvent utilizate specii NAI simple dependență. Regulile de selecție ak. h k poate include calcule suplimentare, adică calculăm anumite caracteristici ale problemă care trebuie rezolvată în celelalte decât x 0, x 1 x k puncte. Acesta este motivul pentru care în formulele (2.2) și (2.3), prin consumul de o varietate de indici.
Vectorul k determină direcția etapei (k +1) a metodei de minimizare, iar coeficientul ak este lungimea acestei etape. Trebuie avut în vedere că atunci când
|| h k || ¹ 1 lungimea segmentului care leagă punctele x k. x k + 1. desigur, nu este egal | ak |. De obicei, numele metodei de minimizare este determinată de metoda de alegere a h k. și diferitele sale variante sunt asociate cu diferite moduri de a alege ak. Împreună cu termenul de metodă pe termen, vom folosi și termenul de iterație a metodei.
Printre metodele de minimizare, putem distinge în mod convențional între metode finite-step și infinite-step. Metode finite-pas sau finite sunt numite care garantează căutarea unei soluții a unei probleme într-un număr finit de pași. Metodele cu etape finite pot fi construite numai pentru anumite tipuri speciale de probleme de optimizare, de exemplu, probleme de programare liniară și patratică. Pentru metode infinite, soluția este garantată numai în limită.
Articole similare
Trimiteți-le prietenilor: