Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Projected nonmonotone search methods for optimization with orthogonality constraints

  • Published:
Computational and Applied Mathematics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

Notes

  1. The tool-box manopt is available in http://www.manopt.org/.

  2. 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    MATH  Google Scholar 

  • Dai YH, Fletcher R (2005) Projected Barzilai–Borwein methods for large-scale box-constrained quadratic programming. Numerische Mathematik 100(1):21–47

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • Edelman A, Arias TA, Smith ST (1998) The geometry of algorithms with orthogonality constraints. SIAM J Matrix Anal Appl 20(2):303–353

    Article  MathSciNet  MATH  Google Scholar 

  • Eldén L, Park H (1999) A Procrustes problem on the Stiefel manifold. Numerische Mathematik 82(4):599–619

    Article  MathSciNet  MATH  Google Scholar 

  • Francisco J, Martini T (2014) Spectral projected gradient method for the procrustes problem. TEMA (São Carlos) 15(1):83–96

    Article  MathSciNet  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • 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

    MathSciNet  MATH  Google Scholar 

  • Kokiopoulou E, Chen J, Saad Y (2011) Trace optimization and eigenproblems in dimension reduction methods. Numer Linear Algebra Appl 18(3):565–602

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Zhang H, Hager WW (2004) A nonmonotone line search technique and its application to unconstrained optimization. SIAM J Optim 14(4):1043–1056

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang Z, Du K (2006) Successive projection method for solving the unbalanced procrustes problem. Sci China Ser A 49(7):971–986

    Article  MathSciNet  MATH  Google Scholar 

  • Zhao Z, Bai ZJ, Jin XQ (2015) A Riemannian Newton algorithm for nonlinear eigenvalue problems. SIAM J Matrix Anal Appl 36(2):752–774

    Article  MathSciNet  MATH  Google Scholar 

  • Zou H, Hastie T, Tibshirani R (2006) Sparse principal component analysis. J Comput Graph Stat 15(2):265–286

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work was supported in part by CONACYT (Mexico), Grant 258033.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Oscar Susano Dalmau Cedeño.

Additional information

Communicated by Joerg Fliege.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40314-017-0501-6

Keywords

Mathematics Subject Classification

Navigation