Internpunktsmetoder

Internpunktsmetoder, eller inre punktsmetoder, är en familj algoritmer för optimeringsproblem där man söker lösningar inne i den Feasibla regionen snarare än längs dess gräns. De används främst för linjärprogrammering och andra konvexa problem som kvadratiska och semidefinita program. Grundidén är att införa en barriärfunktion som avstyr ytterligare att lösningen närmar sig obehöriga gränser, vilket gör att optimeringen sker genom att följa en central väg inuti området.

Historiskt uppstod intresset för inre punktsmetoder med Karmarkars algoritm från 1984, som visade att linjärprogrammering kan lösas i polynomisk tid. Sedan dess har primal-dual och path-following-varianter blivit dominerande i praktiken. Mehrotras predictor-corrector-metoder har särskild spridning inom industrin på grund av bra praktisk prestanda och stabilitet. Modern forskning och kommersiella lösningar omfattar även bredare konvexa problem som kvadratiska och semidefinita program.

Principen i en typisk internpunktsmetod bygger på att optimera en barriärförstärkt objektivfunktion där barriären förtar lösningar som närmar sig gränserna. Vid varje iteration beräknas en Newton-liknande sökdrift som uppdaterar den primal och duala lösningen samtidigt, så kallad primal-dual riktning, och följer den centrala vägen mot ett optimal. Barrierparametern mu sänks stegvis mot noll så att lösningen konvergerar mot det optimala lösningen av det ursprungliga problemet.

Användningsområden inkluderar linjärprogrammering, kvadratiska program och förlängningar till konvexa problem som semidefinite och andra kontrollerade optimeringsproblem. Fördelarna är stabilitet och god skalbarhet på stora, sparsamma problem, medan begränsningar inkluderar krav på en strikt inre startpunkt, höga linjära system-stegningar och känslighet mot numerisk rundning.