research-article

An Augmented Lagrangian Method for $\ell_{1}$-Regularized Optimization Problems with Orthogonality Constraints

Authors:

Yanfei YouAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 38, Issue 4

Pages B570 - B592

https://doi.org/10.1137/140988875

Published: 01 January 2016 Publication History

Abstract

A class of $\ell_1$-regularized optimization problems with orthogonality constraints has been used to model various applications arising from physics and information sciences, e.g., compressed modes for variational problems. Such optimization problems are difficult to solve due to the nonsmooth objective function and nonconvex constraints. Existing methods either are not applicable to such problems or lack convergence analysis, e.g., the splitting of orthogonality constraints (SOC) method. In this paper, we propose a proximal alternating minimized augmented Lagrangian method that hybridizes the augmented Lagrangian method and the proximal alternating minimization scheme. It is shown that the proposed method has the so-called subsequence convergence property; i.e., there exists at least one convergent subsequence, and any convergent subsequence converges to a Karush--Kuhn--Tucker point of an equivalent minimization problem. Experiments on the problem of compressed modes illustrate that the proposed method is noticeably faster than the SOC method.

References

[1]

P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2009.

[2]

R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18 (2007), pp. 1286--1309, http://dx.doi.org/10.1137/060654797 doi.org/10.1137/060654797.

[3]

H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35 (2010), pp. 438--457, http://dx.doi.org/10.1287/moor.1100.0449 http://dx.doi.org/10.1287/moor.1100.0449 1100.0449.

[4]

H. Attouch, J. Bolte, and B. F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward--backward splitting, and regularized Gauss--Seidel methods, Math. Program., 137 (2013), pp. 91--129, http://dx.doi.org/10.1007/s10107-011-0484-9

[5]

F. Barekat, On the consistency of compressed modes for variational problems associated with the Schrödinger operator, SIAM J. Math. Anal., 46 (2014), pp. 3568--3577, http://dx.doi.org/10.1137/130942747

[6]

D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Nashua, NH, 1999.

[7]

F. Bethuel, H. Brezis, and F. Hélein, Asymptotics for the minimization of a Ginzburg-Landau functional, Calc. Var. Partial Differential Equations, 1 (1993), pp. 123--148, http://dx.doi.org/10.1007/BF01191614.

[8]

J. Bolte, S. Sabach, and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146 (2014), pp. 459--494, http://dx.doi.org/10.1007/s10107-013-0701-9.

[9]

J.-F. Cai, S. Osher, and Z. Shen, Convergence of the linearized Bregman iteration for $\ell^{1}$- norm minimization, Math. Comp., 78 (2009), pp. 2127--2136, http://dx.doi.org/10.1090/S0025-5718-09-02242-X.

[10]

E. Candès, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59 (2006), pp. 1207--1223, http://dx.doi.org/10.1002/cpa.20124

[11]

E. J. Candès, X. Li, Y. Ma, and J. Wright, Robust principal component analysis?, J. ACM, 58 (2011), 11, http://dx.doi.org/10.1145/1970392.1970395

[12]

E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), pp. 717--772, http://dx.doi.org/10.1007/s10208-009-9045-5

[13]

T. Chan, A. Marquina, and P. Mulet, High-order total variation-based image restoration, SIAM J. Sci. Comput., 22 (2000), pp. 503--516, http://dx.doi.org/10.1137/S1064827598344169

[14]

D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), pp. 1289--1306, http://dx.doi.org/10.1109/TIT.2006.871582

[15]

I. L. Dryden and K. V. Mardia, Statistical Shape Analysis, John Wiley & Sons, Chichester, UK, 1998.

[16]

A. Edelman, T. A. Arias, and S. T. Smith, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 303--353, http://dx.doi.org/10.1137/S0895479895290954.

[17]

E. Esser, Applications of Lagrangian-based Alternating Direction Methods and Connections to Split Bregman, CAM Report 09-31, UCLA, Los Angeles, CA, 2009.

[18]

M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, North-Holland, Amsterdam, New York, 2000.

[19]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM Stud. Appl. Math. 9, SIAM, Philadelphia, 1989, http://dx.doi.org/10.1137/1.9781611970838.

[20]

D. Goldfarb, Z. Wen, and W. Yin, A curvilinear search method for $p$-harmonic flows on spheres, SIAM J. Imaging Sci., 2 (2009), pp. 84--109, http://dx.doi.org/10.1137/080726926

[21]

T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM J. Imaging Sci., 2 (2009), pp. 323--343, http://dx.doi.org/10.1137/080725891

[22]

R. Lai, J. Lu, and S. Osher, Density Matrix Minimization with $\ell_1$ Regularization, preprint, http://arxiv.org/abs/1403.1525 arXiv:1403.1525v1 [math-ph], 2014.

[23]

R. Lai and S. Osher, A splitting method for orthogonality constrained problems, J. Sci. Comput., 58 (2014), pp. 431--449, http://dx.doi.org/10.1007/s10915-013-9740-x

[24]

Z. Lu and Y. Zhang, An augmented Lagrangian approach for sparse principal component analysis, Math. Program., 135 (2012), pp. 149--193, http://dx.doi.org/10.1007/s10107-011-0452-4

[25]

J. H. Manton, Optimization algorithms exploiting unitary constraints, IEEE Trans. Signal Process., 50 (2002), pp. 635--650, http://dx.doi.org/10.1109/78.984753

[26]

N. Marzari and D. Vanderbilt, Maximally localized generalized Wannier functions for composite energy bands, Phys. Rev. B, 56 (1997), 12847, http://dx.doi.org/10.1103/PhysRevB.56.12847

[27]

M. Meinshausen and B. Yu, Lasso-type recovery of sparse representations for high-dimensional data, Ann. Statist., 37 (2009), pp. 246--270, http://dx.doi.org/10.1214/07-AOS582

[28]

J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer Ser. Oper. Res. Financ. Eng., Springer, New York, 2006.

[29]

S. Osher, Y. Mao, B. Dong, and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci., 8 (2010), pp. 93--111.

[30]

V. Ozolins, R. Lai, R. Caflisch, and S. Osher, Compressed modes for variational problems in mathematics and physics, Proc. Natl. Acad. Sci. USA, 110 (2013), pp. 18368--18373, http://dx.doi.org/10.1073/pnas.1318679110

[31]

V. Ozolins, R. Lai, R. Caflisch, and S. Osher, Compressed plane waves yield a compactly supported multiresolution basis for the Laplace operator, Proc. Natl. Acad. Sci. USA, 111 (2014), pp. 1691--1696, http://dx.doi.org/10.1073/pnas.1323260111

[32]

E. Prodan and W. Kohn, Nearsightedness of electronic matter, Proc. Natl. Acad. Sci. USA, 102 (2005), pp. 11635--11638, http://dx.doi.org/10.1073/pnas.0505436102

[33]

R. T. Rockafellar, and R. J.-B. Wets, Variational Analysis, Grundlehren Math. Wiss. 317, Springer-Verlag, Berlin, 1998.

[34]

L. I. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), pp. 259--268, http://dx.doi.org/10.1016/0167-2789(92)90242-F

[35]

Z. Shen, Wavelet frames and image restorations, in Proceedings of the International Congress of Mathematicians, Vol. IV, Hindustan Book Agency, New Delhi, India, 2010, pp. 2834--2863, http://dx.doi.org/10.1142/9789814324359_0169

[36]

J. Tang and H. Liu, Unsupervised feature selection for linked social media data, in Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2012, pp. 904--912, http://dx.doi.org/10.1145/2339530.2339673

[37]

R. Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B, 58 (1996), pp. 267--288.

[38]

Z. Wen, C. Yang, X. Liu, and Y. Zhang, Trace-penalty minimization for large-scale eigen-space computation, J. Sci. Comput., 66 (2016), pp. 1175--1203, http://dx.doi.org/10.1007/s10915-015-0061-0 http://dx.doi.org/10.1007/s10915-015-0061-0 0061-0.

[39]

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

[40]

M. Yaghoobi and M. E. Davies, Relaxed analysis operator learning, in Proceedings of the NIPS, Workshop on Analysis Operator Learning vs. Dictionary Learning: Fraternal Twins in Sparse Modeling, 2012.

[41]

M. Yaghoobi, S. Nam, R. Gribonval, and M. E. Davies, Noise aware analysis operator learning for approximately cosparse signals, in Proceedings of the 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, Japan, 2012, pp. 5409--5412, http://dx.doi.org/10.1109/ICASSP.2012.6289144

[42]

B. Yang, Projection approximation subspace tracking, IEEE Trans. Signal Process., 43 (1995), pp. 95--107, http://dx.doi.org/10.1109/78.365290

[43]

Y. Yang, H. T. Shen, Z. Ma, Z. Huang, and X. Zhou, $\ell_{2,1}$-norm regularized discriminative feature selection for unsupervised learning, in Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI), AAAI Press, Palo Alto, CA, 2011, pp. 1589--1594, http://dx.doi.org/10.5591/978-1-57735-516-8/IJCAI11-267

[44]

K. Yin and S. Osher, On the Completeness of the Compressed Modes in the Eigenspace, CAM Report 13-62, UCLA, Los Angeles, CA, 2013.

Cited By

Zhang CChen XMa S(2024)A Riemannian Smoothing Steepest Descent Method for Non-Lipschitz Optimization on Embedded Submanifolds of RnMathematics of Operations Research10.1287/moor.2022.028649:3(1710-1733)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/moor.2022.0286
Zhang CXiao RHuang WJiang R(2024)Riemannian Trust Region Methods for MinimizationJournal of Scientific Computing10.1007/s10915-024-02664-5101:2Online publication date: 20-Sep-2024
https://dl.acm.org/doi/10.1007/s10915-024-02664-5
Liu XXiao NYuan Y(2024)A Penalty-Free Infeasible Approach for a Class of Nonsmooth Optimization Problems Over the Stiefel ManifoldJournal of Scientific Computing10.1007/s10915-024-02495-499:2Online publication date: 20-Mar-2024
https://dl.acm.org/doi/10.1007/s10915-024-02495-4
Show More Cited By

Recommendations

Smoothing augmented Lagrangian method for nonsmooth constrained optimization problems

In this paper, we propose a smoothing augmented Lagrangian method for finding a stationary point of a nonsmooth and nonconvex optimization problem. We show that any accumulation point of the iteration sequence generated by the algorithm is a stationary ...
A Proximal Augmented Lagrangian Method for Linearly Constrained Nonconvex Composite Optimization Problems
Abstract
This paper proposes and establishes the iteration complexity of an inexact proximal accelerated augmented Lagrangian (IPAAL) method for solving linearly constrained smooth nonconvex composite optimization problems. Each IPAAL iteration consists of ... $^{}^{}$ $^{}^{}$
Primal-Dual Active-Set Methods for Large-Scale Optimization

In this paper, we introduce two primal-dual active-set methods for solving large-scale constrained optimization problems. The first method minimizes a sequence of primal-dual augmented Lagrangian functions subject to bounds on the primal variables and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 38, Issue 4

DOI:10.1137/sjoce3.38.4

Issue’s Table of Contents

© 2016, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2016

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang CChen XMa S(2024)A Riemannian Smoothing Steepest Descent Method for Non-Lipschitz Optimization on Embedded Submanifolds of RnMathematics of Operations Research10.1287/moor.2022.028649:3(1710-1733)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/moor.2022.0286
Zhang CXiao RHuang WJiang R(2024)Riemannian Trust Region Methods for MinimizationJournal of Scientific Computing10.1007/s10915-024-02664-5101:2Online publication date: 20-Sep-2024
https://dl.acm.org/doi/10.1007/s10915-024-02664-5
Liu XXiao NYuan Y(2024)A Penalty-Free Infeasible Approach for a Class of Nonsmooth Optimization Problems Over the Stiefel ManifoldJournal of Scientific Computing10.1007/s10915-024-02495-499:2Online publication date: 20-Mar-2024
https://dl.acm.org/doi/10.1007/s10915-024-02495-4
Wang LLiu XZhang Y(2023)A communication-efficient and privacy-aware distributed algorithm for sparse PCAComputational Optimization and Applications10.1007/s10589-023-00481-485:3(1033-1072)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1007/s10589-023-00481-4
Dolgopolik M(2023)DC semidefinite programming and cone constrained DC optimization II: local search methodsComputational Optimization and Applications10.1007/s10589-023-00479-y85:3(993-1031)Online publication date: 15-Apr-2023
https://dl.acm.org/doi/10.1007/s10589-023-00479-y
Zhou YBao CDing CZhu J(2022)A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifoldsMathematical Programming: Series A and B10.1007/s10107-022-01898-1201:1-2(1-61)Online publication date: 5-Oct-2022
https://dl.acm.org/doi/10.1007/s10107-022-01898-1
Huang WWei K(2022)Riemannian proximal gradient methodsMathematical Programming: Series A and B10.1007/s10107-021-01632-3194:1-2(371-413)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10107-021-01632-3
Yashtini MKang SZhu W(2019)Efficient alternating minimization methods for variational edge-weighted colorization modelsAdvances in Computational Mathematics10.1007/s10444-019-09702-z45:3(1735-1767)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10444-019-09702-z

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents