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.
Citation
November 2001, Department of Electrical Engineering, Technion - Israel Institute of Technology