Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A feasible method for optimization with orthogonality constraints

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

Minimization with orthogonality constraints (e.g., \(X^\top X = I\)) and/or spherical constraints (e.g., \(\Vert x\Vert _2 = 1\)) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. To deal with these difficulties, we apply the Cayley transform—a Crank-Nicolson-like update scheme—to preserve the constraints and based on it, develop curvilinear search algorithms with lower flops compared to those based on projections and geodesics. The efficiency of the proposed algorithms is demonstrated on a variety of test problems. In particular, for the maxcut problem, it exactly solves a decomposition formulation for the SDP relaxation. For polynomial optimization, nearest correlation matrix estimation and extreme eigenvalue problems, the proposed algorithms run very fast and return solutions no worse than those from their state-of-the-art algorithms. For the quadratic assignment problem, a gap 0.842 % to the best known solution on the largest problem “tai256c” in QAPLIB can be reached in 5 min on a typical laptop.

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

Access this article

Log in via an institution

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.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. Do not confuse \(\nabla \mathcal F (X)\) with \(G=\mathcal D \mathcal F (X)\).

References

  1. Absil, P.-A., Baker, C.G., Gallivan, K.A.: Trust-region methods on Riemannian manifolds. Found. Comput. Math. 7, 303–330 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008)

    MATH  Google Scholar 

  3. Adler, R.L., Dedieu, J.-P., Margulies, J.Y., Martens, M., Shub, M.: Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal. 22, 359–390 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  4. Baker, C.G., Absil, P.-A., Gallivan, K.A.: An implicit trust-region method on Riemannian manifolds. IMA J. Numer. Anal. 28, 665–689 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  5. Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bencteux, G., Cancés, E., Hager, W.W., Le Bris, C.: Analysis of a quadratic programming decomposition algorithm. SIAM J. Numer. Anal. 47, 4517–4539 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. Benson, S.J., Ye, Y., Zhang, X.: Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10, 443–461 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  8. Boufounos, P., Baraniuk, R.: 1-bit Compressive Sensing. Conf. on. Info. Science and Systems (CISS), Princeton (2008)

    Google Scholar 

  9. Brace, I., Manton, J.H.: An improved BFGS-on-manifold algorithm for computing weighted low rank approximations. In Proceedings of the 17th International Symposium on Mathematical Theory of Networks and Systems, pp. 1735–1738 (2006)

  10. Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95, 329–357 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  11. Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB: a quadratic assignment problem library. J. Global Optim. 10, 391–403 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  12. Cancès, E., Le Bris, C., Lions, P.-L.: Molecular simulation and related topics: some open mathematical problems. Nonlinearity 21, T165–T176 (2008)

    Article  MATH  Google Scholar 

  13. Chang, G.J., Huang, L.-H., Yeh, H.-G.: On the rank of a cograph. Linear Algebra Appl. 429, 601–605 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Dai, Y.-H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100, 21–47 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  15. d’Aspremont, A., El Ghaoui, L., Jordan, M., Lanckriet, G.R.: A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49, 434–448 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  16. Davis, T.A.: The University of Florida Sparse Matrix Collection, Technical Report. University of Florida, Florida (2010)

  17. Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking Optimization Software with cops 3.0, Technical Report. Mathematics and Computer Science Division, Argonne National Laboratory (February 2004)

  18. Edelman, A., Arias, T.A., Smith, S.T.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20, 303–353 (1999)

    Article  MathSciNet  Google Scholar 

  19. Fletcher, R.: Practical Methods of Optimization. John Wiley & Sons (2000)

  20. Francisco, J.B., Martínez, J.M., Martínez, L., Pisnitchenko, F.: Inexact restoration method for minimization problems arising in electronic structure calculations. Comput. Opt. Appl. 10(3), 555–590 (2011)

    Google Scholar 

  21. Friedland, S., Nocedal, J., Overton, M.L.: The formulation and analysis of numerical methods for inverse eigenvalue problems. SIAM J. Numer. Anal. 24, 634–667 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  22. Gao, Y., Sun, D.: A Majorized Penalty Approach for Calibrating Rank Constrained Correlation Matrix Problems, Technical Report. National University of Singapore (2010)

  23. Goldfarb, D., Wen, Z., Yin, W.: A curvilinear search method for the p-harmonic flow on spheres. SIAM J. Imaging Sci. 2, 84–109 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  24. Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore (1996)

    MATH  Google Scholar 

  25. Grippo, L., Palagi, L., Piccialli, V.: An unconstrained minimization method for solving low-rank sdp relaxations of the maxcut problem. Math. Program., 1–28 (2009). doi:10.1007/s10107-009-0275-8

  26. Grubišić, I., Pietersz, R.: Efficient rank reduction of correlation matrices. Linear Algebra Appl. 422, 629–653 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  27. He, S., Li, Z., Zhang, S.: Approximation algorithms for homogeneous polynomial optimization with quadratic constraints. Math. Program. 125, 353–383 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  28. Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10, 673–696 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  29. Helmke, U., Moore, J.B.: Optimization and dynamical systems. In: Brockett, R. (ed.) Communications and Control Engineering Series. Springer, London (1994)

    Google Scholar 

  30. Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)

    Book  MATH  Google Scholar 

  31. Kokiopoulou, E., Chen, J., Saad, Y.: Trace Optimization and Eigenproblems in Dimension Reduction Methods, Technical report. University of Minnesota (2010)

  32. Kružík, M., Prohl, A.: Recent developments in the modeling, analysis, and numerics of ferromagnetism. SIAM Rev. 48, 439–483 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  33. Laska, J.N., Wen, Z., Yin, W., Baraniuk, R.G.: Trust, but Verify: Fast and Accurate Signal Recovering from 1-bit Compressive Measurements, Technical report. Rice University (2010)

  34. Lu, Z., Zhang, Y.: An Augmented Lagrangian Approach for Sparse Principal Component, Analysis, arXiv:0907.2079 (2009)

  35. Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20, 336–356 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  36. Moré, J.J., Thuente, D.J.: Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 286–307 (1994)

    Article  MATH  Google Scholar 

  37. Nemirovski, A.: Sums of random symmetric matrices and quadratic optimization under orthogonality constraints. Math. Program. 109, 283–317 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  38. Nie, J.: Regularization Methods for Sum of Squares Relaxations in Large Scale Polynomial Optimization, Technical report. Department of Mathematics, UCSD (2009)

  39. Nishimori, Y., Akaho, S.: Learning algorithms utilizing quasi-geodesic flows on the stiefel manifold. Neurocomputing 67, 106–135 (2005)

    Article  Google Scholar 

  40. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006)

    Google Scholar 

  41. Owren, B., Welfert, B.: The Newton iteration on Lie groups. BIT 40, 121–145 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  42. Pietersz, R., Groenen, P.J.F.: Rank reduction of correlation matrices by majorization. Quant. Finance 4, 649–662 (2004)

    Article  MathSciNet  Google Scholar 

  43. Qi, C., Gallivan, K.A., Absil, P.-A.: Riemannian BFGS algorithm with applications. In: Diehl, M., Glineur, F., Jarlebring, E., Michiels, W. (eds.) Recent Advances in Optimization and its Applications in Engineering. Springer, Berlin (2010)

    Google Scholar 

  44. Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  45. Rebonato, R., Jäckel, P.: The most general methodology to create a valid correlation matrix for risk management and option pricing purposes. J. Risk 2, 17–27 (1999)

    Google Scholar 

  46. Roy, R., Kailath, T.: Esprit—estimation of signal parameters via rotational invariance techniques. IEEE Trans. Acoust, Speech, Signal Process. 37(7), 984–995 (1989)

    Google Scholar 

  47. Schneider, R., Rohwedder, T., Neelov, A., Blauert, J.: Direct minimization for calculating invariant subspaces in density functional computations of the electronic structure. J. Comput. Math. 27, 360–387 (2009)

    MathSciNet  MATH  Google Scholar 

  48. Shub, M.: Some remarks on dynamical systems and numerical analysis. In Dynamical Systems and Partial Differential Equations (Caracas, 1984), pp. 69–91. Univ. Simon Bolivar, Caracas (1986)

  49. Simon, D., Abell, J.: A majorization algorithm for constrained correlation matrix approximation. Linear Algebra Appl. 432, 1152–1164 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  50. Smith, S.T.: Geometric Optimization Methods for Adaptive Filtering. ProQuest LLC, Ann Arbor, MI. PhD Thesis, Harvard University (1993)

  51. Smith, S.T.: Optimization techniques on Riemannian manifolds. In Hamiltonian and Gradient Flows, Algorithms and Control, vol. 3, pp. 113–136. Fields Inst. Commun., Amer. Math. Soc., Providence, RI (1994)

  52. Sun, W., Yuan, Y.-X.: Optimization Theory and Methods, vol. 1 of Springer Optimization and its Applications. Springer, New York (2006)

    Google Scholar 

  53. Udrişte, C.: Convex Functions and Optimization Methods on Riemannian Manifolds, vol. 297 of Mathematics and its Applications. Kluwer Academic Publishers Group, Dordrecht (1994)

    Book  Google Scholar 

  54. Vese, L.A., Osher, S.J.: Numerical methods for \(p\)-harmonic flows and applications to image processing. SIAM J. Numer. Anal. 40, 2085–2104 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  55. Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106, 25–57 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  56. Ward, J.: Space-Time Adaptive Processing for Airborne Radar, Technical report of MIT (1994)

  57. Weber, V., VandeVondele, J., Hütter, J., Niklasson, A.M.: Direct energy functional minimization under orthogonality constraints. J. Chem. Phys. 128(8), 084113 (2008)

    Google Scholar 

  58. Witten, D.M., Tibshirani, R., Hastie, T.: A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostatistics 10, 515–534 (2009)

    Article  Google Scholar 

  59. Yang, B.: Projection approximation subspace tracking. IEEE Trans. Signal Process. 43, 95–107 (1995)

    Article  MATH  Google Scholar 

  60. Yang, C., Meza, J.C., Lee, B., Wang, L.-W.: Kssolv-a matlab toolbox for solving the kohn-sham equations. ACM Trans. Math. Softw. 36, 1–35 (2009)

    Article  MathSciNet  Google Scholar 

  61. Yang, C., Meza, J.C., Wang, L.-W.: A constrained optimization algorithm for total energy minimization in electronic structure calculations. J. Comput. Phys. 217, 709–721 (2006)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  63. Zhao, X., Sun, D., Toh, K.: A Newton-CG augmented lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737–1765 (2010)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We would like to thank Yin Zhang, Xin Liu, and Shiqian Ma for the discussions on optimization conditions, Jiawang Nie for the discussions on polynomial optimization, Chao Yang for the discussions on the Kohn–Sham equation, as well as Franz Rendl and Etienne de Klerk for their comments on QAPs. We would also like to thank Defeng Sun and Yan Gao for sharing their code PenCorr and their improvement for Major, as well as sharing the test data for the nearest correlation matrix problem. The authors are grateful to Adrian Lewis, the Associate Editor and three anonymous referees for their detailed and valuable comments and suggestions.

Author information

Authors and Affiliations

  1. Department of Mathematics and Institute of Natural Sciences, Shanghai Jiaotong University, Shanghai, China

    Zaiwen Wen

  2. Department of Computational and Applied Mathematics, Rice University, Houston, TX, 77005, USA

    Wotao Yin

Authors
  1. Zaiwen Wen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wotao Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zaiwen Wen.

Additional information

The work of Z. Wen was supported in part by NSF DMS-0439872 through UCLA IPAM and NSFC grant 11101274. The work of W. Yin was supported in part by NSF grants DMS-07-48839 and ECCS-10-28790, and ONR Grant N00014-08-1-1101.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wen, Z., Yin, W. A feasible method for optimization with orthogonality constraints. Math. Program. 142, 397–434 (2013). https://doi.org/10.1007/s10107-012-0584-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0584-1

Keywords

Mathematics Subject Classification (2010)

Search

Navigation