The Riemannian Frank–Wolfe Algorithm

Abstract

Frank–Wolfe-algoritmen er en iterativ optimeringsalgoritme for å løse betingede optimeringsproblemer. Metoden er basert på å forenkle problemet til et lineært delproblem som løses i hver iterasjon, og fungerer spesielt bra når delproblemet har en løsning på lukket form.

Algoritmen ble opprinnelig utviklet for å løse problemer i euklidske rom, men det kan ofte være nyttig å jobbe med problemer på mangfoldigheter. I noen tilfeller er løsningen til et euklidisk problem begrenset til å ligge på en mangfoldighet, og i andre tilfeller er dataene eller domenet til objektivfunksjonen allerede definert på mangfoldigheten.

I denne oppgaven studerer vi konvekse problemer på mangfoldigheter, hvor vi i tillegg til mangfoldighetsbetingelsen også har ytterligere betingelser på løsningen. Vi ser på en generalisering av den klassiske Frank–Wolfe-algoritmen til riemannske rom, og undersøker hvordan den skiller seg fra den euklidiske versjonen – spesielt med tanke på hvordan delproblemet ikke lenger er lineært, og dermed må løses med mer avanserte teknikker.

Vårt hovedbidrag ligger i å implementere algoritmen som en generell løser for problemer på vilkårlige riemannske mangfoldigheter, ved å bruke grensesnittet til Manopt.jl, et Julia-bibliotek for optimering på mangfoldigheter. Vi tester implementasjonen vår på den symmetriske positivt bestemte matrisemangfoldigheten, men vi merker oss at ytelsen til algoritmen ikke er så god som forventet.

The Frank–Wolfe method is an iterative optimization algorithm commonly used to solve constrained convex optimization problems. Based on simplifying the problem to a linear subproblem, which is solved in each iteration, the algorithm is especially useful in cases where this subproblem can be solved in closed form.

While the Frank–Wolfe algorithm was originally formulated for solving problems in Euclidean space, it can often be beneficial to work with problems on manifolds. Sometimes the constraints of a Euclidean problem actually constrain the solution to lie on a manifold, and in other cases the data or the domain of the objective function may already be defined on the manifold.

In this thesis we study convex problems on manifold domains where, in addition to the manifold constraint, we also have further constraints on the solution. We work with a generalization of the classical Frank–Wolfe algorithm to Riemannian space, and examine how it differs from the Euclidean version – especially with regard to how the subproblem is no longer linear, and thus requires more sophisticated techniques to solve.

Our main contribution lies in implementing the algorithm as a general solver for problems on arbitrary Riemannian manifolds, using the interface provided by Manopt.jl, a Julia package for manifold optimization. We test the implementation numerically on the manifold of symmetric positive-definite matrices, but we note that the performance of the algorithm is not as good as we expected.