An Extension of the Auxiliary Problem Principle to Nonsymmetric Auxiliary Operators

¹ renaud@clr34el.der.edf.fr
² cohen@cas.ensmp.fr

Abstract

To find a zero of a maximal monotone operator, an extension of the Auxiliary Problem Principle to nonsymmetric auxiliary operators is proposed. The main convergence result supposes a relationship between the main operator and the nonsymmetric component of the auxiliary operator. When applied to the particular case of convex-concave functions, this result implies the convergence of the parallel version of the Arrow-Hurwicz algorithm under the assumptions of Lipschitz and partial Dunn properties of the main operator. The latter is systematically enforced by partial regularization. In the strongly monotone case, it is shown that the convergence is linear in the average. Moreover, if the symmetric part of the auxiliary operator is linear, the Lipschitz property of the inverse suffices to ensure a linear convergence rate in the average.

Résumé

Pour trouver un zéro d'un opérateur maximal monotone, une extension du Principe du Problème Auxiliaire aux opérateurs non symétriques est proposée. Le principal résultat de convergence suppose une relation entre l'opérateur original et la partie non symétrique de l'opérateur auxiliaire. Appliqué au cas particulier d'opérateurs dérivés de fonctions convexes-concaves, ce résultat entraîne la convergence de la version parallèle de l'algorithme d'Arrow-Hurwicz sous les hypothèses de Lipschitz et de Dunn partielle en ce qui concerne l'opérateur original. Cette dernière propriété est obtenue systématiquement par régularisation partielle. Dans le cas fortement monotone, on démontre que la convergence est linéaire en moyenne. De plus, si la partie symétrique de l'opérateur est linéaire, la propriété de Lipschitz de l'inverse suffit à assurer une vitesse de convergence linéaire en moyenne.