Den inre punktmetoden är en metod som tillåter att lösa konvexa optimeringsproblem med villkor specificerade i form av ojämlikheter, vilket reducerar det ursprungliga problemet till ett konvext optimeringsproblem.
Det används för att lösa problem med materialstyrka , matematisk modellering och ekonometri.
Den inre punktmetoden nämndes första gången av I. I. Dikin 1967 . [1] . Dessa studier fortsatte, inklusive av inhemska forskare. På 1970-talet började V.G. Zhadan lyckades få huvudresultaten och utveckla ett allmänt tillvägagångssätt för konstruktion av inre punktmetoder för att lösa problem med linjär och olinjär programmering, baserat på transformation av utrymmen; föreslå barriärprojektiva och barriär-newtonska numeriska metoder.
Västerländsk litteratur hävdar att den inre punktmetoden först föreslogs av John von Neumann och, i sin ursprungliga form, inte hade polynomkomplexitet och inte heller var den effektiv. I praktiken var den till och med sämre än simplexmetoden , som inte heller hade polynomkomplexitet [2] . Men 1984 visade den linjära programmeringsalgoritmen som föreslagits av den indiske matematikern Narendra Karmarkar att polynomtiden till och med överträffade simplexmetoden.
Enligt inre punktmetoder (annars kallade barriärfunktionsmetoder) kan källpunkten för sökningen endast väljas inom det tillåtna området.
Valet av utgångspunkt för sökningen utförs beroende på problemformuleringen. I avsaknad av restriktioner eller deras omvandling till strafffunktioner med en extern punkt, väljs utgångspunkten godtyckligt. I närvaro av restriktioner eller deras omvandling till strafffunktioner med en inre punkt, väljs startpunkten inom det tillåtna området
I det här fallet är poänguppsättningen uppdelad i tillåtna och otillåtna, beroende på begränsningarna. I sin tur är uppsättningen av tillåtna punkter, beroende på begränsningarna, också uppdelad i gräns och inre.
Ursprunget till de centrala vägalgoritmerna går tillbaka till idén om K. Frisch att inkludera strafftermer i den objektiva funktionen i form av en logaritm av ojämlikhetsbegränsningar med en parameter som monotont minskar till noll.
Uppkomsten av Karmarkar-algoritmen [51] fick forskare att aktivt använda de logaritmiska barriärfunktionerna i linjära programmeringsproblem.
Karmakarmetoden liknar logbarriärmetoden.
För att köra barriärmetoden måste du ange den initiala interna punkten, d.v.s. en punkt x för vilken fi(x) < 0 ∀i. I det allmänna fallet kan det vara en icke-trivial uppgift att hitta en inre punkt x. Metoder för att lösa detta problem kallas metoder för den första fasen. Dessa inkluderar barriärmetoden och direkt-dual Newton-metoden.
| Optimeringsmetoder _ | |
|---|---|
| En-dimensionell |
|
| Noll ordning | |
| Första beställning | |
| andra beställning | |
| Stokastisk | |
| Linjära programmeringsmetoder _ | |
| Icke -linjära programmeringsmetoder | |