Optimizare cu constrângeri

Mulți algoritmi de optimizare fără constrângeri pot fi adaptați la cazul cu constrângeri, adesea prin utilizarea unei metode de penalizare. Cu toate acestea, etapele de căutare parcurse de metoda neconstrânsă pot fi inacceptabile pentru problema constrânsă, ceea ce duce la o lipsă de convergență. Acest lucru este denumit efectul Maratos.

Constrângeri de egalitateEdit

Metoda substituțieiEdit

Pentru probleme foarte simple, de exemplu o funcție de două variabile supusă unei singure constrângeri de egalitate, este cel mai practic să se aplice metoda substituției. Ideea este de a substitui constrângerea în funcția obiectiv pentru a crea o funcție compozită care să încorporeze efectul constrângerii. De exemplu, să presupunem că obiectivul este de a maximiza f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}.

sub rezerva x + y = 10 {\displaystyle x+y=10}

. Constrângerea implică y = 10 – x {\displaystyle y=10-x}.

, care poate fi înlocuită în funcția obiectiv pentru a crea p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}}.

. Condiția necesară de ordinul întâi dă ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}

, care poate fi rezolvată pentru x = 5 {\displaystyle x=5}

și, în consecință, y = 10 – 5 = 5 {\displaystyle y=10-5=5}

.

Lagrange multiplierEdit

Dacă problema constrânsă are numai constrângeri de egalitate, metoda multiplicatorilor Lagrange poate fi folosită pentru a o transforma într-o problemă fără constrângeri al cărei număr de variabile este numărul inițial de variabile plus numărul inițial de constrângeri de egalitate. Alternativ, în cazul în care constrângerile sunt toate constrângeri de egalitate și sunt toate liniare, acestea pot fi rezolvate pentru unele dintre variabile în funcție de celelalte, iar primele pot fi înlocuite din funcția obiectiv, lăsând o problemă fără constrângeri cu un număr mai mic de variabile.

Constrângeri de inegalitateEdit

Cu constrângeri de inegalitate, problema poate fi caracterizată în termeni de condiții de optimitate geometrică, condiții Fritz John și condiții Karush-Kuhn-Tucker, sub care problemele simple pot fi rezolvabile.

Programare liniarăEdit

Dacă funcția obiectiv și toate constrângerile dificile sunt liniare și unele constrângeri dificile sunt inegalități, atunci problema este o problemă de programare liniară. Aceasta poate fi rezolvată prin metoda simplex, care, de obicei, funcționează în timp polinomial în mărimea problemei, dar nu este garantat să o facă, sau prin metode de puncte interioare care sunt garantate să funcționeze în timp polinomial.

Programare neliniarăEdit

Dacă funcția obiectiv sau unele dintre constrângeri sunt neliniare, iar unele constrângeri sunt inegalități, atunci problema este o problemă de programare neliniară.

Programare pătraticăEdit

Dacă toate constrângerile tari sunt liniare și unele sunt inegalități, dar funcția obiectiv este pătratică, problema este o problemă de programare pătratică. Este un tip de programare neliniară. Ea poate fi totuși rezolvată în timp polinomial prin metoda elipsoidală dacă funcția obiectiv este convexă; în caz contrar, problema poate fi NP hard.

Condiții KKTEdit

Având constrângeri de inegalitate, abordarea KKT a programării neliniare generalizează metoda multiplicatorilor Lagrange. Ea poate fi aplicată în condiții de diferențiabilitate și convexitate.

Branch and boundEdit

Optimizarea prin constrângeri poate fi rezolvată prin algoritmi branch-and-bound. Aceștia sunt algoritmi de backtracking care stochează costul celei mai bune soluții găsite în timpul execuției și îl folosesc pentru a evita o parte din căutare. Mai precis, ori de câte ori algoritmul întâlnește o soluție parțială care nu poate fi extinsă pentru a forma o soluție cu un cost mai bun decât cel mai bun cost stocat, algoritmul se întoarce înapoi, în loc să încerce să extindă această soluție.

Să presupunem că costul trebuie minimizat, eficiența acestor algoritmi depinde de modul în care este evaluat costul care poate fi obținut prin extinderea unei soluții parțiale. Într-adevăr, dacă algoritmul poate da înapoi de la o soluție parțială, o parte din căutare este sărită. Cu cât costul estimat este mai mic, cu atât algoritmul este mai bun, deoarece un cost estimat mai mic are mai multe șanse să fie mai mic decât cel mai bun cost al soluției găsite până în acel moment.

Pe de altă parte, acest cost estimat nu poate fi mai mic decât costul efectiv care poate fi obținut prin extinderea soluției, deoarece altfel algoritmul ar putea da înapoi în timp ce există o soluție mai bună decât cea mai bună găsită până în acel moment. Ca urmare, algoritmul necesită o limită superioară a costului care poate fi obținut prin extinderea unei soluții parțiale, iar această limită superioară trebuie să fie cât mai mică posibil.

O variantă a acestei abordări numită metoda lui Hansen utilizează metode de interval. Ea implementează în mod inerent constrângeri rectangulare.

Funcții de delimitare de primă alegereEdit

O modalitate de evaluare a acestei limite superioare pentru o soluție parțială este de a considera fiecare constrângere soft separat. Pentru fiecare constrângere soft, se presupune valoarea maximă posibilă pentru orice atribuire a variabilelor neatribuite. Suma acestor valori reprezintă o limită superioară, deoarece constrângerile soft nu pot presupune o valoare mai mare. Este exactă deoarece valorile maxime ale constrângerilor flexibile pot proveni din evaluări diferite: o constrângere flexibilă poate fi maximă pentru x = a {\displaystyle x=a}.

, în timp ce o altă constrângere este maximă pentru x = b {\displaystyle x=b}.

.

Russian doll searchEdit

Această metodă execută un algoritm de tip branch-and-bound pe n {\displaystyle n}

probleme, unde n {\displaystyle n}

este numărul de variabile. Fiecare astfel de problemă este subproblema obținută prin renunțarea la o secvență de variabile x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}}.

din problema inițială, împreună cu constrângerile care le conțin. După ce problema pe variabilele x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}

este rezolvată, costul optim al acesteia poate fi utilizat ca limită superioară în timpul rezolvării celorlalte probleme,

În special, estimarea costului unei soluții având x i + 1 , … , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}

ca variabile neatribuite se adaugă la costul care derivă din variabilele evaluate. Practic, acest lucru corespunde ignorării variabilelor evaluate și rezolvării problemei pe cele neatribuite, cu excepția faptului că această din urmă problemă a fost deja rezolvată. Mai exact, costul constrângerilor flexibile care conțin atât variabile alocate, cât și nealocate se estimează ca mai sus (sau folosind o altă metodă arbitrară); costul constrângerilor flexibile care conțin numai variabile nealocate se estimează, în schimb, folosind soluția optimă a problemei corespunzătoare, care este deja cunoscută în acest moment.

Există o similitudine între metoda de căutare a păpușii rusești și programarea dinamică. Ca și programarea dinamică, Russian Doll Search rezolvă subprobleme pentru a rezolva întreaga problemă. Dar, în timp ce programarea dinamică combină în mod direct rezultatele obținute în subprobleme pentru a obține rezultatul întregii probleme, Russian Doll Search le folosește doar ca limite în timpul căutării sale.

Eliminarea gălețiiEdit

Agoritmul de eliminare a găleții poate fi adaptat pentru optimizarea prin constrângeri. O anumită variabilă poate fi într-adevăr eliminată din problemă prin înlocuirea tuturor constrângerilor soft care o conțin cu o nouă constrângere soft. Costul acestei noi constrângeri este calculat presupunând o valoare maximă pentru fiecare valoare a variabilei eliminate. În mod formal, dacă x {\displaystyle x}

este variabila care trebuie eliminată, C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}

sunt constrângerile soft care o conțin, iar y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}

sunt variabilele lor, cu excepția lui x {\displaystyle x}

, noua constrângere soft este definită prin: C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}

Eliminarea cu găleți funcționează cu o ordine (arbitrară) a variabilelor. Fiecărei variabile i se asociază o găleată de constrângeri; găleata unei variabile conține toate constrângerile care au variabila are cea mai mare valoare în ordine. Eliminarea bucket-ului se face de la ultima variabilă la prima. Pentru fiecare variabilă, toate constrângerile din bucket sunt înlocuite ca mai sus pentru a elimina variabila respectivă. Constrângerea rezultată este apoi plasată în bucket-ul corespunzător.

.