Jul 9 – 11, 2018
Ho Chi Minh City University of Science
Asia/Ho_Chi_Minh timezone

Proximal-type algorithm for structured nonsmooth nonconvex problem involving linear operator

Jul 11, 2018, 12:00 PM
Ho Chi Minh City University of Science

Ho Chi Minh City University of Science

227 Nguyễn Văn Cừ, Phường 4, T.P. Hồ Chí Minh


Dr Dang Khoa NGUYEN (Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria)


Proximal operator, since introduced by French mathematician Jean-Jacques Moreau in 1962 [Moreau], became a fundamental object used to design algorithms for nonsmooth optimization. With reference [Attouch-Bolte] as a starting point, proximal-type algorithm for nonconvex model attracts huge interest due to its increasing applications in real world. However, until recently such model cannot contain complexly structure such as the composition of nonsmooth function with linear operator [Bolte-Sabach-Teboulle], otherwise, we have to sacrifice the proximity step [Li-Pong]. We propose a proximal algorithm for minimizing a nonsmooth nonconvex complexly structured. Our algorithm relies on the augmented Lagrange [Gabay-Meicer] and is formulated in a full splitting spirit in the sense of Lions and Mercier \cite{Lions-Mercier}: the nonsmooth functions are processed via their proximal operators, the smooth function via gradient steps, and the linear operator via matrix times vector multiplication. In the setting of the Kurdyka-Lojasiewicz property [Kurdyka], [Lojasiewicz], we show global convergence and derive convergence rates for the iterates regarding the Lojasiewicz exponent. Finally, we show that the general difference of convex programming can be written in our model. As a theoretical by-product, we deduce a scheme for this problem. This talk relies on the joint works with Radu Ioan Bot and Erno Robert Csetnek. [Attouch-Bolte] H. Attouch, J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming 116(1), 5--16 (2009). [Bolte-Sabach-Teboulle] J. Bolte, S. Sabach and M. Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146(1), 459--494 (2014). [Bot-Csetnek-Nguyen] R. I. Bot, E. R. Csetnek and D.-K. Nguyen. A proximal minimization algorithm for structured nonconvex and nonsmooth problems. [Bot-Nguyen] R. I. Bot and D.-K. Nguyen. The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates. [Gabay-Meicer] D. Gabay and B. Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers and Mathematics with Applications 2(1), 17--40 (1976). [Kurdyka] K. Kurdyka. On gradients of functions definable in o-minimal structures. Annales de l’Institut Fourier 48, 769--783 (1998). [Li-Pong] G. Li and T. K. Pong. Global convergence of splitting methods for nonconvex composite optimization. SIAM Journal on Optimization 25(4), 2434--2460 (2015). [Lions-Mercier] P. L. Lions and B. Mercier. Splitting Algorithms for the Sum of Two Nonlinear Operators. SIAM Journal on Numerical Analysis, 16(6), 964--979 (1979) [Lojasiewicz] S. Lojasiewicz. Une proprété topologique des sous-ensembles analytiques réels, Les Équations aux Dérivées Partielles. Éditions du Centre National de la Recherche Scientifique, Paris, 8--89 (1963). [Moreau] J. Moreau. Fonctions convexes duales et points proximaux dans un espace hilbertien. Comptes Rendus de l’Académie des Sciences (Paris), Série A 255, 2897--2899 (1962).

Primary author

Dr Dang Khoa NGUYEN (Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria)

Presentation materials

There are no materials yet.