Optimization Algorithms on Homogeneous Spaces
Robert E. Mahony, Wei‐Yong Yan · 2005
Constrained optimization problems are commonplace in linear systems theory. In many cases the constraint set is a homogeneous space and the additional geometric insight provided by the Lie-group structure provides a framework in which to tackle the numerical optimization task. The fundamental advantage of this approach is that algorithms designed and implemented using the geometry of the homogeneous space explicitly preserve the constraint set. In this thesis the numerical solution of a number of optimization problems constrained to homogeneous spaces are considered. The first example studied is the task of determining the eigenvalues of a symmetric matrix (or the singular values of an arbitrary matrix) by interpolating known gradient flow solutions using matrix exponentials. Next the related problem of determining principal components of a symmetric matrix is discussed. A continuous-time gradient flow is derived that leads to a discrete exponential interpolation of the continuous-time flow which converges to the desired limit. A comparison to classical algorithms for the same task is given. The third example discussed, this time drawn from the field of linear systems theory, is the task of arbitrary pole placement using static feedback for a structured class of linear systems. The remainder of the thesis provides a review of the underlying theory relevant to the three examples considered and develops a mathematical framework in which the proposed numerical algorithms can be understood. This framework leads to a general form for a solution to any optimization problem on a homogeneous space. An important consequence of the theoretical review is that it develops the mathematical tools necessary to understand more sophisticated numerical algorithms. The thesis concludes by proposing a quadratically convergent numerical optimization method, based on the Newton-Raphson algorithm, which evolves explicitly on a Lie-group.