Mnoho neomezených optimalizačních algoritmů lze přizpůsobit omezenému případu, často pomocí sankční metody. Kroky hledání provedené neomezenou metodou však mohou být pro omezený problém nepřijatelné, což vede k nedostatečné konvergenci. To se označuje jako Maratosův efekt.
Rovnostní omezeníEdit
Substituční metodaEdit
Pro velmi jednoduché problémy, například funkci dvou proměnných podléhající jedinému rovnostnímu omezení, je nejpraktičtější použít substituční metodu. Podstatou je substituovat omezení do účelové funkce a vytvořit složenou funkci, která zahrnuje vliv omezení. Předpokládejme například, že cílem je maximalizovat f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}.
za podmínky x + y = 10 {\displaystyle x+y=10}
. Z omezení vyplývá, že y = 10 – x {\displaystyle y=10-x}
, což lze dosadit do účelové funkce a vytvořit p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}.
. Nutná podmínka prvního řádu dává ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\část p}{\část x}}=10-2x=0}
, což lze řešit pro x = 5 {\displaystyle x=5}
a následně y = 10 – 5 = 5 {\displaystyle y=10-5=5}.
.
Lagrangeův multiplikátorEdit
Pokud má omezený problém pouze rovnostní omezení, lze jej pomocí metody Lagrangeových multiplikátorů převést na neomezený problém, jehož počet proměnných je původní počet proměnných plus původní počet rovnostních omezení. Alternativně, pokud jsou všechna omezení rovnostní a všechna jsou lineární, lze je řešit pro některé proměnné v termínech ostatních a první z nich lze nahradit z účelové funkce, čímž vznikne neomezený problém v menším počtu proměnných.
Nerovnostní omezeníUpravit
S nerovnostními omezeními lze problém charakterizovat pomocí geometrických podmínek optimality, Fritzových Johnových podmínek a Karushových-Kuhn-Tuckerových podmínek, za kterých mohou být jednoduché problémy řešitelné.
Lineární programováníEdit
Je-li účelová funkce a všechna tvrdá omezení lineární a některá tvrdá omezení jsou nerovnosti, pak je problém problémem lineárního programování. Ten lze řešit simplexovou metodou, která obvykle pracuje v polynomiálním čase velikosti problému, ale není zaručeno, že bude, nebo metodami vnitřních bodů, které zaručeně pracují v polynomiálním čase.
Nelineární programováníEdit
Jsou-li účelová funkce nebo některá z omezení nelineární a některá omezení jsou nerovnosti, pak je problém problémem nelineárního programování.
Kvadratické programováníEdit
Jsou-li všechna tvrdá omezení lineární a některá jsou nerovnosti, ale účelová funkce je kvadratická, jedná se o problém kvadratického programování. Jedná se o jeden z typů nelineárního programování. Lze jej ještě řešit v polynomiálním čase metodou elipsoidů, pokud je účelová funkce konvexní; v opačném případě může být problém NP těžký.
KKT podmínkyUpravit
Připuštěním nerovnostních omezení zobecňuje KKT přístup k nelineárnímu programování metodu Lagrangeových multiplikátorů. Lze ji použít za podmínek diferencovatelnosti a konvexity.
Větvení a ohraničeníEdit
Optimalizaci s omezením lze řešit pomocí algoritmů větvení a ohraničení. Jedná se o backtrackingové algoritmy, které ukládají náklady na nejlepší řešení nalezené během provádění a používají je k vyhnutí se části hledání. Přesněji řečeno, kdykoli algoritmus narazí na dílčí řešení, které nelze rozšířit tak, aby vytvořilo řešení s lepšími náklady, než jsou uložené nejlepší náklady, algoritmus se vrátí zpět, místo aby se pokusil toto řešení rozšířit.
Předpokládáme-li, že náklady mají být minimalizovány, závisí účinnost těchto algoritmů na tom, jak se vyhodnocují náklady, které lze získat rozšířením dílčího řešení. Pokud totiž algoritmus může z částečného řešení couvnout, část hledání se vynechá. Čím nižší jsou odhadované náklady, tím lepší je algoritmus, protože nižší odhadované náklady jsou s větší pravděpodobností nižší než náklady dosud nalezeného nejlepšího řešení.
Na druhou stranu tyto odhadované náklady nemohou být nižší než efektivní náklady, které lze získat rozšířením řešení, protože jinak by algoritmus mohl couvat, zatímco existuje řešení lepší než dosud nalezené nejlepší. V důsledku toho algoritmus vyžaduje horní hranici nákladů, které lze získat rozšířením dílčího řešení, a tato horní hranice by měla být co nejmenší.
Varianta tohoto přístupu zvaná Hansenova metoda používá intervalové metody. Její podstatou je implementace obdélníkových omezení.
Ohraničující funkce první volbyUpravit
Jedním ze způsobů, jak vyhodnotit tuto horní hranici pro dílčí řešení, je uvažovat každé měkké omezení zvlášť. Pro každé měkké omezení se předpokládá maximální možná hodnota pro libovolné přiřazení nepřiřazeným proměnným. Součet těchto hodnot je horní hranicí, protože měkká omezení nemohou předpokládat vyšší hodnotu. Je přesný, protože maximální hodnoty měkkých omezení mohou vycházet z různých ohodnocení: měkké omezení může být maximální pro x = a {\displayystyle x=a}
, zatímco jiné omezení je maximální pro x = b {\displaystyle x=b}.
.
Ruská panenka searchEdit
Tato metoda provádí algoritmus větví a hranic na n {\displaystyle n}.
problémů, kde n {\displaystyle n}
je počet proměnných. Každý takový problém je podproblém získaný vypuštěním posloupnosti proměnných x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}}.
z původního problému spolu s omezeními, která je obsahují. Po vyřešení problému na proměnných x i + 1 , … , x n {\displayystyle x_{i+1},\ldots ,x_{n}}.
je vyřešen, lze jeho optimální náklady použít jako horní mez při řešení ostatních problémů,
Zejména odhad nákladů řešení, které má x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}, lze použít jako horní mez při řešení ostatních problémů,
Zejména odhad nákladů řešení, které má x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}
jako nepřiřazené proměnné se přičítá k nákladům, které vyplývají z ohodnocených proměnných. Prakticky to odpovídá ignorování ohodnocených proměnných a řešení problému na nepřiřazených proměnných, s tím rozdílem, že tento druhý problém již byl vyřešen. Přesněji řečeno, náklady měkkých omezení obsahujících přiřazené i nepřiřazené proměnné se odhadují výše uvedeným způsobem (nebo pomocí libovolné jiné metody); náklady měkkých omezení obsahujících pouze nepřiřazené proměnné se místo toho odhadují pomocí optimálního řešení příslušného problému, které je v tomto okamžiku již známo.
Mezi metodou hledání ruské panenky a dynamickým programováním existuje podobnost. Stejně jako Dynamické programování řeší Russian Doll Search dílčí problémy s cílem vyřešit celý problém. Ale zatímco Dynamické programovánípřímo kombinuje výsledky získané na dílčích problémech, aby získalo výsledek celého problému, Russian Doll Search je při prohledávání používá pouze jako hranice.
Eliminace kyblíkuEdit
Algoritmus eliminace kyblíku lze přizpůsobit pro optimalizaci s omezeními. Danou proměnnou lze z problému skutečně odstranit nahrazením všech měkkých omezení, která ji obsahují, novým měkkým omezením. Náklady tohoto nového omezení se počítají za předpokladu maximální hodnoty pro každou hodnotu odstraněné proměnné. Formálně, jestliže x {\displaystyle x}
je proměnná, která má být odstraněna, C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}.
jsou měkká omezení, která ji obsahují, a y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}
jsou jejich proměnné kromě x {\displaystyle x}
, je nové měkké omezení definováno takto: 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})}.
Eliminace z balíčku pracuje s (libovolným) uspořádáním proměnných. Každé proměnné je přiřazeno vědro omezení; vědro proměnné obsahuje všechna omezení, která má proměnná nejvyšší v pořadí. Kbelíková eliminace postupuje od poslední proměnné k první. Pro každou proměnnou se všechna omezení kbelíku nahradí výše uvedeným způsobem, aby se proměnná odstranila. Výsledné omezení se pak umístí do příslušného kbelíku.