×

zbMATH — the first resource for mathematics

A semismooth Newton-CG based dual PPA for matrix spectral norm approximation problems. (English) Zbl 1342.90100
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.

MSC:
90C06 Large-scale problems in mathematical programming
90C25 Convex programming
65F99 Numerical linear algebra
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000) · Zbl 0966.49001
[2] Boyd, S; Diaconis, P; Sun, J; Xiao, L, Fastest mixing Markov chain on a path, Am. Math. Mon., 113, 70-74, (2006) · Zbl 1135.60046
[3] Boyd, S; Diaconis, P; Xiao, L, Fastest mixing Markov chain on a graph, SIAM Rev., 46, 667-689, (2004) · Zbl 1063.60102
[4] Chen, CH; He, BS; Yuan, XM, Matrix completion via alternating direction methods, IMA J. Numer. Anal., 32, 227-245, (2012) · Zbl 1236.65043
[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) · Zbl 1066.90081
[6] Clarke, F.H.: Optimization and Nonsmooth Analysis, 2nd edn. SIAM, Philadelphia (1990) · Zbl 0696.49002
[7] Davis, T.A., Hu, Y.: University of Florida sparse matrix collection (2009) · Zbl 1071.90026
[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, DF; Toh, K-C, An introduction to a class of matrix cone programming, Math. Program. Ser. A, 144, 141-179, (2014) · Zbl 1301.65043
[10] Eckstein, J; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program. Ser. A, 55, 293-318, (1992) · Zbl 0765.90073
[11] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. II. Springer, New York (2003) · Zbl 1062.90002
[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) · Zbl 0352.65034
[13] Glowinski, R., Tallec, P.L.: Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia (1989) · Zbl 0698.73001
[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) · Zbl 0368.65053
[15] Greenbaum, A; Trefethen, LN, GMRES/CR and Arnoldi/Lanczos as matrix approximation problems, SIAM J. Sci. Comput., 15, 359-368, (1994) · Zbl 0806.65031
[16] Ha, CD, A generalization of the proximal point algorithm, SIAM J. Control Optim., 28, 503-512, (1990) · Zbl 0699.49037
[17] He, BS; Liao, L-Z; Han, DR; Yang, H, A new inexact alternating directions method for monotone variational inequalities, Math. Program. Ser. A, 92, 103-118, (2002) · Zbl 1009.90108
[18] Held, M; Wolfe, P; Crowder, HP, Validation of subgradient optimization, Math. Program., 6, 62-88, (1974) · Zbl 0284.90057
[19] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, vols. I and II. Springer, Berlin (1993) · Zbl 0795.49002
[20] Hiriart-Urruty, J-B; Strodiot, J-J; Nguyen, VH, Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data, Appl. Math. Optim., 11, 43-56, (1984) · Zbl 0542.49011
[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) · Zbl 1009.90108
[22] Jiang, KF; Sun, DF; Toh, KC, A partial proximal point algorithm for nuclear norm regularized matrix least squares problems, Math. Program. Comput., 6, 281-325, (2014) · Zbl 1327.90109
[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) · Zbl 1297.90085
[24] Lemaréchal, C; Sagastizábal, C, Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries, SIAM J. Optim., 7, 367-385, (1997) · Zbl 0876.49019
[25] Lewis, AS; Sendov, HS, Nonsmooth analysis of singular values. II: applications, Set-Valued Anal., 13, 243-264, (2005) · Zbl 1129.49026
[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) · Zbl 1190.41011
[27] Faber, V; Liesen, J; Tichý, P, On Chebyshev polynomials of matrices, SIAM J. Matrix Anal. Appl., 31, 2205-2221, (2010) · Zbl 1206.41004
[28] Liu, Y-J; Sun, DF; Toh, K-C, An implementable proximal point algorithmic framework for nuclear norm minimization, Math. Program. Ser. A, 133, 399-436, (2012) · Zbl 1262.90125
[29] Meng, FW; Sun, DF; Zhao, GY, Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization, Math. Program. Ser. B, 104, 561-581, (2005) · Zbl 1093.90059
[30] Moreau, JJ, Proximite et dualite dans un espace hilbertien, Bull. Soc. Math. France, 93, 273-299, (1965) · Zbl 0136.12101
[31] Qi, LQ; Sun, J, A nonsmooth version of newton’s method, Math. Program. Ser. A, 58, 353-367, (1993) · Zbl 0780.90090
[32] Robinson, SM, Local structure of feasible sets in nonlinear programming. II: nondegeneracy, Math. Program. Stud., 22, 217-230, (1984) · Zbl 0573.90075
[33] Rockafellar, RT, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 97-116, (1976) · Zbl 0402.90076
[34] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[35] Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898, (1976) · Zbl 0358.90053
[36] Singer, I.: Best Approximation in Normed Linear Spaces by Elements of Linear Subspaces. Springer, Berlin (1970) · Zbl 0197.38601
[37] Sturm, JF, Using sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11-12, 625-653, (1999) · Zbl 0973.90526
[38] Toh, K-C, Solving large scale semidefinite programs via an iterative solver on the augmented systems, SIAM J. Optim., 14, 670-698, (2003) · Zbl 1071.90026
[39] Toh, K-C; Todd, MJ; Tütüncü, RH, SDPT3—a MATLAB software package for semidefinite programming, version 1.3, Optim. Methods Softw., 11-12, 545-581, (1999) · Zbl 0997.90060
[40] Toh, K-C; Trefethen, LN, The Chebyshev polynomials of a matrix, SIAM J. Matrix Anal. Appl., 20, 400-419, (1999) · Zbl 0922.65019
[41] Neumann, J, Some matrix inequalities and metrization of metric spaces, Tomsk. Univ. Rev., 1, 286-300, (1937)
[42] Wang, CJ; Sun, DF; Toh, K-C, Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm, SIAM J. Optim., 20, 2994-3013, (2010) · Zbl 1211.90130
[43] Watson, GA, Characterization of the subdifferential of some matrix norms, Linear Algebra Appl., 170, 33-45, (1992) · Zbl 0751.15011
[44] Xiao, L; Boyd, S, Fast linear iterations for distributed averaging, Syst. Control Lett., 53, 65-78, (2004) · Zbl 1157.90347
[45] Yang, JF; Zhang, Y, Alternating direction algorithms for \(ℓ _1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 250-278, (2011) · Zbl 1256.65060
[46] Yosida, K.: Functional Analysis. Springer, Berlin (1964) · Zbl 0152.32102
[47] Zhao, X-Y; Sun, DF; Toh, K-C, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optim., 20, 1737-1765, (2010) · Zbl 1213.90175
[48] Zietak, K, Properties of linear approximations of matrices in the spectral norm, Linear Algebra Appl., 183, 41-60, (1993) · Zbl 0770.15011
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.