An active set strategy based on the augmented Lagrangian formulation for image restoration

¹ Department of Mathematics, North Carolina State University, Raleigh, NC 27695, USA.
² Institut für Mathematik, Universität Graz, 8010 Graz, Austria.

Received: 3 January 1997
Revised: 22 September 1997

Abstract

Lagrangian and augmented Lagrangian methods for nondifferentiable optimization problems that arise from the total bounded variation formulation of image restoration problems are analyzed. Conditional convergence of the Uzawa algorithm and unconditional convergence of the first order augmented Lagrangian schemes are discussed. A Newton type method based on an active set strategy defined by means of the dual variables is developed and analyzed. Numerical examples for blocky signals and images perturbed by very high noise are included.

Résumé

On analyse les méthodes de lagrangien et de lagrangien augmenté pour des problèmes d'optimisation non différentiable, provenant de la formulation de variation totale bornée en restauration d'images. La convergence conditionnelle de l'algorithme d'Uzawa et la convergence inconditionnelle des schémas de premier ordre de lagrangien augmenté sont discutées. Une méthode de type Newton basée sur une statégie d'ensemble actif, définie au moyen de variables primales et duales, est développée et analysée. Des exemples numériques sont donnés pour des signaux discontinus et des images pertubées par très fort bruit.