An Eigen-based C++ Linesearch Filter Barrier Interior-Point Algorithm

Abstract

Denne masteroppgaven handler om implementasjon av en interior-point optimaliseringsalgoritme basert på den originale implementasjonen av Interior Point OPTimizer. Hensikten med implementasjone er å untnytte ressurser, abstraksjoner og bibliotek utviklet under C++17 standarden, og å trekke inn egenskaper fra det funksjonelle programmeringsparadigme for å forbedre både ytelse, fleksibilitet og lesbarhet.

En linesearch filter-barrier metode er implementert, hvor lineær-algebraiske beregninger er utført med template C++ bibliotek Eigen. Implementasjonen er configurert opp mot Constrained and Unconstrained Testing Environment (CUTEst), som gir tilgang til sett med ulineære problemer. Med beregningsoperasjoner på vanlige matriser klarer implementasjonen å løse problemer med lavere beregnings tid enn IPOPT (med BLAS og MUMPS), men krever flere iterasjoner for å konvergere til en optimal løsning.

For et subset av problemene i CUTEst klarer implementasjonen å konvergere for flertallet av problemene som er begrenset med lineære likhetsligninger, uavhengig av ulineariteten i objektivfunksjonen. Algoritmen har fortsatt problemer med ulineære begrensninger.

Det funksjonelle designet i implementasjonen er begrenset av det kompilerte programmeringsspråket som er brukt, men klarer å erstatte mange av IPOPT's objektorienterte komponenter uten å gjøre algoritmen ineffektiv. Noen forbedringer på det funksjonelle designet vil kreve rekompilering under kjøretid, som kan bli implementert i fremtidige design.

Totalt sett er implementasjonen ikke robst nok til å kvalifisere for generell bruk på ulineære optimaliseringsproblem, og den har potensiale for forbedring på mange av de ulike feltene som har blitt presentert i oppgaven. Fortsatt så kan ytelsen, konvergeringsresultatene og designet anses som tilfredstillende med hensyn til omfanget av oppgaven.

This thesis will present an interior-point optimization library based on the original implementation of the Interior Point OPTimizer. The intention with the implementation is to utilize resources, abstractions and libraries found under the modern C++17 standard, and features from the functional programming paradigm to improve both performance, flexibility and readability.

A linesearch filter-barrier method is implemented, with linear algebraic operations computed using the templated C++ library Eigen. The implementation is interfaced with the Constrained and Unconstrained Testing Environment (CUTEst) to access sets of nonlinear optimization problems. Using dense operations, the implementation is able to outperform IPOPT (with BLAS and MUMPS) in computation time, but requires more iterations than IPOPT in order to converge to a solution.

For a given set of optimization problems the dense solver is able to converge for a majority of problems with linear constraints, regardless of nonlinearity in the objective. The solver still fails to converge for nonlinear constraints.

The functional design in the implementation is constrained by the compiled language, but is successfully able to replace many of IPOPT's object oriented design patterns without impairing performance. Some improvements to the functional design will require runtime compilation, which can be pursued in future designs.

Overall, the implemented solver is not robust enough to qualify for general use, and has the potential for improvements on many of the topics presented in the thesis. Still, performance, convergence and design is considered satisfactory with respect to the scope of this thesis.