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

A semismooth Newton-CG based dual proximal point algorithm (PPA) is proposed for the solution of a practically relevant class of large scale matrix norm approximation problems, which consist of finding the minimal spectral norm of an affine combination of given matrices subject to linear equality and inequality constraints. Firstly, based on classical results, an inexact dual PPA for the solution of the considered approximation problem is presented and its global and local convergence is verified under suitable assumptions. Next, an inexact semismooth Newton-CG method is studied for the solution of the subproblems in this algorithm and its superlinear convergence is proved under the assumption that the primal constraint nondegeneracy condition is satisfied for these problems. At last, the new algorithm is applied to a variety of problems of different types and its performance is compared with a classical first order alternating direction method of multipliers (ADMM), where the PPA is started with a point obtained from the ADMM. The results show that the PPA is robust and efficient and outperforms the pure ADMM substantially.