Comparison of several fast algorithms for projection onto an ellipsoid

摘要

Projecting a point onto an ellipsoid is one of the fundamental problems in convex analysis and numerical algorithms. Recently, several fast algorithms were proposed for solving this problem such as Lin–Han algorithm, maximum 2-dimensional inside ball algorithm, sequential 2-dimensional projection algorithm and hybrid projection algorithms of Dai. In this paper, we rewrite the problem as a constrained convex optimization problem with separable objective functions, which enables the use of the alternating direction method of multipliers (ADMM). Furthermore, since the efficiency of ADMM depends on the penalty parameter, we choose it in a self-adaptive manner, resulting in the self-adaptive ADMM (S-ADMM). All these methods converge with a global linear rate. We compare them theoretically and numerically and find that S-ADMM is the most efficient one. We also illustrate the flexibility of ADMM by applying it to the more general problem of projecting a point onto the intersection of several ellipsoids, Dantzig selector, and image restoration and reconstruction.