The Linearization Method for Constrained Optimization

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.