Numerical Algorithms For A Class Of Matrix Norm Approxima- Tion Problems

This thesis focuses on designing robust and efficient algorithms for a class of ma-trix norm approximation (MNA) problems that are to find an affine combination of given matrices having the minimal spectral norm subject to some prescribed linear e-quality and inequality constraints. These problems arise often in numerical algebra, network, control, engineering and other areas, such as finding the Chebyshev polyno-mials of matrices and fastest mixing Markov chain models.In this thesis, we first apply the popular first-order algorithm alternating direction method (ADM) to solve such problems. At each iteration of the algorithm, the subprob-lems involved can either be solved by a fast algorithm or admit closed form solutions, which allows us to implement the ADM easily and simply. Unfortunately, numerical experiments on MNA problems reveal that the ADM performs unstably, and it may fail to achieve satisfactory accuracy in reasonable cpu time for some tested examples, especially for the constrained cases.To overcome this difficulty, we also introduce an inexact dual proximal point al-gorithm (in short SNDPPA) for solving the MNA problems. At each iteration, the inner problem, rewritten as a system of semismooth equations, is solved by an inexact semismooth Newton method using the preconditioned conjugate gradient method to compute the Newton directions. Furthermore, when the primal constraint nondegener-acy condition holds for the inner problems, our inexact semismooth Newton method is proven to have a suplinear convergence rate. We also design efficient implementation for the proposed algorithm to solve a variety of instances and compare its performance with that of ADM. Numerical results show that the semismooth Newton-CG dual prox-imal point algorithm substantially outperforms the alternating direction method, and it is able to solve the matrix norm approximation problems efficiently and stably to a relatively high accuracy.When one restricts the matrices to vectors, then the matrix norm approximation problem can be converted into a second order cone (SOC) problem, which can be solved by Newton’s method such as IPMs even for large scale problems. Motivated by this, we also consider a squared smoothing Newton method, to solve the MNA problems in which the matrix is of much more columns than rows (skinny ones) such as the vector case. For this purpose, we present an interior smoothing function for the metric projector over the epigraph cone of spectral norm and establish its γ or-der semismoothness everywhere. Moreover, suplinear convergence of the smoothing Newton method for solving the MNA problems is also shown to hold under the primal dual constraint nondegenerate conditions for the MNA problems and their dual at the primal dual optimal solution pairs. Preliminary numerical result demonstrate that the smoothing Newton is robust and efficient for the problem of small and moderate scale. Specifically, we can successfully find the solution with the desired accuracy in a few iterations.