Sok korlátlan optimalizálási algoritmus adaptálható a korlátozott esetre, gyakran büntetési módszer alkalmazásával. A nem korlátozott módszer által végzett keresési lépések azonban elfogadhatatlanok lehetnek a korlátozott problémára, ami a konvergencia hiányához vezet. Ezt nevezik Maratos-effektusnak.
Egyenlőségi korlátokSzerkesztés
Helyettesítési módszerSzerkesztés
Nagyon egyszerű problémákra, például két változó függvényére, amelyre egyetlen egyenlőségi korlát vonatkozik, a legpraktikusabb a helyettesítési módszer alkalmazása. Ennek lényege, hogy a kényszert behelyettesítjük a célfüggvénybe, hogy egy olyan összetett függvényt hozzunk létre, amely magában foglalja a kényszer hatását. Tegyük fel például, hogy a cél az f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y} maximalizálása.
feltétele x + y = 10 {\displaystyle x+y=10}
. A kényszerből következik, hogy y = 10 – x {\displaystyle y=10-x}
, amit a célfüggvénybe behelyettesítve megkapjuk p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}}
. Az elsőrendű szükséges feltétel szerint ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}
, ami megoldható x = 5-re {\displaystyle x=5}
és ebből következően y = 10 – 5 = 5 {\displaystyle y=10-5=5}
.
Lagrange-szorzóSzerkesztés
Ha a korlátos probléma csak egyenlőségi korlátokkal rendelkezik, a Lagrange-szorzók módszerével átalakítható korlátlan problémává, amelynek változóinak száma az eredeti változószám plusz az egyenlőségi korlátok eredeti száma. Alternatív megoldásként, ha a kényszerek mind egyenlőségi kényszerek és mind lineárisak, akkor néhány változóra megoldhatóak a többi változóval, és az előbbiek kiválthatók a célfüggvényből, így kisebb változószámú korlátlan probléma marad.
Egyenlőtlenségi korlátokSzerkesztés
Egyenlőtlenségi korlátok esetén a probléma jellemezhető a geometriai optimalitási feltételekkel, a Fritz John-feltételekkel és a Karush-Kuhn-Tucker-feltételekkel, amelyek mellett egyszerű problémák is megoldhatók.
Lineáris programozásSzerkesztés
Ha a célfüggvény és az összes kemény kényszer lineáris, és néhány kemény kényszer egyenlőtlenség, akkor a probléma lineáris programozási probléma. Ez megoldható a szimplex módszerrel, amely általában a probléma méretének polinomiális idejében működik, de nem garantáltan, vagy belső pont módszerekkel, amelyek garantáltan polinomiális időben működnek.
Nemlineáris programozásSzerkesztés
Ha a célfüggvény vagy néhány kényszer nemlineáris, és néhány kényszer egyenlőtlenség, akkor a probléma nemlineáris programozási probléma.
Kvadratikus programozásSzerkesztés
Ha az összes kemény kényszer lineáris, néhány pedig egyenlőtlenség, de a célfüggvény kvadratikus, akkor a probléma kvadratikus programozási probléma. Ez a nemlineáris programozás egyik típusa. Ez még polinomiális idő alatt megoldható az ellipszoid módszerrel, ha a célfüggvény konvex; ellenkező esetben a probléma NP nehéz lehet.
KKT-feltételekSzerkesztés
A nemlineáris programozás KKT-megközelítése az egyenlőtlenségi kényszerek megengedésével a Lagrange-szorzók módszerét általánosítja. Differenciálhatóság és konvexitás mellett alkalmazható.
Branch and boundSzerkesztés
A kényszeroptimalizálás megoldható branch-and-bound algoritmusokkal. Ezek olyan visszafelé haladó algoritmusok, amelyek a végrehajtás során talált legjobb megoldás költségét tárolják, és azt használják fel a keresés egy részének elkerülésére. Pontosabban, amikor az algoritmus olyan részmegoldással találkozik, amely nem bővíthető úgy, hogy a tárolt legjobb költségnél jobb költségű megoldást alkosson, az algoritmus visszalép, ahelyett, hogy megpróbálná ezt a megoldást bővíteni.
Föltételezve, hogy a költséget minimalizálni kell, ezen algoritmusok hatékonysága attól függ, hogyan értékelik a részmegoldás bővítésével elérhető költséget. Ha ugyanis az algoritmus egy részmegoldásból visszaléphet, akkor a keresés egy részét kihagyja. Minél alacsonyabb a becsült költség, annál jobb az algoritmus, mivel az alacsonyabb becsült költség nagyobb valószínűséggel alacsonyabb, mint az eddig talált legjobb megoldás költsége.
Másrészt ez a becsült költség nem lehet alacsonyabb, mint a megoldás kiterjesztésével elérhető tényleges költség, mivel különben az algoritmus visszaléphet, miközben létezik az eddig talált legjobb megoldásnál jobb megoldás. Ennek következtében az algoritmusnak szüksége van egy felső korlátra a részmegoldás kiterjesztésével elérhető költségre, és ennek a felső korlátnak a lehető legkisebbnek kell lennie.
A megközelítés egy változata, a Hansen-módszer intervallumos módszereket használ. Ez eredendően téglalap alakú kényszereket valósít meg.
Első választási korlátozó függvényekSzerkesztés
Egy részleges megoldásra vonatkozó felső korlát kiértékelésének egyik módja az, hogy minden egyes lágy kényszert külön-külön vizsgálunk. Minden egyes lágy kényszer esetében a ki nem rendelt változók bármely hozzárendelésének maximális lehetséges értékét feltételezzük. Ezeknek az értékeknek az összege egy felső korlát, mivel a lágy kényszer nem vehet fel ennél magasabb értéket. Azért pontos, mert a lágy kényszerek maximális értékei különböző értékelésekből származhatnak: egy lágy kényszer lehet maximális az x = a {\displaystyle x=a}
, míg egy másik kényszer maximális x = b {\displaystyle x=b} esetén.
.
Russian doll searchEdit
Ez a módszer egy branch-and-bound algoritmust futtat n {\displaystyle n}
problémán, ahol n {\displaystyle n}
a változók száma. Minden ilyen probléma az x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}} változók egy sorozatának elhagyásával kapott részprobléma.
az eredeti problémából, az őket tartalmazó kényszerekkel együtt. Az x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}} változókra vonatkozó probléma után {\displaystyle x_{i+1},\ldots ,x_{n}}
megoldottuk, annak optimális költsége felső korlátként használható a többi probléma megoldása során,
Igazából az x i + 1 , … , x n {\displaystyle x_{i+1}},\ldots ,x_{n}}}
mint nem hozzárendelt változókat, hozzáadódik ahhoz a költséghez, amely az értékelt változókból származik. Gyakorlatilag ez megfelel az értékelt változók figyelmen kívül hagyásának és a probléma megoldásának a ki nem rendelt változókon, kivéve, hogy az utóbbi probléma már megoldott. Pontosabban, a hozzárendelt és nem hozzárendelt változókat egyaránt tartalmazó lágy korlátozások költségét a fentiek szerint (vagy tetszőleges más módszerrel) becsüljük meg; a csak nem hozzárendelt változókat tartalmazó lágy korlátozások költségét ehelyett a megfelelő probléma optimális megoldása alapján becsüljük meg, amely ekkor már ismert.
A Russian Doll Search módszer és a dinamikus programozás között hasonlóság van. A dinamikus programozáshoz hasonlóan a Russian Doll Search is részproblémákat old meg a teljes probléma megoldása érdekében. De míg a Dinamikus programozásközvetlenül kombinálja az alproblémákon kapott eredményeket, hogy megkapja a teljes probléma eredményét, addig a Russian Doll Search csak korlátként használja azokat a keresés során.
Bucket eliminationEdit
A bucket elimination algoritmus adaptálható a korlátok optimalizálására. Egy adott változó valóban eltávolítható a problémából úgy, hogy az azt tartalmazó összes lágy kényszert egy új lágy kényszerrel helyettesítjük. Ennek az új kényszernek a költségét úgy számítjuk ki, hogy az eltávolított változó minden értékére maximális értéket feltételezünk. Formálisan, ha x {\displaystyle x}
az eltávolítandó változó, C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}}
az azt tartalmazó lágy korlátozások, és y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}}
a változóik, kivéve x {\displaystyle x}
, az új lágy kényszer a következőképpen definiált: C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}.
A vödörelimináció a változók (tetszőleges) rendezésével működik. Minden változóhoz tartozik egy vödörnyi kényszer; egy változó vödre tartalmazza az összes olyan kényszert, amelynek a változó a legmagasabb a sorrendjében. A vödörelimináció az utolsó változótól az elsőig halad. Minden egyes változó esetében a változó eltávolításához a vödör összes kényszerét a fentiek szerint kell kicserélni. Az így kapott kényszer ezután a megfelelő vödörbe kerül.