Metode de gradient

Folosind metode de gradient, se poate găsi soluția oricărei probleme de programare neliniară. Aplicarea acestor metode în cazul general face posibilă găsirea unui punct extrem de local. Prin urmare, este mai bine să le folosiți pentru a găsi soluții la probleme de programare convexe. Procesul de găsire a soluției unei probleme folosind metode de gradient







constă în faptul că pornind de la un anumit punct, o tranziție succesivă la alte puncte se realizează până când se găsește o soluție acceptabilă a problemei inițiale. Metodele gradient pot fi împărțite în două grupuri.

Primul grup include metode în care punctele investigate nu depășesc gama de soluții admisibile ale problemei. În acest caz, cea mai comună este metoda Frank-Wolf. Al doilea este metodele prin care punctele de studiu pot să aparțină și să nu aparțină domeniului soluțiilor admise. Cu toate acestea, ca rezultat al implementării procesului iterativ, există un punct al regiunii soluțiilor admisibile care determină o soluție acceptabilă. Metoda funcțiilor de pedeapsă și metoda Arrow-Hurwitz sunt cele mai des folosite. Atunci când soluția problemei se găsește prin metode de gradient, procesul iterativ continuă până când gradientul funcției la punctul următor devine zero sau până când inegalitatea

. unde (acuratețea soluției obținute).

Metoda Frank-Wulf. Să se solicite să se găsească valoarea maximă a unei funcții concave







Limitările conțin doar inegalități liniare. Această caracteristică este baza pentru înlocuirea funcției obiective neliniare cu una liniară în vecinătatea punctului studiat, ca urmare a soluției problemei inițiale, care se reduce la soluția secvențială a problemelor de programare liniară.

Procesul de găsire a unei soluții începe cu definirea unui punct care aparține domeniului soluțiilor admisibile. Lasă asta să fie un punct. Calculați în acest moment gradientul funcției (9):

construi o funcție liniară

Găsiți funcția maximă (12) sub constrângerile (10) și (11). Fie ca soluția problemei date să fie determinată de un punct. Coordonatele punctului sunt considerate ca fiind noua soluție acceptabilă a problemei inițiale. care se găsesc prin formule

unde este un anumit număr, numit pasul de calcul. 3a ia cel puțin rădăcina ecuației sau alege arbitrar dacă nu aparține intervalului (0; 1).

Metoda funcțiilor de penalizare. Considerăm problema de programare neliniară (6) - (8), unde sunt funcții convexe.

În loc de asta. pentru a rezolva această problemă, găsiți funcția maximă

unde este definit printr-un sistem de restricții și se numește o funcție penală. Acestea din urmă pot fi construite în diverse moduri. Cel mai adesea are forma

a sunt unele numere constante reprezentând coeficienți de greutate.

Folosind funcția de pedeapsă, mergeți în mod constant de la un punct la altul până când găsiți o soluție acceptabilă. Sunt găsite coordonatele punctului următor

unde este etapa de calcul.

Procesul iterativ începe, de obicei, la valori relativ mici și, continuând, aceste valori cresc treptat.

Arrow - metoda Hurwitz. Atunci când găsim soluția problemei programării neliniare prin metoda funcțiilor de pedeapsă de valoare. sunt alese arbitrar, ceea ce duce la fluctuații semnificative în depărtarea punctelor determinate din regiunea soluțiilor admise. Acest defect este eliminat în soluția problemei prin metoda Arrow-Hurwitz, conform căreia, la următoarea etapă, cifrele sunt găsite din

Deoarece valorile inițiale iau numere arbitrare ne-negative.







Articole similare

Trimiteți-le prietenilor: