A convergent algorithm for non-smooth convex saddle-point problems

Applications of Mathematics 2 Minutes

You need to know: Euclidean space {\mathbb R}^n, inner product (x,y) for x,y\in {\mathbb R}^n, norm ||x||=\sqrt{(x,x)}, proper convex lower-semicontinuous (l.s.c.) function F:{\mathbb R}^n \to [0,+\infty], continuous linear operator K:{\mathbb R}^n \to {\mathbb R}^m, its norm ||K||=\max\limits_{x\in{\mathbb R}^n}\frac{||Kx||}{||x||}.

Background:  Let G:{\mathbb R}^n \to [0,+\infty] and F:{\mathbb R}^m \to [0,+\infty] be proper convex l.s.c. functions, and let F^*(y)=\sup\limits_{x\in{\mathbb R}^m}((y,x)-F(x)) be the convex conjugate of F. Let K:{\mathbb R}^n \to {\mathbb R}^m be a continuous linear operator, and let K^*:{\mathbb R}^m \to {\mathbb R}^n be such that (Kx,y)=(x,K^*y) for all x\in {\mathbb R}^n, y\in {\mathbb R}^m. Let H(x,y)=(Kx,y)+G(x)-F^*(y). By saddle-point problem we mean the problem of the form \min\limits_{x\in {\mathbb R}^n}\max\limits_{y\in {\mathbb R}^m}H(x,y). A pair (x^*,y^*) is called a saddle-point of this problem if H(x,y^*)\geq H(x^*,y^*) for all x\in{\mathbb R}^n and H(x^*,y)\leq H(x^*,y^*) for all y\in{\mathbb R}^m. For any V:{\mathbb R}^n \to [0,+\infty], y\in{\mathbb R}^n, and \tau>0, denote d_{V,\tau}(x)=\arg\min\limits_{x\in{\mathbb R}^n}\left(\frac{||x-y||^2}{2\tau}+V(x)\right). For \tau>0, \sigma>0, \theta\in[0,1], initial points x^0 \in {\mathbb R}^n, y^0 \in {\mathbb R}^m, and \bar{x}^0=x^0, define sequences x^n, y^n, \bar{x}^n iteratively as follows: y^{n+1}=d_{F^*,\sigma}(y^n+\sigma K \bar{x}^n), x^{n+1}=d_{G,\tau}(x^n-\tau K^* y^{n+1}), \bar{x}^{n+1} = x^{n+1}+\theta(x^{n+1}-x^n), n \geq 0.

The Theorem: On 21st December 2010, Antonin Chambolle and Thomas Pock published in the Journal of Mathematical Imaging and Vision a paper in which they proved that if \theta=1 and \tau\sigma(||K||)^2<1, then there exist a saddle-point (x^*,y^*) such that \lim\limits_{n\to\infty}x^n = x^* and \lim\limits_{n\to\infty}y^n = y^*.

Short context: Saddle-point problems of the form as above arise in many applications, for example in image denoising and segmentation. The Theorem proves that a simple algorithm converges to a saddle-point. Practical experiments suggests that the convergence is in fact fast, which makes the algorithm widely applicable.

Links: The original paper is available here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment