An Easily Implementable Algorithm for Efficient Projection onto the Ordered Weighted $\ell_1$ Norm Ball

doi:10.1007/s40305-022-00414-8

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (4): 925-940.doi: 10.1007/s40305-022-00414-8

收稿日期:2021-07-19 修回日期:2022-03-09 出版日期:2023-12-30 发布日期:2023-12-26
通讯作者: Yong-Jin Liu, Jia-Jing Xu, Lan-Yu Lin E-mail:yjliu@fzu.edu.cn;xujiajing95574@163.com;llany8250@163.com

An Easily Implementable Algorithm for Efficient Projection onto the Ordered Weighted $\ell_1$ Norm Ball

Yong-Jin Liu, Jia-Jing Xu, Lan-Yu Lin

School of Mathematics and Statistics, Fuzhou University, Fuzhou, 350108, Fujian, China

Received:2021-07-19 Revised:2022-03-09 Online:2023-12-30 Published:2023-12-26
Contact: Yong-Jin Liu, Jia-Jing Xu, Lan-Yu Lin E-mail:yjliu@fzu.edu.cn;xujiajing95574@163.com;llany8250@163.com
Supported by:
The work of Yong-Jin Liu was in part supported by the National Natural Science Foundation of China (No. 11871153) and the Natural Science Foundation of Fujian Province of China (No. 2019J01644).

摘要/Abstract

Abstract: This paper concerns with efficient projection onto the ordered weighted $\ell_1$ norm ball, which is equivalent to the problem of finding projector onto the intersection of the monotone nonnegative cone and an affine subspace. Based on Lagrangian relaxation and secant approximation method, we propose an easily implementable yet efficient algorithm to solve the projection problem which is proved to terminate after a finite number of iterations. Furthermore, we design efficient implementations for our algorithm and compare it with a semismooth Newton (SSN) algorithm and a root-finding (Root-F) algorithm. Numerical results on a diversity of test problems show that our algorithm is superior than SSN and Root-F.

Key words: Lagrangian relaxation, secant method, ordered weighted $\ell_1$ norm ball

中图分类号:

65K05
90C25

. [J]. Journal of the Operations Research Society of China, 2023, 11(4): 925-940.

Yong-Jin Liu, Jia-Jing Xu, Lan-Yu Lin. An Easily Implementable Algorithm for Efficient Projection onto the Ordered Weighted $\ell_1$ Norm Ball[J]. Journal of the Operations Research Society of China, 2023, 11(4): 925-940.

参考文献

[1] Bondell, H., Reich, B.: Simultaneous regression shrinkage, variable selection, and supervised clustering of predictors with OSCAR. Biometrics. 64, 115-123 (2007)
[2] Bogdan, M., Van den Berg, E., Su, W.J., Candès, E.J.: Statistical estimation and testing via the sorted l₁ norm. http://arxiv.org/abs/1310.1969, (2013)
[3] Zeng, X.R., Figueiredo, M.A.T.: Decreasing weighted sorted l₁ regularization. IEEE Signal Process. Lett. 21, 1240-1244 (2014)
[4] Wu, B., Ding, C., Sun, D.F., Toh, K.-C.: On the Moreau-Yosida regularization of the vector k-norm related functions. SIAM J. Optim. 24, 766-794 (2014)
[5] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2, 183-202 (2009)
[6] Wright, S., Nowak, R., Figueiredo, M.: Sparse reconstruction by separable approximation. IEEE Trans. Signal Process. 57, 2479-2493 (2009)
[7] Ivanov, V.K.: On linear problems which are not well-posed. Dokl. Akad. Nauk SSSR 145, 270-272 (1962)
[8] Morozov, V.A.: Choice of parameter for the solution of functional equations by the regularization method. Dokl. Akad. Nauk SSSR. 175, 1225-1228 (1967)
[9] Tikhonov, A.N.: Solution of incorrectly formulated problems and the regularization method. Dokl. Akad. Nauk SSSR. 151, 501-504 (1963)
[10] Zeng, X.R., Figueiredo, M.A.T.: The ordered weighted l₁ norm: atomic formulation, projections, and algorithms. http://arxiv.org/abs/1409.4271 (2014)
[11] Lorenz, D., Worliczek, N.: Necessary conditions for variational regularization schemes. Inverse Probl. 29, 871 (2013)
[12] Seidman, T.I., Vogel, C.R.: Well posedness and convergence of some regularisation methods for nonlinear ill posed problems. Inverse Probl. 5, 227-238 (1989)
[13] Davis, D.: An O(n log (n)) algorithm for projecting onto the ordered weighted l₁ norm ball. http://arxiv.org/abs/1505.00870 (2015)
[14] Li, Q.Z., Li, X.D.: Fast projection onto the ordered weighted ell₁ norm ball. Sci. China Math. 64, doi: 10.1007/s11425-020-1743-9 (2021)
[15] Han, J.Y., Sun, D.F.: Newton and quasi-Newton methods for normal maps with polyhedral sets. J. Optim. Theory Appl. 94, 659-676 (1997)
[16] Li, X.D., Sun, D.F., Toh, K.-C.: On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope. Math. Program. 179, 419-446 (2020)
[17] Best, M.J., Chakravarti, N.: Active set algorithms for isotonic regression. a unifying framework. Math. Program. 47, 425-439 (1990)
[18] Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge University Press, New York (2004)
[19] Bonnans, J.F., Shapiro, A.: Perturbation analysis of optimization problems. Springer Verlag, New York (2000)
[20] Hiriart-Urruty, J.-B., Lemaréchal, C.: Fundamentals of convex analysis. Springer, New York (2001)
[21] Facchinei, F., Pang, J.-S.: Finite-dimensional variational inequalities and complementarity problems. Springer, New York (2003)
[22] Dai, Y.-H., Fletcher, R.: New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math. Program. 106, 403-421 (2006)
[23] Rockafellar, R.T., Wets, R.J.-B.: Variational analysis. Springer, Berlin (1998)
[24] Potra, F.A., Qi, L.Q., Sun, D.F.: Secant methods for semismooth equations. Numer. Math. 80, 305-324 (1998)
[25] Ayer, M., Brunk, H.D., Ewing, G.M., Reid, W.T., Silverman, E.: An empirical distribution function for sampling with incomplete information. Ann. Math. Stat. 26, 641-647 (1955)
[26] Kruskal, J.B.: Nonmetric multidimensional scaling: a numerical method. Psychometrika. 29, 115-129 (1964)
[27] Miles, R.E.: The complete amalgamation into blocks, by weighted means, of a finite set of real numbers. Biometrika. 46, 317-327 (1959)
[28] Brunk, H.D., Ewing, G.M., Utz, W.R.: Minimizing integrals in certain classes of monotone functions. Pacific J. Math. 7, 833-847 (1957)
[29] Van Eeden, C.: Maximum likelihood estimation of ordered probabilities. Indag. Math. 59, 444-455 (1956)
[30] Bogdan, M., Van den Berg, E., Sabatti, C., Su, W.J., Candès, E.J.: SLOPE-adaptive variable selection via convex optimization. Ann. Appl. Stat. 9, 1103-1140 (2015)
[31] Liu, M.J., Liu, Y.-J.: Fast algorithm for singly linearly constrained quadratic programs with box-like constraints. Comput. Optim. Appl. 66, 309-326 (2017)

An Easily Implementable Algorithm for Efficient Projection onto the Ordered Weighted $\ell_1$ Norm Ball

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价