Penalty/Barrier Multiplier Methods for Convex Programming Problems

SIAM Journal on OptimizationPublished 1 May 1997

Aharon Ben‐Tal, Michael Zibulevsky

DOI10.1137/s1052623493259215

Source URL

Citations201

SJR quartileQ1

SJR score1.39

SNIP1.79

TL;DR

A new type of penalty/barrier function (having a logarithmic branch glued to a quadratic branch) is introduced and used to construct an efficient algorithm that is tested on large-scale quadratically constrained problems arising in structural optimization.

Abstract

We study a class of methods for solving convex programs, which are based on nonquadratic augmented Lagrangians for which the penalty parameters are functions of the multipliers. This gives rise to Lagrangians which are nonlinear in the multipliers. Each augmented Lagrangian is specified by a choice of a penalty function $\varphi$ and a penalty-updating function $\pi$. The requirements on $\varphi$ are mild and allow for the inclusion of most of the previously suggested augmented Lagrangians. More importantly, a new type of penalty/barrier function (having a logarithmic branch glued to a quadratic branch) is introduced and used to construct an efficient algorithm. Convergence of the algorithms is proved for the case of $\pi$ being a sublinear function of the dual multipliers. The algorithms are tested on large-scale quadratically constrained problems arising in structural optimization.

Keywords

Computer ScienceMathematicsEngineering

Mathematics of Operations ResearchAugmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming

1,209 Citations1976R. T. Rockafellar

The theory of the proximal point algorithm for maximal monotone operators is applied to three algorithms for solving convex programs, one of which has not previously been formulated and is shown to have much the same convergence properties, but with some potential advantages.

Mathematical ProgrammingA dual approach to solving nonlinear programming problems by unconstrained optimization

435 Citations1973R. T. Rockafellar

This paper has shown that any maximizing sequence for the dual can be made to yield, in a general way, an asymptotically minimizingsequence for the primal which typically converges at least as rapidly.

Structural and Multidisciplinary OptimizationOptimization methods for truss geometry and topology design

307 Citations1994Martin P. Bendsøe, Aharon Ben‐Tal +1 more

Journal of Applied MechanicsAn Analytical Model to Predict Optimal Material Properties in the Context of Optimal Structural Design

254 Citations1994Martin P. Bendsøe, J. M. Guedes +3 more

Mathematical ProgrammingModified barrier functions (theory and methods)

254 Citations1992Roman A. Polyak

The excellent MBF properties allow us to discover that for any nondegenerate constrained optimization problem, there exists a “hot” start, from which the NMBM has a better rate of convergence, a better complexity bound, and is more stable than the interior point methods, which are based on the classical barrier functions.

Mathematics of Operations ResearchEntropic Proximal Mappings with Applications to Nonlinear Programming

243 Citations1992Marc Teboulle

A family of new transforms based on imitating the proximal mapping of Moreau and the associated Moreau-Yosida proximal approximation of a function are introduced, providing a fairly general framework for constructing approximation and smoothing schemes for optimization problems.

SIAM Journal on OptimizationPenalty/Barrier Multiplier Methods for Convex Programming Problems

201 Citations1997Aharon Ben‐Tal, Michael Zibulevsky

Mathematical ProgrammingOn the convergence of the exponential multiplier method for convex programming

175 Citations1993Paul Tseng, Dimitri P. Bertsekas

This paper analyzes the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic.

SIAM Journal on OptimizationA New Method for Optimal Truss Topology Design

163 Citations1993Aharon Ben‐Tal, Martin P. Bendsøe

A new equivalent of an unconstrained and convex minimization problem in displacements only, where the function to be minimized is the sum of terms, each of which is the maximum of two convex,quadratic functions.

Mathematics of Operations ResearchEntropy-Like Proximal Methods in Convex Programming

154 Citations1994Alfredo N. Iusem, B. F. Svaiter +1 more

An extension of the proximal method for convex programming, where the quadratic regularization kernel is substituted by a class of convex statistical distances, called φ- divergences, is studied and a convergence analysis of the resulting entropy-like proximal algorithm is presented.