×

zbMATH — the first resource for mathematics

The constrained Newton method on a Lie group and the symmetric eigenvalue problem. (English) Zbl 0864.65032
An important class of subproblems in nonlinear equality constrained optimization problems is where the constraint space is a Lie group. Symmetric eigenvalue problems may also be formulated in this manner.
Given a Lie group \(G\) and a smooth function \(\varphi: G\to\mathbb{R}\), the author gives the Newton method on \(G\), defined in terms of an appropriate gradient and Hessian of \(\varphi\). Quadratic convergence of the method is proved. The method as described depends on a choice of basis vectors for the local tangent space of \(G\); in the next section this method is extended to a coordinate free version.
The coordinate free Newton method is then developed for the symmetric eigenvalue problem. Two numerical examples are presented, and the results of the second compared with those from the shifted QR method.

MSC:
65H10 Numerical computation of solutions to systems of equations
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bayer, D.A.; Lagarias, J.C., The nonlinear geometry of linear programming I, affine and projective scaling trajectories; II, Legendre transform coordinates and central trajectories, Trans. amer. math. soc., 314, 499-581, (1989) · Zbl 0671.90046
[2] Brockett, R.W., Dynamical systems that sort lists, diagonalise matrices and solve linear programming problems, (), 799-803
[3] Brockett, R.W., Dynamical systems that sort lists, diagonalise matrices, and solve linear programming problems, Linear algebra appl., 146, 79-91, (1991) · Zbl 0719.90045
[4] Brockett, R.W., Differential geometry and the design of gradient algorithms, (), 69-92 · Zbl 1107.37306
[5] Chu, M.T.; Driessel, K.R., The projected gradient method for least squares matrix approximations with spectral constraints, SIAM J. numer. anal., 27, 4, 1050-1060, (1990) · Zbl 0704.65025
[6] Faybusovich, L.E., Hamiltonian structure of dynamical systems which solve linear programming problems, Phys. D., (1991) · Zbl 0745.58023
[7] Golub, G.H.; Van Loan, C.F., Matrix computations, (1989), Johns Hopkins U.P Baltimore · Zbl 0733.65016
[8] Halgason, S., Differential geometry, Lie groups and symmetric spaces, (1978), Academic New York
[9] Helmke, U.; Moore, J.B., Singular value decomposition via gradient flows, Systems control lett., 14, 369-377, (1990) · Zbl 0699.93010
[10] Helmke, U.; Moore, J.B., Optimization and dynamical systems, (1994), Comm. Control Eng. Set., Springer-Verlag London · Zbl 0943.93001
[11] Mahony, R.E., Optimization algorithms on homogeneous spaces: with applications in linear systems theory, () · Zbl 0864.65032
[12] Mahony, R.E.; Helmke, U., System assignment and pole placement for symmetric realisations, J. math. systems estim. control, (1995), to appear · Zbl 0852.93035
[13] Mahony, R.E.; Helmke, U.; Moore, J.B., Pole placement algorithms for symmetric realisations, () · Zbl 0855.65033
[14] Minoux, M., Mathematical programming: theory and algorithms, (1986), Wiley Chichester · Zbl 0602.90090
[15] Moore, J.B.; Mahony, R.E.; Helmke, U., Recursive gradient algorithms for eigenvalue and singular value decompositions, () · Zbl 0855.65033
[16] Moore, J.B.; Mahony, R.E.; Helmke, U., Numerical gradient algorithms for eigenvalue and singular value calculations, SIAM J. matrix anal., 15, 3, 881-902, (1994) · Zbl 0808.65031
[17] Nesterov, Y.; Nemirovskii, A., Interior-point polynomical algorithms in convex programming, (1994), SIAM Philadelphia · Zbl 0824.90112
[18] Perkins, J.E.; Helmke, U.; Moore, J.B., Balanced realizations via gradient flow techniques, Systems control lett., 14, 369-380, (1990) · Zbl 0699.93010
[19] Shub, M.; Smale, S., Complexity of Bezout’s theorem. I: geometric aspects, J. amer. math. soc., 6, 2, 459-501, (1993) · Zbl 0821.65035
[20] Smith, S.T., Dynamical systems the perform the singular value decomposition, Systems control lett., 16, 5, 319-327, (1991) · Zbl 0728.93051
[21] Smith, S.T., Geometric optimization methods for adaptive filtering, ()
[22] Varadarajan, V.S., Lie groups, Lie algebras, and their representations, () · Zbl 0371.22001
[23] Warner, F.W., Foundations of differentiable manifolds and Lie groups, () · Zbl 0172.23003
[24] Wilkinson, J.H., Global convergence of the QR algorithm, Linear algebra appl., (1968) · Zbl 0237.65029
[25] Yan, W.-Y.; Moore, J.B.; Helmke, U., Recursive algorithms for solving a class of nonlinear matrix equations with applications to certain sensitivity optimization problems, SIAM J. control optim., (1994), to appear
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.