Projections onto the Intersection of a One-Norm Ball or Sphere and a Two-Norm Ball or Sphere

Hongying Liu (), Hao Wang () and Mengmeng Song ()
Additional contact information
Hongying Liu: Beihang University
Hao Wang: ShanghaiTech University
Mengmeng Song: Beihang University

Journal of Optimization Theory and Applications, 2020, vol. 187, issue 2, No 12, 520-534

Abstract: Abstract This paper focuses on designing a unified approach for computing the projection onto the intersection of a one-norm ball or sphere and a two-norm ball or sphere. We show that the solutions of these problems can all be determined by the root of the same piecewise quadratic function. We make use of the special structure of the auxiliary function and propose a novel bisection algorithm with finite termination. We show that the proposed method possesses quadratic time worst-case complexity. The efficiency of the proposed algorithm is demonstrated in numerical experiments, which show the proposed method has linear time complexity in practice.

Keywords: Projection; Intersection; $$\ell _1$$ ℓ 1 ball; Bisection method; Duality; 49M29; 90C06; 90C46 (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-020-01766-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:187:y:2020:i:2:d:10.1007_s10957-020-01766-y

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-020-01766-y

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().