A primal dual modified subgradient algorithm with sharp Lagrangian

Jefferson D.G. Mello | Burachik, Regina S. | Iusem, Alfredo N.

Keywords: Nonsmooth optimization | sharp Lagrangian | modified subgradient algorithm

We apply a modified subgradient algorithm (MSG) for solving the dual of a nonlinear and nonconvex optimization problem. The dual scheme we consider uses the sharp augmented Lagrangian. A desirable feature of this method is primal convergence, which means that every accumulation point of the generated sequence is a primal solution. This feature is not true in general for available variants of MSG. We propose here two new variants of MSG which enjoy both primal and dual convergence, as long as the dual optimal set is nonempty. These variants have very simple choices for the stepsizes. Moreover, we also establish primal convergence when the dual optimal set is empty. Finally, our second variant of MSG converges in a finite number of steps.

Anexos:

• regina7.pdf