Metoda vnitřních bodů je metoda, která umožňuje řešení konvexních optimalizačních problémů s podmínkami specifikovanými ve formě nerovností, redukujících původní problém na konvexní optimalizační problém.
Používá se při řešení problémů pevnosti materiálů , matematického modelování a ekonometrie.
Metodu vnitřních bodů poprvé zmínil I. I. Dikin v roce 1967 . [1] . Tyto studie pokračovaly, včetně domácích vědců. V 70. letech 20. století V.G. Zhadanovi se podařilo získat hlavní výsledky a vyvinout obecný přístup ke konstrukci metod vnitřních bodů pro řešení problémů lineárního a nelineárního programování, založených na transformaci prostorů; navrhnout bariérově-projektivní a bariérově-newtonovské numerické metody.
Západní literatura tvrdí, že metoda vnitřního bodu byla poprvé navržena Johnem von Neumannem a ve své původní podobě neměla polynomiální složitost , ani nebyla účinná. V praxi to bylo dokonce horší než simplexová metoda , která také neměla polynomiální složitost [2] . V roce 1984 však algoritmus lineárního programování navržený indickým matematikem Narendrou Karmarkarem prokázal, že polynomiální čas dokonce překonal simplexovou metodu.
Podle metod vnitřních bodů (jinak nazývaných metody bariérové funkce) lze zdrojový bod pro hledání vybrat pouze uvnitř povolené oblasti.
Volba výchozího bodu hledání se provádí v závislosti na formulaci problému. Při absenci omezení nebo jejich transformace na penalizační funkce s vnějším bodem je výchozí bod zvolen libovolně. V případě omezení nebo jejich transformace na penalizační funkce s vnitřním bodem je výchozí bod zvolen uvnitř povolené oblasti
V tomto případě se soubor bodů v závislosti na omezení dělí na přípustné a nepřípustné. Sada přípustných bodů se zase v závislosti na omezení dělí na hraniční a vnitřní.
Počátky algoritmů centrální cesty sahají k myšlence K. Frische zahrnout penalizační členy do objektivní funkce ve formě logaritmu omezení nerovností s parametrem monotónně klesajícím k nule.
Objevení se Karmarkarova algoritmu [51] přimělo výzkumníky k aktivnímu používání logaritmických bariérových funkcí v problémech lineárního programování.
Metoda Karmakar je podobná metodě log-bariér.
Pro spuštění bariérové metody musíte zadat počáteční vnitřní bod, tzn. bod x, pro který fi(x) < 0 ∀i. V obecném případě může být nalezení vnitřního bodu x netriviálním úkolem. Metody řešení tohoto problému se nazývají metody první fáze. Patří mezi ně bariérová metoda a přímo-duální Newtonova metoda.
| Optimalizační metody | |
|---|---|
| Jednorozměrný |
|
| Nulové pořadí | |
| První objednávka | |
| druhá objednávka | |
| Stochastické | |
| Metody lineárního programování | |
| Metody nelineárního programování | |