Abstract
In this paper, we propose two feasible methods based on projections using a curvilinear search for solving optimization problems with orthogonality constraints. In one of them we apply a projected Adams–Moulton-like update scheme. All our algorithms compute the SVD decomposition in each iteration to preserve feasibility. Additionally, we present some convergence results. Finally, we perform numerical experiments with simulated problems; and analyze the performance of the proposed methods compared with state-of-the-art algorithms.
Similar content being viewed by others
Notes
The tool-box manopt is available in http://www.manopt.org/.
The tool-box manopt is available in http://www.manopt.org/.
References
Absil PA, Malick J (2012) Projection-like retractions on matrix manifolds. SIAM J Optim 22(1):135–158
Absil PA, Mahony R, Sepulchre R (2007) Optimization algorithms on matrix manifolds. Princeton University Press, Princeton NJ, USA. ISBN:0691132984; 9780691132983
Barzilai J, Borwein JM (1988) Two-point step size gradient methods. IMA J Numer Anal 8(1):141–148
Boumal N, Mishra B, Absil PA, Sepulchre R (2014) Manopt, a Matlab toolbox for optimization on manifolds. J Mach Learn Res 15(1):1455–1459
Dai YH, Fletcher R (2005) Projected Barzilai–Borwein methods for large-scale box-constrained quadratic programming. Numerische Mathematik 100(1):21–47
d’Aspremont A, El Ghaoui L, Jordan MI, Lanckriet GR (2007) A direct formulation for sparse PCA using semidefinite programming. SIAM Rev 49(3):434–448
Edelman A, Arias TA, Smith ST (1998) The geometry of algorithms with orthogonality constraints. SIAM J Matrix Anal Appl 20(2):303–353
Eldén L, Park H (1999) A Procrustes problem on the Stiefel manifold. Numerische Mathematik 82(4):599–619
Francisco J, Martini T (2014) Spectral projected gradient method for the procrustes problem. TEMA (São Carlos) 15(1):83–96
Francisco J, Bazán FV, Mendonça MW (2017) Non-monotone algorithm for minimization on arbitrary domains with applications to large-scale orthogonal procrustes problem. Appl Numer Math 112:51–64
Gallivan KA, Absil P (2010) Note on the convex hull of the Stiefel manifold. Technical note
Golub GH, Van Loan CF (1996) Matrix computations. 3rd edn. Johns Hopkins University Press, Baltimore, MD, USA. ISBN:0801854148
Grubisi I, Pietersz R (2007) Efficient rank reduction of correlation matrices. Linear Algebra Appl 422(2):629–653
Hiriart-Urruty JB (1982) At what points is the projection mapping differentiable? Am Math Mon 89(7):456–458
Holmes RB (1973) Smoothness of certain metric projections on Hilbert space. Trans Am Math Soc 184:87–100
Joho M, Mathis H (2002) Joint diagonalization of correlation matrices by using gradient methods with application to blind signal separation. In: Sensor array and multichannel signal processing workshop proceedings, 2002, IEEE, pp 273–277
Journée M, Nesterov Y, Richtárik P, Sepulchre R (2010) Generalized power method for sparse principal component analysis. J Mach Learn Res 11:517–553
Kokiopoulou E, Chen J, Saad Y (2011) Trace optimization and eigenproblems in dimension reduction methods. Numer Linear Algebra Appl 18(3):565–602
Koonin SE, Meredith DC (1990) Computational physics: Fortran version. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA. ISBN:0201127792; 9780201127799
Liu Y-F, Dai Y-H, Luo ZQ (2011) 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. doi:10.1109/SPAWC.2011.5990455
Manton JH (2002) Optimization algorithms exploiting unitary constraints. IEEE Trans Signal Process 50(3):635–650
Martin RM (2004) Electronic structure: basic theory and practical methods. Cambridge University Press, Cambridge, UK. ISBN:0521782856
Pietersz R 4, Groenen PJ (2004) Rank reduction of correlation matrices by majorization. Quant Finance 4(6):649–662
Raydan M (1997) The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J Optim 7(1):26–33
Rebonato R, Jäckel P (1999) The most general methodology to create a valid correlation matrix for risk management and option pricing purposes. J Risk 2(2):17–27
Saad Y (1992) Numerical methods for large eigenvalue problems. Manchester University Press, Manchester, UK
Sato H (2014) Riemannian Newton’s method for joint diagonalization on the Stiefel manifold with application to ICA. arXiv:1403.8064 (preprint)
Schönemann PH (1966) A generalized solution of the orthogonal procrustes problem. Psychometrika 31(1):1–10
Szabo A, Ostlund NS (2012) Modern quantum chemistry: introduction to advanced electronic structure theory. In: Dover books on chemistry. Dover Publications, Mineola, New York
Theis FJ, Cason TP, Absil P-A (2009) Soft dimension reduction for ICA by joint diagonalization on the Stiefel manifold. In: Adali T, Jutten C, Romano JMT, Barros AK (eds) Independent Component Analysis and Signal Separation: 8th International Conference, ICA 2009, Paraty, Brazil, March 15–18, 2009. Proceedings, Springer, Berlin, Heidelberg, pp 354–361
Wen Z, Yin W (2013) A feasible method for optimization with orthogonality constraints. Math Program 142(1–2):397–434
Yang C, Meza JC, Wang LW (2006) A constrained optimization algorithm for total energy minimization in electronic structure calculations. J Comput Phys 217(2):709–721
Yang C, Meza JC, Wang LW (2007) A trust region direct constrained minimization algorithm for the Kohn–Sham equation. SIAM J Sci Comput 29(5):1854–1875
Yang C, Meza JC, Lee B, Wang LW (2009) KSSOLVoa MATLAB toolbox for solving the Kohn–Sham equations. ACM Trans Math Softw (TOMS) 36(2):10
Zhang H, Hager WW (2004) A nonmonotone line search technique and its application to unconstrained optimization. SIAM J Optim 14(4):1043–1056
Zhang Z, Du K (2006) Successive projection method for solving the unbalanced procrustes problem. Sci China Ser A 49(7):971–986
Zhao Z, Bai ZJ, Jin XQ (2015) A Riemannian Newton algorithm for nonlinear eigenvalue problems. SIAM J Matrix Anal Appl 36(2):752–774
Zou H, Hastie T, Tibshirani R (2006) Sparse principal component analysis. J Comput Graph Stat 15(2):265–286
Acknowledgements
This work was supported in part by CONACYT (Mexico), Grant 258033.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Joerg Fliege.
Rights and permissions
About this article
Cite this article
Dalmau Cedeño, O.S., Oviedo Leon, H.F. Projected nonmonotone search methods for optimization with orthogonality constraints. Comp. Appl. Math. 37, 3118–3144 (2018). https://doi.org/10.1007/s40314-017-0501-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40314-017-0501-6
Keywords
- Constrained optimization
- Orthogonality constraints
- Non-monotone algorithm
- Stiefel manifold
- Optimization on manifolds