Proximal Point Algorithm Controlled by a Slowly Vanishing Term: Applications to Hierarchical Minimization

Let Φ₀:Rⁿ→ R∪ \+∞\ be a closed convex function and Φ₁:Rⁿ→ R be a finite convex function that are bounded from below. Our goal is to build an algorithm which first minimizes the map Φ₀ and secondly the map Φ₁ over the set S₀:= argmin\, Φ₀. For that purpose, we define the following proximal-type algorithm: -(xₙ₊₁-xₙ)/λₙ∈ ∂ηₙ (Φ₀+εₙ Φ₁) (xₙ₊₁),( A₁) where (λₙ) is a positive step sequence, (ηₙ) is a summable error sequence, and (εₙ) is a control sequence tending toward 0; ∂_η denotes the η-approximate subdifferential. When (εₙ) is a slow control, i.e., \,∑ₙ₌₀+∞=εₙ +∞, we prove that, under adequate conditions, the sequence (xₙ) defined by ( A₁) tends toward an element of S₁:= argmin\,S₀Φ₁. More generally, given finite convex functions Φ₂,…,ΦN:Rⁿ→ R, let us define the sets (Sᵢ)_i∈\1,…,N\ by the recursive relation Sᵢ:= argmin\,_Sᵢ₋₁Φᵢ. We introduce an extension of algorithm ( A₁) to minimize hierarchically each function Φᵢ on the set Sᵢ₋₁, for i∈\1,…,N\.