Programare neliniară

Programarea neliniară (PNL) — este o ramură a programării matematice și a cercetării operaționale, care se ocupă cu probleme de optimizare în care funcția obiectiv și/sau cel puțin una dintre restricții sunt funcții neliniare ale variabilelor de decizie.

PNL reprezintă o generalizare a programării liniare și permite modelarea unei clase mai largi de sisteme și procese reale, în care dependențele dintre variabile nu sunt strict proporționale (adică sunt descrise de curbe, nu de drepte).

Obiect și destinație

Programarea neliniară este utilizată pentru găsirea soluțiilor optime în situații în care:

• Dependența indicatorului obiectiv (profit, costuri, eficiență etc.) față de parametrii controlați este neliniară (de exemplu, randamente descrescătoare la scară, costuri pătratice).
• Restricțiile privind resursele sau procesele tehnologice sunt descrise prin relații neliniare (de exemplu, reacții chimice, legi fizice, dependențe economice).

Probleme de PNL apar în multe domenii:

• Proiectare inginerească (optimizarea structurilor, proceselor).
• Economie și finanțe (optimizarea portofoliului cu luarea în considerare a riscului, modelarea pieței).
• Tehnologie chimică (optimizarea regimurilor reactoarelor).
• Machine Learning (antrenarea rețelelor neuronale, metoda vectorilor suport).
• Managementul proceselor de producție. Logistică (cu luarea în considerare a costurilor neliniare).

Formularea matematică a problemei PNL

Problema generală de programare neliniară se formulează astfel:

Se cere să se găsească un set de valori ale variabilelor de decizie care maximizează sau minimizează funcția obiectiv neliniară. Totodată, valorile variabilelor trebuie să satisfacă un sistem de restricții, care pot fi exprimate atât sub formă de inegalități (de exemplu, „mărimea A trebuie să fie mai mică sau egală cu B"), cât și sub formă de egalități (de exemplu, „mărimea C trebuie să fie exact egală cu D"). Este important că cel puțin una dintre funcțiile care descriu obiectivul sau restricțiile este neliniară. Adesea se adaugă condiții de non-negativitate a variabilelor, adică cerința ca valorile lor să fie mai mari sau egale cu zero.

Mulțimea tuturor seturilor de valori ale variabilelor care satisfac restricțiile formează domeniul soluțiilor admisibile (DSA).

Diferențe față de programarea liniară

Programarea neliniară diferă esențial de programarea liniară (PL):

• Neliniaritatatea: Funcția obiectiv sau restricțiile (sau ambele) conțin dependențe neliniare.
• Proprietățile DSA: Domeniul soluțiilor admisibile în PNL poate fi neconvex (spre deosebire de PL, unde DSA este întotdeauna un poliedru convex).
• Proprietățile optimului: Soluția optimă în PNL nu se găsește în mod obligatoriu la un vârf al DSA; ea poate fi situată pe frontieră sau în interiorul domeniului. În PNL pot exista optimuri locale care nu sunt globale.
• Complexitatea rezolvării: Problemele de PNL sunt, în general, considerabil mai dificil de rezolvat decât problemele de PL. Nu există un algoritm universal unic, analog metodei simplex, pentru toate problemele de PNL.

Principalele dificultăți și provocări ale PNL

Rezolvarea problemelor de programare neliniară este însoțită de o serie de dificultăți:

• Prezența extremelor locale: Majoritatea metodelor de PNL garantează găsirea doar a unui optim local (o soluție mai bună într-o anumită vecinătate). Căutarea optimului global (cea mai bună soluție din întregul DSA) este o problemă dificilă, în special pentru problemele neconvexe.
• Neconvexitatea: Dacă problema nu este convexă (funcția obiectiv sau DSA sunt neconvexe), pot exista multiple optimuri locale, iar metodele gradientului standard se pot „bloca" în unul dintre ele.
• Complexitatea computațională: Algoritmii de rezolvare a PNL necesită adesea resurse computaționale considerabil mai mari în comparație cu PL.

Clase importante de probleme PNL

În ciuda complexității generale, există subclase importante de probleme PNL pentru care au fost dezvoltate metode eficiente de rezolvare:

• Programarea convexă: Problema minimizării unei funcții convexe pe o mulțime convexă de soluții admisibile (sau maximizarea unei funcții concave). Proprietatea cheie: orice minim local este totodată și minim global. Aceasta simplifică semnificativ căutarea soluției optime.
• Programarea pătratică: Funcția obiectiv este pătratică, iar toate restricțiile sunt liniare.
• Programarea separabilă: Funcția obiectiv și restricțiile pot fi reprezentate ca sume de funcții, fiecare dintre ele depinzând doar de o singură variabilă.

Metode de rezolvare a problemelor PNL

Metode de rezolvare a problemelor de programare neliniară (PNL)

I. Metode de optimizare necondiționată (optimizare fără restricții):

• Metode gradientului (metoda celei mai abrupte coborâri, metoda gradienților conjugați);
• Metoda Newton și metodele cvasi-Newton (de exemplu, BFGS);
• Metode cu utilizarea aproximării Hessianului.

II. Metode de optimizare condiționată (optimizare cu restricții):

• Metode de transformare:
  • Metoda funcțiilor de penalizare (penalty methods);
  • Metoda funcțiilor de barieră (barrier methods).
• Metode de căutare directă a direcțiilor:
  • Metoda direcțiilor admisibile.
• Metode bazate pe condițiile de optimalitate:
  • Metodele Karush-Kuhn-Tucker (condiții KKT);
  • Metoda multiplicatorilor Lagrange.
• Metode iterative:
  • Programarea pătratică secvențială (SQP);
  • Metodele punctelor interioare.

III. Metode de optimizare globală:

• Metode euristice și metaeuristice:
  • Algoritmi genetici;
  • Recoacere simulată;
  • Căutare cu interdicții (tabu search).
• Metode deterministe:
  • Ramificare și mărginire (branch and bound);
  • Algoritmi de optimizare globală pentru probleme cu structură specială.

Bibliografie

• Bazara M., Shetty C. Programare neliniară. Teorie și algoritmi. — M.: Mir, 1982.
• Fiacco A., McCormick G. Programare neliniară. Metode de minimizare necondiționată secvențială. — M.: Mir, 1972.
• Himmelblau D. Programare neliniară aplicată. — M.: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Vezi și

• Cercetarea operațională
• Optimizare
• Programare liniară
• Programare convexă
• Funcție obiectiv
• Restricții
• Domeniul soluțiilor admisibile