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

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

Received date: 2021-07-19

  Revised date: 2022-03-09

  Online published: 2023-12-26

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

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.

Cite this article

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 . DOI: 10.1007/s40305-022-00414-8

References

[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 l1 norm. http://arxiv.org/abs/1310.1969, (2013)
[3] Zeng, X.R., Figueiredo, M.A.T.: Decreasing weighted sorted l1 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 l1 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 l1 norm ball. http://arxiv.org/abs/1505.00870 (2015)
[14] Li, Q.Z., Li, X.D.: Fast projection onto the ordered weighted ell1 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)
Options
Outlines

/