A semismooth Newton-CG based dual PPA for matrix spectral norm approximation problems

C. Chen, Y.-J. Liu, Defeng Sun, K.-C. Toh

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

© 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. We consider a class of matrix spectral norm approximation problems for finding an affine combination of given matrices having the minimal spectral norm subject to some prescribed linear equality and inequality constraints. These problems arise often in numerical algebra, engineering and other areas, such as finding Chebyshev polynomials of matrices and fastest mixing Markov chain models. Based on classical analysis of proximal point algorithms (PPAs) and recent developments on semismooth analysis of nonseparable spectral operators, we propose a semismooth Newton-CG based dual PPA for solving the matrix norm approximation problems. Furthermore, when the primal constraint nondegeneracy condition holds for the subproblems, our semismooth Newton-CG method is proven to have at least a superlinear convergence rate. We also design efficient implementations for our proposed algorithm to solve a variety of instances and compare its performance with the nowadays popular first order alternating direction method of multipliers (ADMM). The results show that our algorithm, which is warm-started with an initial point obtained from the ADMM, substantially outperforms the pure ADMM, especially for the constrained cases and it is able to solve the problems robustly and efficiently to a relatively high accuracy.
Original languageEnglish
Pages (from-to)435-470
Number of pages36
JournalMathematical Programming
Volume155
Issue number1-2
DOIs
Publication statusPublished - 1 Jan 2016
Externally publishedYes

Keywords

  • PPA
  • Semismooth Newton-CG method
  • Spectral norm approximation
  • Spectral operator

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this