Iteration-complexity of first-order penalty methods

Guanghui Lan(glanisye.gatech.edu)
Renato Monteiro(monteiroisye.gatech.edu)

Abstract: This paper considers a special but broad class of convex programing (CP) problems whose feasible region is a simple compact convex set intersected with the inverse image of a closed convex cone under an affine transformation. We study two first-order penalty methods for solving the above class of problems, namely: the quadratic penalty method and the exact penalty method. In addition to one or two gradient evaluations, an iteration of these methods requires one or two projections onto the simple convex set. We establish the iteration-complexity bounds for these methods to obtain two types of near optimal solutions, namely: near primal and near primal-dual optimal solutions. Finally, we present variants, with possibly better iteration-complexity bounds than the aforementioned methods, which consist of applying penalty-based methods to the perturbed problem obtained by adding a suitable perturbation term to the objective function of the original CP problem.

Keywords: Convex programming, quadratic penalty method,exact penalty method, Lagrange multiplier

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Nonlinear Optimization

Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, July, 2008.

Download: [PDF]

Entry Submitted: 07/24/2008
Entry Accepted: 07/24/2008
Entry Last Modified: 07/24/2008

Modify/Update this entry