Comparison Of Fast Algorithm For Ellipsoid Projection

The optimization problem of projecting a point onto a general convex set is one of the fundamental problems in convex analysis. It is also an important problem of projection methods for nonlinear programming, variational inequality problems, etc. Since a proper local approximation to a nonlinear function is a quadratic function, projecting a point onto an ellipsoid is a basic subproblem in solving projection onto a convex set, and also associated to the trust region subproblem in nonlinear optimization. Current fast algorithms for projection onto an ellipsoid are Lin-Han algorithm, maximal2-dimensional inside ball algorithm, sequential2-dimensional projection algorithm, hybrid projection algorithm, etc.In this paper, we rewrite the problem of projection on an ellipsoid to a con-strained convex optimization problem with separable objective functions, then it can be solved by alternating direction method of multipliers (ADMM), so we just need to project a point onto a ball in every iteration. In order to accelerate the convergence rate, we give ADMM algorithm with self-adaptive penalty parameters and analyze the convergence of this method. We prove that the problem is global linear convergent, and give the relationship between convergence rate and the penal-ty parameter of ADMM. In the numerical experiment, we compare our algorithm to the current algorithms, and verify the efficiency of it. At last, we give two other examples which can be solved by our method, one is projecting a point onto the in-tersection of several ellipsoids, the other is Dantzig selectors, and give the numerical results.