A new class of alternating proximal minimization algorithms with costs-to-move

Given two objective functions f : X -> R boolean OR{+infinity} and g : Y -> R boolean OR{+infinity} on abstract spaces X and Y, and a coupling function c : X x Y -> R+, we introduce and study alternative minimization algorithms of the following type: ( x(0), y(0)) is an element of X x Y given; (x(n), y(n)) -> ( x(n+1), y(n)) -> (x(n+1), y(n+1)) as follows: x(n+1) is an element of argmin{f(xi) + beta(n)c(xi, y(n)) + alpha(n)h(x(n), xi) : xi is an element of X}, y(n+1) is an element of argmin{g(eta) + mu(n)c(x(n+1), eta) + nu(n)k( y(n), eta) : eta is an element of Y}. Their most original feature is the introduction of the terms h : X x X -> R+ and k : Y x Y -> R+ which are costs to change or to move (distance- like functions, relative entropies) accounting for various inertial, friction, or anchoring e. ects. These algorithms are studied in a general abstract framework. The introduction of the costs to change h and k leads to proximal minimizations with corresponding dissipative effects. As a result, the algorithms enjoy nice convergent properties. Coefficients alpha(n), beta(n), mu(n), nu(n) are nonnegative parameters. When taking alpha(n) = nu(n) = 0 and quadratic costs on a Hilbert space, one recovers the classical alternating minimization algorithm, which itself is a natural extension of the alternating projection algorithm of von Neumann. A number of new signi. cant results hold in general metric spaces. We pay particular attention to the following cases: (1.) (X, d(X)) and (Y, d(Y)) are complete metric spaces and h >= d(X), k >= d(Y) ("high local costs to move"); the algorithms then provide sequences that converge to Nash equilibria. (2.) X = Y = H is a Hilbert space, the costs to change are quadratic ("low local costs to move") and the functions f, g : H -> R boolean OR{+infinity} are closed, convex, proper; then some of the classical convergence theorems for alternating convex minimization algorithms, including those of Acker and Prestel, are properly extended with original proofs.