\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

An alternate gradient method for optimization problems with orthogonality constraints

  • * Corresponding author: Yakui Huang

    * Corresponding author: Yakui Huang

The second author is supported by NSFC grant 11701137

Abstract Full Text(HTML) Figure(1) / Table(4) Related Papers Cited by
  • In this paper, we propose a new alternate gradient (AG) method to solve a class of optimization problems with orthogonal constraints. In particular, our AG method alternately takes several gradient reflection steps followed by one gradient projection step. It is proved that any accumulation point of the iterations generated by the AG method satisfies the first-order optimal condition. Numerical experiments show that our method is efficient.

    Mathematics Subject Classification: Primary: 65F15, 65K05; Secondary: 90C06.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Numerical results of the AG method with different $ m $

    Table 1.  The results of GP, GR and AG on problem (2) with $ n = 500 $, $ p = 6 $

    cpu iter fun KKT violation feasibility
    GP 3.74 682.0 -91.651414 3.8477E-04 4.0577E-15
    GR 2.40 502.4 -91.646891 3.8305E-04 1.9524E-13
    AG$ (m=2) $ 2.01 433.4 -91.646891 3.8447E-04 4.5582E-15
    AG$ (m=3) $ 2.21 483.4 -91.642235 3.8370E-04 6.2797E-15
    AG$ (m=5) $ 2.34 503.0 -91.646891 3.8142E-04 6.1260E-15
     | Show Table
    DownLoad: CSV

    Table 2.  Numerical results on problem (2) with $ n = 1000 $ and $ \delta = 1 $

    cpu iter fun KKT violation feasibility
    $ p=6 $
    GBB 9.474 734.2 -131.5233622 2.6304E-04 1.7197E-15
    AFBB 13.388 326.3 -131.5249367 1.7790E-03 2.2349E-15
    GP 10.992 939.4 -131.5225679 5.4438E-04 4.3864E-15
    GR 9.764 832.6 -131.5214683 5.4198E-04 1.8122E-13
    AG 8.882 749.9 -131.5221231 5.4445E-04 6.1051E-15
    $ p=10 $
    GBB 11.263 780.5 -218.5897386 4.1310E-04 1.9883E-15
    AFBB 18.575 527.3 -218.5916071 3.2611E-03 2.9976E-15
    GP 15.173 1075.2 -218.5856256 7.0932E-04 6.6001E-15
    GR 11.220 820.6 -218.594843 7.0782E-04 2.3583E-13
    AG 9.986 706.5 -218.5926144 7.0900E-04 8.0173E-15
    $ p=20 $
    GBB 14.344 825.5 -478.6533636 6.3350E-04 1.8762E-15
    AFBB 22.275 465.6 -478.6490255 9.4387E-03 3.4080E-15
    GP 23.287 1251.6 -478.6547359 1.1447E-03 1.2903E-14
    GR 15.833 915.2 -478.6564912 1.1402E-03 6.0783E-13
    AG 15.426 872.9 -478.6534441 1.1421E-03 1.6879E-14
    $ p=30 $
    GBB 31.84 1226.0 -1245.746827 1.5488E-03 2.1434E-15
    AFBB 48.68 661.4 -1245.748650 1.8988E-02 5.0980E-15
    GP 21.86 784.0 -1245.750942 8.4329E-05 1.5679E-14
    GR 17.06 656.8 -1245.750942 7.1151E-05 8.0287E-13
    AG 16.24 602.0 -1245.750942 6.7208E-05 1.5920E-14
    $ p=40 $
    GBB 61.73 2142.0 -5639.853266 9.3744E-03 2.7954E-15
    AFBB 87.39 853.6 -5639.770839 1.2351E-01 5.1548E-15
    GP 29.81 861.2 -5639.853800 7.2273E-05 1.9845E-14
    GR 24.26 693.2 -5639.853800 5.9084E-05 7.8415E-13
    AG 21.82 654.0 -5639.853800 5.7129E-05 1.9641E-14
    $ p=50 $
    GBB 160.670 4324.2 -32893.22537 1.4305E-01 2.4661E-15
    AFBB 195.783 902.0 -32892.54444 6.1956E-01 7.0825E-15
    GP 10.488 234.8 -32893.2292 1.3979E-01 2.3702E-14
    GR 10.261 253.2 -32893.23767 1.3921E-01 7.1360E-13
    AG 8.226 189.8 -32893.23383 1.3910E-01 1.6358E-13
    $ p=60 $
    GBB 181.231 4479.6 -201185.9576 5.2503E-01 2.5522E-15
    AFBB 220.369 889.4 -201182.0639 4.6276E+00 7.5163E-15
    GP 3.832 71.0 -201185.8551 8.6024E-01 2.5309E-14
    GR 5.578 122.2 -201186.0137 7.7927E-01 6.1877E-13
    AG 3.139 63.5 -201185.8558 8.6000E-01 1.6652E-13
     | Show Table
    DownLoad: CSV

    Table 3.  Numerical results on problem (2) with $ n = 1000 $ and $ \delta = 10 $

    cpu iter fun KKT violation feasibility
    $ p=6 $
    GBB 2.350 193.7 -162.4333197 5.1684E-04 1.5849E-15
    AFBB 4.323 168.4 -162.3569464 8.9896E-02 1.0327E-14
    GP 9.625 833.8 -162.4646836 6.9011E-04 4.5461E-15
    GR 7.432 653.8 -162.4753778 6.8193E-04 2.0315E-13
    AG 6.443 572.0 -162.4788103 6.8824E-04 5.2647E-15
    cpu iter fun KKT violation feasibility
    $ p=10 $
    GBB 2.412 212.8 -162.4445186 3.0936E-04 1.6845E-15
    AFBB 4.108 150.2 -162.3883351 9.9274E-02 2.3889E-15
    GP 10.028 892.1 -162.4445179 6.8857E-04 4.8457E-15
    GR 6.242 546.8 -162.4768871 6.8015E-04 1.9881E-13
    AG 5.447 484.1 -162.4667359 6.8719E-04 6.6787E-15
    $ p=20 $
    GBB 8.38 454.0 -1504.964138 2.6761E-03 1.8293E-15
    AFBB 14.92 385.6 -1504.918549 1.6780E-02 3.5068E-15
    GP 7.20 391.8 -1504.918628 1.0776E-04 1.2022E-14
    GR 5.94 337.2 -1504.918628 9.4064E-05 6.5906E-13
    AG 5.61 310.8 -1504.918628 8.8531E-05 1.2883E-14
    $ p=30 $
    GBB 29.689 1243.9 -8613.088591 2.0335E-02 2.2557E-15
    AFBB 43.338 565.2 -8613.038104 1.4066E-01 5.1917E-15
    GP 10.754 401.0 -8613.086436 3.6167E-02 1.5379E-14
    GR 6.938 275.4 -8613.096615 3.6090E-02 8.1878E-13
    AG 6.811 259.9 -8613.096568 3.6147E-02 8.1414E-14
    $ p=40 $
    GBB 66.861 2384.3 -52514.12943 1.0842E-01 2.7336E-15
    AFBB 85.967 657.8 -52513.74516 1.0337E+00 5.2309E-15
    GP 4.311 128.6 -52514.11926 2.2352E-01 1.9552E-14
    GR 5.342 176.4 -52514.09427 2.2260E-01 7.8898E-13
    AG 3.657 114.3 -52514.08076 2.2395E-01 1.4507E-13
    $ p=50 $
    GBB 101.840 2667.2 -323993.0909 5.2023E-01 2.4041E-15
    AFBB 131.354 735.0 -323989.6253 4.9496E+00 7.1751E-15
    GP 2.297 45.4 -323992.3883 1.3801E+00 2.1972E-14
    GR 2.527 59.2 -323992.4399 1.3566E+00 8.8005E-13
    AG 1.867 39.8 -323992.402 1.3720E+00 2.3366E-13
     | Show Table
    DownLoad: CSV

    Table 4.  Numerical results on Kohn-Sham total energy minimization problem

    cpu iter fun KKT violation feasibility
    co2, $ n=2103,p=8 $
    SCF 31.768 17 -35.124396 1.5035E-06 6.5360E-15
    GBB 32.818 53 -35.124396 3.4202E-06 9.5236E-14
    AFBB 35.728 61 -35.124396 1.2646E-06 3.5113E-14
    GP 32.941 46 -35.124396 9.5300E-06 3.8009E-15
    AG 28.840 44 -35.124396 6.0064E-06 2.7404E-15
    c2h6, $ n=2103,p=7 $
    SCF 28.294 18 -14.420491 1.0304E-06 1.5356E-14
    GBB 32.388 51 -14.420491 9.7967E-06 1.0002E-14
    AFBB 32.524 52 -14.420491 4.7573E-06 1.2778E-14
    GP 32.879 50 -14.420491 9.7401E-06 4.2016E-15
    AG 31.951 50 -14.420491 5.9437E-06 4.2785E-15
    benzene, $ n=8047,p=15 $
    SCF 601.321 118 -37.225751 1.9756E-06 6.9301E-14
    GBB 183.137 51 -37.225751 7.4389E-06 8.7418E-14
    AFBB 200.916 58 -37.225751 2.0575E-06 1.7646E-13
    GP 207.944 60 -37.225751 9.6828E-06 8.3590E-15
    AG 200.898 56 -37.225751 4.9222E-06 9.8340E-15
    h2o, $ n=2103,p=4 $
    SCF 20.570 26 -16.440507 9.3011E-07 5.5665E-15
    GBB 28.780 53 -16.440507 9.4006E-06 1.8356E-14
    AFBB 30.198 59 -16.440507 4.8143E-07 1.9661E-14
    GP 26.768 51 -16.440507 6.6455E-06 6.5909E-15
    AG 23.697 44 -16.440507 8.0030E-06 4.8574E-14
    c12h26, $ n=5709,p=37 $
    SCF 418.609 55 -81.536092 3.9309E-06 3.8821E-14
    GBB 283.230 66 -81.536092 9.6402E-06 6.5371E-14
    AFBB 269.654 61 -81.536092 6.0986E-06 1.0709E-13
    GP 301.821 71 -81.536092 5.9451E-06 1.4570E-14
    AG 261.392 60 -81.536092 6.4962E-06 1.7237E-14
    si2h4, $ n=2103,p=6 $
    SCF 36.054 19 -6.300975 1.5619E-06 8.8784E-15
    GBB 43.816 70 -6.300975 3.9377E-06 3.7868E-14
    AFBB 44.630 69 -6.300975 4.7737E-06 1.5903E-14
    GP 32.075 53 -6.300975 9.6973E-06 3.9623E-14
    AG 36.636 62 -6.300975 8.4565E-06 2.7022E-13
    nic, $ n=251,p=7 $
    SCF 10.995 14 -23.543530 1.2291E-06 3.2549E-15
    GBB 10.030 45 -23.543530 7.4993E-06 2.1795E-14
    AFBB 9.038 45 -23.543530 7.4993E-06 1.1159E-14
    GP 11.812 84 -23.543530 6.9368E-06 1.9205E-15
    AG 11.162 82 -23.543530 6.1287E-06 3.3939E-15
     | Show Table
    DownLoad: CSV
  • [1] P. A. AbsilR. Mahony and  R. SepulchreOptimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, 2008.  doi: 10.1515/9781400830244.
    [2] T. AbrudanJ. Eriksson and V. Koivunen, Steepest descent algorithms for optimization under unitary matrix constraint, IEEE Transactions on Signal Processing, 56 (2008), 1134-1147.  doi: 10.1109/TSP.2007.908999.
    [3] J. Barzilai and J. M. Borwein, Two-point step size gradient methods, IMA Journal of Numerical Analysis, 8 (1988), 141-148.  doi: 10.1093/imanum/8.1.141.
    [4] A. D'AspremontL. E. Ghaoui and J. G. R. G. Lanckriet, A direct formulation for sparse PCA using semidefinite programming, SIAM Review, 49 (2007), 434-448.  doi: 10.1137/050645506.
    [5] Y. Dai and R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numerische Mathematik, 100 (2005), 21-47.  doi: 10.1007/s00211-004-0569-y.
    [6] L. Eldén and H. Park, A procrustes problem on the Stiefel manifold, Numerische Mathematik, 82 (1999), 599-619.  doi: 10.1007/s002110050432.
    [7] A. EdelmanT. A. Arias and S. T. Smith, The geometry of algorithms with orthogonality constraints, SIAM Journal on Matrix Analysis and Applications, 20 (1998), 303-353.  doi: 10.1137/S0895479895290954.
    [8] B. GaoX. LiuX. Chen and Y. Yuan, A new first-order algorithmic framework for optimization problems with orthogonality constraints, SIAM Journal on Optimization, 28 (2018), 302-332.  doi: 10.1137/16M1098759.
    [9] J. HuB. Jiang and X. Liu et al, A note on semidefinite programming relaxations for polynomial optimization over a single sphere, Science China Mathematics, 59 (2016), 1543-1560.  doi: 10.1007/s11425-016-0301-5.
    [10] B. Jiang and Y. Dai, A framework of constraint preserving update schemes for optimization on Stiefel manifold, Mathematical Programming, 153 (2015), 535-575.  doi: 10.1007/s10107-014-0816-7.
    [11] X. Liu, C. Hao and M. Cheng, A sequential subspace projection method for linear symmetric eigenvalue problem, Asia-Pacific Journal of Operational Research, 30 (2013), 1340003.1-1340003.17. doi: 10.1142/S0217595913400034.
    [12] X. LiuX. Wang and Z. Wen et al, On the convergence of the self-consistent field iteration in Kohn-Sham density functional theory, SIAM Journal on Matrix Analysis and Applications, 35 (2014), 546-558.  doi: 10.1137/130911032.
    [13] Y. Nishimori and S. Akaho, Learning algorithms utilizing quasi-geodesic flows on the Stiefel manifold, Neurocomputing, 67 (2005), 106-135. 
    [14] A. Sameh and Z. Tong, The trace minimization method for the symmetric generalized eigenvalue problem, Journal of Computational and Applied Mathematics, 123 (2000), 155-175.  doi: 10.1016/S0377-0427(00)00391-5.
    [15] M. Ulbrich, Z. Wen and C. Yang et al, A proximal gradient method for ensemble density functional theory, SIAM Journal on Scientific Computing, 37 (2015), A1975–A2002. doi: 10.1137/14098973X.
    [16] Z. Wen and W. Yin, A feasible method for optimization with orthogonality constraints, Mathematical Programming, 142 (2013), 397-434.  doi: 10.1007/s10107-012-0584-1.
    [17] C. YangJ. C. Meza and L. Wang, A constrained optimization algorithm for total energy minimization in electronic structure calculations, Journal of Computational Physics, 217 (2006), 709-721.  doi: 10.1016/j.jcp.2006.01.030.
    [18] C. YangJ. C. Meza and B. Lee et al, KSSOLV-a MATLAB toolbox for solving the Kohn-Sham equations, ACM Transactions on Mathematical Software, 36 (2009), 1-35.  doi: 10.1145/1499096.1499099.
    [19] H. Zhang and W. W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM Journal on Optimization, 14 (2004), 1043-1056.  doi: 10.1137/S1052623403428208.
    [20] H. ZouT. Hastie and R. Tibshirani, Sparse principal component analysis, Journal of Computational and Graphical Statistics, 15 (2006), 265-286.  doi: 10.1198/106186006X113430.
    [21] X. Zhang, J. Zhu and Z. Wen, Gradient type optimization methods for electronic structure calculations, SIAM Journal on Scientific Computing, 36 (2014), A265–A289. doi: 10.1137/130932934.
  • 加载中

Figures(1)

Tables(4)

SHARE

Article Metrics

HTML views(1188) PDF downloads(246) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return