Metoda aktivní sady - Active-set method

V matematice optimalizace, je problém definován pomocí objektivní funkce k minimalizaci nebo maximalizaci a množiny omezení

${ displaystyle g_ {1} (x) geq 0, tečky, g_ {k} (x) geq 0}$

které definují proveditelný region, tj. soubor všech X hledat optimální řešení. Daný bod ${ displaystyle x}$ v proveditelné oblasti omezení

${ displaystyle g_ {i} (x) geq 0}$

je nazýván aktivní na ${ displaystyle x}$ -li ${ displaystyle g_ {i} (x) = 0}$, a neaktivní na ${ displaystyle x}$ -li ${ displaystyle g_ {i} (x)> 0.}$ Omezení rovnosti jsou vždy aktivní. The aktivní sada na ${ displaystyle x}$ se skládá z těchto omezení ${ displaystyle g_ {i} (x)}$ které jsou aktivní v aktuálním bodě (Nocedal & Wright 2006, str. 308).

Aktivní sada je zvláště důležitá v teorii optimalizace, protože určuje, která omezení ovlivní konečný výsledek optimalizace. Například při řešení lineární programování problém, aktivní sada dává hyperplanes které se protínají v bodě řešení. v kvadratické programování, protože řešení nemusí být nutně na jednom z okrajů ohraničujícího polygonu, odhad aktivní množiny nám dává podmnožinu nerovností, které je třeba sledovat při hledání řešení, což snižuje složitost hledání.

Metody aktivní sady

Algoritmus aktivní sady má obecně následující strukturu:

Najděte proveditelný výchozí bod

opakujte do "dostatečně optimální"

řešit problém rovnosti definovaný aktivní sadou (přibližně)

vypočítat the Lagrangeovy multiplikátory aktivní sady

odstranit podmnožina omezení s negativními Lagrangeovými multiplikátory

Vyhledávání pro nemožná omezení

konec opakování

Metody, které lze popsat jako metody aktivní sady zahrnout:^[1]

• Postupné lineární programování (SLP)
• Sekvenční kvadratické programování (SQP)
• Sekvenční lineární kvadratické programování (SLQP)
• Metoda redukovaného gradientu (RG)
• Zobecněná metoda se sníženým gradientem (GRG)

Reference

Bibliografie

• Murty, K. G. (1988). Lineární komplementarita, lineární a nelineární programování. Série Sigma v aplikované matematice. 3. Berlín: Heldermann Verlag. str. xlviii + 629 str. ISBN  3-88538-403-5. PAN  0949214. Archivovány od originál dne 01.04.2010. Citováno 2010-04-03.CS1 maint: ref = harv (odkaz)
• Nocedal, Jorge; Wright, Stephen J. (2006). Numerická optimalizace (2. vyd.). Berlín, New York: Springer-Verlag. ISBN  978-0-387-30303-1.CS1 maint: ref = harv (odkaz)