ManPG for nonsmooth optimization on the Stiefel manifold uses a fixed proximal parameter $ t = 1/L $. When the global Lipschitz constant overestimates local curvature, steps become far too small; a moderately larger fixed $ t $ already recovers most of the speed. We replace $ t $ by Barzilai–Borwein (BB) stepsizes computed from ambient secants, with the absolute curvature $ |\langle s, y\rangle| $ so that the rule stays active on concave quadratics where the signed guard freezes at $ 1/L $. Because BB values oscillate naturally, a monotone Armijo test would backtrack excessively; we therefore pair the adaptive parameter with a GLL nonmonotone line search on the retraction stepsize, which tolerates occasional objective increases over a sliding window. The analysis covers any safeguarded $ t_k \in [1/L, t_{\max}] $ for exact subproblem solves: $ \|V_k\|_F \to 0 $, every accumulation point is stationary, and $ O(\epsilon^{-2}) $ complexity holds. The main contributions are (ⅰ) a matched-start ablation showing that $ t = 1/L $ is the main bottleneck on ill-conditioned problems; (ⅱ) a safeguarded alternating BB rule for the proximal parameter with the absolute-curvature policy, together with global convergence and $ O(\epsilon^{-2}) $ complexity; and (ⅲ) a matched protocol with comparisons against ManPG, ManPG-Ada, and scalar reimplementations of an outer-stepsize-BB nonmonotone proximal method (NPGL-type) and of a scalar-metric proximal quasi-Newton scheme. On compressed modes and $ \ell_1 $-regularized PCA, BB-ManPG converges reliably where fixed-parameter ManPG is slow or fails, and ablations separate the contributions of the adaptive parameter, the nonmonotone criterion, and the warm start.
Citation: Di Tang, Lin Chen. Barzilai–Borwein stepsizes with nonmonotone line search for proximal gradient methods on the Stiefel manifold[J]. Journal of Industrial and Management Optimization, 2026, 22(12): 6539-6558. doi: 10.3934/jimo.2026219
ManPG for nonsmooth optimization on the Stiefel manifold uses a fixed proximal parameter $ t = 1/L $. When the global Lipschitz constant overestimates local curvature, steps become far too small; a moderately larger fixed $ t $ already recovers most of the speed. We replace $ t $ by Barzilai–Borwein (BB) stepsizes computed from ambient secants, with the absolute curvature $ |\langle s, y\rangle| $ so that the rule stays active on concave quadratics where the signed guard freezes at $ 1/L $. Because BB values oscillate naturally, a monotone Armijo test would backtrack excessively; we therefore pair the adaptive parameter with a GLL nonmonotone line search on the retraction stepsize, which tolerates occasional objective increases over a sliding window. The analysis covers any safeguarded $ t_k \in [1/L, t_{\max}] $ for exact subproblem solves: $ \|V_k\|_F \to 0 $, every accumulation point is stationary, and $ O(\epsilon^{-2}) $ complexity holds. The main contributions are (ⅰ) a matched-start ablation showing that $ t = 1/L $ is the main bottleneck on ill-conditioned problems; (ⅱ) a safeguarded alternating BB rule for the proximal parameter with the absolute-curvature policy, together with global convergence and $ O(\epsilon^{-2}) $ complexity; and (ⅲ) a matched protocol with comparisons against ManPG, ManPG-Ada, and scalar reimplementations of an outer-stepsize-BB nonmonotone proximal method (NPGL-type) and of a scalar-metric proximal quasi-Newton scheme. On compressed modes and $ \ell_1 $-regularized PCA, BB-ManPG converges reliably where fixed-parameter ManPG is slow or fails, and ablations separate the contributions of the adaptive parameter, the nonmonotone criterion, and the warm start.
| [1] |
V. Ozoliňš, R. Lai, R. Caflisch, S. Osher, Compressed modes for variational problems in mathematics and physics, Proc. Natl. Acad. Sci. USA, 110 (2013), 18368–18373. https://doi.org/10.1073/pnas.1318679110 doi: 10.1073/pnas.1318679110
|
| [2] |
H. Zou, T. Hastie, R. Tibshirani, Sparse principal component analysis, J. Comput. Graph. Statist., 15 (2006), 265–286. https://doi.org/10.1198/106186006X113430 doi: 10.1198/106186006X113430
|
| [3] |
Y. Yang, H. T. Shen, Z. Ma, Z. Huang, X. Zhou, $\ell_{2, 1}$-norm regularized discriminative feature selection for unsupervised learning, Proc. 22nd Int. Joint Conf. Artif. Intell., (2011), 1589–1593. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-267 doi: 10.5591/978-1-57735-516-8/IJCAI11-267
|
| [4] |
Y. Zhang, Y. Lau, H. W. Kuo, S. Cheung, A. Pasupathy, J. Wright, On the global geometry of sphere-constrained sparse blind deconvolution, Proc. IEEE Conf. Comput. Vis. Pattern Recognit., (2017), 4381–4389. https://doi.org/10.1109/CVPR.2017.466 doi: 10.1109/CVPR.2017.466
|
| [5] |
P. A. Absil, R. Mahony, R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton: Princeton University Press, 2009. https://doi.org/10.1515/9781400830244 |
| [6] |
N. Boumal, P. A. Absil, C. Cartis, Global rates of convergence for nonconvex optimization on manifolds, IMA J. Numer. Anal., 39 (2019), 1–33. https://doi.org/10.1093/imanum/drx080 doi: 10.1093/imanum/drx080
|
| [7] |
J. Hu, X. Liu, Z. Wen, Y. Yuan, A brief introduction to manifold optimization, J. Oper. Res. Soc. China, 8 (2020), 199–248. https://doi.org/10.1007/s40305-020-00295-9 doi: 10.1007/s40305-020-00295-9
|
| [8] |
O. P. Ferreira, P. R. Oliveira, Subgradient algorithm on Riemannian manifolds, J. Optim. Theory Appl., 97 (1998), 93–104. https://doi.org/10.1023/A:1022675100677 doi: 10.1023/A:1022675100677
|
| [9] |
S. Hosseini, A. Uschmajew, A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds, SIAM J. Optim., 27 (2017), 173–189. https://doi.org/10.1137/16M1069298 doi: 10.1137/16M1069298
|
| [10] |
X. Li, Y. Zhong, The stochastic projected gradient method for optimization problems on Hadamard manifolds, Optim. Erudit., 3 (2026), 20–33. https://doi.org/10.69829/oper-026-0301-ta03 doi: 10.69829/oper-026-0301-ta03
|
| [11] |
O. P. Ferreira, P. R. Oliveira, Proximal point algorithm on Riemannian manifolds, Optimization, 51 (2002), 257–270. https://doi.org/10.1080/02331930290019413 doi: 10.1080/02331930290019413
|
| [12] |
G. C. Bento, J. X. Cruz Neto, P. R. Oliveira, A new approach to the proximal point method: Convergence on general Riemannian manifolds, J. Optim. Theory Appl., 168 (2016), 743–755. https://doi.org/10.1007/s10957-015-0861-2 doi: 10.1007/s10957-015-0861-2
|
| [13] |
G. C. Bento, C. R. Santiago, On the convergence and properties of a proximal-gradient method on Hadamard manifolds, J. Nonlinear Var. Anal., 10 (2026), 617–633. https://doi.org/10.23952/jnva.10.2026.3.06 doi: 10.23952/jnva.10.2026.3.06
|
| [14] |
R. Lai, S. Osher, A splitting method for orthogonality constrained problems, J. Sci. Comput., 58 (2014), 431–449. https://doi.org/10.1007/s10915-013-9740-x doi: 10.1007/s10915-013-9740-x
|
| [15] |
W. Chen, H. Ji, Y. You, An augmented Lagrangian method for $\ell_1$-regularized optimization problems with orthogonality constraints, SIAM J. Sci. Comput., 38 (2016), B570–B592. https://doi.org/10.1137/140988875 doi: 10.1137/140988875
|
| [16] |
A. Kovnatsky, K. Glashoff, M. M. Bronstein, MADMM: A generic algorithm for non-smooth optimization on manifolds, Proc. European Conf. Comput. Vis., (2016), 680–696. https://doi.org/10.1007/978-3-319-46454-1_41 doi: 10.1007/978-3-319-46454-1_41
|
| [17] |
K. Deng, Z. Peng, A manifold inexact augmented Lagrangian method for nonsmooth optimization on Riemannian submanifolds in Euclidean space, IMA J. Numer. Anal., 43 (2023), 1653–1684. https://doi.org/10.1093/imanum/drac018 doi: 10.1093/imanum/drac018
|
| [18] |
W. Huang, K. Wei, Riemannian proximal gradient methods, Math. Program., 194 (2022), 371–413. https://doi.org/10.1007/s10107-021-01632-3 doi: 10.1007/s10107-021-01632-3
|
| [19] |
W. Huang, K. Wei, An extension of fast iterative shrinkage-thresholding algorithm to Riemannian optimization for sparse principal component analysis, Numer. Linear Algebra Appl., 29 (2022), e2409. https://doi.org/10.1002/nla.2409 doi: 10.1002/nla.2409
|
| [20] |
B. Gao, X. Liu, X. Chen, Y. Yuan, A new first-order algorithmic framework for optimization problems with orthogonality constraints, SIAM J. Optim., 28 (2018), 302–332. https://doi.org/10.1137/16M1098759 doi: 10.1137/16M1098759
|
| [21] |
N. Xiao, X. Liu, Y. Yuan, Exact penalty function for $\ell_{2, 1}$ norm minimization over the Stiefel manifold, SIAM J. Optim., 31 (2021), 3097–3126. https://doi.org/10.1137/20M1354313 doi: 10.1137/20M1354313
|
| [22] |
N. Xiao, X. Liu, K. C. Toh, Dissolving constraints for Riemannian optimization, Math. Oper. Res., 49 (2023), 366–397. https://doi.org/10.1287/moor.2023.1360 doi: 10.1287/moor.2023.1360
|
| [23] |
X. Hu, N. Xiao, X. Liu, K. C. Toh, A constraint dissolving approach for nonsmooth optimization over the Stiefel manifold, IMA J. Numer. Anal., 44 (2024), 3717–3748. https://doi.org/10.1093/imanum/drad098 doi: 10.1093/imanum/drad098
|
| [24] |
X. Liu, N. Xiao, Y. Yuan, A penalty-free infeasible approach for a class of nonsmooth optimization problems over the Stiefel manifold, J. Sci. Comput., 99 (2024), 30. https://doi.org/10.1007/s10915-024-02495-4 doi: 10.1007/s10915-024-02495-4
|
| [25] |
N. Xiao, X. Liu, Solving optimization problems over the Stiefel manifold by smooth exact penalty function, J. Comput. Math., 42 (2024), 1246–1276. https://doi.org/10.4208/jcm.2307-m2021-0331 doi: 10.4208/jcm.2307-m2021-0331
|
| [26] |
S. Chen, S. Ma, A. M. C. So, T. Zhang, Proximal gradient method for nonsmooth optimization over the Stiefel manifold, SIAM J. Optim., 30 (2020), 210–239. https://doi.org/10.1137/18M122457X doi: 10.1137/18M122457X
|
| [27] |
Y. Wang, W. Yin, J. Zeng, Global convergence of ADMM in nonconvex nonsmooth optimization, J. Sci. Comput., 78 (2019), 29–63. https://doi.org/10.1007/s10915-018-0757-z doi: 10.1007/s10915-018-0757-z
|
| [28] |
J. Barzilai, J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141–148. https://doi.org/10.1093/imanum/8.1.141 doi: 10.1093/imanum/8.1.141
|
| [29] |
S. J. Wright, R. D. Nowak, M. A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57 (2009), 2479–2493. https://doi.org/10.1109/TSP.2009.2016892 doi: 10.1109/TSP.2009.2016892
|
| [30] |
L. Grippo, F. Lampariello, S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal., 23 (1986), 707–716. https://doi.org/10.1137/0723046 doi: 10.1137/0723046
|
| [31] |
B. Iannazzo, M. Porcelli, The Riemannian Barzilai–Borwein method with nonmonotone line search and the matrix geometric mean computation, IMA J. Numer. Anal., 38 (2018), 495–517. https://doi.org/10.1093/imanum/drx015 doi: 10.1093/imanum/drx015
|
| [32] |
Z. Ma, T. Yan, S. Zhao, Global convergence of a Barzilai–Borwein scaling HZ-type Riemannian conjugate gradient method, J. Appl. Math. Inform., 44 (2026), 921–943. |
| [33] |
Q. Wang, W. H. Yang, Proximal quasi-Newton method for composite optimization over the Stiefel manifold, J. Sci. Comput., 95 (2023), 39. https://doi.org/10.1007/s10915-023-02165-x doi: 10.1007/s10915-023-02165-x
|
| [34] |
J. C. Zhang, J. Gao, Y. K. Huang, X. W. Liu, Two nonmonotone proximal gradient methods for nonsmooth optimization over the Stiefel manifold, Acta Math. Appl. Sin. Engl. Ser., 42 (2026), 105–120. https://doi.org/10.1007/s10255-024-1065-z doi: 10.1007/s10255-024-1065-z
|
| [35] |
W. Huang, P. A. Absil, K. A. Gallivan, A Riemannian BFGS method without differentiated retraction for nonconvex optimization problems, SIAM J. Optim., 28 (2018), 470–495. https://doi.org/10.1137/17M1127582 doi: 10.1137/17M1127582
|
| [36] |
R. Fletcher, On the Barzilai–Borwein method, Optim. Control Appl., (2005), 235–256. https://doi.org/10.1007/0-387-24255-4_10 doi: 10.1007/0-387-24255-4_10
|
| [37] |
M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim., 7 (1997), 26–33. https://doi.org/10.1137/S1052623494266365 doi: 10.1137/S1052623494266365
|