Constrained optimization and Lagrange multiplier methods.

*(English)*Zbl 0572.90067
Computer Science and Applied Mathematics. New York - London etc.: Academic Press. A Subsidiary of Harcourt Brace Jovanovich, Publishers. XIII, 395 p. $ 65.00 (1982).

This book deals with a class of algorithms to solve finite dimensional optimization problems with equality and inequality constraints. The Lagrange multiplier methods are related to the concept of penalty functions and multiplier methods. Presently, they form a considerable area of research in the numerical analysis of optimization and this monograph gives a presentation of the concepts and analysis of these methods.

In Chapter 1 some of the mathematical background is provided with an introduction which finally leads into an actual research topic of this area. The chapter starts with an outline of the basic definitions and statements of linear algebra and convergence analysis. Then unconstrained optimization problems are addressed with a development of the principle of the most common minimization algorithms such as steepest descent, conjugate gradient or quasi Newton methods. Notes on comparisons of various algorithms present the state of the art at the time the book was written. The Kuhn Tucker rule for constrained optimization is presented and the chapter is finished with a Newton like algorithm for optimization problems with simple linear inequality constraints which is particularly interesting for discretized optimal control problems with bounds on the controls.

Multiplier methods for optimization problems with equality constraints is the topic in the second chapter. Introductory remarks on the invention of the augmented Lagrangean method are made in view of the potential ill conditioning of penalty methods. Some results on the sensitivity of the minima of the augmented Lagrangean with respect to its parameters are shown. The linear and superlinear rates of convergence for the method of multipliers is proven depending on the choice of the coefficients in the augmented term. Various other aspects follow this discussion: notes on the improvement over penalty methods, the effect of more sophisticated step size strategies and the interpretation as a steepest ascent method for the dual problem. This leads into a section on second order multiplier update strategies. Here the superlinear and quadratic convergence rates are proven with some notes on drawbacks with regard to computational complexity of this class of multiplier methods. Quasi Newton versions are shortly discussed and a section on partial elimination of the constraints, i.e. some constraints are not incorporated in the Lagrangean, follows. At the end, the author discusses the fact that the unconstrained minimization which is necessary for the update of the multiplier need not be carried out exactly.

Constrained optimization problems where inequalities are present are treated in Chapter 3 using slack variables to rewrite them as equality constraints. Furthermore, nondifferentiable constraints are examined and various special cases are discussed.

The first half of the fourth chapter treats methods based on exact penalty functions. First, several examples of nondifferentiable penalty functions for equality and inequality constraints are given. The minimizers of the exact penalty functions are related to Kuhn-Tucker points of the original problems. Quadratic subproblems are examined which yield descent directions at nonoptimal points. An algorithm is given which is based on successive quadratic programming. Its convergence to Kuhn-Tucker points is shown for certain step size rules under a uniform positive definiteness assumption on the matrices describing the quadratic part. Another section describes differentiable exact penalty functions. Also, the practical choice of the penalty parameter is discussed either through a priori information or iteratively.

In the second part of chapter 4 Lagrangian methods are discussed. These are variations of Newton’s method applied to the nonlinear system of equations which describe the first order necessary optimality conditions. There are various possibilities to implement these methods depending on e.g. how much of the structure inherited in the problem is taken into account. Some of these variants are presented and applied to problems with equality constraints and also to inequality constraints. By design all these methods are locally convergent at best. In a final section, the combination of these methods with global ones like multiplier methods is addressed. This section also outlines some of the connections that can be drawn to quasi Newton methods. Proofs for rates of convergence are given.

Chapter five is devoted to extensions to nonquadratic penalty functions. The methods are motivated by simple examples and they are analyzed using the dual problem. Under various assumptions such as some type of second order sufficiency condition, rates of convergence are proven. Depending on certain parameters in the growth conditions for the problem to be solved it can be shown that these multiplier methods exhibit linear or superlinear convergence where the superlinear rate statement can be even specified by an order. The chapter ends with an application to an integer programming problem with a large number of constraints.

At the end of each chapter one can find bibliographical remarks on the literature corresponding to the material presented in each section. In several of the chapters the reader can find worked numerical examples. Most concepts are accompanied by a geometrical interpretation with graphs. Parts of the book can be used for an introduction in this field whereas other sections of it provide a guide to an area of active research in the numerical analysis of constrained optimization problems.

In Chapter 1 some of the mathematical background is provided with an introduction which finally leads into an actual research topic of this area. The chapter starts with an outline of the basic definitions and statements of linear algebra and convergence analysis. Then unconstrained optimization problems are addressed with a development of the principle of the most common minimization algorithms such as steepest descent, conjugate gradient or quasi Newton methods. Notes on comparisons of various algorithms present the state of the art at the time the book was written. The Kuhn Tucker rule for constrained optimization is presented and the chapter is finished with a Newton like algorithm for optimization problems with simple linear inequality constraints which is particularly interesting for discretized optimal control problems with bounds on the controls.

Multiplier methods for optimization problems with equality constraints is the topic in the second chapter. Introductory remarks on the invention of the augmented Lagrangean method are made in view of the potential ill conditioning of penalty methods. Some results on the sensitivity of the minima of the augmented Lagrangean with respect to its parameters are shown. The linear and superlinear rates of convergence for the method of multipliers is proven depending on the choice of the coefficients in the augmented term. Various other aspects follow this discussion: notes on the improvement over penalty methods, the effect of more sophisticated step size strategies and the interpretation as a steepest ascent method for the dual problem. This leads into a section on second order multiplier update strategies. Here the superlinear and quadratic convergence rates are proven with some notes on drawbacks with regard to computational complexity of this class of multiplier methods. Quasi Newton versions are shortly discussed and a section on partial elimination of the constraints, i.e. some constraints are not incorporated in the Lagrangean, follows. At the end, the author discusses the fact that the unconstrained minimization which is necessary for the update of the multiplier need not be carried out exactly.

Constrained optimization problems where inequalities are present are treated in Chapter 3 using slack variables to rewrite them as equality constraints. Furthermore, nondifferentiable constraints are examined and various special cases are discussed.

The first half of the fourth chapter treats methods based on exact penalty functions. First, several examples of nondifferentiable penalty functions for equality and inequality constraints are given. The minimizers of the exact penalty functions are related to Kuhn-Tucker points of the original problems. Quadratic subproblems are examined which yield descent directions at nonoptimal points. An algorithm is given which is based on successive quadratic programming. Its convergence to Kuhn-Tucker points is shown for certain step size rules under a uniform positive definiteness assumption on the matrices describing the quadratic part. Another section describes differentiable exact penalty functions. Also, the practical choice of the penalty parameter is discussed either through a priori information or iteratively.

In the second part of chapter 4 Lagrangian methods are discussed. These are variations of Newton’s method applied to the nonlinear system of equations which describe the first order necessary optimality conditions. There are various possibilities to implement these methods depending on e.g. how much of the structure inherited in the problem is taken into account. Some of these variants are presented and applied to problems with equality constraints and also to inequality constraints. By design all these methods are locally convergent at best. In a final section, the combination of these methods with global ones like multiplier methods is addressed. This section also outlines some of the connections that can be drawn to quasi Newton methods. Proofs for rates of convergence are given.

Chapter five is devoted to extensions to nonquadratic penalty functions. The methods are motivated by simple examples and they are analyzed using the dual problem. Under various assumptions such as some type of second order sufficiency condition, rates of convergence are proven. Depending on certain parameters in the growth conditions for the problem to be solved it can be shown that these multiplier methods exhibit linear or superlinear convergence where the superlinear rate statement can be even specified by an order. The chapter ends with an application to an integer programming problem with a large number of constraints.

At the end of each chapter one can find bibliographical remarks on the literature corresponding to the material presented in each section. In several of the chapters the reader can find worked numerical examples. Most concepts are accompanied by a geometrical interpretation with graphs. Parts of the book can be used for an introduction in this field whereas other sections of it provide a guide to an area of active research in the numerical analysis of constrained optimization problems.

Reviewer: E.Sachs

##### MSC:

90Cxx | Mathematical programming |

90-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming |

90C20 | Quadratic programming |

65K05 | Numerical mathematical programming methods |

49-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to calculus of variations and optimal control |

49M29 | Numerical methods involving duality |

49M37 | Numerical methods based on nonlinear programming |

49K10 | Optimality conditions for free problems in two or more independent variables |

49M15 | Newton-type methods |

49M30 | Other numerical methods in calculus of variations (MSC2010) |

90C99 | Mathematical programming |

90C55 | Methods of successive quadratic programming type |

65K10 | Numerical optimization and variational techniques |