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

Previous Articles     Next Articles

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

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

  1. 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: 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

CLC Number: