Nelinearno programiranje (NLP)

Izvor: DALL·E

Nelinearno programiranje (NLP) je grana operacijskog istraživanja koja se bavi optimizacijom kad je funkcija cilja i/ili ograničenja nelinearna (kvadratne, eksponencijalne, logaritamske, trigonometrijske funkcije, umnošci varijabli, itd.).

Za razliku od LP-a, NLP često ima:

više lokalnih optimuma (ne-konveksnost),
osjetljivost na početnu točku,
potrebu za derivacijama ili robustnim bezgradijentnim metodama.

Značajan razvoj započinje nakon Drugog svjetskog rata, usko povezan s razvojem operacijskog istraživanja i računalne tehnologije.

Nelinearno programiranje proizašlo je iz potrebe za rješavanjem kompleksnijih stvarnih problema koji nisu mogli biti adekvatno modelirani linearnim pristupima.
Ključni trenuci u razvoju nelinearnog programiranja uključuju:
- Razvoj metoda optimizacije: Metode kao što su Newtonova metoda i metoda gradijentnog spusta razvijene su za rješavanje nelinearnih problema. Te metode koriste derivacije za pronalaženje ekstrema funkcija.
- Karush-Kuhn-Tucker (KKT) uvjeti: Uvedeni 1951. godine, KKT uvjeti generaliziraju Lagrangeove multiplikatore za nelinearne optimizacijske probleme s ograničenjima, pružajući neophodan alat za analizu i rješavanje tih problema.
- Razvoj računalne tehnologije: S pojavom moćnijih računala, mogućnosti za rješavanje složenijih nelinearnih problema znatno su se povećale. Računalni algoritmi postali su ključni u primjeni nelinearnog programiranja.
Primjena u različitim područjima: inženjerstvo, ekonomija, upravljanje lancima opskrbe i znanost o podacima.
Razvoj nelinearnog programiranja nastavlja se i danas, s fokusom na povećanje efikasnosti algoritama, rješavanje većih i složenijih problema, te integraciju s drugim područjima kao što su strojno učenje i umjetna inteligencija.

Osnove NLP-a

Opći zapis

Minimizirati (ili maksimizirati) \(f(x)\), \(x \in \mathbb{R}^n\)

uz ograničenja:

nejednakosti: \(g_i(x) \le 0,\; i=1,\dots,m\)
jednakosti: \(h_j(x) = 0,\; j=1,\dots,k\)
granice varijabli: \(l \le x \le u\)

gdje je barem jedna od \(g_i(x)\), \(h_i(x)\) ili \(f(x)\) nelinearna funkcija.

Gradijent i Hessian (intuicija)

Gradijent \(\nabla f(x)\) pokazuje smjer najvećeg rasta funkcije.
Negativni gradijent \(-\nabla f(x)\) je “najstrmiji” smjer pada.
Hessian \(H(x)\) (matrica drugih derivacija) opisuje zakrivljenost.
Taylor (2. reda) oko \(x\):

\[ f(x+p) \approx f(x) + \nabla f(x)^\top p + \tfrac12 p^\top H(x) p \]

Konveksnost i “lokalno = globalno”

Ako je problem:

minimizacija konveksne funkcije uz konveksna ograničenja, ili
maksimizacija konkavne funkcije uz konveksna ograničenja,

onda je svaki KKT optimum (pod blagim uvjetima) i globalni optimum.

KKT uvjeti

Karush–Kuhn–Tucker (KKT) uvjeti su uvjeti optimalnosti prvog reda za probleme optimizacije s ograničenjima. U teoriji i praksi nelinearnog programiranja KKT uvjeti predstavljaju temeljni alat jer generaliziraju Lagrangeove multiplikatore na slučaj nejednakosnih ograničenja.

KKT je NLP analog LP dualnosti/sjena cijena te govori kako se optimum balansira s ograničenjima i koje je ograničenje “kritično”. Ne morate znati ručno računati KKT, ali trebate znati:

zašto algoritam uopće može tvrditi da je našao optimum,
zašto ponekad dobije lokalni optimum,
zašto ograničenja i početna točka/skaliranje mogu utjecati na ishod.

Razmatra se problem minimizacije: \[ \min_x \ f(x) \] uz ograničenja \[ g_i(x)\le 0,\quad i=1,\dots,m, \qquad h_j(x)=0,\quad j=1,\dots,p. \]

Definira se Lagrangeova funkcija: \[ \mathcal{L}(x,\lambda,\nu)= f(x)+\sum_{i=1}^m \lambda_i g_i(x)+\sum_{j=1}^p \nu_j h_j(x), \] gdje su \(\lambda_i\) Lagrangeovi multiplikatori za nejednakosti, a \(\nu_j\) multiplikatori za jednakosti.

KKT uvjeti

Točka \(x^*\) je kandidat za optimalno rješenje ako postoje multiplikatori \(\lambda^*\) i \(\nu^*\) takvi da vrijedi:

Primalna izvedivost (poštivanje ograničenja): \[ g_i(x^*)\le 0,\ \forall i,\qquad h_j(x^*)=0,\ \forall j. \]
Dualna izvedivost (znak multiplikatora za nejednakosti): \[ \lambda_i^*\ge 0,\ \forall i. \]
Stacionarnost (nul-gradijent Lagrangiana po \(x\)): \[ \nabla_x \mathcal{L}(x^*\,,\lambda^*\,,\nu^*)= \nabla f(x^*)+\sum_{i=1}^m \lambda_i^*\ \nabla g_i(x^*)+\sum_{j=1}^p \nu_j^*\ \nabla h_j(x^*)=0. \]
Komplementarna zategnutost (engl. complementary slackness): \[ \lambda_i^*\, g_i(x^*)=0,\ \forall i. \]

Intuicija komplementarne zategnutosti - za svako nejednakosno ograničenje vrijedi sljedeći princip:

ako je ograničenje neaktivno u optimumu (\(g_i(x^*\)<0)), tada multiplikator mora biti \(\lambda_i^*=0\);
ako je ograničenje aktivno u optimumu (\(g_i(x^*\)=0)), tada multiplikator može biti pozitivan (\(\lambda_i^*\ge 0\)) i “utječe” na optimalno rješenje.

Drugim riječima, u optimumu neaktivna ograničenja nemaju cijenu, dok aktivna ograničenja imaju pridruženu “sjenu” (engl. shadow price) kroz vrijednost multiplikatora.

Kad su KKT uvjeti nužni i/ili dovoljni?

Za konveksne probleme (konveksna funkcija cilja \(f\), konveksna nejednakosna ograničenja \(g_i\), linearna jednakosna ograničenja \(h_j\)) i uz odgovarajuću regularnost (npr. Slaterov uvjet), KKT uvjeti su nužni i dovoljni: svako rješenje koje zadovoljava KKT uvjete je globalni optimum.
Za nekonveksne probleme, KKT uvjeti su tipično samo nužni: mogu opisati lokalni optimum, ali ne jamče globalnu optimalnost.

KKT uvjeti su izravno povezani s praktičnim algoritmima:

SQP/SLSQP metode traže rješenja koja zadovoljavaju KKT uvjete rješavanjem niza aproksimacijskih potproblema.
Interior-point metode često rješavaju perturbirane KKT uvjete (uz barijerni parametar) i postupno smanjuju barijeru kako bi se približile izvornom problemu.

Ručni izračun - primjeri

Gradijentni spust (2 iteracije)

U praksi IKT sustava (npr. web-servisi, mikroservisi, API gateway, sustavi za obradu događaja) često je potrebno podešavati konfiguracijske parametre kako bi se zadovoljili ciljevi izvedbe (SLA): stabilan odziv, stabilan protok i niska stopa grešaka. Takvo podešavanje može se interpretirati kao optimizacijski problem: odabirom parametara minimizira se kazna (loss) koja mjeri odstupanje od željenog ponašanja sustava.

Razmotrit će se pojednostavljeni model s dvije varijable odluke:

\(x\): parametar povezan s memorijskim resursima (npr. razina cachiranja, veličina buffera ili ograničenje memorije),
\(y\): parametar povezan s konkurentnošću (npr. broj radnih dretvi/worker procesa ili razina paralelizacije).

Pretpostavlja se da sustav ima ciljane vrijednosti tih parametara, \(x^*\ = 2\) i \(y^*\ = -1\), pri kojima je ponašanje sustava najstabilnije. Odstupanje od cilja povećava ukupnu kaznu, pri čemu se kazna često modelira kvadratno (analogno metodi najmanjih kvadrata u statistici i strojnome učenju), jer kvadratna kazna snažnije penalizira veća odstupanja.

Minimizira se funkcija: \[ f(x,y)=(x-2)^2+2(y+1)^2, \] gdje ponder 2 uz drugi član znači da je odstupanje u \(y\)-dimenziji procijenjeno kao važnije ili osjetljivije.

U jednodimenzionalnom slučaju, derivacija opisuje nagib funkcije i smjer rasta/pada. U višedimenzionalnom slučaju ista ideja generalizira se pomoću gradijenta, vektora parcijalnih derivacija koji u svakoj točki pokazuje smjer najbržeg rasta funkcije.

Za zadanu funkciju vrijedi: \[ \nabla f(x,y)=\begin{bmatrix}2(x-2)\\4(y+1)\end{bmatrix}. \]

Gradijentni spust koristi činjenicu da se funkcija najbrže smanjuje u smjeru suprotnom od gradijenta, pa se iterativno ažuriranje definira kao:

\[ (x_{k+1},y_{k+1})=(x_k,y_k)-\alpha \nabla f(x_k,y_k), \]

gdje je \(\alpha>0\) stopa učenja (korak). Intuitivno, \(\alpha\) određuje koliko se “agresivno” mijenja rješenje: premalen korak vodi sporoj konvergenciji, a prevelik može uzrokovati preskakanje optimuma ili oscilacije.

Ručno izvođenje dviju iteracija gradijentnog spusta

Odabire se početna točka \((x_0,y_0)=(0,0)\) i stopa učenja \(\alpha=0.25\).

Iteracija 1 \[ \nabla f(0,0)=\begin{bmatrix}2(0-2)\\4(0+1)\end{bmatrix}=\begin{bmatrix}-4\\4\end{bmatrix}, \] \[ (x_1,y_1)=(0,0)-0.25(-4,4)=(1,-1). \]

Iteracija 2 \[ \nabla f(1,-1)=\begin{bmatrix}2(1-2)\\4(-1+1)\end{bmatrix}=\begin{bmatrix}-2\\0\end{bmatrix}, \] \[ (x_2,y_2)=(1,-1)-0.25(-2,0)=(1.5,-1). \]

Komponenta gradijenta po \(y\) već u prvoj iteraciji postaje nula jer je \(y\) dosegnuo optimalnu vrijednost \(-1\). Nakon toga se algoritam u ovom primjeru praktički “kreće” samo u \(x\)-smjeru prema 2. Ovaj detalj ilustrira da različite dimenzije mogu konvergirati različitim brzinama, ovisno o zakrivljenosti (težinama) u funkciji cilja.

Učinak izbora stope učenja \(\alpha\) i početne točke

Za kvadratne (konveksne) funkcije poput ove, gradijentni spust konvergira prema jedinstvenom globalnom minimumu pri razumnim vrijednostima \(\alpha\). Međutim, ponašanje algoritma se jasno razlikuje u sljedećim situacijama:

premalen \(\alpha\): kretanje prema optimumu je sigurno, ali sporo (mnogo iteracija),
umjeren \(\alpha\): brzo približavanje optimumu, stabilna putanja,
prevelik \(\alpha\): preskakanje optimuma, oscilacije, a ponekad i divergencija (osobito u “strmijim” smjerovima).

Početna točka \((x_0,y_0)\) utječe na početnu vrijednost funkcije i putanju kretanja po konturama funkcije (iako se kod konveksnih funkcija minimum u konačnici postiže neovisno o početnoj točki, uz stabilan korak).

Paralelne vizualizacije međurješenja: konture i putanje iteracija

Sljedeći ispis olakšava usporedbu “koliko brzo” se smanjuje funkcija cilja pri različitim stopama učenja, za početnu točku (0, 0).

##    iter        x           y            z alpha  start
## 1     0 0.000000   0.0000000 6.000000e+00  0.05 (0, 0)
## 2     1 0.200000  -0.2000000 4.520000e+00  0.05 (0, 0)
## 3     2 0.380000  -0.3600000 3.443600e+00  0.05 (0, 0)
## 4     3 0.542000  -0.4880000 2.650052e+00  0.05 (0, 0)
## 5     4 0.687800  -0.5904000 2.057413e+00  0.05 (0, 0)
## 6     5 0.819020  -0.6723200 1.609462e+00  0.05 (0, 0)
## 7     6 0.937118  -0.7378560 1.267157e+00  0.05 (0, 0)
## 8     7 1.043406  -0.7902848 1.003033e+00  0.05 (0, 0)
## 9     8 1.139066  -0.8322278 7.975031e-01  0.05 (0, 0)
## 10    9 1.225159  -0.8657823 6.364073e-01  0.05 (0, 0)
## 11   10 1.302643  -0.8926258 5.093650e-01  0.05 (0, 0)
## 12    0 0.000000   0.0000000 6.000000e+00  0.25 (0, 0)
## 13    1 1.000000  -1.0000000 1.000000e+00  0.25 (0, 0)
## 14    2 1.500000  -1.0000000 2.500000e-01  0.25 (0, 0)
## 15    3 1.750000  -1.0000000 6.250000e-02  0.25 (0, 0)
## 16    4 1.875000  -1.0000000 1.562500e-02  0.25 (0, 0)
## 17    5 1.937500  -1.0000000 3.906250e-03  0.25 (0, 0)
## 18    6 1.968750  -1.0000000 9.765625e-04  0.25 (0, 0)
## 19    7 1.984375  -1.0000000 2.441406e-04  0.25 (0, 0)
## 20    8 1.992188  -1.0000000 6.103516e-05  0.25 (0, 0)
## 21    9 1.996094  -1.0000000 1.525879e-05  0.25 (0, 0)
## 22   10 1.998047  -1.0000000 3.814697e-06  0.25 (0, 0)
## 23    0 0.000000   0.0000000 6.000000e+00  0.45 (0, 0)
## 24    1 1.800000  -1.8000000 1.320000e+00  0.45 (0, 0)
## 25    2 1.980000  -0.3600000 8.196000e-01  0.45 (0, 0)
## 26    3 1.998000  -1.5120000 5.242920e-01  0.45 (0, 0)
## 27    4 1.999800  -0.5904000 3.355444e-01  0.45 (0, 0)
## 28    5 1.999980  -1.3276800 2.147484e-01  0.45 (0, 0)
## 29    6 1.999998  -0.7378560 1.374390e-01  0.45 (0, 0)
## 30    7 2.000000  -1.2097152 8.796093e-02  0.45 (0, 0)
## 31    8 2.000000  -0.8322278 5.629500e-02  0.45 (0, 0)
## 32    9 2.000000  -1.1342177 3.602880e-02  0.45 (0, 0)
## 33   10 2.000000  -0.8926258 2.305843e-02  0.45 (0, 0)
## 34    0 0.000000   0.0000000 6.000000e+00  0.60 (0, 0)
## 35    1 2.400000  -2.4000000 4.080000e+00  0.60 (0, 0)
## 36    2 1.920000   0.9600000 7.689600e+00  0.60 (0, 0)
## 37    3 2.016000  -3.7440000 1.505933e+01  0.60 (0, 0)
## 38    4 1.996800   2.8416000 2.951579e+01  0.60 (0, 0)
## 39    5 2.000640  -6.3782400 5.785093e+01  0.60 (0, 0)
## 40    6 1.999872   6.5295360 1.133878e+02  0.60 (0, 0)
## 41    7 2.000026 -11.5413504 2.222401e+02  0.60 (0, 0)
## 42    8 1.999995  13.7578906 4.355907e+02  0.60 (0, 0)
## 43    9 2.000001 -21.6610468 8.537577e+02  0.60 (0, 0)
## 44   10 2.000000  27.9254655 1.673365e+03  0.60 (0, 0)

Poveznica s Newtonovom metodom

Newtonova metoda koristi ne samo gradijent (prvi izvod), nego i Hessian (matricu drugih derivacija), koji opisuje zakrivljenost funkcije. U višedimenzionalnom slučaju Newtonov korak definiran je kao:

\[ \begin{bmatrix}x_{k+1}\\y_{k+1}\end{bmatrix} = \begin{bmatrix}x_k\\y_k\end{bmatrix} - H(x_k,y_k)^{-1}\nabla f(x_k,y_k). \]

Za promatranu funkciju: \[ f(x,y)=(x-2)^2+2(y+1)^2 \] Hessian je konstantan (ne ovisi o \(x,y\)): \[ H(x,y)= \begin{bmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x\partial y}\\ \frac{\partial^2 f}{\partial y\partial x} & \frac{\partial^2 f}{\partial y^2} \end{bmatrix} = \begin{bmatrix} 2 & 0\\ 0 & 4 \end{bmatrix}. \] Stoga je \(H^{-1}\):

za dijagonalnu (u ovom slučaju i trokutastu) matricu determinanta je umnožak dijagonalnih elemenata: \[ \det(H)=2\cdot 4=8\neq 0. \] Budući da je \(\det(H)\neq 0\), matrica \(H\) je invertibilna.

Ako je \[ D=\mathrm{diag}(d_1,d_2), \] onda je \[ D^{-1}=\mathrm{diag}\!\left(\frac{1}{d_1},\frac{1}{d_2}\right), \] pod uvjetom da su \(d_1\neq 0\) i \(d_2\neq 0\).

Primjenom na \(H\) dobiva se:

\[ H^{-1}= \begin{bmatrix} \frac{1}{2} & 0\\ 0 & \frac{1}{4} \end{bmatrix}. \]

Uvrštavanjem gradijenta \(\nabla f(x,y)=[2(x-2),\;4(y+1)]^\top\) dobiva se: \[ H^{-1}\nabla f(x,y)= \begin{bmatrix} \frac{1}{2}\cdot 2(x-2)\\ \frac{1}{4}\cdot 4(y+1) \end{bmatrix} = \begin{bmatrix} x-2\\ y+1 \end{bmatrix}. \] Newtonov korak tada postaje: \[ (x_{k+1},y_{k+1})=(x_k,y_k) - (x_k-2,\;y_k+1) = (2,-1). \]

Za ovaj kvadratni problem Newtonova metoda dolazi u optimum \((2,-1)\) u jednom koraku, neovisno o početnoj točki (u idealnim uvjetima, bez numeričkih poteškoća).

# f() i grad_f() već definirani ranije u lekciji.

# Hessian i njegov inverz (konstantni u ovom primjeru)
H <- matrix(c(2, 0,
              0, 4), nrow = 2, byrow = TRUE)
H_inv <- solve(H)

# Jedan Newtonov korak iz (x0, y0)
newton_step <- function(x0, y0){
  g <- grad_f(x0, y0)
  step <- H_inv %*% matrix(g, ncol = 1)
  c(x0, y0) - as.numeric(step)
}

# Primjer: Newtonov korak iz (0,0)
newton_step(0, 0)

## [1]  2 -1

Jednostavna bezgradijentna metoda (koordinatna/ pattern search)

U mnogim IKT problemima funkcija koju se optimira nije dostupna u zatvorenom obliku ili je preskupo/nesigurno računati derivacije. Tipični primjeri su: - “black-box” mjerenja performansi (npr. latency, jitter, error rate) koja se dobivaju izvođenjem sustava u testnom okruženju, - simulacije (npr. mrežne simulacije, simulacije opterećenja, digital twins), - optimizacija hiperparametara ili konfiguracijskih parametara gdje je evaluacija funkcije skupa (pokretanje benchmarka).

U takvim situacijama primjenjuju se bezgradijentne metode (engl. derivative-free optimization). Ideja je jednostavna: umjesto da se računa gradijent, funkcija se evaluira u nekoliko susjednih točaka i bira se ona koja daje poboljšanje.

Problem (isti kao ranije)

Minimizira se: \[ f(x,y)=(x-2)^2+2(y+1)^2. \]

Iako je funkcija u ovom primjeru glatka i derivabilna, metoda se uvodi kao prototip algoritama koji su primjenjivi i kad gradijenti nisu dostupni.

Polazi se iz početne točke i zadanog koraka \(\Delta\). U svakoj iteraciji testiraju se četiri susjedne točke u koordinatnim smjerovima:

\[ (x+\Delta, y),\ (x-\Delta, y),\ (x, y+\Delta),\ (x, y-\Delta). \]

Ako se pronađe točka s manjom vrijednošću funkcije, algoritam se pomiče u tu točku (prihvaća “najbolji pomak”).
Ako se ne pronađe poboljšanje, korak se smanjuje (npr. \(\Delta \leftarrow \Delta/2\)) i pretraga se ponavlja.

Ovaj pristup pokazuje da se optimizacija može shvatiti kao sustavna lokalna pretraga prostora rješenja.

Početna točka: \[ (x_0,y_0)=(0,0), \qquad \Delta=1. \]

Vrijednost funkcije u startu: \[ f(0,0)=(0-2)^2+2(0+1)^2 = 4+2 = 6. \]

Testiraju se četiri susjedne točke:

\((1,0)\): \[ f(1,0)=(1-2)^2+2(0+1)^2 = 1+2=3 \quad \Rightarrow \text{poboljšanje}. \]
\((-1,0)\): \[ f(-1,0)=(-1-2)^2+2(0+1)^2 = 9+2=11. \]
\((0,1)\): \[ f(0,1)=(0-2)^2+2(1+1)^2 = 4+8=12. \]
\((0,-1)\): \[ f(0,-1)=(0-2)^2+2(-1+1)^2 = 4+0=4. \]

Najbolja testirana točka je \((1,0)\) s vrijednošću 3, pa se prihvaća pomak: \[ (x_1,y_1)=(1,0). \]

U ovoj iteraciji već se vidi “logika” metode: algoritam ne koristi derivacije, nego bira najbolju susjednu točku prema vrijednosti funkcije.

Što se događa dalje (intuicija kretanja prema \((2,-1)\))

U sljedećim iteracijama algoritam ponavlja isti postupak iz nove točke \((1,0)\):

evaluira se funkcija u četiri koordinatna smjera,
prihvaća se pomak koji smanjuje \(f\),
a ako nema poboljšanja, korak \(\Delta\) se smanjuje.

Budući da je globalni minimum funkcije u \((2,-1)\), algoritam će se tipično najprije kretati prema toj točki “grubim” koracima, a zatim, kad dođe u blizinu optimuma, smanjivanjem \(\Delta\) će postupno rafinirati rješenje.

Povezivanje s gradijentnim spustom (sličnosti i razlike)

Sličnosti:

Obje metode iterativno poboljšavaju rješenje koristeći lokalnu informaciju oko trenutne točke.

Razlike:

Gradijentni spust koristi smjer pada dobiven iz derivacija; izravna pretraga koristi samo evaluacije funkcije.
Izravna pretraga je robusnija kad gradijenti nisu dostupni ili su nepouzdani, ali često zahtijeva više evaluacija funkcije.

##    iter x  y        delta z
## 1     0 0  0 1.0000000000 6
## 2     1 1  0 1.0000000000 3
## 3     2 1 -1 1.0000000000 1
## 4     3 2 -1 1.0000000000 0
## 5     4 2 -1 0.5000000000 0
## 6     5 2 -1 0.2500000000 0
## 7     6 2 -1 0.1250000000 0
## 8     7 2 -1 0.0625000000 0
## 9     8 2 -1 0.0312500000 0
## 10    9 2 -1 0.0156250000 0
## 11   10 2 -1 0.0078125000 0
## 12   11 2 -1 0.0039062500 0
## 13   12 2 -1 0.0019531250 0
## 14   13 2 -1 0.0009765625 0

Vizualizacija: konture funkcije i putanja izravne pretrage

Usporedba s gradijentnim spustom

Ako se želi eksplicitna usporedba putanja, može se prikazati i gradijentni spust na istim konturama te usporediti broj iteracija i oblik putanje.

Primjene

Nelinearno programiranje (NLP) pojavljuje se u vrlo različitim domenama jer omogućuje modeliranje realističnih nelinearnih odnosa (troškovi, fizikalni zakoni, dinamika, rizik, penalizacije, saturacije), uz eksplicitno zadavanje ograničenja. U nastavku su sažeti tipični obrasci problema, s motivacijom i povezivanjem s relevantnom literaturom iz popisa.

1) Portfelj i troškovi transakcija (konveksni nelinearni modeli)

U portfeljnim problemima investitor ne mijenja portfelj “besplatno”: svaka kupnja/prodaja nosi transakcijske troškove. U praksi se često susreću:

linearni troškovi (proporcionalni volumenu),
fiksni troškovi (npr. minimalna naknada po transakciji),
ograničenja portfelja (budžet, granice udjela, zabrana shortanja, limiti izloženosti).

Ovakvi modeli prirodno postaju nelinearni (i ponekad mješoviti) jer “fiksna naknada” uvodi diskontinuitet ili potrebu za dodatnim varijablama (često binarne).

Varijable:

\(w \in \mathbb{R}^n\): udjeli imovine u novom portfelju
\(u \in \mathbb{R}^n\): trgovani volumeni (kupnja/prodaja)
moguće binarne varijable za aktiviranje fiksnog troška

Cilj (primjer): maksimizacija očekivanog prinosa uz penalizaciju rizika i troškova \[ \max \ \mu^\top w - \lambda \, \text{Risk}(w) - \text{TC}(u) \] uz budžetsko ograničenje i operativne limite: \[ \mathbf{1}^\top w = 1,\quad w \ge 0,\quad l \le w \le u \]

Kad su troškovi transakcija modelirani na način koji se može izraziti konveksno (ili se problem reformulira), dobiva se konveksni optimizacijski problem koji se može rješavati učinkovito.

Lobo i sur. (2007) daju formulaciju i rješenja za portfelj s linearnim i fiksnim transakcijskim troškovima, naglašavajući kako se problem može postaviti tako da bude numerički rješiv standardnim metodama konveksne optimizacije (Lobo et al., 2007).

2) Portfelj s kvadratnim troškovima transakcija (teži modeli i drugačija struktura)

Kvadratni troškovi transakcija pojavljuju se kad trošak raste nelinearno s volumenom trgovanja (npr. učinci tržišnog utjecaja / market impact). Takvi troškovi:

čine penalizaciju “jačom” za velike promjene portfelja,
mijenjaju geometriju feasible skupa i optimuma,
zahtijevaju pažljiviji numerički tretman (osobito kad se kombiniraju s dodatnim ograničenjima).

Neka je \(u\) vektor promjena pozicija. Kvadratni trošak se često piše kao: \[ \text{TC}(u)= u^\top Q u \] ili komponentno: \[ \text{TC}(u)=\sum_i c_i u_i^2 \]

Cilj tada postaje “glatkiji”, ali se struktura ograničenja i trade-offa mijenja, pa optimizacija može biti zahtjevnija u praksi (ovisno o dodatnim uvjetima i mjeri rizika).

Chen, Lezmi, Roncalli i Xu eksplicitno raspravljaju kako kvadratni transakcijski troškovi čine problem drukčijim (i često “težim” za tretman) od slučaja linearnih troškova, te daju smjernice za formulaciju i rješavanje (Chen et al., 2019).

3) Optimal Power Flow (OPF) u elektroenergetici (klasičan NLP)

Optimalni tok snaga (engl. Optimal Power Flow, OPF) je temeljni problem elektroenergetike: treba odrediti proizvodnju, napone i tokove tako da:

se minimizira ukupni trošak proizvodnje ili gubici,
zadovolje fizikalni zakoni mreže (nelinearne AC jednadžbe),
poštuju ograničenja (naponi, struje, granice generatora, sigurnosni uvjeti).

U literaturi se često razlikuju dvije verzije modela:

AC-OPF (Alternating Current Optimal Power Flow): model temeljen na fizikalno točnim jednadžbama izmjenične struje (AC = alternating current = izmjenična struja). Ovaj je model tipično nelinearan, jer jednadžbe tokova snage uključuju trigonometrijske funkcije (sinus i kosinus) te umnoške napona i kutova.
DC-OPF (Direct Current Optimal Power Flow): pojednostavljena aproksimacija (DC = direct current = istosmjerna struja) koja linearizira dio odnosa. DC-OPF je često linearni ili kvadratni problem, ali je fizički grublja aproksimacija.

Ovdje je fokus na AC-OPF, jer predstavlja klasičan primjer nelinearnog programiranja.

Varijable (primjer): - naponi \(V\), kutovi \(\theta\), - proizvodnje \(P_G, Q_G\).

Ograničenja: - AC jednadžbe ravnoteže snage (nelinearne jednakosti), - granice napona i proizvodnje (nejednakosti).

Cilj: \[ \min \ \sum_{g} C_g(P_G) \] gdje je \(C_g\) često kvadratna funkcija troška proizvodnje.

Metode unutrašnje točke (engl. interior-point methods) se često koriste u ovakvim situacijama jer:

dobro se skaliraju na velike mreže,
prirodno rukuju velikim sustavima nelinearnih ograničenja,
dobro rade na glatkim (diferencijabilnim) problemima.
Wei i suradnici prikazuju interior-point NLP pristup za OPF, s naglaskom na formulaciju i računalnu učinkovitost.
Wei et al., 1998
Capitanescu i suradnici daju pregled interior-point pristupa za OPF i pozicioniraju ih kao standardni alat u rješavanju ovih problema.
Capitanescu et al., 2007

4) Robotika i planiranje putanje (dinamika + ograničenja ⇒ NLP / SCP / SQP)

U robotici se često optimira kretanje kroz vrijeme (putanja + vremenska parametrizacija) uz zahtjeve:

izbjegavanje prepreka,
dinamička ograničenja (maksimalna ubrzanja, brzine, sile),
sigurnosne margine,
neizvjesnost (senzorska i modelna), ponekad i probabilistička ograničenja (chance constraints).

Takvi problemi vrlo prirodno vode na NLP jer se pojavljuju nelinearne veze između stanja i upravljanja kroz jednadžbe gibanja i nelinearna ograničenja sigurnosti.

Diskretizirana putanja:

stanja \(x_t\), upravljanja \(u_t\), \(t=0,\dots,T\)

Cilj (primjer): \[ \min \ \sum_{t=0}^{T-1} \ell(x_t,u_t) + \ell_T(x_T) \] uz ograničenja:

dinamika \(x_{t+1}=f(x_t,u_t)\) (nelinearna jednakost),
ograničenja stanja i upravljanja,
izbjegavanje prepreka (često nelinearne nejednakosti).

U tom kontekstu često se pojavljuju sljedeće kratice:

NLP (Nonlinear Programming): nelinearno programiranje.
SCP (Sequential Convex Programming): sekvencijalno konveksno programiranje, tj. rješavanje niza konveksnih aproksimacija nelinearnog problema.
SQP (Sequential Quadratic Programming): sekvencijalno kvadratno programiranje; u svakoj iteraciji rješava se kvadratni podproblem koji aproksimira izvorni NLP.

Dodatno, u nekim radovima pojavljuju se chance constraints (probabilistička ograničenja), gdje se traži da se ograničenje zadovolji s visokom vjerojatnošću (npr. 95% ili 99%), što je važno u prisutnosti neizvjesnosti.

Nakka i Chung razvijaju pristup koji povezuje NLP s postupcima sekvencijalne konveksne optimizacije za planiranje pod neizvjesnošću (chance constraints), Nakka & Chung, 2023
Richter, De Marchi i Britzelmeier (IFAC) daju primjer trajektorijskog planiranja u dinamičkim okruženjima gdje je NLP prirodna jezgra metoda, Richter et al., 2025

5) Lanac opskrbe i dizajn mreža (često MINLP: lokacije/kapaciteti + nelinearni troškovi)

U lancima opskrbe često se istovremeno donose:

diskretne odluke: otvaranje lokacija, odabir tehnologije, aktivacija dobavljača (binarne varijable),
kontinuirane odluke: količine tokova, zalihe, proizvodnje, transporta,
nelinearnosti: penalizacije kašnjenja, ekonomija obujma, nelinearne funkcije troškova skladištenja i servisa, rizici, robustnost.

Kombinacija diskretnih i nelinearnih elemenata tipično vodi na mješovito-cjelobrojno nelinearno programiranje (MINLP).

Varijable:

\(y_j \in \{0,1\}\): otvara li se lokacija \(j\)
\(x_{ij}\ge 0\): tok između čvorova \(i \to j\)

Cilj: \[ \min \ \text{FixedCost}(y) + \text{Transport}(x) + \text{Inventory}(x) + \text{Penalty}(x) \] Ograničenja:

kapaciteti uvjetovani \(y\),
bilance tokova,
servisne razine,
nelinearne penalizacije ili troškovi.

Algoritamske implikacije

Često se kombiniraju heuristike/metaheuristike s lokalnim NLP korakom (“hybrid” pristupi).
Za MINLP: branch-and-bound / outer approximation / decomposition pristupi, ovisno o strukturi.
You i Grossmann daju MINLP modele i algoritme za dizajn velikih lanaca opskrbe uz stohastičko upravljanje zalihama You & Grossmann, 2008
Roy i Sana daju primjer optimizacije lanca opskrbe s nelinearnim penalizacijama (rani/kasni delivery), gdje nelinearni troškovni termini prirodno induciraju NLP formulaciju Roy & Sana, 2021

Izvor: DALL·E

Upravljanje lancem opskrbe: modeliranje i optimizacija složenih lanaca opskrbe uključuju nelinearne troškove, kapacitete proizvodnje i transportne ograničenja.
Financijsko modeliranje: nelinearne funkcije koriste se u modeliranju opcija i derivata, procjeni rizika, te u optimizaciji portfelja.
Optimizacija energetskih sistema: uključuje modeliranje distribucije električne energije, optimizaciju proizvodnje i potrošnje energije, gdje su odnosi često nelinearni.
Bioinformatika i farmaceutski razvoj: modeliranje bioloških procesa i interakcija lijekova, gdje nelinearni modeli mogu pomoći u razumijevanju kompleksnih biokemijskih procesa.
Optimizacija procesa kemijskog inženjerstva: procesi poput reaktorskog dizajna i procesiranja materijala često uključuju nelinearne odnose između varijabli poput temperature, tlaka i koncentracije.
Telekomunikacijsko mrežno planiranje: optimizacija protoka podataka i raspodjele resursa u telekomunikacijskim mrežama s nelinearnim ograničenjima.
Aerodinamički dizajn: modeliranje i optimizacija oblika letjelica i vozila, gdje su aerodinamička svojstva često opisana nelinearnim jednadžbama.
Robotika i automatizacija: nelinearno programiranje se koristi za optimizaciju putanja i kretanja robota u složenim okruženjima.
Ekološki modeli: modeliranje ekoloških sustava i procjena utjecaja promjena okoliša, gdje su interakcije između vrsta i ekosistema često nelinearne.
Urbanističko planiranje i razvoj: modeliranje i optimizacija prometnih tokova, urbanog razvoja i raspodjele resursa, gdje se često susreću nelinearni odnosi između različitih varijabli i ograničenja.

Što je zajedničko svim primjenama?

Bez obzira na domenu, ove primjene dijele isti obrazac:

modeliranje realnog procesa uvodi nelinearnost (fizika mreže, dinamika gibanja, dinamika tržišta, penalizacije),
ograničenja su ključna (sigurnost, kapaciteti, budžet, stabilnost),
izbor algoritma ovisi o:
- glatkoći (može li se funkcija derivirati),
- konveksnosti (lokalni vs globalni),
- tipu ograničenja (jednakosti/nejednakosti, diskretne odluke),
- skali problema (veliki sustavi ⇒ interior-point/SQP/dekompozicija).

Za teorijsku pozadinu i algoritamske temelje, korisne reference su:

Nocedal i Wright (2006) — Numerical Optimization
Wächter i Biegler (2006) — interior-point filter line-search

Algoritmi i kako ih odabrati

Za rješavanje nelinearnih programskih problema koriste se različite metode i algoritmi, ovisno o prirodi problema i vrsti ograničenja. Nekoliko najčešće korištenih metoda:

Metoda gradijentnog spusta (Gradient Descent): Koristi se za pronalaženje lokalnih minimuma funkcije cilja smanjujući se u smjeru negativnog gradijenta funkcije. Ova metoda je posebno popularna u strojnom učenju i optimizaciji.
Newtonova metoda (Newton’s Method): numerička tehnika za pronalaženje aproksimativnih korijena nelinearnih jednadžbi i za pronalaženje ekstrema (minimuma ili maksimuma) funkcija. Metoda koristi prvog i drugog derivata funkcije kako bi pronašla točku u kojoj je funkcija minimalna (ili maksimalna). Kvazi-Newtonova metoda (BFGS) dostupna je u paketu stats, naredba optim.
Karush-Kuhn-Tucker (KKT) uvjeti: Nije algoritam sam po sebi, ali KKT uvjeti su temeljni za rješavanje nelinearnih problema s ograničenjima. Oni daju neophodne uvjete za optimalno rješenje.
Sequential Quadratic Programming (SQP): Ova metoda aproksimira nelinearni problem serijom kvadratnih (drugog reda) problema, koji se onda rješavaju iterativno.
Interior Point Methods: Koriste se za probleme s ograničenjima, gdje se iterativno prilagođava granica optimizacije kako bi se pristupilo optimalnom rješenju iz “unutrašnjosti” dopuštenog prostora.
Branch and bound: Algoritam koristan za nelinearne probleme koji uključuju diskretne varijable, poput cijelobrojnog programiranja.
Conjugate Gradient Methods: Koristi se za velike probleme optimizacije, posebno one koji uključuju velike matrice. Dostupan je u paketu stats, naredba optim.
Genetski algoritmi i evolucijski algoritmi: Ovi algoritmi koriste koncepte iz prirodne selekcije i genetike, poput mutacije i križanja, za pronalaženje optimalnih rješenja. To su, na primjer crs2lm (Controlled Random Search), DIRECT (deterministic search algorithm), isres (Improved Stochastic Ranking Evolution Strategy) ili neldermead (Nelder-Mead simplex algorithm) u paketu nloptr.
Simulated annealing: Inspiriran procesom termičkog kaljenja, koristi slučajnu pretragu s kontroliranim hlađenjem kako bi se izbjeglo zaglavljivanje u lokalnim minimumima. Ova metoda (SANN) dostupna je u paketu stats, naredba optim.
Particle Swarm Optimization (PSO): Metaheuristički algoritam koji simulira socijalno ponašanje, poput jata ptica, za pronalaženje optimalnih rješenja.
Metode bez gradienta: poznate i kao metode bez derivacija ili derivative-free metode, su tehnike optimizacije koje pronalaze minimum (ili maksimum) funkcije cilja bez izračunavanja njenih derivata. Ove metode su posebno korisne kad su gradijenti funkcije cilja teško izračunljivi, nepouzdani, ili uopće nedostupni. Bezgradijentne metode često koriste alternativne pristupe za pretraživanje prostora rješenja.

Gruba taksonomija

Lokalni, gradijentni (glatki problemi)

Gradient descent, Newton, (L-)BFGS
Dobri kad je funkcija glatka i dimenzije velike (L-BFGS) (Nocedal & Wright, 2006).

Lokalni, s ograničenjima

SQP / SLSQP (jako dobar “default” za glatka ograničenja)
Interior-point (osnova IPOPT i velikih NLP sustava) (Wächter & Biegler, 2006).

Bezgradijentni

Nelder–Mead (bez eksplicitnih ograničenja), COBYLA (nejednakosti)
Nelder & Mead (1965), Singer & Nelder (2009).

Globalni / metaheuristike

DIRECT, CRS, ISRES, GA, PSO, simulated annealing
Dobri kad ima puno lokalnih optimuma ili je funkcija “crna kutija”.

Mini “cheat-sheet” za odabir

Glatko + samo granice (box): L-BFGS-B
Glatko + nelinearne nejednakosti: SLSQP ili interior-point
Bez derivacija + nejednakosti: COBYLA
Nekonveksno + puno lokalnih optimuma: globalni (DIRECT/ISRES/CRS) pa lokalni “polishing”

Metode rješavanja nelinearnih optimizacijskih problema – korak po korak

U nastavku se daje “proceduralni” prikaz glavnih metoda: što se računa u svakoj iteraciji, koje informacije su potrebne (funkcija, gradijent, Hessian), kako se biraju koraci i kako se provjerava zaustavljanje. Tekst je pisan kao tutorijal koji možete pratiti uz rješavanje zadataka i implementaciju u R-u.

Metoda gradijentnog spusta (Gradient Descent)

Kad se koristi

Metoda gradijentnog spusta je osnovna metoda za neograničenu (unconstrained) optimizaciju diferencijabilne funkcije. U praksi se često koristi i kao “unutarnji korak” drugih metoda te u strojnome učenju.

Što je potrebno

funkcija cilja \(f(x)\)
gradijent \(\nabla f(x)\) (analitički ili numerički)
početna točka \(x_0\)
pravilo za izbor koraka (stopa učenja) \(\alpha_k\)
kriterij zaustavljanja

Koraci

Korak 0 — inicijalizacija

Odabrati početnu točku \(x_0\).
Odabrati početnu stopu učenja \(\alpha_0>0\) (ili pravilo za \(\alpha_k\)).
Postaviti maksimalni broj iteracija \(K_{\max}\) i tolerancije (npr. \(\varepsilon_g,\varepsilon_x,\varepsilon_f\)).

Korak 1 — računanje gradijenta

Izračunati gradijent u trenutnoj točki: \[ g_k=\nabla f(x_k). \]

Korak 2 — odabir veličine koraka

Odabrati \(\alpha_k\).
- Konstanta: \(\alpha_k=\alpha\) (najjednostavnije, ali može oscilirati).
- Line search (pretraživanje koraka): pronaći \(\alpha_k\) tako da dovoljno smanji \(f\) (npr. Armijo uvjet).
- Opadajući korak: npr. \(\alpha_k=\frac{\alpha_0}{1+k}\) (stabilnije, ali često sporije).

Korak 3 — ažuriranje točke

Izračunati novu točku: \[ x_{k+1}=x_k-\alpha_k\,g_k. \]

Korak 4 — provjera zaustavljanja

Provjeriti kriterije zaustavljanja, npr.:

mali gradijent: \(\|g_k\|\le \varepsilon_g\),
mala promjena u varijablama: \(\|x_{k+1}-x_k\|\le \varepsilon_x\),
mala promjena funkcije: \(|f(x_{k+1})-f(x_k)|\le \varepsilon_f\),
ili \(k=K_{\max}\).

Ako kriterij nije zadovoljen, postaviti \(k \leftarrow k+1\) i vratiti se na Korak 1.

Tipične “pojave” u praksi

prevelik \(\alpha_k\) ⇒ preskakanje optimuma i oscilacije,
premalen \(\alpha_k\) ⇒ stabilno, ali sporo približavanje,
kondicioniranost (različite “strmine” u različitim smjerovima) ⇒ “cik-cak” putanja.

Newtonova metoda (Newton–Raphson u optimizaciji)

Kad se koristi

Newtonova metoda je metoda za neograničenu optimizaciju diferencijabilne funkcije koja koristi i informaciju o zakrivljenosti (Hessian). U blizini optimuma često konvergira vrlo brzo (kvadratna konvergencija), ali može biti osjetljiva na početnu točku.

Što je potrebno

funkcija \(f(x)\)
gradijent \(\nabla f(x)\)
Hessian \(H(x)=\nabla^2 f(x)\)
početna točka \(x_0\)
(preporučeno) line search ili damping parametar

Koraci

Korak 0 — inicijalizacija

Odabrati \(x_0\), \(K_{\max}\), tolerancije.

Korak 1 — računanje gradijenta i Hessiana

Izračunati: \[ g_k=\nabla f(x_k),\qquad H_k=\nabla^2 f(x_k). \]

Korak 2 — Newtonov smjer

Riješiti linearni sustav: \[ H_k p_k = -g_k \] za \(p_k\) (Newtonov smjer).

Napomena: u numerici se ne računa \(H_k^{-1}\) eksplicitno, nego se rješava sustav.

Korak 3 — odabir koraka (damping / line search)

Odabrati \(\alpha_k\in(0,1]\).
- “čisti” Newton: \(\alpha_k=1\),
- “damped” Newton: odabrati \(\alpha_k\) line searchom radi stabilnosti.

Korak 4 — ažuriranje

Ažurirati:

\[ x_{k+1}=x_k+\alpha_k p_k. \]

Korak 5 — provjera zaustavljanja

Kao i kod gradijentnog spusta, provjeriti \(\|g_k\|\), promjenu u \(x\), promjenu u \(f\), ili \(k=K_{\max}\).

Kad Newton “zapne”…

Hessian može biti nepozitivno definitan daleko od optimuma ⇒ smjer nije silazni.
Rješenje može “odletjeti” bez damping koraka. Zato se u praksi često koristi kvazi-Newton (npr. BFGS) ili Newton + line search.

SQP (Sequential Quadratic Programming) — za NLP s ograničenjima

Kad se koristi

SQP je standardna metoda za nelinearne probleme s ograničenjima (nejednakosti i jednakosti). Intuicija: u svakoj iteraciji rješava se kvadratni program (QP) koji lokalno aproksimira originalni problem.

Opći problem

\[ \min_x\ f(x)\quad \text{uz}\quad g(x)\le 0,\ h(x)=0. \]

Što je potrebno

\(f(x)\), \(\nabla f(x)\)
\(g(x)\), \(\nabla g(x)\)
\(h(x)\), \(\nabla h(x)\)
aproksimacija Hessiana Lagrangiana (ili točan Hessian)
početna točka \(x_0\) (po mogućnosti blizu izvedivog skupa)

Koraci

Korak 0 — inicijalizacija

Odabrati \(x_0\) i početne multiplikatore \((\lambda_0,\nu_0)\) (često inicijalno nule).
Postaviti inicijalnu aproksimaciju Hessiana Lagrangiana \(B_0\) (npr. identitet).

Korak 1 — lokalna aproksimacija (linearizacija ograničenja)

Linearizirati ograničenja oko \(x_k\): \[ g(x_k)+\nabla g(x_k)^\top d \le 0, \qquad h(x_k)+\nabla h(x_k)^\top d = 0. \]

Korak 2 — kvadratna aproksimacija cilja

Aproksimirati cilj kvadratno (Taylor do 2. reda):

\[ f(x_k+d)\approx f(x_k)+\nabla f(x_k)^\top d+\frac{1}{2} d^\top B_k d. \]

Korak 3 — rješavanje QP pod-problema

Riješiti QP:

\[ \min_d\ \nabla f(x_k)^\top d+\frac{1}{2} d^\top B_k d \] uz linearizirana ograničenja iz Koraka 1.

Dobiva se smjer \(d_k\) (i procjena multiplikatora iz QP-a).

Korak 4 — izbor koraka (line search / trust region)

Odabrati \(\alpha_k\) tako da se osigura napredak i očuva izvedivost (ili barem smanji kršenje). U praksi se često koristi:

line search nad merit funkcijom,
trust-region varijante.

Korak 5 — ažuriranje varijabli

Ažurirati:

\[ x_{k+1}=x_k+\alpha_k d_k. \]

Korak 6 — ažuriranje Hessiana Lagrangiana

Ažurirati \(B_k\) (npr. BFGS ažuriranjem) kako bi aproksimacija zakrivljenosti bila bolja.

Korak 7 — provjera zaustavljanja

Provjeriti kriterije:

KKT rezidual (stacionarnost + izvedivost),
mala promjena u \(x\),
mala promjena cilja,
ili \(k=K_{\max}\).

Interior-Point metode (metode unutrašnje točke) — “barijerni” pristup

Kad se koriste

Interior-point metode su vrlo učinkovite za velike probleme s ograničenjima. Često su “radni konj” u solverima za LP, QP i NLP.

Nejednakosti \(g(x)\le 0\) se pretvaraju u barijerni problem gdje se dodaje član koji “kažnjava” približavanje granici.

Što je potrebno

\(f(x)\), \(\nabla f(x)\), često i Hessian ili njegova aproksimacija
funkcije ograničenja i njihovi gradijenti
početna točka unutar izvedivog skupa (ili se koristi faza za nalaženje takve točke)
raspored smanjivanja barijernog parametra \(\mu\)

Koraci

Pretpostavimo ograničenja \(g_i(x)\le 0\) i da su uvedene slack varijable \(s_i>0\) tako da: \[ g_i(x)+s_i=0,\quad s_i>0. \]

Korak 0 — inicijalizacija

Odabrati početno \(x_0\) i \(s_0>0\) (strogo izvedivo: “unutrašnja” točka).
Odabrati početni barijerni parametar \(\mu_0>0\).

Korak 1 — formiranje barijernog problema

Rješavati slijed problema:

\[ \min_{x,s}\ f(x) - \mu \sum_i \ln(s_i) \] uz jednakosti \(g(x)+s=0\) i ostale jednakosti \(h(x)=0\).

Korak 2 — Newtonov korak za (perturbirane) KKT uvjete

Izvesti (primal-dual) Newtonov korak na sustavu uvjeta optimalnosti (KKT), gdje se pojavljuje \(\mu\) i uvjet \(s_i \lambda_i \approx \mu\).

Korak 3 — izbor koraka

Odabrati korak tako da \(s\) ostane pozitivan i da se reziduali smanjuju (line search).

Korak 4 — ažuriranje

Ažurirati \(x, s\) i multiplikatore.

Korak 5 — smanjivanje barijere

Smanjiti \(\mu\) (npr. \(\mu \leftarrow \tau \mu\), \(\tau\in(0,1)\)).

Korak 6 — provjera zaustavljanja

Zaustaviti kad su KKT reziduali mali i \(\mu\) dovoljno malo.

Bezgradijentne metode: izravna pretraga i metaheuristike (kad derivacije nisu dostupne)

Kad se koriste

Bezgradijentne metode koriste se kada:

gradijent nije dostupan (black-box),
funkcija nije glatka ili je šumovita,
evaluacija funkcije dolazi iz simulacije ili mjerenja.

U nastavku su precizno opisane dvije tipične skupine: (A) izravna pretraga i (B) metaheuristike.

Izravna pretraga (pattern search / koordinatna pretraga) — korak po korak

Ideja: u svakoj iteraciji evaluirati funkciju u nekoliko susjednih točaka; prihvatiti poboljšanje; ako ga nema, smanjiti korak.

Koraci:

Odabrati početnu točku \(x_0\) i početni korak \(\Delta_0\).
Definirati skup smjerova (npr. koordinatni: \(\pm e_i\)).
U iteraciji \(k\), ispitati kandidat točke: \[ x_k + \Delta_k d,\quad d\in D \]
Ako postoji kandidat s manjim \(f\), preći u najbolji kandidat: \[ x_{k+1}=\arg\min_{d\in D} f(x_k+\Delta_k d). \]
Ako nema poboljšanja, smanjiti korak: \[ \Delta_{k+1}=\gamma \Delta_k,\quad \gamma\in(0,1). \]
Zaustaviti kad je \(\Delta_k\) dovoljno mali ili kad nema promjene.

Nelder–Mead simplex (bez derivacija, za neograničene probleme)

Ideja: održava se simplex (u 2D trokut, u 3D tetraedar). U svakoj iteraciji simplex se transformira (refleksija/ekspanzija/kontrakcija/redukcija) tako da se “vuče” prema nižim vrijednostima funkcije.

Koraci:

Inicijalizirati simplex s \(n+1\) točaka \(x^{(1)},\dots,x^{(n+1)}\).
Evaluirati \(f\) u svim točkama.
Sortirati točke po vrijednosti \(f\): najbolja \(x_b\), najgora \(x_w\), druga najgora \(x_{sw}\).
Izračunati centroid svih točaka osim najgore: \[ \bar{x}=\frac{1}{n}\sum_{i\neq w} x^{(i)}. \]
Napraviti refleksiju najgore točke: \[ x_r=\bar{x}+\rho(\bar{x}-x_w). \]
Ako je refleksija vrlo dobra, pokušati ekspanziju: \[ x_e=\bar{x}+\chi(x_r-\bar{x}). \]
Ako refleksija nije dobra, napraviti kontrakciju (prema unutra): \[ x_c=\bar{x}+\beta(x_w-\bar{x}) \quad \text{(ili varijante)}. \]
Ako ni kontrakcija ne pomaže, napraviti redukciju simplexa prema najboljoj točki: \[ x^{(i)} \leftarrow x_b + \sigma(x^{(i)}-x_b). \]
Ponavljati dok simplex ne postane “mali” ili se \(f\) više ne poboljšava.

COBYLA (Constrained Optimization BY Linear Approximations) — korak po korak

Kad se koristi?

Za probleme s nejednakosnim ograničenjima, COBYLA u svakoj iteraciji gradi lokalne linearne aproksimacije cilja i ograničenja te rješava pomoćni problem unutar “trust region” radijusa.

Koraci:

Odabrati početnu točku \(x_0\) i početni radijus \(\Delta_0\).
Aproksimirati cilj i ograničenja linearnim modelom u okolini \(x_k\) (na temelju evaluacija funkcije).
Riješiti pomoćni problem:
- minimizirati linearni model cilja,
- uz linearna ograničenja,
- i uz ograničenje pomaka \(\|d\|\le \Delta_k\).
Dobiti kandidata \(x_k+d\) i evaluirati originalnu funkciju i ograničenja.
Ako kandidat poboljšava cilj i/ili izvedivost, prihvatiti ga; inače odbiti.
Prilagoditi \(\Delta_k\): povećati ako je model dobar, smanjiti ako je loš.
Zaustaviti kad je \(\Delta_k\) mali ili se napredak zaustavi.

SLSQP (Sequential Least Squares Programming) — praktična SQP varijanta

SLSQP je implementacija SQP logike koja u svakoj iteraciji rješava pod-problem u kojem se cilj kvadratno aproksimira, a ograničenja lineariziraju, uz dodatnu “least-squares” strukturu u rješavanju.

Koraci

Definirati:
- \(f(x)\) i (po mogućnosti) \(\nabla f(x)\),
- ograničenja \(g(x)\le 0\), \(h(x)=0\) i njihove Jacobiane (ili numeričke aproksimacije).
Odabrati početnu točku \(x_0\) (po mogućnosti izvedivu).
U svakoj iteraciji:
- linearizirati ograničenja oko \(x_k\),
- aproksimirati cilj kvadratno,
- riješiti QP pod-problem za smjer \(d_k\),
- provesti line search radi poboljšanja i stabilnosti,
- ažurirati \(x_{k+1}=x_k+\alpha_k d_k\).
Zaustaviti kad su KKT reziduali mali ili je promjena mala.

L-BFGS-B (ograničenja granica + kvazi-Newton)

Kad se koristi

Kad postoje ograničenja granica \(l \le x \le u\) i funkcija je glatka. Često se koristi za velike dimenzije jer ne pohranjuje puni Hessian.

Što je potrebno

\(f(x)\) i \(\nabla f(x)\) (ili numerički gradijent)
granice \(l,u\)
početna točka \(x_0\)

Koraci

Postaviti \(x_0\) unutar granica.
Izračunati gradijent \(g_k=\nabla f(x_k)\).
Konstruirati kvazi-Newton aproksimaciju inverza Hessiana korištenjem samo posljednjih \(m\) parova \((s_k, y_k)\) (limited memory).
Izračunati smjer pretraživanja \(p_k\) (kvazi-Newton smjer).
Primijeniti “projekciju” na granice (rad u aktivnom skupu granica).
Odabrati korak \(\alpha_k\) (line search) uz poštivanje granica.
Ažurirati \(x_{k+1}\).
Ponoviti dok je normirani gradijent (projekcijski) mali ili je promjena mala.

Sažetak: koja informacija je potrebna za koju metodu?

Gradijentni spust: \(f\), \(\nabla f\)
Newton: \(f\), \(\nabla f\), \(\nabla^2 f\)
SQP / SLSQP: \(f\), \(\nabla f\), ograničenja i njihove Jacobiane, Hessian Lagrangiana (ili aproksimacija)
Interior-point: isto kao SQP, uz barijerni parametar i primal-dual korake
Nelder–Mead / izravna pretraga: samo evaluacije \(f\) (bez derivacija)
COBYLA: evaluacije \(f\) i ograničenja (gradi linearne aproksimacije bez gradijenata)
L-BFGS-B: \(f\), \(\nabla f\), granice varijabli

Paketi u R-u

Paket nloptr i funkcija optim() u R-u nude različite algoritme za optimizaciju, a razlikuju se i po vrstama ograničenja koje svaki od njih može obraditi.

Algoritmi u nloptr:

Paket nloptr omogućuje širok spektar algoritama za optimizaciju, uključujući one koji podržavaju ograničenja nejednakosti i jednakosti. To čini nloptr fleksibilnijim za složenije probleme optimizacije koji uključuju ograničenja. Neki od algoritama dostupnih u nloptr su:

COBYLA (Constrained Optimization BY Linear Approximations): Podržava ograničenja nejednakosti.
SLSQP (Sequential Least Squares Programming): Podržava i ograničenja jednakosti i nejednakosti.
Nelder-Mead: Bezgradijentna metoda, ne podržava izravno ograničenja.
L-BFGS-B (Limited-memory Broyden-Fletcher-Goldfarb-Shanno Bounded): Podržava ograničenja granica (ograničene vrijednosti varijabli).
I druge metode koje uključuju različite vrste gradijentnih i bezgradijentnih pristupa.
Bezgradijentne metode (npr. Nelder-Mead, COBYLA): Ovi algoritmi su dobri za funkcije cilja gdje gradijenti nisu dostupni ili su skupi za izračun. Oni pretražuju prostor rješenja bez izračuna derivacija.
Gradijentne metode (npr. BFGS, SLSQP, L-BFGS): Ovi algoritmi su efikasniji za glatke funkcije cilja gdje su gradijenti lako dostupni i pouzdani.
Globalne optimizacijske metode (npr. stohastički algoritmi): Koriste se za funkcije cilja koje imaju više lokalnih minimuma, gdje je potrebno globalno pretraživanje prostora rješenja.

Algoritmi u optim():

Funkcija optim() u R-u je osnovnija u odnosu na nloptr i podržava manje vrsta ograničenja. Algoritmi dostupni u optim() uključuju:

Nelder-Mead: Bezgradijentna metoda, ne podržava izravno ograničenja.
L-BFGS-B: Podržava ograničenja granica.
BFGS: Gradijentna metoda bez podrške za ograničenja.
CG (Conjugate Gradient): Gradijentna metoda bez podrške za ograničenja.
SANN (Simulated Annealing): Heuristička metoda koja ne podržava izravno ograničenja.
Nelder-Mead: Bezgradijentna metoda koja je dobra za nesavršene funkcije cilja, ali može biti sporija i manje precizna za složene funkcije.
BFGS i L-BFGS-B: Gradijentne metode koje su efikasne za glatke funkcije cilja s dostupnim derivacijama. L-BFGS-B dodatno omogućava ograničenja na varijable.
CG (Conjugate Gradients): Pogodan za velike probleme s glatkim funkcijama cilja.
SANN (Simulated Annealing): Koristi se za globalnu optimizaciju, posebno kad postoji više lokalnih minimuma.

Glavne razlike:

Podrška za ograničenja: nloptr nudi veću fleksibilnost s više algoritama koji podržavaju različite vrste ograničenja (uključujući i nejednakosti i jednakosti), dok optim() ima ograničenije mogućnosti, uglavnom podržavajući ograničenja granica.
Vrste algoritama: nloptr uključuje specijalizirane algoritme koji su prilagođeni za složenije scenarije optimizacije, dok optim() pruža osnovniji set algoritama koji su dovoljni za mnoge standardne probleme optimizacije.
Složenost funkcija cilja: nloptr pruža veću fleksibilnost za različite vrste funkcija cilja, uključujući nesavršene i funkcije s mnogo lokalnih minimuma, dok optim() ima tendenciju biti bolji za glatke funkcije cilja.
Podrška za gradijente: nloptr nudi više algoritama koji mogu raditi bez derivacija, dok optim() uključuje nekoliko gradijentnih metoda koje su dobre za funkcije gdje su derivacije dostupne i pouzdane.
Prilagodljivost i napredne opcije: nloptr nudi naprednije opcije i veću kontrolu nad procesom optimizacije, što može biti korisno u složenijim problemima optimizacije.
U funkciji optim() u R-u, nema metode koja izravno podržava ograničenja nejednakosti. optim() primarno podržava neograničene probleme optimizacije, kao i probleme s ograničenjima granica (putem metode L-BFGS-B). Međutim, za složenije vrste ograničenja, uključujući ograničenja nejednakosti, optim() nije izravno opremljen.

Za složenije probleme optimizacije s više ograničenja, nloptr je obično bolji izbor, dok za jednostavnije probleme optimizacije bez ograničenja ili samo s ograničenjima granica, optim() može biti jednostavno i efikasno rješenje.

Primjeri

1. primjer

Profit od proizvoda A i B nije fiksan po jedinici, već opada kako se povećava količina proizvedenih proizvoda. Na primjer, profit po jedinici može biti veći za manje količine, ali se smanjuje kako se proizvodnja povećava zbog tržišnih zasićenja ili povećanih troškova proizvodnje.

Svaka jedinica proizvoda A zahtijeva 3 jedinice resursa R1 i \(2+0.1𝑥_𝐴\) jedinica resursa R2.
Svaka jedinica proizvoda B zahtijeva \(2+0.05𝑥_𝐵\) jedinica resursa R1 i 1 jedinicu resursa R2.
Dostupno je 60 jedinica resursa R1 i 40 jedinica resursa R2.
Profit po jedinici proizvoda A je \(50−0.2𝑥_𝐴\) eur, a za proizvod B \(40−0.1𝑥_𝐵\) eur.

Struktura problema:

Neka \(𝑥_𝐴\) označava količinu proizvoda A koju tvrtka proizvodi, a \(𝑥_𝐵\) količinu proizvoda B.

Funkcija cilja (maximiziranje profita): Max \(𝑍=(50−0.2𝑥_𝐴 ) 𝑥_𝐴+(40−0.1𝑥_𝐵 ) 𝑥_𝐵\)

Nelinearna ograničenja resursa:

Za resurs R1: \(3𝑥_𝐴+(2+0.05𝑥_𝐵 ) 𝑥_𝐵≤60\)

Za resurs R2: \((2+0.1𝑥_𝐴 ) 𝑥_𝐴+𝑥_𝐵≤40\)

Ne-negativnost:

\(𝑥_𝐴≥0\)

\(𝑥_𝐵≥0\)

Vizualizacija funkcija

Sljedeća vizualizacija funkcija i rješenja kreirana je uz pomoć paketa plotly koji omogućuje 3D vizualizaciju i interakciju s vizualnim prikazom. Prikaz možete rotirati kako biste bolje vidjeli plohe, presjeke i rješenje.

Ovdje je \(Z\) konkavna kvadratna funkcija, a \(g_1,g_2\) su konveksne (kvadratni članovi s pozitivnim koeficijentom u \(\le\) ograničenju). To je tip strukture gdje KKT često lijepo “radi”.

S obzirom da je funkcija nelinearna, ograničenja su nelinearna i ograničenja su nejednakosti, to sužava mogućnosti odabira algoritama pri rješavanju. Za početak, isprobat ćemo algoritam COBYLA.

Za korištenje ovog algoritma potrebno je pripremiti podatke:

Definirajte funkciju cilja koja prima vektor varijabli i vraća vrijednost koju treba minimizirati. Ako maksimizirate, pomnožite funkciju cilja s -1.
Definirajte ograničenja kao funkcije koje prihvaćaju vektor varijabli i vraćaju vrijednost koja mora biti manja ili jednaka nuli za ograničenja nejednakosti. COBYLA ne podržava ograničenja jednakosti.
Odredite početne vrijednosti za varijable optimizacije. Početne vrijednosti bi trebale biti unutar dopuštenog prostora rješenja.
Ako vaš problem uključuje ograničenja granica za varijable, definirajte ih. COBYLA podržava ograničenja granica.
Postavite opcije za nloptr funkciju, uključujući odabir algoritma (NLOPT_LN_COBYLA), postavljanje tolerancija, maksimalnog broja evaluacija i drugih parametara koji kontroliraju proces optimizacije.

# Instalirajte paket nloptr ako već nije instaliran
library(nloptr)

# Maksimizacija -> minimiziramo -Z
#Kreiramo funkciju objective_function, kojom definiramo funkciju cilja koju želimo maksimizirati (u ovom slučaju, koristimo negativnu vrijednost jer nloptr minimizira po defaultu).
objective_function <- function(x){
  xA <- x[1]
  xB <- x[2]
  -(50*xA - 0.2*xA^2 + 40*xB - 0.1*xB^2)
}  

# Definiramo ograničenja
# NLopt/ nloptr: nejednakosti su g(x) <= 0
#Funkcija constraints definira ograničenja.
constraints <- function(x){
  xA <- x[1]
  xB <- x[2]
  c(3*xA + (2 + 0.05*xB)*xB - 60,
    (2 + 0.1*xA)*xA + xB - 40)
}

# Početne vrijednosti: initial_values su početne pretpostavke za varijable.
initial_values <- c(1,1)

# Granice varijabli
#lower_bounds i upper_bounds definiraju granice varijabli.
lower_bounds <- c(0, 0)
upper_bounds <- c(Inf, Inf)


# nloptr se koristi za pronalaženje optimalnog rješenja s određenim algoritmom i postavkama.
# Primijenimp nloptr, "NLOPT_LN_COBYLA" algoritam

rezultat <- nloptr(x0 = initial_values,
                 eval_f = objective_function,
                 eval_g_ineq = constraints,
                 lb = lower_bounds,
                 ub = upper_bounds,
                 opts = list("algorithm" = "NLOPT_LN_COBYLA", "xtol_rel" = 1.0e-6))

rezultat

## 
## Call:
## 
## nloptr(x0 = initial_values, eval_f = objective_function, lb = lower_bounds, 
##     ub = upper_bounds, eval_g_ineq = constraints, opts = list(algorithm = "NLOPT_LN_COBYLA", 
##         xtol_rel = 1e-06))
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 41 
## Termination conditions:  xtol_rel: 1e-06 
## Number of inequality constraints:  2 
## Number of equality constraints:    0 
## Optimal value of objective function:  -925.624352315684 
## Optimal value of controls: 9.459952 12.13103

Rješenje nelinearnog programa koje smo dobili pomoću NLopt i metode NLOPT_LN_COBYLA može se protumačiti na sljedeći način:

Status rješavanja (Solver Status):
- NLOPT_XTOL_REACHED: Ovaj status ukazuje da je optimizacija zaustavljena jer je postignuta zadana tolerancija na promjene varijabli (xtol). To znači da se u posljednjim iteracijama varijable nisu znatno mijenjale, što obično ukazuje na to da je algoritam dostigao točku gdje daljnje iteracije ne donose značajna poboljšanja.
Broj iteracija:
- Algoritam je izvršio 41 iteraciju prije nego što je postigao uvjet za zaustavljanje.
Terminacijski uvjeti:
- xtol_rel: 1e-06: Ovaj uvjet označava relativnu toleranciju promjene u varijablama. Ako su promjene u varijablama između iteracija manje od ove vrijednosti, algoritam prestaje s radom. Postizanje ovog uvjeta ukazuje na to da je algoritam konvergirao prema rješenju.
Broj ograničenja:
- Postoji 2 ograničenja nejednakosti (inequality constraints) i nema ograničenja jednakosti (equality constraints).
Optimalna vrijednost funkcije cilja:
- -925.624352315684: Algoritam je pronašao minimum funkcije cilja, a ta vrijednost je približno -925.62. Ovo je vrijednost funkcije cilja za optimalne vrijednosti kontrolnih varijabli.
Optimalne vrijednosti kontrolnih varijabli:
- 9.459952 12.13103: Ovo su vrijednosti varijabli (kontrola) za koje je funkcija cilja minimizirana. U vašem slučaju, varijabla xA je oko 9.46, a xB oko 12.13.

Ukratko, rješenje ukazuje na to da je algoritam uspješno konvergirao prema optimalnom rješenju, gdje su vrijednosti varijabli približno 9.46 i 12.13, a vrijednost funkcije cilja je -925.62. Ovo bi trebalo biti optimalno rješenje vašeg nelinearnog programskog problema unutar zadanih ograničenja i tolerancije.

Ilustracija algoritamskog traženja rješenja i dijela područja dopustivih rješenja:

Isprobajmo još jednu metodu koja dobro funkcionira uz dana nelinearna ograničenja, SLSQP (numerički stabilniji, često i brži). Za potrebe ove metode bit će potrebno pripremiti podatke.

Funkcija cilja mora biti definirana tako da prihvaća vektor varijabli (npr., x) i vraća vrijednost koja treba biti minimizirana (ili maksimizirana). U slučaju maksimizacije, funkcija cilja se obično množi s -1 jer nloptr implicitno minimizira funkciju cilja.
SLSQP zahtijeva gradijent funkcije cilja. Gradijent može biti definiran analitički ili numerički. Ako nemate analitički izraz, možete koristiti paket kao što je numDeriv za numeričku aproksimaciju.
SLSQP može rukovati i ograničenjima jednakosti i ograničenjima nejednakosti. Ograničenja se definiraju kao funkcije koje prihvaćaju vektor varijabli i vraćaju vrijednost koja mora biti veća od (ili jednaka) nuli za ograničenja nejednakosti, ili jednaka nuli za ograničenja jednakosti.
Slično kao i za funkciju cilja, potrebno je pružiti gradijente za svako ograničenje. To može biti izvedeno analitički ili numerički.
Odredite početne vrijednosti za varijable optimizacije. Početne vrijednosti bi trebale biti unutar dopuštenog prostora rješenja.
Ako vaš problem uključuje ograničenja granica za varijable (npr., varijable moraju biti unutar određenih granica), trebate ih definirati.
Postavite opcije za nloptr funkciju, uključujući odabir algoritma (NLOPT_LD_SLSQP), postavljanje tolerancija, maksimalnog broja evaluacija i drugih parametara koji kontroliraju proces optimizacije.

objective_function <- function(x) {
  -((50 - 0.2 * x[1]) * x[1] + (40 - 0.1 * x[2]) * x[2])
}

# Definirajte ograničenja
constraint1 <- function(x) {
  3 * x[1] + (2 + 0.05 * x[2]) * x[2] - 60
}

constraint2 <- function(x) {
  (2 + 0.1 * x[1]) * x[1] + x[2] - 40
}

# Početne vrijednosti
initial_values <- c(1, 1)  # Početne vrijednosti
lower_bounds <- c(0, 0)    # Donje granice varijabli
upper_bounds <- c(Inf, Inf)  # Gornje granice varijabli


# Izračun gradijenta
library(numDeriv)

# funkcija gradijenta funkcije cilja
grad_function <- function(x) {
  grad(objective_function, x)
}

# funkcija gradijenta prvog ograničenja
grad_constraint1 <- function(x) {
  grad(constraint1, x)
}

# funkcija gradijenta drugog ograničenja
grad_constraint2 <- function(x) {
  grad(constraint2, x)
}

opts <- list("algorithm"="NLOPT_LD_SLSQP",  # Odabir algoritma
             "xtol_rel"=1e-6,               # Postavljanje tolerancije/ preciznosti
             "maxeval"=1000)                # najveći broj iteracija


result <- nloptr(x0 = initial_values,
                 eval_f = objective_function,
                 eval_grad_f = grad_function, # Pretpostavlja se da je ovo definirano
                 lb = lower_bounds,
                 ub = upper_bounds,
                 eval_g_ineq = function(x) {
                   c(constraint1(x), constraint2(x))
                 },
                 eval_jac_g_ineq = function(x) {
                   rbind(grad_constraint1(x), grad_constraint2(x))
                 },
                 opts = opts)
result

## 
## Call:
## 
## nloptr(x0 = initial_values, eval_f = objective_function, eval_grad_f = grad_function, 
##     lb = lower_bounds, ub = upper_bounds, eval_g_ineq = function(x) {
##         c(constraint1(x), constraint2(x))    }, eval_jac_g_ineq = function(x) {
##         rbind(grad_constraint1(x), grad_constraint2(x))    }, opts = opts)
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 5 
## Termination conditions:  xtol_rel: 1e-06 maxeval: 1000 
## Number of inequality constraints:  2 
## Number of equality constraints:    0 
## Optimal value of objective function:  -925.624350880851 
## Optimal value of controls: 9.459952 12.13103

Rješenje nelinearnog optimizacijskog problema koristeći SLSQP algoritam kroz nloptr paket u R-u može se interpretirati na sljedeći način:

Status rješavanja (Solver Status):

NLOPT_XTOL_REACHED: Optimizacija je zaustavljena jer je dostignuta zadana tolerancija na promjene u varijablama (xtol). Ovo ukazuje da su daljnje promjene u varijablama između iteracija postale dovoljno male, i smatra se da je algoritam konvergirao prema rješenju.

Broj iteracija:

Algoritam je izvršio samo 5 iteracija, što je relativno brzo. To može ukazivati na to da je početna točka bila već blizu optimalnom rješenju ili da algoritam efikasno napreduje prema rješenju.

Terminacijski uvjeti:

xtol_rel: 1e-06 i maxeval: 1000 ukazuju na to da je algoritam zaustavljen zbog zadovoljavanja relativne tolerancije na promjene u x, a ne zbog dostizanja maksimalnog broja evaluacija funkcije.

Ograničenja:

Algoritam je rukovao s 2 ograničenja nejednakosti (inequality constraints) i nema ograničenja jednakosti (equality constraints).

Optimalna vrijednost funkcije cilja:

-925.624350880851 je optimalna (maksimalna) vrijednost funkcije cilja. Negativan predznak proizlazi iz činjenice da nloptr minimizira funkciju cilja, a originalna funkcija cilja je maksimizirana (zbog negativnog znaka u definiciji).

Optimalne vrijednosti kontrolnih varijabli:

Najbolje vrijednosti varijabli su 9.459952 i 12.13103 za prvu i drugu varijablu, respektivno.

Ukratko, rješenje ukazuje na to da je algoritam efikasno pronašao rješenje koje maksimizira vašu funkciju cilja, uz poštivanje zadanih ograničenja. Vrijednosti 9.459952 i 12.13103 su optimalne vrijednosti varijabli koje postižu ovaj maksimum.

Provjera:

xA <- result$solution[1]
xB <- result$solution[2]

profit <- 50*xA - 0.2*xA^2 + 40*xB - 0.1*xB^2
ogr1 <- 3 * xA + (2 + 0.05 * xB) * xB - 60
ogr2 <- (2 + 0.1 * xA) * xA + xB - 40

list(solution = result$solution, profit = profit, constraint1 = ogr1, constraint2 = ogr2)

## $solution
## [1]  9.459952 12.131027
## 
## $profit
## [1] 925.6244
## 
## $constraint1
## [1] 2.689546e-10
## 
## $constraint2
## [1] 1.252495e-09

Vrijednosti 9.459952 za proizvod A i 12.13103 za proizvod B su optimalne vrijednosti koje maksimiziraju profit. Ovo rješenje ukazuje na optimalnu alokaciju ili razinu ovih varijabli. Optimalna vrijednost funkcije cilja iznosi 925.624350880851. Budući da je originalna funkcija cilja bila maksimizirana, a u procesu optimizacije je korištena njezina negativna vrijednost, ovaj rezultat ukazuje na maksimalnu ostvarivu vrijednost funkcije cilja. Funkcija cilja predstavlja profit, pa to znači da je maksimalni ostvarivi profit u modelu 925.624350880851 (uzimajući u obzir negativni predznak pri modeliranju i u rješenju).

S obzirom na to da je algoritam konvergirao u samo 5 iteracija, to sugerira da je algoritam bio učinkovit u pronalaženju optimalnog rješenja, što je korisno u situacijama gdje je vremenska efikasnost važna. Rješenje je pronađeno uzimajući u obzir ograničenja nejednakosti. To znači da su optimalne vrijednosti kontrolnih varijabli takve da zadovoljavaju sva postavljena ograničenja našeg problema.

Provjerite možete li problem riješiti koristeći još neki dostupan algoritam?

2. primjer

Pretpostavimo da ste vlasnik lanca trgovina koji prodaje dva proizvoda, A i B. Želite odabrati optimalni asortiman proizvoda za svaku trgovinu kako biste maksimizirali ukupnu dobit. Svaka trgovina ima ograničen prostor za skladištenje i ograničen kapacitet prodaje za svaki proizvod. Funkcija cilja je trošak i ima tendenciju opadanja za veću količinu proizvoda.

Trgovina A: Kapacitet skladišta je 500 proizvoda, kapacitet prodaje je 100 proizvoda po danu.
Trgovina B: Kapacitet skladišta je 800 proizvoda, kapacitet prodaje je 150 proizvoda po danu.

Za trgovinu A:

Trošak nabave proizvoda 1 za trgovinu A: \(10 \cdot x_{A,1}\)
Trošak nabave proizvoda 2 za trgovinu A: \(12 \cdot x_{A,2}\)
Trošak skladištenja proizvoda 1 za trgovinu A: \(0.1 \cdot x_{A,1}\)
Trošak skladištenja proizvoda 2 za trgovinu A: \(0.15 \cdot x_{A,2}\)

Za trgovinu B:

Trošak nabave proizvoda 1 za trgovinu B: \(10 \cdot x_{B,1}\)
Trošak nabave proizvoda 2 za trgovinu B: \(12 \cdot x_{B,2}\)
Trošak skladištenja proizvoda 1 za trgovinu B: \(0.1 \cdot x_{B,1}\)
Trošak skladištenja proizvoda 2 za trgovinu B: \(0.15 \cdot x_{B,2}\)

Nelinearna komponenta koja odražava tendenciju opadanja troškova može se definirati kao kvadratna funkcija. Na primjer, možemo koristiti sljedeće nelinearne funkcije:

Troškovi nabave i skladištenja za tvornicu A u suradnji s nabavom iz tvornice B:

Troškovi nabave i skladištenja opadaju za svaku dodatnu jedinicu proizvoda 1, kao i kombinaciju oba proizvoda: \(-0.001 \cdot (x_{A,1})^2 - 0.0015 \cdot x_{B,1} \cdot x_{B,2}\)
Troškovi nabave i skladištenja opadaju za svaku dodatnu jedinicu proizvoda 2, kao i kombinaciju oba proizvoda: \(-0.002 \cdot (x_{A,2})^2- 0.0022 \cdot x_{B,1} \cdot x_{B,2}\)

Troškovi nabave i skladištenja za tvornicu B u suradnji s nabavom iz tvornice A:

Troškovi nabave i skladištenja opadaju za svaku dodatnu jedinicu proizvoda 1, kao i kombinaciju oba proizvoda: \(0.001 \cdot (x_{B,1})^2- 0.0008 \cdot x_{A,1} \cdot x_{A,2}\)
Troškovi nabave i skladištenja opadaju za svaku dodatnu jedinicu proizvoda 2, kao i kombinaciju oba proizvoda: \(0.002 \cdot (x_{B,2})^2- 0.001 \cdot x_{A,1} \cdot x_{A,2}\)

Cilj je pronaći broj proizvoda svake vrste koji se naručuju za svaku trgovinu kako biste minimizirali ukupan trošak. Istražite mogućnosti rješavanja različitim algoritmima i usporedite rješenja.

## 
## Call:
## 
## nloptr(x0 = initial_values, eval_f = objective_function, lb = lower_bounds, 
##     ub = upper_bounds, opts = opts)
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 6236 
## Termination conditions:  xtol_rel: 1e-06 maxeval: 1e+05 
## Number of inequality constraints:  0 
## Number of equality constraints:    0 
## Optimal value of objective function:  5562.5 
## Optimal value of controls: 100 100 150 150

3. primjer

Pretpostavimo da ste vlasnik lanca trgovina računalnom opremom i da prodajete dva proizvoda, računala (označena kao A) i monitori (označeni kao B). Želite odabrati optimalni asortiman proizvoda za svaku trgovinu kako biste maksimizirali ukupnu dobit. Svaka trgovina ima ograničen kapacitet skladišta i ograničen kapacitet prodaje za svaki proizvod. Funkcija cilja je trošak i ima tendenciju opadanja za veću količinu proizvoda.

Podaci za trgovinu A:

Kapacitet skladišta za računala (A) je 200 jedinica.
Kapacitet skladišta za monitore (B) je 300 jedinica.
Kapacitet prodaje za računala (A) je 50 jedinica dnevno.
Kapacitet prodaje za monitore (B) je 80 jedinica dnevno.

Podaci za trgovinu B:

Kapacitet skladišta za računala (A) je 400 jedinica.
Kapacitet skladišta za monitore (B) je 600 jedinica.
Kapacitet prodaje za računala (A) je 70 jedinica dnevno.
Kapacitet prodaje za monitore (B) je 100 jedinica dnevno.

Osim toga, troškovi nabave i skladištenja za proizvode A i B mogu se izraziti na sljedeći način:

Za trgovinu A:

Trošak nabave računala (A) za trgovinu A: \(800 \cdot x_{A,1}\)
Trošak nabave monitora (B) za trgovinu A: \(600 \cdot x_{A,2}\)
Trošak skladištenja računala (A) za trgovinu A: \(0.2 \cdot x_{A,1}\)
Trošak skladištenja monitora (B) za trgovinu A: \(0.25 \cdot x_{A,2}\)

Za trgovinu B:

Trošak nabave računala (A) za trgovinu B: \(750 \cdot x_{B,1}\)
Trošak nabave monitora (B) za trgovinu B: \(550 \cdot x_{B,2}\)
Trošak skladištenja računala (A) za trgovinu B: \(0.15 \cdot x_{B,1}\)
Trošak skladištenja monitora (B) za trgovinu B: \(0.2 \cdot x_{B,2}\)

Za trgovinu A:

Troškovi nabave i skladištenja opadaju za svaku dodatnu jedinicu računala (A): \(-0.0032 \cdot (x_{A,1})^2\)
Troškovi nabave i skladištenja opadaju za svaku dodatnu jedinicu monitora (B): \(-0.0023 \cdot (x_{A,2})^2\)

Za trgovinu B:

Troškovi nabave i skladištenja opadaju za svaku dodatnu jedinicu računala (A): \(-0.0021 \cdot (x_{B,1})^2\)
Troškovi nabave i skladištenja opadaju za svaku dodatnu jedinicu monitora (B): \(-0.0012 \cdot (x_{B,2})^2\)

Istražite mogućnosti rješavanja različitim algoritmima i usporedite rješenja.

## 
## Call:
## 
## nloptr(x0 = initial_values, eval_f = objective_function, lb = lower_bounds, 
##     ub = upper_bounds, opts = opts)
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 106 
## Termination conditions:  xtol_rel: 1e-06 maxeval: 10000 
## Number of inequality constraints:  0 
## Number of equality constraints:    0 
## Optimal value of objective function:  195515.49 
## Optimal value of controls: 50 80 70 100

4. primjer

Podaci za trgovinu A:

Kapacitet skladišta računala (A) i monitore (B) je najviše 400 jedinica.

Podaci za trgovinu B:

Kapacitet skladišta računala (A) i monitore (B) je najviše 600 jedinica.

Potrebno je osigurati barem 100 jedinica računala i 50 jedinica monitora u trgovini A dnevno, dok u trgovini B treba osigurati barem 150 računala i 100 monitora.

Osim toga, troškovi nabave i skladištenja za proizvode A i B mogu se izraziti na sljedeći način:

Za trgovinu A:

Trošak nabave računala (A) za trgovinu A: \(800 \cdot x_{A,1}\)
Trošak nabave monitora (B) za trgovinu A: \(600 \cdot x_{A,2}\)
Trošak skladištenja računala (A) za trgovinu A: \(0.2 \cdot x_{A,1}\)
Trošak skladištenja monitora (B) za trgovinu A: \(0.25 \cdot x_{A,2}\)
no, ako se računala i monitori nabavljaju zajedno, tada se trošak nabave umanjuje za \(0.5 \cdot x_{A,1} \cdot x_{A,2}\)
odnosno, ako se skladište zajedno, tada se trošak skladištenja umanjuje za \(0.3 \cdot x_{A,1} \cdot x_{A,2}\)

Za trgovinu B:

Trošak nabave računala (A) za trgovinu B: \(750 \cdot x_{B,1}\)
Trošak nabave monitora (B) za trgovinu B: \(550 \cdot x_{B,2}\)
Trošak skladištenja računala (A) za trgovinu B: \(0.15 \cdot x_{B,1}\)
Trošak skladištenja monitora (B) za trgovinu B: \(0.2 \cdot x_{B,2}\)
no, ako se računala i monitori nabavljaju zajedno, tada se trošak nabave umanjuje za \(0.4 \cdot x_{B,1} \cdot x_{B,2}\)
odnosno, ako se skladište zajedno, tada se trošak skladištenja umanjuje za \(0.3 \cdot x_{B,1} \cdot x_{B,2}\)

Pretpostavimo da postoji ograničenje vezano uz kombinirani volumen ili težinu proizvoda koje možete skladištiti, a koje raste nelinearno s količinom proizvoda. Na primjer, može postojati veći trošak ili tehnička složenost kada se povećava broj različitih vrsta proizvoda u skladištu. Ovo bi se moglo modelirati kao nelinearno ograničenje:

Za trgovinu A: \(x_{A,1}^2 + x_{A,2}^2 ≤ 160000\)
Za trgovinu B: \(x_{B,1}^2 + x_{B,2}^2 ≤ 360000\)

## 
## Call:
## 
## nloptr(x0 = initial_values, eval_f = objective_function, lb = lower_bounds, 
##     ub = upper_bounds, eval_g_ineq = constraints, opts = opts)
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 224 
## Termination conditions:  xtol_rel: 1e-06 maxeval: 1e+05 
## Number of inequality constraints:  4 
## Number of equality constraints:    0 
## Optimal value of objective function:  263075.000000026 
## Optimal value of controls: 100 50 150 100

5. primjer

Mnoge web aplikacije (npr. web shop, LMS sustav ili aplikacija za naručivanje) sastoje se od više mikroservisa. Mikroservis je “mala” aplikacija koja obavlja jednu ulogu (npr. autentifikacija, katalog proizvoda, plaćanje).

U cloud okruženju broj instanci mikroservisa može se automatski povećavati ili smanjivati (autoscaling). Ideja je jednostavna: u vršnom opterećenju sustav pokreće više instanci kako bi se zahtjevi brže obrađivali; kada opterećenje padne, broj instanci se smanjuje radi uštede.

Međutim, autoscaling ima kompromis:

više instanci smanjuje prosječnu latenciju, ali povećava trošak,
nakon određene točke dodatne instance imaju sve manji učinak (tzv. diminishing returns),
moguće je i ograničenje budžeta ili resursa (npr. maksimalan broj instanci ili maksimalna CPU kvota).

Pretpostavimo da se u vršnom satu može odabrati “intenzitet skaliranja” \(x\) (kontinuirani ekvivalent broja instanci) i CPU kvota po instanci \(y\).

\(x \ge 0\): ekvivalent broja instanci (npr. 0 do 20)
\(y \ge 0\): CPU kvota po instanci (npr. 0 do 4 vCPU)

Minimizira se kombinacija procijenjene latencije i mjesečnog troška:

\[ \min_{x,y}\; f(x,y)= \underbrace{\frac{120}{x+1}}_{\text{latencijski dio}} + \underbrace{4y^2}_{\text{penal prevelike CPU kvote}} + \underbrace{6x}_{\text{trošak instanci}} \]

izraz \(\frac{120}{x+1}\) modelira da latencija opada s većim \(x\), ali sve sporije,
\(4y^2\) modelira da agresivno povećavanje CPU-a postaje sve skuplje,
\(6x\) je linearni trošak instanci.

resursni limit (ukupno CPU opterećenje u klasteru): \[ x\cdot y \le 30 \]
gornje granice (administrativni limit): \[ 0 \le x \le 20,\quad 0 \le y \le 4 \]

## 
## Call:
## nloptr(x0 = x0, eval_f = obj_1, lb = c(0, 0), ub = c(20, 4), 
##     eval_g_ineq = g_ineq_1, opts = list(algorithm = "NLOPT_LN_COBYLA", 
##         xtol_rel = 1e-08, maxeval = 5000))
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 89 
## Termination conditions:  xtol_rel: 1e-08 maxeval: 5000 
## Number of inequality constraints:  1 
## Number of equality constraints:    0 
## Optimal value of objective function:  47.665631459995 
## Optimal value of controls: 3.472136 1.174125e-24

6. primjer

API gateway je komponenta koja stoji “ispred” servisa i upravlja prometom (autentifikacija, logging, throttling). Jedna standardna tehnika zaštite i stabilnosti je rate limiting: ograničavanje broja zahtjeva u sekundi po korisniku ili po IP adresi.

Ako je limit prenizak:

legitimni korisnici dobivaju greške (429 Too Many Requests),
korisničko iskustvo pada, a time i prihod.

Ako je limit previsok:

sustav je osjetljiviji na napade (DDoS),
ili će se preopteretiti i padati.

Cilj je pronaći limit koji balansira rizik i korisničko iskustvo.

Neka su varijable:

\(r\): limit zahtjeva po sekundi (req/s), \(1 \le r \le 50\)
\(b\): “burst” dopuštenje (koliko se može kratko probiti limit), \(0 \le b \le 20\)

\[ \min_{r,b}\; f(r,b)= \underbrace{\frac{200}{r+5}}_{\text{manje blokiranja pri većem }r} + \underbrace{0.5(r-20)^2}_{\text{preferencija oko }r\approx 20} + \underbrace{0.8b^2}_{\text{penal prevelikog burst-a}} \]

\(\frac{200}{r+5}\) pada s \(r\): veći limit smanjuje “frikciju”,
\((r-20)^2\) izražava da je oko 20 req/s “operativno poželjna” zona (npr. kapacitet backend-a),
\(b^2\) penalizira prevelike burst-ove.

Nadalje, burst povećava efektivni vršni promet, pa se mora držati pod kontrolom:

\[ r + 2b \le 55 \]

## 
## Call:
## nloptr(x0 = x0, eval_f = obj_2, lb = c(1, 0), ub = c(50, 20), 
##     eval_g_ineq = g_ineq_2, opts = list(algorithm = "NLOPT_LN_COBYLA", 
##         xtol_rel = 1e-09, maxeval = 5000))
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 85 
## Termination conditions:  xtol_rel: 1e-09 maxeval: 5000 
## Number of inequality constraints:  1 
## Number of equality constraints:    0 
## Optimal value of objective function:  7.95006263228178 
## Optimal value of controls: 20.31216 1.887411e-40

7. primjer

Sustavi detekcije upada (IDS) često rade tako da računaju neku “sumnjivost” prometa (skor). Ako je skor veći od praga \(\tau\), događaj se označi kao sumnjiv.

prenizak prag → puno lažnih alarma (tim troši vrijeme),
previsok prag → propuštaju se stvarni napadi.

U praksi se prag kalibrira na temelju povijesnih podataka ili testiranja.

Varijabla: \(\tau \in [0,10]\)

Pretpostavimo aproksimacije (glatke funkcije) za:

očekivani broj lažnih alarma u satu:
\[ FP(\tau)= 100\,e^{-0.6\tau} \]
očekivani broj propuštenih napada u satu: \[ FN(\tau)= 2 + 0.3\tau^2 \]

\[ \min_{\tau}\; f(\tau)= 1\cdot FP(\tau) + 40\cdot FN(\tau) \]

Lažni alarmi su “jeftiniji” od propuštenih napada, pa je težina za \(FN\) veća.

Pretpostavimo da detekcija raste s nižim pragom, modelirano kao: \[ TPR(\tau)= 1 - e^{-0.7(10-\tau)} \] i zahtijeva se: \[ TPR(\tau)\ge 0.95 \]

## 
## Call:
## nloptr(x0 = x0, eval_f = obj_3, lb = 0, ub = 10, eval_g_ineq = g_ineq_3, 
##     opts = list(algorithm = "NLOPT_LN_COBYLA", xtol_rel = 1e-10, 
##         maxeval = 5000))
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 42 
## Termination conditions:  xtol_rel: 1e-10 maxeval: 5000 
## Number of inequality constraints:  1 
## Number of equality constraints:    0 
## Optimal value of objective function:  145.953247541023 
## Optimal value of controls: 1.209769

8. primjer

U bežičnim mrežama (LTE/5G) signal s jedne bazne stanice može smetati drugoj. Veća snaga povećava kvalitetu signala vlastitim korisnicima, ali povećava interferenciju susjedima.

Kako bi problem bio rješiv, uzima se pojednostavljeni model: dvije stanice koje dijele frekvencijski resurs.

Varijable: \(p_1, p_2 \in [0,10]\) (snage)

Pretpostavimo korisnost (throughput proxy) po stanici: \[ U_1(p_1,p_2)=\log(1+\frac{3p_1}{1+0.8p_2}),\quad U_2(p_1,p_2)=\log(1+\frac{2.5p_2}{1+0.6p_1}) \]

Želi se maksimizirati ukupna korisnost uz penal potrošnje energije. Piše se kao minimizacija:

\[ \min_{p_1,p_2}\; f(p_1,p_2)= -\left(U_1(p_1,p_2)+U_2(p_1,p_2)\right) +0.05(p_1^2+p_2^2) \]

\(0 \le p_1 \le 10\),
\(0 \le p_2 \le 10\)
ukupno ograničenje energije: \[ p_1+p_2 \le 12 \]

## 
## Call:
## nloptr(x0 = x0, eval_f = obj_4, lb = c(0, 0), ub = c(10, 10), 
##     eval_g_ineq = g_ineq_4, opts = list(algorithm = "NLOPT_LN_COBYLA", 
##         xtol_rel = 1e-09, maxeval = 8000))
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 85 
## Termination conditions:  xtol_rel: 1e-09 maxeval: 8000 
## Number of inequality constraints:  1 
## Number of equality constraints:    0 
## Optimal value of objective function:  -1.99841686877371 
## Optimal value of controls: 1.938071 1.558071

9. primjer

U elektroenergetici operator mora odrediti koliko svaki generator proizvodi kako bi:

ukupna proizvodnja pokrila potrošnju,
generatori ostali unutar svojih granica,
trošak proizvodnje bio minimalan.

Puni AC-OPF je nelinearan i kompleksan. Za nastavu iz tog područja se često prvo uvede pojednostavljeni DC model koji je i dalje optimizacijski problem, ali lakši.

Dva generatora pokrivaju ukupnu potražnju \(D=100\) MW.

Varijable: \(P_1, P_2\) (snage generatora)

Trošak (konveksan kvadratni): \[ \min\; f(P_1,P_2)= 0.01P_1^2+2P_1 + 0.015P_2^2+1.5P_2 \]

Ograničenja: \[ P_1+P_2 = 100 \] \[ 20 \le P_1 \le 80,\quad 10 \le P_2 \le 90 \]

## 
## Call:
## nloptr(x0 = x0_5, eval_f = obj_5, eval_grad_f = grad_5, lb = c(20, 
##     10), ub = c(80, 90), eval_g_eq = g_eq_5, eval_jac_g_eq = jac_g_eq_5, 
##     opts = list(algorithm = "NLOPT_LD_SLSQP", xtol_rel = 1e-12, 
##         maxeval = 1000))
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 1 
## Termination conditions:  xtol_rel: 1e-12 maxeval: 1000 
## Number of inequality constraints:  0 
## Number of equality constraints:    1 
## Optimal value of objective function:  237.5 
## Optimal value of controls: 50 50

10. primjer

U robotici se često želi planirati putanju koja je:

dovoljno brza,
ali i glatka (izbjegava nagle promjene smjera/ubrzanja).

Ovdje se uzima planiranje putanje u 2D bez prepreka, s nekoliko “kontrolnih točaka”.

Robot ide od \((0,0)\) do \((10,0)\). Odabiru se dvije međutočke:

\((x_1,y_1)\), \((x_2,y_2)\)

Cilj: minimalna “duljina” putanje + penal zakrivljenosti (glatkoća):

\[ \min f= \left\|\begin{bmatrix}x_1\\y_1\end{bmatrix}-\begin{bmatrix}0\\0\end{bmatrix}\right\|^2 +\left\|\begin{bmatrix}x_2\\y_2\end{bmatrix}-\begin{bmatrix}x_1\\y_1\end{bmatrix}\right\|^2 +\left\|\begin{bmatrix}10\\0\end{bmatrix}-\begin{bmatrix}x_2\\y_2\end{bmatrix}\right\|^2 +0.2(y_1^2+y_2^2) \]

Ograničenja (npr. robot mora napredovati po x-osi i ostati u “koridoru”): \[ 0 \le x_1 \le x_2 \le 10 \] \[ -3 \le y_1 \le 3,\quad -3 \le y_2 \le 3 \]

obj_6 <- function(z){
  x1 <- z[1]
  y1 <- z[2]
  x2 <- z[3]
  y2 <- z[4]
  s1 <- (x1-0)^2 + (y1-0)^2
  s2 <- (x2-x1)^2 + (y2-y1)^2
  s3 <- (10-x2)^2 + (0-y2)^2
  s1 + s2 + s3 + 0.2*(y1^2 + y2^2)
}

g_ineq_6 <- function(z){
  x1 <- z[1]
  x2 <- z[3]
  c(x1 - x2)  # <= 0
}

x0_6 <- c(x1 = 3, y1 = 1, x2 = 7, y2 = -1)

res6 <- nloptr(
  x0 = x0_6,
  eval_f = obj_6,
  eval_g_ineq = g_ineq_6,
  lb = c(0, -3, 0, -3),
  ub = c(10, 3, 10, 3),
  opts = list(algorithm = "NLOPT_LN_COBYLA", xtol_rel = 1e-9, maxeval = 8000)
)

res6

## 
## Call:
## nloptr(x0 = x0_6, eval_f = obj_6, lb = c(0, -3, 0, -3), ub = c(10, 
##     3, 10, 3), eval_g_ineq = g_ineq_6, opts = list(algorithm = "NLOPT_LN_COBYLA", 
##     xtol_rel = 1e-09, maxeval = 8000))
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 169 
## Termination conditions:  xtol_rel: 1e-09 maxeval: 8000 
## Number of inequality constraints:  1 
## Number of equality constraints:    0 
## Optimal value of objective function:  33.3333333333334 
## Optimal value of controls: 3.333333 -1.455348e-07 6.666667 -1.210646e-07

11. primjer

Tvrtka proizvodi proizvod koji se skladišti. Trošak skladištenja nije uvijek linearan: kada se skladište puni, rastu troškovi (zagušenje, dodatni najam prostora, veći rizik kvarenja).

Za jednostavan model uzima se jedan period (jedan mjesec).

Varijable:

\(q\) = proizvedena količina (kom)
\(s\) = zaliha na kraju (kom)

Parametri:

potražnja \(d=500\)

Bilanca: \[ q - s = d \]

Trošak proizvodnje + nelinearni trošak skladištenja: \[ \min f(q,s)= 2q + 0.01q^2 + 0.05s^2 \]

Ograničenja: \[ 0 \le q \le 800,\quad 0 \le s \le 400 \]

## 
## Call:
## nloptr(x0 = x0_7, eval_f = obj_7, eval_grad_f = grad_7, lb = c(0, 
##     0), ub = c(800, 400), eval_g_eq = g_eq_7, eval_jac_g_eq = jac_g_eq_7, 
##     opts = list(algorithm = "NLOPT_LD_SLSQP", xtol_rel = 1e-12, 
##         maxeval = 1000))
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 5 
## Termination conditions:  xtol_rel: 1e-12 maxeval: 1000 
## Number of inequality constraints:  0 
## Number of equality constraints:    1 
## Optimal value of objective function:  3499.99999999981 
## Optimal value of controls: 500 0

12. primjer

U investicijskom portfelju se bira udio ulaganja u dvije imovine. Ako se portfelj “rebalansira”, plaćaju se transakcijski troškovi (provizije). Troškovi mogu biti aproksimirani kvadratno ili apsolutno. U nastavku se uzima glatka kvadratna aproksimacija radi jednostavnosti.

Varijable: \(w_1, w_2\) (udjeli), s uvjetom \(w_1+w_2=1\), \(w_i\ge 0\)

Početni portfelj: \(w_1^{(0)}=0.6\), \(w_2^{(0)}=0.4\)

Očekivani povrati: \(\mu_1=0.08\), \(\mu_2=0.05\)
Kovarijanca: \[ \Sigma=\begin{bmatrix} 0.10 & 0.02\\ 0.02 & 0.08 \end{bmatrix} \]

Cilj (minimizacija rizika – povrat + trošak transakcija): \[ \min f(w)= \gamma\, w^\top\Sigma w -\mu^\top w +\eta\left((w_1-0.6)^2+(w_2-0.4)^2\right) \] Uz npr. \(\gamma=2\), \(\eta=0.5\).

Ograničenja: \[ w_1+w_2=1,\quad 0\le w_1\le 1,\quad 0\le w_2\le 1 \]

gamma <- 2
eta <- 0.5
w0 <- c(0.6, 0.4)
mu <- c(0.08, 0.05)
Sigma <- matrix(c(0.10, 0.02,
                  0.02, 0.08), nrow = 2, byrow = TRUE)

obj_8 <- function(w){
  quad <- as.numeric(t(w) %*% Sigma %*% w)
  gamma*quad - sum(mu*w) + eta*sum((w - w0)^2)
}

grad_8 <- function(w){
  as.numeric(2*gamma*(Sigma %*% w) - mu + 2*eta*(w - w0))
}

g_eq_8 <- function(w){
  c(w[1] + w[2] - 1)
}

jac_g_eq_8 <- function(w){
  matrix(c(1, 1), nrow = 1)
}

x0_8 <- c(0.6, 0.4)
res8 <- nloptr(
  x0 = x0_8,
  eval_f = obj_8,
  eval_grad_f = grad_8,
  eval_g_eq = g_eq_8,
  eval_jac_g_eq = jac_g_eq_8,
  lb = c(0, 0),
  ub = c(1, 1),
  opts = list(algorithm = "NLOPT_LD_SLSQP", xtol_rel = 1e-12, maxeval = 1000)
)
res8

## 
## Call:
## nloptr(x0 = x0_8, eval_f = obj_8, eval_grad_f = grad_8, lb = c(0, 
##     0), ub = c(1, 1), eval_g_eq = g_eq_8, eval_jac_g_eq = jac_g_eq_8, 
##     opts = list(algorithm = "NLOPT_LD_SLSQP", xtol_rel = 1e-12, 
##         maxeval = 1000))
## 
## 
## Minimization using NLopt version 2.8.0 
## 
## NLopt solver status: 4 ( NLOPT_XTOL_REACHED: Optimization stopped because 
## xtol_rel or xtol_abs (above) was reached. )
## 
## Number of Iterations....: 15 
## Termination conditions:  xtol_rel: 1e-12 maxeval: 1000 
## Number of inequality constraints:  0 
## Number of equality constraints:    1 
## Optimal value of objective function:  0.04794921875 
## Optimal value of controls: 0.5742187 0.4257812

Pitanja za ponavljanje

Uputa: Za svako pitanje moguće je odabrati jedan ili više točnih odgovora.

1. pitanje

U mobilnoj mreži podešavaju se snage \(p_1,p_2\in[0,10]\). Ukupna korisnost je \[ U(p_1,p_2)=\log\!\left(1+\frac{3p_1}{1+0.8p_2}\right)+\log\!\left(1+\frac{2.5p_2}{1+0.6p_1}\right), \] a penal energije \(0.05(p_1^2+p_2^2)\). Postoji ograničenje \(p_1+p_2\le 12\). Cilj je maksimizirati \(U-\text{penal}\).

Koje tvrdnje su točne?

1. Problem je NLP jer se pojavljuju logaritmi i razlomci.
1. Problem je LP jer je ograničenje linearno.
1. Ciljna funkcija je glatka (diferencijabilna) na domeni \(p_i\ge 0\).
1. COBYLA je prikladan izbor ako se ne koriste derivacije.
1. SLSQP je prikladan izbor ako se mogu dati gradijenti ili koristiti numerički gradijenti.

2. pitanje

U portfelju se minimizira rizik \(w^\top\Sigma w\), a transakcijski trošak je \(\sum_i |w_i-w_i^{(0)}|\). Vrijedi \(w_1+w_2=1\) i \(w\ge 0\).

Koje tvrdnje su točne?

1. Cilj je neglađen (nondifferentiable) zbog \(|\cdot|\).
1. Problem je i dalje NLP, ali SLSQP može imati poteškoće jer pretpostavlja glatkoću.
1. Problem se može reformulirati u LP uvođenjem pomoćnih varijabli za apsolutne vrijednosti (ako se rizik izostavi).
1. Ako ostaje kvadratni rizik + \(|\cdot|\), dobiva se konveksan problem (često rješiv specijaliziranim konveksnim pristupima).
1. Nelder–Mead je dobar izbor jer podržava nejednakosti i jednakosti.

3. pitanje

Tvornica bira \(q\) i završnu zalihu \(s\). Bilanca: \(q-s=d\). Trošak je \(2q+0.01q^2+0.05s^2\). Granice: \(0\le q\le 800\), \(0\le s\le 400\).

Koje tvrdnje su točne?

1. Problem ima jednakosno ograničenje pa COBYLA nije dobar “default”.
1. SLSQP je tipično dobar izbor (jednakosti + glatko).
1. Ciljna funkcija je konveksna.
1. Zbog kvadratnih članova, problem je nužno nekonveksan.
1. Ako je problem konveksan, lokalni optimum je globalni.

4. pitanje

U cloudu se bira \(x\) = broj instanci i \(y\) = CPU kvota. Postoji ograničenje \(x\cdot y \le 30\), uz granice \(0\le x\le 20\), \(0\le y\le 4\). Cilj je glatka funkcija (npr. \(120/(x+1)+4y^2+6x\)).

Koje tvrdnje su točne?

1. Ograničenje \(x\cdot y\le 30\) čini problem nelinearnim.
1. SLSQP i COBYLA su oba moguća izbora, ovisno o dostupnosti derivacija.
1. To je LP jer su granice linearne.
1. Ako cilj uključuje \(1/(x+1)\), funkcija je glatka za \(x>-1\).
1. Ako se starta s “lošom” početnom točkom, algoritam nužno završava u različitim lokalnim optimumima.

5. pitanje

Kazna za kašnjenje je \(\max\{0, t - T\}\) i ulazi u cilj. Uz to postoje nelinearna ograničenja.

Koje tvrdnje su točne?

1. \(\max\{0,\cdot\}\) uvodi neglađenu točku.
1. COBYLA često može biti robusniji izbor od SLSQP kad je cilj neglađen.
1. Newtonova metoda je dobar izbor jer koristi Hessian.
1. Može se uvesti pomoćna varijabla \(u\ge 0\) i ograničenje \(u\ge t-T\) radi reformulacije.
1. Problem postaje linearni čim se uvede \(u\).

6. pitanje

Funkcija cilja se dobiva iz simulacije (npr. load test i mjerenje latency). Rezultat je šumovit: ista točka daje malo različite vrijednosti. Ograničenja su samo granice varijabli (box).

Koje tvrdnje su točne?

1. Bezgradijentne metode imaju smisla (npr. Nelder–Mead, CRS, ISRES).
1. BFGS je idealan jer pretpostavlja točne gradijente.
1. L-BFGS-B je moguć, ali numerički gradijent može biti nepouzdan zbog šuma.
1. Globalni algoritam može biti koristan ako postoji mnogo lokalnih optimuma.
1. Ovo je nužno LP.

7. pitanje

U dizajnu lanca opskrbe odlučuje se: otvoriti skladište (binarno \(y\in\{0,1\}\)) i količinu toka \(x\ge 0\). Trošak uključuje kvadratnu penalizaciju zagušenja \(0.01x^2\).

Koje tvrdnje su točne?

1. Ovo je MINLP (mješovito-cjelobrojni nelinearni problem).
1. Problem se ne rješava izravno nloptr-om bez dodatne “vanjske” logike jer nloptr ne podržava binarne varijable direktno.
1. Branch-and-bound / outer approximation su tipične ideje za takve probleme.
1. Problem je LP jer je \(y\) samo 0/1.
1. COBYLA je standardno rješenje za binarne varijable.

8. pitanje

Razmatra se minimizacija konveksne funkcije uz konveksna ograničenja. Netko tvrdi: “KKT uvjeti uvijek daju globalni optimum.”

Koje tvrdnje su točne?

1. Ako je problem konveksan i vrijedi regularnost (npr. Slater), KKT su nužni i dovoljni.
1. Za nekonveksne probleme KKT mogu opisivati lokalni optimum ili sedlo.
1. KKT se ne odnosi na probleme s ograničenjima.
1. Ako je funkcija cilja konkavna i minimizira se, problem je konveksan.
1. Ako su ograničenja linearna, skup izvedivih rješenja je konveksan.

9. pitanje

Profit po jedinici pada s količinom: \((50-0.2x_A)x_A + (40-0.1x_B)x_B\). Ograničenja resursa su nelinearna, npr. \(3x_A+(2+0.05x_B)x_B\le 60\).

Koje tvrdnje su točne?

1. Cilj je konkavna kvadratna funkcija (negativni kvadratni koeficijenti).
1. Maksimizacija konkavne funkcije može se tretirati kao konveksni optimizacijski problem (u smislu strukture).
1. Ograničenja s pozitivnim kvadratnim članovima u \(\le\) formi često su konveksna.
1. Problem je LP.
1. SLSQP ili interior-point su razumna opcija (ako su funkcije glatke).

10. pitanje

Netko želi koristiti COBYLA za problem s ograničenjem \(P_1+P_2=100\).

Koje tvrdnje su točne?

1. COBYLA ne podržava jednakosti direktno; potrebna je reformulacija ili uporaba SLSQP.
1. SLSQP je prirodniji izbor za jednakosti.
1. Ako se jednakost napiše kao \(P_1+P_2-100\le 0\), to je ekvivalentno originalu.
1. Ako se napiše kao \(|P_1+P_2-100|\le \epsilon\), dobiva se aproksimacija.
1. Newton je standardni izbor za ovakve probleme s ograničenjima.

11. pitanje

Podešava se 100 hiperparametara modela uz granice \(0\le x_i\le 1\). Cilj je glatka funkcija.

Koje tvrdnje su točne?

1. L-BFGS-B je tipičan izbor.
1. SLSQP je nužan jer postoje ograničenja.
1. Kod velikih dimenzija, “limited-memory” varijante (L-BFGS) imaju prednost nad punim BFGS.
1. Nelder–Mead je obično vrlo učinkovit u 100 dimenzija.
1. Problem je NLP (ne LP) ako cilj nije linearan.

12. pitanje

Pokrene se COBYLA iz 10 početnih točaka i dobiju se različita rješenja.

Koje tvrdnje su točne?

1. To može ukazivati na nekonveksnost i više lokalnih optimuma.
1. To može ukazivati na numeričku osjetljivost i loše skaliranje.
1. U konveksnom problemu očekuje se isto rješenje (ako solver konvergira).
1. To se ne može dogoditi u NLP.
1. Globalni algoritam (npr. DIRECT/ISRES) + lokalni “polishing” je čest pristup.

13. pitanje

U elektroenergetici se pojavljuju relacije tipa \[ P = V_iV_j(G\cos(\theta_i-\theta_j)+B\sin(\theta_i-\theta_j)). \]

Koje tvrdnje su točne?

1. Problem je nelinearan i tipično nekonveksan.
1. SLSQP / interior-point su tipični alati (u specijaliziranim solverima).
1. To se rješava simplex metodom za LP bez aproksimacija.
1. DC aproksimacija često linearizira problem.
1. Funkcije su neglađene zbog sinusa i kosinusa.

14. pitanje

Umjesto ograničenja \(x\cdot y\le 30\) u cilj se doda penal \(\rho\max\{0, xy-30\}^2\).

Koje tvrdnje su točne?

1. Ograničenje se zamjenjuje penaliziranim (unconstrained) problemom.
1. \(\max\) uvodi neglađenost na prijelomu, iako je penal kvadratni.
1. Ako \(\rho\) nije dovoljno velik, rješenje može kršiti originalno ograničenje.
1. Ovaj pristup može pomoći kad solver ne podržava ograničenja.
1. Time problem postaje LP.

15. pitanje

U SQP se u svakoj iteraciji rješava QP podproblem.

Koje tvrdnje su točne?

1. Ograničenja se lineariziraju oko trenutne točke.
1. Cilj se aproksimira kvadratno (Taylor 2. reda).
1. SQP se koristi samo za probleme bez ograničenja.
1. Za glatke probleme SQP je često vrlo učinkovit.
1. SQP traži KKT točke.

16. pitanje

Postoji nejednakost \(g(x)\le 0\), a početna točka ima \(g(x)>0\).

Koje tvrdnje su točne?

1. Neki solveri mogu krenuti iz neizvedive točke i iterativno smanjivati kršenje ograničenja.
1. Interior-point metode često preferiraju start unutar izvedivog skupa ili koriste “fazu I”.
1. Ako start nije izvediv, optimizacija je matematički nemoguća.
1. COBYLA često može krenuti iz neizvedivog starta jer radi s aproksimacijama ograničenja.
1. U LP-u je uvijek nužno krenuti iz izvedive točke, bez iznimke.

17. pitanje

Varijable su vrlo različitih redova veličine: neke su reda \(10^{-6}\), druge reda \(10^{6}\). Solver pokazuje nestabilno ponašanje.

Koje tvrdnje su točne?

1. To je problem skaliranja; normalizacija varijabli može pomoći.
1. To je znak da je problem LP.
1. Loše skaliranje može pogoršati numeričke gradijente.
1. Može pomoći podešavanje tolerancija i maxeval.
1. Skaliranje nikad ne utječe na optimizaciju.

18. pitanje

Ograničenje je \(x^2+y^2\le 1\).

Koje tvrdnje su točne?

1. Ovo opisuje disk i izvedivi skup je konveksan.
1. Ovo je linearno ograničenje.
1. Ovo je nelinearno, ali konveksno ograničenje.
1. Ako je cilj konveksan i minimizira se, dobiva se konveksni problem.
1. COBYLA ne može rješavati ovakav tip ograničenja.

19. pitanje

Želi se minimizirati latency i trošak. Cilj se definira kao \[ f=\alpha\cdot \text{latency} + (1-\alpha)\cdot \text{trošak}. \]

Koje tvrdnje su točne?

1. To je metoda ponderirane sume; daje jedno kompromisno rješenje za zadani \(\alpha\).
1. Promjenom \(\alpha\) mogu se dobiti različiti Pareto-kompromisi.
1. Time problem postaje LP.
1. Ako su latency i trošak nelinearni, i \(f\) je nelinearan.
1. Višekriterijski problemi se ne mogu rješavati NLP metodama.

20. pitanje

Koristi se SLSQP s numeričkim gradijentima (numDeriv::grad). Cilj uključuje if grananje (piecewise), npr. druga formula kad \(x>10\).

Koje tvrdnje su točne?

1. Numerički gradijenti mogu biti nestabilni na prijelomima (nediferencijabilnost).
1. To je uvijek bez problema jer grad() “sve rješava”.
1. COBYLA može biti sigurniji izbor ako se ne želi oslanjati na gradijente.
1. Ako je moguće, korisno je izgladiti prijelaz (npr. softplus) ili reformulirati.
1. Ako postoji if, problem je automatski linearan.

Literatura

Bertsekas, D. P. (2016). Nonlinear programming (3rd ed.). Athena Scientific. https://athenasc.com/nonlinbook.html

Capitanescu, F., Glavic, M., Ernst, D., & Wehenkel, L. (2007). Interior-point based algorithms for the solution of optimal power flow problems. Electric Power Systems Research, 77(5–6), 508–517. https://doi.org/10.1016/j.epsr.2006.05.003

Chen, P., Lezmi, E., Roncalli, T., & Xu, J. (2019). A note on portfolio optimization with quadratic transaction costs. SSRN. https://doi.org/10.2139/ssrn.3683466 (Preprint verzija: https://arxiv.org/abs/2001.01612 ; PDF: https://www.thierry-roncalli.com/download/Quadratic-Transaction-Costs.pdf)

Lobo, M. S., Fazel, M., & Boyd, S. (2007). Portfolio optimization with linear and fixed transaction costs. Annals of Operations Research, 152(1), 341–365. https://doi.org/10.1007/s10479-006-0145-1

Nakka, Y. K., & Chung, S.-J. (2023). Trajectory optimization of chance-constrained nonlinear stochastic systems for motion planning under uncertainty. IEEE Transactions on Robotics, 39(1), 203–222. https://doi.org/10.1109/TRO.2022.3197072

Nelder, J. A., & Mead, R. (1965). A simplex method for function minimization. The Computer Journal, 7(4), 308–313. https://doi.org/10.1093/comjnl/7.4.308

Nocedal, J., & Wright, S. J. (2006). Numerical optimization (2nd ed.). Springer. https://doi.org/10.1007/978-0-387-40065-5

Richter, R., De Marchi, E., & Britzelmeier, A. (2025). Dynamic and nonlinear programming for trajectory planning in moving environments. IFAC-PapersOnLine, 59(1), 265–270. https://doi.org/10.1016/j.ifacol.2025.03.046

Roy, M. D., & Sana, S. S. (2021). Optimizing a supply chain problem with nonlinear penalty costs for early and late delivery under generalized lead time distribution. Computers & Industrial Engineering, 160, 107536. https://doi.org/10.1016/j.cie.2021.107536

Singer, S., & Nelder, J. A. (2009). Nelder-Mead algorithm. Scholarpedia. https://www.scholarpedia.org/article/Nelder-Mead_algorithm

Wächter, A., & Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1), 25–57. https://doi.org/10.1007/s10107-004-0559-y

Wei, H., Sasaki, H., Kubokawa, J., & Yokoyama, R. (1998). An interior point nonlinear programming for optimal power flow problems with a novel data structure. IEEE Transactions on Power Systems, 13(3), 870–877. https://doi.org/10.1109/59.708745

You, F., & Grossmann, I. E. (2008). Mixed-integer nonlinear programming models and algorithms for large-scale supply chain design with stochastic inventory management. Industrial & Engineering Chemistry Research, 47(20), 7802–7817. https://doi.org/10.1021/ie800257x

Ključ rješenja

P1: A, C, D, E
P2: A, B, D
P3: A, B, C, E
P4: A, B, D
P5: A, B, D
P6: A, C, D
P7: A, B, C
P8: A, B, E
P9: A, B, C, E
P10: A, B, D
P11: A, C, E
P12: A, B, C, E
P13: A, B, D
P14: A, B, C, D
P15: A, B, D, E
P16: A, B, D
P17: A, C, D
P18: A, C, D
P19: A, B, D
P20: A, C, D

Nelinearno programiranje

Katarina Kostelić

Nelinearno programiranje (NLP)

Osnove NLP-a

Opći zapis

Gradijent i Hessian (intuicija)

Konveksnost i “lokalno = globalno”

KKT uvjeti

Ručni izračun - primjeri

Gradijentni spust (2 iteracije)

Jednostavna bezgradijentna metoda (koordinatna/ pattern search)

Primjene

Algoritmi i kako ih odabrati

Gruba taksonomija

Metode rješavanja nelinearnih optimizacijskih problema – korak po korak

Metoda gradijentnog spusta (Gradient Descent)

Newtonova metoda (Newton–Raphson u optimizaciji)

SQP (Sequential Quadratic Programming) — za NLP s ograničenjima

Interior-Point metode (metode unutrašnje točke) — “barijerni” pristup

Bezgradijentne metode: izravna pretraga i metaheuristike (kad derivacije nisu dostupne)

Izravna pretraga (pattern search / koordinatna pretraga) — korak po korak

Nelder–Mead simplex (bez derivacija, za neograničene probleme)

COBYLA (Constrained Optimization BY Linear Approximations) — korak po korak

SLSQP (Sequential Least Squares Programming) — praktična SQP varijanta

L-BFGS-B (ograničenja granica + kvazi-Newton)

Paketi u R-u

Primjeri

1. primjer

2. primjer

3. primjer

4. primjer

5. primjer

6. primjer

7. primjer

8. primjer

9. primjer

10. primjer

11. primjer

12. primjer

Pitanja za ponavljanje

Literatura

Ključ rješenja