Wiele algorytmów optymalizacji nieograniczonej może być zaadaptowanych do przypadku ograniczonego, często poprzez zastosowanie metody kar. Jednakże, kroki wyszukiwania podjęte przez metodę nieograniczoną mogą być nie do przyjęcia dla problemu ograniczonego, prowadząc do braku zbieżności. Jest to określane jako efekt Maratosa.
Ograniczenia równościoweEdit
Metoda podstawianiaEdit
W przypadku bardzo prostych problemów, powiedzmy funkcji dwóch zmiennych podlegających pojedynczemu ograniczeniu równościowemu, najbardziej praktyczne jest zastosowanie metody podstawiania. Pomysł polega na zastąpieniu ograniczenia w funkcji celu, aby utworzyć złożoną funkcję, która zawiera efekt ograniczenia. Na przykład, załóżmy, że celem jest maksymalizacja f ( x , y ) = x ⋅ y {{displaystyle f(x,y)=x ⋅ y}
z zastrzeżeniem x + y = 10 {displaystyle x+y=10}
. Ograniczenie implikuje, że y = 10 – x {{displaystyle y=10-x}
, co można podstawić do funkcji celu, aby otrzymać p ( x ) = x ( 10 – x ) = 10 x – x 2 {{displaystyle p(x)=x(10-x)=10x-x^{2}}.
. Warunek konieczny pierwszego rzędu daje ∂ p ∂ x = 10 – 2 x = 0 {{displaystyle {{frac {{partial p}{{partial x}}}=10-2x=0}}.
, które można rozwiązać dla x = 5 {{displaystyle x=5}}
i w konsekwencji y = 10 – 5 = 5 {displaystyle y=10-5=5}
.
Mnożnik Lagrange’aEdit
Jeśli problem z ograniczeniami ma tylko ograniczenia równościowe, można użyć metody mnożników Lagrange’a, aby przekształcić go w problem bez ograniczeń, którego liczba zmiennych jest oryginalną liczbą zmiennych plus oryginalną liczbą ograniczeń równościowych. Alternatywnie, jeśli wszystkie ograniczenia są równościowe i wszystkie są liniowe, mogą być rozwiązane dla niektórych zmiennych w kategoriach innych, a te pierwsze mogą być zastąpione z funkcji celu, pozostawiając problem bez ograniczeń w mniejszej liczbie zmiennych.
Ograniczenia nierównościoweEdit
Przy ograniczeniach nierównościowych problem można scharakteryzować w kategoriach geometrycznych warunków optymalności, warunków Fritza Johna i warunków Karush-Kuhn-Tuckera, przy których proste problemy mogą być rozwiązywalne.
Programowanie linioweEdit
Jeśli funkcja celu i wszystkie twarde ograniczenia są liniowe, a niektóre twarde ograniczenia są nierównościami, to problem jest problemem programowania liniowego. To może być rozwiązane przez metodę simpleks, która zwykle działa w czasie wielomianu w wielkości problemu, ale nie jest gwarantowane, lub przez metody punktu wewnętrznego, które są gwarantowane do pracy w czasie wielomianu.
Programowanie nielinioweEdit
Jeśli funkcja celu lub niektóre z ograniczeń są nieliniowe, a niektóre ograniczenia są nierówności, to problem jest problem programowania nieliniowego.
Programowanie kwadratoweEdit
Jeśli wszystkie twarde ograniczenia są liniowe, a niektóre są nierównościami, ale funkcja celu jest kwadratowa, to problem jest problemem programowania kwadratowego. Jest to jeden z rodzajów programowania nieliniowego. Nadal może być rozwiązany w czasie wielomianowym metodą elipsoidalną, jeśli funkcja celu jest wypukła; w przeciwnym razie problem może być NP trudny.
Warunki KKTEdit
Dopuszczając ograniczenia nierównościowe, podejście KKT do programowania nieliniowego uogólnia metodę mnożników Lagrange’a. Można ją stosować w warunkach różniczkowalności i wypukłości.
Branch and boundEdit
Optymalizacja z ograniczeniami może być rozwiązywana za pomocą algorytmów branch-and-bound. Są to algorytmy backtrackingowe przechowujące koszt najlepszego rozwiązania znalezionego podczas wykonywania i wykorzystujące go do ominięcia części poszukiwań. Dokładniej, ilekroć algorytm napotyka częściowe rozwiązanie, które nie może być rozszerzone w celu utworzenia rozwiązania o lepszym koszcie niż przechowywany najlepszy koszt, algorytm cofa się, zamiast próbować rozszerzyć to rozwiązanie.
Zakładając, że koszt ma być minimalizowany, efektywność tych algorytmów zależy od tego, jak oceniany jest koszt, który można uzyskać z rozszerzenia częściowego rozwiązania. W rzeczywistości, jeśli algorytm może cofnąć się z częściowego rozwiązania, część wyszukiwania jest pomijana. Im niższy szacowany koszt, tym lepszy algorytm, ponieważ niższy szacowany koszt jest bardziej prawdopodobne, że będzie niższy niż najlepszy koszt rozwiązania znalezionego do tej pory.
Z drugiej strony, ten szacowany koszt nie może być niższy niż efektywny koszt, który można uzyskać przez rozszerzenie rozwiązania, ponieważ w przeciwnym razie algorytm mógłby cofnąć się, podczas gdy istnieje rozwiązanie lepsze niż najlepsze znalezione do tej pory. W rezultacie, algorytm wymaga górnego ograniczenia na koszt, który można uzyskać z rozszerzenia częściowego rozwiązania, a to górne ograniczenie powinno być tak małe, jak to możliwe.
Odmiana tego podejścia zwana metodą Hansena wykorzystuje metody interwałowe. W sposób naturalny implementuje ona ograniczenia prostokątne.
Funkcje ograniczające pierwszego wyboruEdit
Jednym ze sposobów oceny tego górnego ograniczenia dla rozwiązania częściowego jest rozważenie każdego miękkiego ograniczenia osobno. Dla każdego miękkiego ograniczenia przyjmowana jest maksymalna możliwa wartość dla dowolnego przypisania do nieprzypisanych zmiennych. Suma tych wartości jest górnym ograniczeniem, ponieważ miękkie ograniczenia nie mogą przyjąć wyższej wartości. Jest ona dokładna, ponieważ maksymalne wartości miękkich ograniczeń mogą pochodzić z różnych ocen: miękkie ograniczenie może być maksymalne dla x = a {{displaystyle x=a}
, podczas gdy inne ograniczenie jest maksymalne dla x = b {{displaystyle x=b}
.
Russian doll searchEdit
Ta metoda uruchamia algorytm branch-and-bound na n {{displaystyle n}
problemów, gdzie n {displaystyle n}
jest liczbą zmiennych. Każdy taki problem jest podproblemem otrzymanym przez usunięcie sekwencji zmiennych x 1 , … , x i {{displaystyle x_{1}},\dots ,x_{i}}
z pierwotnego problemu, wraz z zawierającymi je ograniczeniami. Po rozwiązaniu problemu na zmiennych x i + 1 , … , x n {{displaystyle x_{i+1}},ldots ,x_{n}}
jest rozwiązany, jego optymalny koszt może być użyty jako górna granica przy rozwiązywaniu innych problemów,
W szczególności, oszacowanie kosztu rozwiązania mającego x i + 1 , … , x n {\displaystyle x_{i+1},\dots ,x_{n}}
jako zmienne nieprzypisane jest dodawany do kosztu, który wynika z ocenianych zmiennych. Praktycznie odpowiada to ignorowaniu zmiennych ocenianych i rozwiązywaniu problemu na zmiennych nieprzypisanych, z tą różnicą, że ten drugi problem został już rozwiązany. Dokładniej, koszt miękkich ograniczeń zawierających zarówno przypisane jak i nieprzypisane zmienne jest szacowany jak powyżej (lub przy użyciu arbitralnej innej metody); koszt miękkich ograniczeń zawierających tylko nieprzypisane zmienne jest zamiast tego szacowany przy użyciu optymalnego rozwiązania odpowiedniego problemu, który jest już znany w tym momencie.
Istnieje podobieństwo między metodą Russian Doll Search a programowaniem dynamicznym. Podobnie jak programowanie dynamiczne, Russian Doll Search rozwiązuje podproblemy w celu rozwiązania całego problemu. Jednak, podczas gdy programowanie dynamiczne bezpośrednio łączy wyniki uzyskane na podproblemach, aby uzyskać wynik całego problemu, Russian Doll Search używa ich tylko jako granic podczas wyszukiwania.
Eliminacja kubełkówEdit
Algorytm eliminacji kubełków może być zaadaptowany do optymalizacji ograniczeń. Dana zmienna może być rzeczywiście usunięta z problemu przez zastąpienie wszystkich zawierających ją miękkich ograniczeń nowym miękkim ograniczeniem. Koszt tego nowego ograniczenia jest obliczany przy założeniu wartości maksymalnej dla każdej wartości usuniętej zmiennej. Formalnie, jeśli x {displaystyle x}
jest zmienną do usunięcia, to C 1 , … , C n {displaystyle C_{1}},\dots ,C_{n}}
są miękkimi ograniczeniami zawierającymi ją, a y 1 , … , y m {displaystyle y_{1},\dots ,y_{m}}
są ich zmiennymi z wyjątkiem x {displaystyle x}
, nowe miękkie ograniczenie jest zdefiniowane przez: C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {C(y_{1}=a_{1},y_{n}=a_{n})=max _{a}suma _{i}C_{i}(x=a,y_{1}=a_{1},y_{n}=a_{n}).}
Eliminacja kubełkowa działa z (arbitralnym) uporządkowaniem zmiennych. Z każdą zmienną związany jest kubełek ograniczeń; kubełek zmiennej zawiera wszystkie ograniczenia, które zmienna ma najwyżej w kolejności. Eliminacja kubełkowa przebiega od ostatniej zmiennej do pierwszej. Dla każdej zmiennej, wszystkie ograniczenia z kubełka są zastępowane jak wyżej, aby usunąć zmienną. Powstałe w ten sposób ograniczenie jest następnie umieszczane w odpowiednim kubełku.