Trumpf, Jochen (The Australian National Univ. and National ICT Australia Ltd.), Manton, Jonathan (The Australian National Univ.), Mahony, Robert (The Australian National Univ.)

Curvature Based Updates for Optimisation Problems on a Hypersurface.

Scheduled for presentation during the Mini-Symposium "Geometric Optimisation in Systems and Control I" (WeA07), Wednesday, July 26, 2006, 11:15−11:40, Room H

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on April 20, 2024

Abstract

Recently there has been significant interest in the development of efficient optimisation algorithms for a class of constrained optimization problems where the constraint set is a smooth matrix manifold. The new algorithms are motivated by a range of linear algebra problems involving the factorisation of matrices and determination of invariant subspaces that can be reformulated as constrained optimisation algorithms. The matrix manifolds considered are often matrix groups and have a Lie-group structure, or are quotients of Lie-groups leading to homogeneous or even symmetric space structures. The main contribution of the last few years of work has been to apply the modern theory of differential geometry to these problems to provide a means to apply the tools and techniques of unconstrained optimisation such as Newton methods and trust region methods to the solution of the optimisation problem by exploiting the intrinsic geometry of the underlying constraints.

In this paper we consider optimisation problems motivated by the same class of linear algebra problems discussed above, however, we develop by exploiting the extrinsic geometry of the constraint sets. That is, we wish to consider the embedding structure of the constraint set in some overarching space on which a cost function may be defined that specialises to the specific cost on the constraint set. In a sense we approach the problem from the perspective of classical constrained optimisation, however, it is our goal to base the algorithms developed on the twin principals of symmetry of the constraint and simplicity of the cost.

To this extent we propose to approximate the constraint set (in the case where it is a hypersurface in the embedding space) by a quadric, solve the optimisation problem on the quadric, and project back onto the hypersurface in each iteration step. Clearly, this will only lead to a competitive algorithm where each of these steps is easily computable.