The Linearization Method for Constrained Optimization

ISBN-13: 9783642634017 / Angielski / Miękka / 2012 / 150 str.

Boris N. Pshenichnyj; S. S. Wilson

Opis

Techniques of optimization are applied in many problems in economics, automatic control, engineering, etc. and a wealth of literature is devoted to this subject. The first computer applications involved linear programming problems with simp- le structure and comparatively uncomplicated nonlinear pro- blems: These could be solved readily with the computational power of existing machines, more than 20 years ago. Problems of increasing size and nonlinear complexity made it necessa- ry to develop a complete new arsenal of methods for obtai- ning numerical results in a reasonable time. The lineariza- tion method is one of the fruits of this research of the last 20 years. It is closely related to Newton's method for solving systems of linear equations, to penalty function me- thods and to methods of nondifferentiable optimization. It requires the efficient solution of quadratic programming problems and this leads to a connection with conjugate gra- dient methods and variable metrics. This book, written by one of the leading specialists of optimization theory, sets out to provide - for a wide readership including engineers, economists and optimization specialists, from graduate student level on - a brief yet quite complete exposition of this most effective method of solution of optimization problems.

Spis treści

1. Convex and Quadratic Programming.- 1.1 Introduction.- 1.1.1 The Linearization Algorithm.- 1.1.2 Convergence of the Algorithm.- 1.1.3 General Remarks.- 1.1.4 Notation.- 1.2 Necessary Conditions for a Minimum and Duality.- 1.2.1 Convex Sets.- 1.2.2 Convex Functions.- 1.2.3 Foundations of Convex Programming.- 1.2.4 Duality in Convex Programming.- 1.2.5 Necessary Conditions for Extrema. General Problem.- 1.2.6 Necessary Conditions for Extrema: Second Order Conditions . ..- 1.2.7 Minimax Problems.- 1.2.8 Penalty Functions.- 1.3 Quadratic Programming Problems.- 1.3.1 Conjugate Gradient Method.- 1.3.2 Conjugate Gradient Algorithm.- 1.3.3 Existence of a Solution.- 1.3.4 Necessary Conditions for an Extremum and the Dual Problem.- 1.3.5 Application, Projection onto a Subspace.- 1.3.6 Algorithm for the Quadratic Programming Problem.- 1.3.7 Computational Aspects.- 1.3.8 Algorithms for Simple Constraints. Generalization.- 2. The Linearization Method.- 2.1 The General Algorithm.- 2.1.1 Main Assumptions.- 2.1.2 Formulation of the Algorithm.- 2.1.3 Convergence of the Algorithm.- 2.1.4 Computational Aspects.- 2.1.5 Generalizations.- 2.1.6 The Linear Programming Problem.- 2.1.7 The Linearization Method with Equality-Type Constraints.- 2.1.8 Simple Constraints.- 2.1.9 Choice of Parameters in the Linearization Method. Modified Algorithm.- 2.2 Resolution of Systems of Equations and Inequalities.- 2.2.1 The Auxiliary Problem.- 2.2.2 The Algorithm.- 2.2.3 Convergence of the Algorithm.- 2.3 Acceleration of the Convergence of the Linearization Method.- 2.3.1 Main Assumptions.- 2.3.2 Local Analysis of the Auxiliary Problem.- 2.3.3 Preliminary Lemmas.- 2.3.4 The Linearization Algorithm and Acceleration of Convergence.- 2.3.5 Linear Transformations of the Problem.- 2.3.6 Modifications of the Linearization Method.- 3. The Discrete Minimax Problem and Algorithms.- 3.1 The Discrete Minimax Problem.- 3.1.1 The Auxiliary Problem.- 3.1.2 Some Bounds.- 3.1.3 Algorithms.- 3.1.4 Algorithm for Ak =In.- 3.1.5 Acceleration of Convergence in the Convex Case.- 3.2 The Dual Algorithm for Convex Programming Problems.- 3.2.1 The Dual Algorithm.- 3.2.2 Bounds on the Rate of Convergence.- 3.2.3 An Algorithm for Convex Programming Problems.- 3.3 Algorithms and Examples.- 3.3.1 The Linearization Method.- 3.3.2 The Accelerated Linearization Method.- 3.3.3 Examples of Calculations.- Appendix: Comments on the Literature.- References.

O autorze

Techniques of optimization are applied in many problems to economics, automatic control, engineering etc. This book, written by one of the leading specialists of optimization theory, provides a brief yet quite complete exposition of the most effective method of the solution of optimization problems.