Printable PDF
Department of Mathematics,
University of California San Diego

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

Math 278C: Optimization and Data Science

Xin Jiang

UCLA

Primal-dual optimization methods with Bregman divergence

Abstract:

 

We discuss Bregman distance extensions of the primal-dual three-operator (PD3O) and Condat-Vu proximal algorithms. When used with standard proximal operators these algorithms include several important methods as special cases. Extensions to generalized Bregman distances are attractive if the complexity per iteration can be reduced by matching the Bregman distance to the structure in the problem. As an example, we apply the proposed method to the centering problem in sparse semidefinite programming. The logarithmic barrier function for the cone of positive semidefinite completable sparse matrices is used as a distance-generating kernel. For this distance, the complexity of evaluating the Bregman proximal operator is shown to be roughly proportional to the cost of a sparse Cholesky factorization. This is much cheaper than the standard proximal operator with Euclidean distances, which requires an eigenvalue decomposition.

Hosts: Yang Zheng, Jiawang Nie

October 5, 2022

3:00 PM

https://ucsd.zoom.us/j/94199223268

Meeting ID: 941 9922 3268
Password: 278CF22

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