Nelinearno programiranje

U matematici, nelinearno programiranje (NLP) je proces rešavanja optimizacionog problema^[1][2] gde su neka od ograničenja ili objektivnih funkcija nelinearna. Optimizacioni problem je jedan od proračuna ekstrema (maksimuma, minimuma ili stacionarnih tačaka) jedne objektivne funkcije nad setom nepoznatih realnih promenljivih, koji je uslovljen zadovoljavanjem sistema jednačina i nejednačina, kolektivno zvanih ograničenja. To je potpolje matematičke optimizacije koje se bavi problemima koji nisu linearni.^[3][4][5]

Primenjivost

Tipični nekonveksni problem je problem optimizacije troškova prevoza selekcijom iz seta transportnih metoda, od kojih jedan ili više manifestuju efekte razmera, s različitim stepenima povezivanja i ograničenjima kapaciteta. Primer bi bio transport naftnih derivata s obzirom na izbor ili kombinaciju cevovoda, željezničkih tankera, cestovnih tankera, rečne barke ili priobalskog broda. Zbog ekonomije veličine šarže, troškovne funkcije mogu imati i diskontinuitete osim glatkih promena.

U eksperimentalnoj nauci neke se jednostavnih analiza podataka (poput uklapanja spektra sa zbirom pikova poznatog položaja i oblika, ali nepoznate magnitude) mogu se obaviti linearnim metodama, ali generalno su i ovi problemi nelinearni. Tipično postoji teorijski model ispitivanog sistema s promenjivim parametrima u njemu, i model eksperimenta ili eksperimenata, koji takođe može da ima nepoznate parametre. Potrebno je da se numerički pronađe najbolje uklapanje. U ovom slučaju se često zahteva izvesna mera preciznosti rezultata, kao i samo najbolje uklapanje.

Definicija

Neka su n, m, i p pozitivni celi brojevi. Neka je X podskup skupa Rⁿ, neka su f, g_i, i h_j funkcije realnih vrednosti na X za svako i u {1, …, m} i svako j u {1, …, p}, pri čemu je bar jedna od f, g_i, i h_j nelinearna.

Problem nelineare minimizacije je problem optimizacije oblika

${\displaystyle {\begin{aligned}{\text{minimiziraj }}&f(x)\\{\text{tako da je }}&g_{i}(x)\leq 0{\text{ za svako }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ za svako }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}}$

Problem nelinearne maksimizacije je definisan na sličan način.

Mogući tipovi seta ograničenja

Postoji nekoliko mogućnosti za prirodu skupa ograničenja, poznatog i pod nazivom izvodljivi skup ili izvodljiva regija. Neizvodljiv je problem za koji nijedan skup vrednosti za izabrane promenljive ne zadovoljava sva ograničenja. To jest, ograničenja su uzajamno kontradiktorna i ne postoji rešenje, te je izvodljivi skup je prazan skup. Izvodljiv je problem za koji postoji barem jedan niz vrednosti za skup izabranih promenljivih koji zadovoljava sva ograničenja. Neograničeni problem je izvodljiv problem za koji se ciljna funkcija može učiniti boljom od bilo koje date konačne vrednosti. Prema tome, ne postoji optimalno rešenje, jer uvek postoji izvodljivo rešenje koje daje bolju vrednost objektivne funkcije od bilo kojeg predloženog rešenja.

Metodi za rešavanje problema

Ako je ciljna funkcija f linearna, a ograničeni prostor politop, problem je problem linearnog programiranja, koji se može rešiti korišćenjem poznatih tehnika linearnog programiranja, kao što je simpleks metoda.

Ako je ciljna funkcija konkavna (problem maksimizacije), ili konveksna (problem minimizacije), i skup ograničenja je konveksan, onda se program naziva konveksnim i opšte metode iz konveksne optimizacije mogu se koristiti u većini slučajeva.

Ako je ciljna funkcija kvadratna, a ograničenja linearna, koriste se tehnike kvadratnog programiranja.

Ako je ciljna funkcija odnos konkavne i konveksne funkcije (u slučaju maksimizacije), a ograničenja su konveksna, onda se problem može transformisati u problem konveksne optimizacije pomoću tehnika frakcijskog programiranja.

Dostupno je nekoliko metoda za rešavanje nekonveksnih problema. Jedan od pristupa je upotreba posebnih formulacija problema linearnog programiranja. Druga metoda uključuje upotrebu tehnika separacije i evaluacije, gde je program podeljen na podklase koje treba rešiti konveksnim (problem minimizacije) ili linearnim aproksimacijama, koje formiraju donju granicu sveukupnih troškova u podelama. S naknadnim podelama, u nekom trenutku će se dobiti stvarno rešenje, čiji je trošak jednak najboljoj donjoj granici dobivenoj za bilo koje od približnih rešenja. Ovo rešenje je optimalno, mada je moguće da nije jedinstveno. Algoritam se takođe može zaustaviti rano, sa sigurnošću da je najbolje moguće rešenje unutar tolerancije od najbolje pronađene tačke; takve tačke se nazivaju ε-optimalnim. Prekid na ε-optimalnim tačkama je obično neophodan da bi se osigurao konačni prekid. Ovo je posebno korisno za velike, teške probleme i probleme sa nepredvidivim troškovima ili vrednostima, gde se neizvesnost može proceniti odgovarajućom procenom pouzdanosti.

Pod pretpostavkama diferencijabilnosti i konstantnih kvalifikacija, Karuš–Kan–Takerovi uslovi (KKT) pružaju potrebne uslove da rešenje bude optimalno. Pod pretpostavkom konveksnosti, ovi uslovi su takođe dovoljni. Ako su neke funkcije nediferencirane, subdiferencijabilne verzije KKT uslova su dostupne.^[6]

Primeri

Dvodimenzioni primer

Jednostavni problem (prikazan na dijagramu) može se definisati pomoću ograničenja

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

sa objektivnom funkcijom koju treba maksimizovati

f(x) = x₁ + x₂

gde je x = (x₁, x₂).

Trodimenzioni primer

Još jedan jednostavan problem (pogledajte dijagram) može se definisati pomoću ograničenja

x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

sa objektivnom funkcijom koju treba maksimizovati

f(x) = x₁x₂ + x₂x₃

gde je x = (x₁, x₂, x₃).

Reference

Literatura

Spoljašnje veze