Proximal minimization algorithm withD-functions

The original proximal minimization algorithm employs quadratic additive terms in the objectives of the subproblems. In this paper, we replace these quadratic additive terms by more generalD-functions which resemble (but are not strictly) distance functions. We characterize the properties of suchD-functions which, when used in the proximal minimization algorithm, preserve its overall convergence. The quadratic case as well as an entropy-oriented proximal minimization algorithm are obtained as special cases.The work of the first author was supported by NSF Grant CCR-8811135 and NIH Grant HL-28438, while visiting the Decision Sciences Department of the Wharton School and the Medical Image Processing Group at the Department of Radiology, both at the University of Pennsylvania, Philadelphia, Pennsylvania. The work of the second author was supported by NSF Grant CCR-91-04042 and AFOSR Grant 91-0168.The authors received valuable comments on the December 1989 and June 1990 versions of this paper, which led to considerable improvements of the results and their presentation. For this, they are indebted to D. Bertsekas, A. De Pierro, J. Eckstein, P. Eggermont, A. Iusem, M. Ferris, M. Teboulle, and three anonymous referees.