Smoothing Method of Multipliers for Sum-Max Problems

Michael Zibulevsky (mzibee.technion.ac.il)

Abstract: We study nonsmooth unconstrained optimization problem, which includes sum of pairwise maxima of smooth functions. Minimum $l_1$-norm approximation is a particular case of this problem. Combining ideas Lagrange multipliers with smooth approximation of max-type function, we obtain a new kind of nonquadratic augmented Lagrangian. Our approach does not require artificial variables, and preserves sparse structure of Hessian in many practical cases. We present the corresponding method of multipliers, and its convergence analysis for a dual counterpart, resulting in a proximal point maximization algorithm. The practical efficiency of the algorithm is supported by computational results for large-scale problems, arising in structural optimization.

Keywords: Nonsmooth Optimization, Smoothing Technique, Augmented Lagrangian, Method of Multipliers

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Nonlinear Optimization (Unconstrained Optimization )

Citation: November 2001, Department of Electrical Engineering, Technion - Israel Institute of Technology

Download: [Postscript][PDF]

Entry Submitted: 11/27/2001
Entry Accepted: 11/27/2001
Entry Last Modified: 12/02/2001

Modify/Update this entry