Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 278C: Optimization seminar

Shiqian Ma

UC Davis

On the Convergence and Complexity of Nonconvex ADMM

Abstract:

The alternating direction method of multipliers (ADMM) has been successfully used in solving problems arising from different fields such as machine learning, image processing, statistics and so on. However, most existing works on analyzing the convergence and complexity of ADMM are for convex problems. In this talk, we discuss several recent results on convergence behavior of ADMM for solving nonconvex problems. We consider two nonconvex models. The first model allows the objective function to be nonconvex and nonsmooth, but the constraints are convex. The second model allows the constraints to be Riemannian manifolds. For both models, we propose ADMM variants for solving them and analyze their iteration complexities for obtaining an $\epsilon$-stationary solution. Numerical results on tensor robust PCA, maximum bisection problem and community detection problem are reported to demonstrate the efficiency of the proposed methods.

Host: Jiawang Nie

December 6, 2017

3:00 PM

AP&M 2402

****************************