×

A framework of constraint preserving update schemes for optimization on Stiefel manifold. (English) Zbl 1325.49037

Summary: This paper considers optimization problems on the Stiefel manifold \(X^{\mathsf{T}}X=I_p\), where \(X\in \mathbb{R}^{n \times p}\) is the variable and \(I_p\) is the \(p\)-by-\(p\) identity matrix. A framework of constraint preserving update schemes is proposed by decomposing each feasible point into the range space of \(X\) and the null space of \(X^{\mathsf{T}}\). While this general framework can unify many existing schemes, a new update scheme with low complexity cost is also discovered. Then, we study a feasible Barzilai-Borwein-like method under the new update scheme. The global convergence of the method is established with an adaptive nonmonotone line search. The numerical tests on the nearest low-rank correlation matrix problem, the Kohn-Sham total energy minimization and a specific problem from statistics demonstrate the efficiency of the new method. In particular, the new method performs remarkably well for the nearest low-rank correlation matrix problem in terms of speed and solution quality and is considerably competitive with the widely used SCF iteration for the Kohn-Sham total energy minimization.

MSC:

49M37 Numerical methods based on nonlinear programming
49Q99 Manifolds and measure-geometric topics
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming

Software:

SparseMatrix; KSSOLV
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Abrudan, T; Eriksson, J; Koivunen, V, Steepest descent algorithms for optimization under unitary matrix constraint, IEEE Trans. Signal Process., 56, 1134-1147, (2008) · Zbl 1390.90510
[2] Abrudan, T; Eriksson, J; Koivunen, V, Conjugate gradient algorithm for optimization under unitary matrix constraint, Sig. Process., 89, 1704-1714, (2009) · Zbl 1178.94048
[3] Absil, P.A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008) · Zbl 1147.65043
[4] Absil, PA; Malick, J, Projection-like retractions on matrix manifolds, SIAM J. Optim., 22, 135-158, (2012) · Zbl 1248.49055
[5] Andreani, R; Birgin, EG; Martínez, JM; Schuverdt, ML, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18, 1286-1309, (2007) · Zbl 1151.49027
[6] Balogh, J; Csendes, T; Rapcsák, T, Some global optimization problems on Stiefel manifolds, J. Global Optim., 30, 91-101, (2004) · Zbl 1136.90507
[7] Barzilai, J; Borwein, JM, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 141-148, (1988) · Zbl 0638.65055
[8] Birgin, EG; Martínez, JM; Raydan, M, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10, 1196-1211, (2000) · Zbl 1047.90077
[9] Bolla, M; Michaletzky, G; Tusnády, G; Ziermann, M, Extrema of sums of heterogeneous quadratic forms, Linear Algebra Appl., 269, 331-365, (1998) · Zbl 0893.65030
[10] Borsdorf, R.: An Algorithm for Finding the Optimal Embedding of a Symmetric Matrix Into the Set of Diagonal Matrices. Technical report, University of Manchester (2012) · Zbl 1281.49030
[11] Dai, YH; Fletcher, R, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numer. Math., 100, 21-47, (2005) · Zbl 1068.65073
[12] Dai, YH; Fletcher, R, New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds, Math. Program., 106, 403-421, (2006) · Zbl 1134.90030
[13] Dai, YH; Hager, WW; Schittkowski, K; Zhang, HC, The cyclic Barzilai-Borwein method for unconstrained optimization, IMA J. Numer. Anal., 26, 604-627, (2006) · Zbl 1147.65315
[14] Dai, YH; Liao, LZ, R-linear convergence of the Barzilai and Borwein gradient method, IMA J. Numer. Anal., 22, 1-10, (2002) · Zbl 1002.65069
[15] Dai, YH; Zhang, HC, Adaptive two-point stepsize gradient algorithm, Numer. Algorithms, 27, 377-385, (2001) · Zbl 0992.65063
[16] d’Aspremont, A; Ei Ghaoui, L; Jordan, MI; Lanckriet, GR, A direct formulation for sparse PCA using semidefinite programming, SIAM Rev., 49, 434-448, (2007) · Zbl 1128.90050
[17] Davis, T., Hu, Y.F.: University of Florida sparse matrix collection. Technical report, University of Florida (2009) · Zbl 1365.65123
[18] Edelman, A; Arias, TA; Smith, ST, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20, 303-353, (1998) · Zbl 0928.65050
[19] Eldén, L; Park, H, A procrustes problem on the Stiefel manifold, Numer. Math., 82, 599-619, (1999) · Zbl 0934.65052
[20] Fletcher, R; Qi, LQ (ed.); Teo, K (ed.); Yang, XQ (ed.), On the Barzilai-Borwein method, No. 96, 235-256, (2005), US · Zbl 1118.90318
[21] Flury, B.: Common principal components & related multivariate models. Wiley, New York (1988) · Zbl 1081.62535
[22] Gao, Y., Sun, D.F.: A majorized penalty approach for calibrating rank constrained correlation matrix problems. Technical report, National University of Signapore (2010)
[23] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins Univerisity Press, Maryland (1996) · Zbl 0865.65009
[24] Grippo, L; Lampariello, F; Lucidi, S, A nonmonotone line search technique for newton’s method, SIAM J. Numer. Anal., 23, 707-716, (1986) · Zbl 0616.65067
[25] Grubišić, I; Pietersz, R, Efficient rank reduction of correlation matrices, Linear Algebra Appl., 422, 629-653, (2007) · Zbl 1112.65036
[26] Jiang, B., Dai, Y.H.: A framework of constraint preserving update schemes for optimization on Stiefel manifold. Technical report, Institue of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Sciences, Chinese Academy of Sicences (2012) · Zbl 1325.49037
[27] Jiang, B; Dai, YH, Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems, Optim. Methods Softw., 28, 756-784, (2013) · Zbl 1302.90209
[28] Jiang, KF; Sun, DF; Toh, KC, An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP, SIAM J. Optim., 22, 1042-1064, (2012) · Zbl 1401.90120
[29] Joho, M., Mathis, H.: Joint diagonalization of correlation matrices by using gradient methods with application to blind signal separation. In: IEEE Proceedings of the Sensor Array and Multichannel Signal Processing Workshop, 2002, pp. 273-277 (2002) · Zbl 1068.65073
[30] Journée, M; Nesterov, Y; Richtárik, P; Sepulchre, R, Generalized power method for sparse principal component analysis, J. Mach. Learn. Res., 11, 517-553, (2010) · Zbl 1242.62048
[31] Lai, R; Wen, Z; Yin, W; Gu, X; Lui, LM, Folding-free global conformal mapping for genus-0 surfaces by harmonic energy minimization, J. Sci. Comput., 58, 705-725, (2014) · Zbl 1298.30007
[32] Li, L; Toh, KC, An inexact interior point method for L1-regularized sparse covariance selection, Math. Program. Comput., 2, 291-315, (2010) · Zbl 1208.90131
[33] Li, QN; Qi, HD, A sequential semismooth Newton method for the nearest low-rank correlation matrix problem, SIAM J. Optim., 21, 1-26, (2011)
[34] Liu, Y.F., Dai, Y.H., Luo, Z.Q.: On the complexity of leakage interference minimization for interference alignment. In: 2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, pp. 471-475 (2011) · Zbl 0147.19401
[35] Manton, JH, Optimization algorithms exploiting unitary constraints, IEEE Trans. Signal Process., 50, 635-650, (2002) · Zbl 1369.90169
[36] Nishimori, Y; Akaho, S, Learning algorithms utilizing quasi-geodesic flows on the Stiefel manifold, Neurocomputing, 67, 106-135, (2005)
[37] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006) · Zbl 1104.65059
[38] Peters, S.W., Heath, R.W.: Interference alignment via alternating inimization. In: Proceedings of the 2009 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 2445-2448. IEEE Computer Society (2009)
[39] Pietersz, R; Groenen, PJ, Rank reduction of correlation matrices by majorization, Quant. Financ., 4, 649-662, (2004)
[40] Qi, HD; Sun, DF, A quadratically convergent Newton method for computing the nearest correlation matrix, SIAM J. Matrix Anal. Appl., 28, 360-385, (2007) · Zbl 1120.65049
[41] Rapcsák, T.: On minimization of sums of heterogeneous quadratic functions on Stiefel manifolds. In: Migdalas, A., Pardalos, P.M., Värbrand, P. (eds.) From Local to Global Optimization, vol. 53, pp. 277-290. Kluwer Academic Publishers (2001) · Zbl 0934.65052
[42] Rapcsák, T, On minimization on Stiefel manifolds, Eur. J. Oper. Res., 143, 365-376, (2002) · Zbl 1058.90064
[43] Raydan, M, On the Barzilai and Borwein choice of steplength for the gradient method, IMA J. Numer. Anal., 13, 321-326, (1993) · Zbl 0778.65045
[44] Raydan, M, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim., 7, 26-33, (1997) · Zbl 0898.90119
[45] Rebonato, R; Jäckel, P, The most general methodology to creating a valid correlation matrix for risk management and option pricing purposes, J. Risk, 2, 17-27, (1999)
[46] Saad, Y.: Numerical Methods for Large Eigenvalue Problems. Manchester University Press, Manchester (1992) · Zbl 0991.65039
[47] Savas, B; Lim, LH, Quasi-Newton methods on Grassmannians and multilinear approximations of tensors, SIAM J. Sci. Comput., 32, 3352-3393, (2010) · Zbl 1226.65058
[48] Schönemann, PH, A generalized solution of the orthogonal procrustes problem, Psychometrika, 31, 1-10, (1966) · Zbl 0147.19401
[49] Stiefel, E, Richtungsfelder und fernparallelismus in n-dimensionalen mannigfaltigkeiten, Comment. Math. Helv., 8, 305-353, (1935) · Zbl 0014.41601
[50] Sun, W.Y., Yuan, Y.X.: Optimization Theory and Methods, Springer Optimization and Its Applications, vol. 1. Springer, New York (2006) · Zbl 1129.90002
[51] Theis, F; Cason, T; Absil, PA; Adali, T (ed.); Jutten, C (ed.); Romano, JMT (ed.); Barros, A (ed.), Soft dimension reduction for ica by joint diagonalization on the Stiefel manifold, No. 5441, 354-361, (2009), Berlin
[52] Toint, PL, Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints, Math. Program., 77, 69-94, (1997) · Zbl 0891.90153
[53] Wen, Z; Yin, W, A feasible method for optimization with orthogonality constraints, Math. Program., 142, 397-434, (2013) · Zbl 1281.49030
[54] Yang, C; Meza, JC; Lee, B; Wang, LW, KSSOLV—a Matlab toolbox for solving the Kohn-Sham equations, ACM Trans. Math. Softw., 36, 1-35, (2009) · Zbl 1364.65112
[55] Yang, C; Meza, JC; Wang, LW, A constrained optimization algorithm for total energy minimization in electronic structure calculations, J. Comput. Phys., 217, 709-721, (2006) · Zbl 1102.81340
[56] Yang, C; Meza, JC; Wang, LW, A trust region direct constrained minimization algorithm for the Kohn-Sham equation, SIAM J. Sci. Comput., 29, 1854-1875, (2007) · Zbl 1154.65340
[57] Zhang, HC; Hager, WW, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14, 1043-1056, (2004) · Zbl 1073.90024
[58] Zhang, LH; Liao, LZ, An alternating variable method for the maximal correlation problem, J. Global Optim., 54, 199-218, (2012) · Zbl 1318.62200
[59] Zhou, B; Gao, L; Dai, YH, Gradient methods with adaptive step-sizes, Comput. Optim. Appl., 35, 69-86, (2006) · Zbl 1121.90099
[60] Zou, H; Hastie, T; Tibshirani, R, Sparse principal component analysis, J. Comput. Graph. Stat., 15, 265-286, (2006)
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.