Programare neliniară

Programarea neliniară ( NLP , N on Linear Programare ) este un caz de programare matematică care nu se rezumă la stabilirea unei probleme de programare liniară (de exemplu, în care funcția obiectiv sau constrângerea este o funcție neliniară ) [1] .

Problema programării neliniare se pune ca problema găsirii optimului unei anumite funcții obiectiv în condițiile $F(x_{1},\ldots x_{n})$

g_{j}(x_{1},\ldots x_{n})\geq 0

unde - parametri, - restricții, - număr de parametri, - număr de restricții. $x_{i},i=1,\ldots,n$ $g_{j},j=1,\ldots,s$ $n$ $s$

Spre deosebire de o problemă de programare liniară, într-o problemă de programare neliniară, optimul nu se află neapărat la limita regiunii definite de constrângeri.

Metode de rezolvare a problemei

Una dintre metodele care ne permit să reducem problema programării neliniare la rezolvarea unui sistem de ecuații este metoda multiplicatorilor Lagrange nedeterminați .

Dacă funcția obiectiv este liniară , iar spațiul mărginit este un politop , atunci problema este o problemă de programare liniară care poate fi rezolvată folosind soluții de programare liniară bine-cunoscute . $F$

Dacă funcția obiectiv este concavă (problema de maximizare) sau convexă (problema de minimizare) și setul de constrângeri este convex, atunci problema se numește convexă , iar în cele mai multe cazuri pot fi utilizate metode de optimizare convexe generale .

Dacă funcția obiectiv este raportul dintre funcțiile concave și convexe (la maximizare) și constrângerile sunt convexe, atunci problema poate fi transformată într-o problemă de optimizare convexă folosind tehnici de programare fracțională.

Există mai multe metode de rezolvare a problemelor neconvexe. O abordare este utilizarea formulărilor speciale ale problemelor de programare liniară. O altă metodă implică utilizarea metodelor ramificate și legate , în care problema este subdivizată pentru a fi rezolvată cu aproximări convexe (problema de minimizare) sau liniare care formează o limită inferioară a costului total în cadrul partiției. În secțiunile următoare, la un moment dat, se va obține o soluție reală, al cărei cost este egal cu cea mai bună limită inferioară obținută pentru oricare dintre soluțiile aproximative. Această soluție este optimă, deși poate nu singura. Algoritmul poate fi terminat într-un stadiu incipient, cu încredere că soluția optimă se află în deviația acceptabilă de la punctul cel mai bun găsit; astfel de puncte sunt numite ε-optimale. Terminarea punctelor ε-optime, de regulă, este necesară pentru a asigura caracterul finit al terminației. Acest lucru este util în special pentru probleme mari, complexe și probleme cu costuri sau valori incerte, unde incertitudinea poate fi determinată dintr-o estimare adecvată a fiabilității.

Condiții de diferențiere și regularitate , condițiile Karush-Kuhn-Tucker (KKT) asigură condițiile necesare optimității soluției. Pentru convexitate, aceste condiții sunt și ele suficiente.

O altă metodă de rezolvare a problemelor de programare neliniară este programarea dinamică [2] .

Vezi și

Programare liniară

Link -uri

Găsirea optimului online prin metoda complexelor

Note

↑ Hadley, 1967 , p. 11, 12.
↑ Hadley, 1967 , p. cincisprezece.

Literatură

Headley J. Programare neliniară și dinamică. - M . : Mir, 1967. - 506 p.

Dicționare și enciclopedii	Rusă mare Britannica (online)
În cataloagele bibliografice	BNF : 122677537 J9U : 987007533977205171 LCCN : sh85092331 NKC : ph293203

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică