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

详细信息    查看全文

• 作者：Caihua Chen ; Yong-Jin Liu ; Defeng Sun ; Kim-Chuan Toh
• 关键词：Spectral norm approximation ; Spectral operator ; PPA ; Semismooth Newton ; CG method ; 90C06 ; 90C25 ; 65F10
• 刊名：Mathematical Programming
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：155
• 期：1-2
• 页码：435-470
• 全文大小：670 KB
• 参考文献：1.Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000)MATH CrossRef
  2.Boyd, S., Diaconis, P., Sun, J., Xiao, L.: Fastest mixing Markov chain on a path. Am. Math. Mon. 113, 70–74 (2006)MATH MathSciNet CrossRef
  3.Boyd, S., Diaconis, P., Xiao, L.: Fastest mixing Markov chain on a graph. SIAM Rev. 46, 667–689 (2004)MATH MathSciNet CrossRef
  4.Chen, C.H., He, B.S., Yuan, X.M.: Matrix completion via alternating direction methods. IMA J. Numer. Anal. 32, 227–245 (2012)MATH MathSciNet CrossRef
  5.Chen, X., Qi, H.-D., Qi, L., Teo, K.-L.: Smooth convex approximation to the maximum eigenvalue function. J. Glob. Optim. 30, 253–270 (2004)MATH MathSciNet CrossRef
  6.Clarke, F.H.: Optimization and Nonsmooth Analysis, 2nd edn. SIAM, Philadelphia (1990)MATH CrossRef
  7.Davis, T.A., Hu, Y.: University of Florida sparse matrix collection (2009)
  8.Ding, C.: An introduction to a class of matrix optimization problems. Ph.D. thesis, National University of Singapore, Singapore (2012)
  9.Ding, C., Sun, D.F., Toh, K.-C.: An introduction to a class of matrix cone programming. Math. Program. Ser. A 144, 141–179 (2014)MATH MathSciNet CrossRef
  10.Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. Ser. A 55, 293–318 (1992)MATH MathSciNet CrossRef
  11.Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. II. Springer, New York (2003)
  12.Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2, 17–40 (1976)MATH CrossRef
  13.Glowinski, R., Tallec, P.L.: Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia (1989)MATH CrossRef
  14.Glowinski, R., Marrocco, A.: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non-linéaires. Rev. Française Autom. Inf. Recherche Opérationnelle Anal. Numér. 9, 41–76 (1975)MATH MathSciNet
  15.Greenbaum, A., Trefethen, L.N.: GMRES/CR and Arnoldi/Lanczos as matrix approximation problems. SIAM J. Sci. Comput. 15, 359–368 (1994)MATH MathSciNet CrossRef
  16.Ha, C.D.: A generalization of the proximal point algorithm. SIAM J. Control Optim. 28, 503–512 (1990)MATH MathSciNet CrossRef
  17.He, B.S., Liao, L.-Z., Han, D.R., Yang, H.: A new inexact alternating directions method for monotone variational inequalities. Math. Program. Ser. A 92, 103–118 (2002)MATH MathSciNet CrossRef
  18.Held, M., Wolfe, P., Crowder, H.P.: Validation of subgradient optimization. Math. Program. 6, 62–88 (1974)MATH MathSciNet CrossRef
  19.Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, vols. I and II. Springer, Berlin (1993)
  20.Hiriart-Urruty, J.-B., Strodiot, J.-J., Nguyen, V.H.: Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data. Appl. Math. Optim. 11, 43–56 (1984)MATH MathSciNet CrossRef
  21.Jiang, K.F.: Algorithms for large scale nuclear norm minimization and convex quadractic semidefinite programming problems. Ph.D. thesis. National University of Singapore, Singapore (2012)
  22.Jiang, K.F., Sun, D.F., Toh, K.C.: A partial proximal point algorithm for nuclear norm regularized matrix least squares problems. Math. Program. Comput. 6, 281–325 (2014)MathSciNet CrossRef
  23.Jiang, K.F., Sun, D.F., Toh, K.C.: Solving nuclear norm regularized and semidefinite matrix least squares problems with linear equality constraints. In: Bezdek, K., Ye, Y., Deza, A. (eds.) Fields Institute Communications Series on Discrete Geometry and Optimization. Springer, Switzerland (2013)
  24.Lemaréchal, C., Sagastizábal, C.: Practical aspects of the Moreau–Yosida regularization: theoretical preliminaries. SIAM J. Optim. 7, 367–385 (1997)MATH MathSciNet CrossRef
  25.Lewis, A.S., Sendov, H.S.: Nonsmooth analysis of singular values. II: Applications. Set-Valued Anal. 13, 243–264 (2005)MATH MathSciNet CrossRef
  26.Liese, J., Tichý, P.: On best approximations of polynomials in matrices in the matrix 2-norm. SIAM J. Matrix Anal. Appl. 31, 853–863 (2009)MathSciNet CrossRef
  27.Faber, V., Liesen, J., Tichý, P.: On Chebyshev polynomials of matrices. SIAM J. Matrix Anal. Appl. 31, 2205–2221 (2010)MATH CrossRef
  28.Liu, Y.-J., Sun, D.F., Toh, K.-C.: An implementable proximal point algorithmic framework for nuclear norm minimization. Math. Program. Ser. A 133, 399–436 (2012)MATH MathSciNet CrossRef
  29.Meng, F.W., Sun, D.F., Zhao, G.Y.: Semismoothness of solutions to generalized equations and the Moreau–Yosida regularization. Math. Program. Ser. B 104, 561–581 (2005)MATH MathSciNet CrossRef
  30.Moreau, J.J.: Proximite et dualite dans un espace hilbertien. Bull. Soc. Math. France 93, 273–299 (1965)MATH MathSciNet
  31.Qi, L.Q., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. Ser. A 58, 353–367 (1993)MATH MathSciNet CrossRef
  32.Robinson, S.M.: Local structure of feasible sets in nonlinear programming. II: Nondegeneracy. Math. Program. Stud. 22, 217–230 (1984)MATH CrossRef
  33.Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1, 97–116 (1976)MATH MathSciNet CrossRef
  34.Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)MATH CrossRef
  35.Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976)MATH MathSciNet CrossRef
  36.Singer, I.: Best Approximation in Normed Linear Spaces by Elements of Linear Subspaces. Springer, Berlin (1970)MATH CrossRef
  37.Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11–12, 625–653 (1999)MathSciNet CrossRef
  38.Toh, K.-C.: Solving large scale semidefinite programs via an iterative solver on the augmented systems. SIAM J. Optim. 14, 670–698 (2003)MATH MathSciNet CrossRef
  39.Toh, K.-C., Todd, M.J., Tütüncü, R.H.: SDPT3—a MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11–12, 545–581 (1999)CrossRef
  40.Toh, K.-C., Trefethen, L.N.: The Chebyshev polynomials of a matrix. SIAM J. Matrix Anal. Appl. 20, 400–419 (1999)MathSciNet CrossRef
  41.von Neumann, J.: Some matrix inequalities and metrization of metric spaces. Tomsk. Univ. Rev. 1, 286–300 (1937)
  42.Wang, C.J., Sun, D.F., Toh, K.-C.: Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm. SIAM J. Optim. 20, 2994–3013 (2010)MATH MathSciNet CrossRef
  43.Watson, G.A.: Characterization of the subdifferential of some matrix norms. Linear Algebra Appl. 170, 33–45 (1992)MATH MathSciNet CrossRef
  44.Xiao, L., Boyd, S.: Fast linear iterations for distributed averaging. Syst. Control Lett. 53, 65–78 (2004)MATH MathSciNet CrossRef
  45.Yang, J.F., Zhang, Y.: Alternating direction algorithms for \(\ell _1\) -problems in compressive sensing. SIAM J. Sci. Comput. 33, 250–278 (2011)MATH MathSciNet CrossRef
  46.Yosida, K.: Functional Analysis. Springer, Berlin (1964)
  47.Zhao, X.-Y., Sun, D.F., Toh, K.-C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737–1765 (2010)MATH MathSciNet CrossRef
  48.Zietak, K.: Properties of linear approximations of matrices in the spectral norm. Linear Algebra Appl. 183, 41–60 (1993)MATH MathSciNet CrossRef
  
• 作者单位：Caihua Chen (1)
  Yong-Jin Liu (2)
  Defeng Sun (3)
  Kim-Chuan Toh (4)
  
  1. International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, Nanjing, Jiangsu, China
  2. School of Science, Shenyang Aerospace University, Shenyang, China
  3. Department of Mathematics and Risk Management Institute, National University of Singapore, 10 Lower Kent Ridge Road, Singapore, 119076, Singapore
  4. Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, Singapore, 119076, Singapore
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

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. Keywords Spectral norm approximation Spectral operator PPA Semismooth Newton-CG method