OPTEC - K.U.Leuven Center of Excellence: Optimization in Engineering

"Solving Lyapunov equations by geometric optimization on the  manifold of low-rank matrices"
Bart Vandereycken, Department of Computer Science, TWR

Place: Celestijnenlaan 200A, Auditorium 00.225, 3001 Leuven
Date and Time: Friday, October 3, 2008,  11h-12h

Abstract:

We present a geometric  optimization approach to approximate solutions of certain  matrix equations, e.g. the Lyapunov  equation, by low-rank positive semidefinite (PSD) matrices.

The solution of  a matrix equation is in general  a dense matrix which poses significant problems in  large-scale applications. The mere fact that the number of unknowns scales quadratically with the problem size necessitates  some sort  of approximation  of the  solution  itself. A popular  technique  to overcome  this  curse  of  dimensionality is  a low-rank approximation. We  will  obtain  these  approximations  by  minimizing  an  objective function  representing  the  error  defined  on the  set  of  low-rank matrices.  Because  this set is a  smooth manifold, we end  up with an unconstrained minimization  problem  on  a  Riemannian  manifold.  An advantage of  this approach is that  we have reduced  the dimension of the original problem to the dimension of the manifold, which is linear in the number of discretization variables.

However, standard optimization  techniques are not directly applicable since the problem  is no longer defined on  a Euclidean space. Luckily we  can exploit the  Riemannian geometry  of the  set of  low-rank PSD matrices by  using geometric optimization.  This leads to a  series of consecutive minimizations,  each defined on  the tangent space  of the current  approximation.  This way  we  retrieve a  predictor-corrector algorithm:
  1) Make a step in the  tangent space by minimizing a suitable  model
     of the  cost function.
  2) Retract this step to the manifold, e.g. by projection.

This framework  includes well-known geometric  optimization techniques on manifolds,   like    non-linear   CG,   Riemannian   Newton   and Trust-Region. In our case this can also be related to the steady stateof  a gradient  flow  integrated  on the  manifold.  The geometry  and efficient implementation of the manifold as well as locally optimal CG and Trust-Region methods are discussed and illustrated numerically.