A Riemannian Smoothing Steepest Descent Method for Non-Lipschitz Optimization on Embedded Submanifolds of ${\mathbb{R}}^n$

References

• [1] Absil PA, Gallivan KA (2009) Accelerated line-search and trust-region methods. SIAM J. Numer. Anal. 47(2):997–1018.Crossref, Google Scholar
• [2] Absil PA, Mahony R, Sepulchre R (2008) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [3] Adler RL, Dedieu JP, Margulies JY, Martens M, Shub M (2002) Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal. 22(3):359–390.Crossref, Google Scholar
• [4] Alcantara JH, Nguyen CT, Okuno T, Takeda A, Chen JS (2021) Unified smoothing approach for best hyperparameter selection problem using a bilevel optimization strategy. Preprint, submitted October 25, https://arxiv.org/abs/2110.12630.Google Scholar
• [5] Azagra D, Ferrera J, López-Mesas F (2005) Nonsmooth analysis and Hamilton–Jacobi equations on Riemannian manifolds. J. Funct. Anal. 220(2):304–361.Crossref, Google Scholar
• [6] Azagra D, Ferrera J, Sanz B (2012) Viscosity solutions to second order partial differential equations on Riemannian manifolds. J. Differential Equations 245(2):307–336.Crossref, Google Scholar
• [7] Bačák M, Bergmann R, Steidl G, Weinmann A (2016) A second order non-smooth variational model for restoring manifold-valued images. SIAM J. Sci. Comput. 38(1):A567–A597.Crossref, Google Scholar
• [8] Bertsekas DP (1999) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• [9] Bian W, Chen X (2013) Worst-case complexity of smoothing quadratic regularization methods for non-Lipschitzian optimization. SIAM J. Optim. 23(3):1718–1741.Crossref, Google Scholar
• [10] Bian W, Chen X (2015) Linearly constrained non-Lipschitz optimization for image restoration. SIAM J. Imaging Sci. 8(4):2294–2322.Crossref, Google Scholar
• [11] Bolte J, Danilids D, Lewis A, Shiota M (2007) Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2):556–572.Crossref, Google Scholar
• [12] Boumal N (2023) An Introduction to Optimization on Smooth Manifolds (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [13] Burke JV, Hoheisel T (2013) Epi-convergent smoothing with applications to convex composite functions. SIAM J. Optim. 23(3):1457–1479.Crossref, Google Scholar
• [14] Burke JV, Hoheisel T, Kanzow C (2013) Gradient consistency for integral-convolution smoothing functions. Set-Valued Variational Anal. 21(2):359–376.Crossref, Google Scholar
• [15] Chartrand R, Yin W (2008) Iteratively reweighted algorithms for compressive sensing. 2008 IEEE Internat. Conf. Acoustics, Speech Signal Processing (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 3869–3872.Crossref, Google Scholar
• [16] Chen S, Deng Z, Ma S, So AMC (2021) Manifold proximal point algorithms for dual principal component pursuit and orthogonal dictionary learning. IEEE Trans. Signal Processing 69:4759–4773.Crossref, Google Scholar
• [17] Chen S, Ma S, So AMC, Zhang T (2020a) Proximal gradient method for nonsmooth optimization over the Stiefel manifold. SIAM J. Optim. 30(1):210–239.Crossref, Google Scholar
• [18] Chen S, Ma S, Xue L, Zou H (2020b) An alternating manifold proximal gradient method for sparse principal component analysis and sparse canonical correlation analysis. INFORMS J. Optim. 2(3):192–208.Link, Google Scholar
• [19] Chen W, Ji H, You Y (2016) An augmented Lagrangian method for ℓ1-regularized optimization problems with orthogonality constraints. SIAM J. Sci. Comput. 38(4):B570–B592.Crossref, Google Scholar
• [20] Chen X (2012) Smoothing methods for nonsmooth, nonconvex minimization. Math. Programming 134(1):71–99.Crossref, Google Scholar
• [21] Chen X, Zhou W (2010) Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization. SIAM J. Imaging Sci. 3(4):765–790.Crossref, Google Scholar
• [22] Chen X, Ng MK, Zhang C (2012) Non-Lipschitz ℓp regularization and box constrained model for image restoration. IEEE Trans. Image Processing 21(12):4709–4721.Crossref, Google Scholar
• [23] Chen X, Niu L, Yuan Y (2013) Optimality conditions and smoothing trust region Newton method for non-Lipschitz optimization. SIAM J. Optim. 23(3):1528–1552.Crossref, Google Scholar
• [24] Chen X, Xu F, Ye Y (2010) Lower bound theory of nonzero entries in solutions of ℓ2 − ℓp minimization. SIAM J. Sci. Comput. 32(5):2832–2852.Crossref, Google Scholar
• [25] Chen X, Ge D, Wang Z, Ye Y (2014) Complexity of unconstrained L2-Lp minimization. Math. Programming 143(1–2):371–383.Crossref, Google Scholar
• [26] Chen X, Guo L, Lu Z, Ye JJ (2017) An augmented Lagrangian method for non-Lipschitz nonconvex programming. SIAM J. Numer. Anal. 55(1):168–193.Crossref, Google Scholar
• [27] Clarke FH (1990) Optimization and Nonsmooth Analysis (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• [28] Foucart S, Lai MJ (2009) Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0 < q ≤ 1. Appl. Comput. Harmonic Anal. 26:395–407.Crossref, Google Scholar
• [29] Garmanjani R, Vicente LN (2013) Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization. IMA J. Numer. Anal. 33(3):1008–1028.Crossref, Google Scholar
• [30] Grohs P, Hosseini S (2016) ϵ-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds. Adv. Comput. Math. 42(2):333–366.Crossref, Google Scholar
• [31] Hosseini S, Pouryayevali MR (2001) Generalized gradients and characterization of epi-Lipschitz sets in Riemannian manifolds. Nonlinear Anal.: Theory, Methods, Appl. 74(12):3884–3895.Crossref, Google Scholar
• [32] Hosseini S, Uschmajew A (2017) A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds. SIAM J. Optim. 27(1):173–189.Crossref, Google Scholar
• [33] Hosseini S, Huang W, Yousefpour R (2018) Line search algorithms for locally Lipschitz functions on Riemannian manifolds. SIAM J. Optim. 28(1):596–619.Crossref, Google Scholar
• [34] Huang W, Wei K (2022) Riemannian proximal gradient methods. Math. Programming 194(1–2):371–413.Crossref, Google Scholar
• [35] Huang W, Absil PA, Gallivan KA (2018) A Riemannian BFGS method without differentiated retraction for nonconvex optimization problems. SIAM J. Optim. 28(1):470–495.Crossref, Google Scholar
• [36] Jiang B, Meng X, Wen Z, Chen X (2023) An exact penalty approach for optimization with nonnegative orthogonality constraints. Math. Programming 198(1):855–897.Crossref, Google Scholar
• [37] Kovnatsky A, Glashoff K, Bronstein MM (2016) MADMM: A generic algorithm for non-smooth optimization on manifolds. Leibe B, Matas J, Sebe N, Welling M, eds. Computer Vision—ECCV 2016. Lecture Notes in Computer Science, vol. 9909 (Springer, Cham), 680–696.Crossref, Google Scholar
• [38] Lai R, Osher S (2014) A splitting method for orthogonality constrained problems. J. Sci. Comput. 58(2):431–449.Crossref, Google Scholar
• [39] Ledyaev YS, Zhu QJ (2007) Nonsmooth analysis on smooth manifolds. Trans. Amer. Math. Soc. 359(8):3687–3732.Crossref, Google Scholar
• [40] Li J, Balasubramanian K, Ma S (2022a) Stochastic zeroth-order Riemannian derivative estimation and optimization. Math. Oper. Res. 48(2):1183–1211.Link, Google Scholar
• [41] Li J, Ma S, Srivastava T (2022b) A Riemannian ADMM. Preprint, submitted November 3, https://arxiv.org/abs/2211.02163.Google Scholar
• [42] Li X, Chen S, Deng Z, Qu Q, Zhu Z, So AMC (2021) Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods. SIAM J. Optim. 31(3):1605–1634.Crossref, Google Scholar
• [43] Liu YF, Dai YH, Ma S (2015) Joint power and admission control: Non-convex Lq approximation and an effective polynomial time deflation approach. IEEE Trans. Signal Processing 63(14):3641–3656.Crossref, Google Scholar
• [44] Liu YF, Ma S, Dai YH, Zhang S (2016) A smoothing SQP framework for a class of composite Lq minimization over polyhedron. Math. Programming 158(1–2):467–500.Crossref, Google Scholar
• [45] Qu Q, Sun J, Wright J (2016) Finding a sparse vector in a subspace: Linear sparsity using alternating directions. IEEE Trans. Inform. Theory 62(10):5855–5880.Crossref, Google Scholar
• [46] Qu Q, Zhu Z, Li X, Tsakiris MC, Wright J, Vidal R (2020) Finding the sparsest vectors in a subspace: Theory, algorithms, and applications. Preprint, submitted January 20, https://arxiv.org/abs/2001.06970.Google Scholar
• [47] Rockafellar RT, Wets RJB (1998) Variational Analysis (Springer, New York).Crossref, Google Scholar
• [48] Shang F, Cheng J, Liu Y, Luo ZQ, Lin Z (2018) Bilinear factor matrix norm minimization for robust PCA: Algoirthms and applications. IEEE Trans. Pattern Anal. 40(9):2066–2080.Crossref, Google Scholar
• [49] Spielman DA, Wang H, Wright J (2012) Exact recovery of sparsely-used dictionaries. Proc. 25th Annual Conf. Learn. Theory JMLR: Workshop Conf. Proc., vol. 23 (JMLR), 37.1–37.18.Google Scholar
• [50] Sun J, Qu Q, Wright J (2017) Complete dictionary recovery over the sphere I: Overview and the geometric picture. IEEE Trans. Inform. Theory 63(2):853–884.Crossref, Google Scholar
• [51] Tsakiris MC, Vidal R (2018) Dual principal component pursuit. J. Mach. Learn. Res. 19(1):684–732.Google Scholar
• [52] Wang B, Ma S, Xue L (2022) Riemannian stochastic proximal gradient methods for nonsmooth optimization over the Stiefel manifold. J. Mach. Learn. Res. 23(1):4599–4631.Google Scholar
• [53] Wang Z, Liu B, Chen S, Ma S, Xue L, Zhao H (2021) A manifold proximal linear method for sparse spectral clustering with application to single-cell RNA sequencing data analysis. INFORMS J. Optim. 4(2):200–214.Link, Google Scholar
• [54] Whitney H (1934) Analytic extensions of differentiable functions defined in closed sets. Trans. Amer. Math. Soc. 36(1):63–89.Crossref, Google Scholar
• [55] Xu M, Ye JJ, Zhang L (2015) Smoothing SQP methods for solving degenerate nonsmooth constrained optimization problems with applications to bilevel programs. SIAM J. Optim. 25(3):1388–1410.Crossref, Google Scholar
• [56] Yang W, Zhang LH, Song R (2014) Optimality conditions for the nonlinear programming problems on Riemannian manifolds. Pacific J. Optim. 10(2):415–434.Google Scholar
• [57] Zeng C, Wu C, Jia R (2019) Non-Lipschitz models for image restoration with impulse noise removal. SIAM J. Imaging Sci. 12(1):420–458.Crossref, Google Scholar
• [58] Zhang C, Chen X (2009) Smoothing projected gradient method and its application to stochastic linear complementarity problem. SIAM J. Optim. 20(2):627–649.Crossref, Google Scholar
• [59] Zhang C, Chen X (2020) A smoothing active set method for linearly constrained non-Lipschitz nonconvex optimization. SIAM J. Optim. 30(1):1–30.Crossref, Google Scholar
• [60] Zhou Y, Bao C, Ding C, Zhu J (2023) A semi-smooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds. Math. Programming 201(1–2):1–61.Crossref, Google Scholar
• [61] Zhu H, Zhang X, Chu D, Liao L (2017) Nonconvex and nonsmooth optimization with generalized orthogonality constraints: An approximate augmented Lagrangian method. J. Sci. Comput. 72(1):331–372.Crossref, Google Scholar
• [62] Zhu Z, Ding T, Robinson DP, Tsakiris MC, Vidal R (2019) A linearly convergent method for non-smooth non-convex optimization on the Grassmannian with applications to robust subspace and dictionary learning. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (NIPS, San Diego), 9442–9452.Google Scholar
• [63] Zhu Z, Wang Y, Robinson DP, Naiman D, Vidal R, Tsakiris MC (2018) Dual principal component pursuit: Improved analysis and efficient algorithms. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (NIPS, San Diego), 2175–2185.Google Scholar