Introduction to Optimization, 1987, 464 pp., ISBN 0-911575-14-6, $95.00

Treatise on current theory and techniques of numerical optimization, covering a wide range of topics from Linear Programming through Unconstrained Minimization to Stochastic Programming. A unique feature is the treatment of errors due to noise in optimization. Accessible to Engineers and Economists. "... the first comprehensive synthesis of nonlinear programming methodologies ... in the West and the Soviet Union" -- from the foreword by Professor D. Bertsekas of the MIT.
 

Foreword ..... xv

Preface ..... xvii

Introduction ..... xix

Notation ..... xxv
 

1.1. Review of Mathematical Analysis ..... 2

1.1.1. Differentiation of Scalar Functions ..... 2

1.1.2. Differentiation of Vector Functions ..... 5

1.1.3. Second Derivatives ..... 6

1.1.4. Convex Functions ..... 8

1.2. Extremum Conditions ..... 11

1.2.1. A First-Order Necessary Condition ..... 11

1.2.2. A First-Order Sufficient Condition ..... 12

1.2.3. A Second-Order Necessary Condition ..... 12

1.2.4. A Second-Order Sufficient Condition ..... 13

1.2.5. What are Extremum Conditions Good for? ..... 14

1.3. Existence, Uniqueness, and Stability of a Minimum ..... 14

1.3.1. Existence of a Minimum ..... 14

1.3.2. Uniqueness of a Solution ..... 15

1.3.3. Stability of a Solution ..... 16

1.4. The Gradient Method ..... 20

1.4.1. Heuristic Considerations ..... 20

1.4.2. Convergence ..... 21

1.5. Newton’s Method ..... 27

1.5.1. Heuristic Considerations ..... 27

1.5.2. Convergence ..... 28

1.5.3. Newton’s Method for Solving Equations ..... 31

1.6. The Role of Convergence Theorems ..... 31

1.6.1. Extreme Viewpoints ..... 31

1.6.2. Why are Convergence Theorems Necessary? ..... 32

1.6.3. Proceed with Caution ..... 34
 

2.1. Lyapunov’s First Method ..... 37

2.1.1. Review of Linear Algebra ..... 37

2.1.2. Theorems on Linear Convergence ..... 40

2.1.3. A Theorem on Superlinear Convergence ..... 42

2.2. Lyapunov’s Second Method ..... 43

2.2.1. Lemmas on Numerical Sequences ..... 43

2.2.2. Lemmas on Random Sequences ..... 47

2.2.3. The Main Theorems ..... 50

2.2.4. Possible Modifications ..... 54

2.3. Other Schemes ..... 56

2.3.1. The Contraction Mapping Principle ..... 56

2.3.2. The Implicit Function Theorem ..... 57

2.3.3. The Role of General Schemes for Investigating Convergence ..... 58
 

3.1. Modifications of the Gradient Method and of Newton’s Method ..... 59

3.1.1. Advantages and Drawbacks of the Earlier Methods ..... 59

3.1.2. Modifications of the Gradient Method ..... 60

3.1.3. Modifications of Newton’s Method ..... 63

3.2. Multistep Methods ..... 65

3.2.1. The Heavy Ball Method ..... 65

3.2.2. The Conjugate Gradient Method ..... 68

3.3. Other First-Order Methods ..... 75

3.3.1. Quasi-Newton Methods ..... 75

3.3.2. Methods of Variable Metric and Methods of Conjugate Directions ..... 78

3.3.3. The Secant Method ..... 81

3.3.4. Other Approaches for Constructing the First-Order Methods ..... 83

3.4. Direct Methods ..... 87

3.4.1. General Characteristics ..... 87

3.4.2. Methods of Linear Approximation ..... 87

3.4.3. Nonlocal Linear Approximation ..... 90

3.4.4. Quadratic Approximation ..... 92
 

4.1. Sources and Types of Noise ..... 95

4.1.1. Sources of Noise ..... 95

4.1.2. Types of Noise ..... 97

4.2. The Gradient Method in the Presence of Noise ..... 98

4.2.1. The Statement of the Problem ..... 98

4.2.2. Absolute Deterministic Noise ..... 98

4.2.3. Relative Deterministic Noise ..... 100

4.2.4. Absolute Random Noise ..... 100

4.2.5. Relative Random Noise ..... 102

4.3. Other Minimization Methods in the Presence of Noise ..... 103

4.3.1. Newton’s Method ..... 103

4.3.2. Multistep Methods ..... 104

4.3.3. Other Methods ..... 105

4.4. Direct Methods ..... 106

4.4.1. The Statement of the Problem ..... 106

4.4.2. Difference Methods for Random Noise ..... 106

4.4.3. Other Methods ..... 109

4.5. Optimal Methods in the Presence of Noise ..... 111

4.5.1. Potential Possibilities of Iterative Methods ..... 111

4.5.2. Optimal Algorithms ..... 116
 

5.1. Convex Analysis: Fundamentals ..... 119

5.1.1. Convex Sets and Projection ..... 120

5.1.2. Separation Theorems ..... 122

5.1.3. Convex Nondifferentiable Functions ..... 124

5.1.4. The Subgradient ..... 127

5.1.5. The -subgradient ..... 132

5.2. Extremum Conditions, Existence, Uniqueness, and Stability of a Solution ..... 133

5.2.1. Extremum Conditions ..... 133

5.2.2. Existence and Uniqueness of a Minimum ..... 135

5.2.3. Stability of a Minimum ..... 135

5.3. The Subgradient Method ..... 138

5.3.1. The Substance of the Method ..... 138

5.3.2. The Main Results ..... 140

5.3.3. The -subgradient Method ..... 144

5.4. Alternative Methods ..... 145

5.4.1. Preliminary Remarks ..... 145

5.4.2. Multistep Methods ..... 146

5.4.3. Optimal Methods ..... 153

5.4.4. Space Extension Methods ..... 154

5.5. The Influence of Noise ..... 158

5.5.1. The Statement of the Problem ..... 158

5.5.2. Absolute Deterministic Noise ..... 158

5.5.3. Relative Deterministic Noise ..... 159

5.5.4. Absolute Random Noise ..... 159

5.6. Search Methods ..... 160

5.6.1. The One-Dimensional Case ..... 160

5.6.2. The Multidimensional Case ..... 162
 

6.1. A Singular Minimum ..... 165

6.1.1. The Behavior of Standard Methods ..... 165

6.1.2. Special Methods for Singular Problems ..... 173

6.1.3. Methods in the Presence of Noise ..... 179

6.1.4. Summary ..... 182

6.2. Multimodality ..... 185

6.2.1. Preliminary Remarks ..... 185

6.2.2. Exact Methods ..... 187

6.2.3. Deterministic Heuristic Methods ..... 189

6.2.4. Stochastic Heuristic Methods ..... 192

6.3. Nonstationary Problems ..... 194

6.3.1. The Form of f(x, t) is Known ..... 194

6.3.2. The Form of f(x, t) is Unknown ..... 195

6.3.3. Summary ..... 196
 

7.1. Theoretical Foundations ..... 200

7.1.1. Extremum Conditions in the Smooth Case ..... 200

7.1.2. Extremum Conditions in the Convex Case ..... 203

7.1.3. Existence, Uniqueness, and Stability of a Minimum ..... 204

7.2. Basic Methods ..... 206

7.2.1. The Gradient Projection Method ..... 206

7.2.2. The Subgradient Projection Method ..... 210

7.2.3. The Conditional Gradient Method ..... 210

7.2.4. Newton’s Method ..... 214

7.3. Other Methods ..... 216

7.3.1. Quasi-Newton Methods ..... 216

7.3.2. The Conjugate Gradient Method ..... 219

7.3.3. Minimization of Nonsmooth Functions ..... 221

7.4. The Influence of Noise ..... 221

7.4.1. Absolute Deterministic Noise ..... 221

7.4.2. Absolute Random Noise ..... 222

7.4.3. Relative Noise ..... 223
 

8.1. Theoretical Foundations ..... 224

8.1.1. Lagrange Multipliers ..... 224

8.1.2. Second-Order Minimum Conditions ..... 230

8.1.3. The Usage of Extremum Conditions ..... 233

8.1.4. Existence, Uniqueness, and Stability of a Solution ..... 234

8.2. Minimization Methods ..... 237

8.2.1. Classification of the Methods ..... 237

8.2.2. The Linearization Method ..... 238

8.2.3. Dual Methods ..... 240

8.2.4. The Augmented Lagrangian Method ..... 241

8.2.5. The Penalty Function Method ..... 244

8.2.6. The Reduced Gradient Method ..... 245

8.2.7. Newton’s Method ..... 246

8.2.8. Other Quadratically Convergent Methods ..... 247

8.3. How to Handle Possible Complications ..... 248

8.3.1. A Global Minimum ..... 248

8.3.2. Noise ..... 249

8.3.3. A Singular Minimum ..... 251

8.3.4. Incompatibility of Constraints ..... 252
 

9.1. The Theory of Convex Programming ..... 253

9.1.1. Convex Analysis: Fundamentals ..... 253

9.1.2. The Kuhn-Tucker Theorem ..... 259

9.1.3. Duality ..... 265

9.1.4. Existence, Uniqueness, and Stability of a Solution ..... 268

9.2. Nonlinear Programming (Theory) ..... 270

9.2.1. Necessary Conditions for a Minimum ..... 270

9.2.2. Sufficient Conditions for a Minimum ..... 274

9.2.3. Uniqueness and Stability of a Solution ..... 276

9.3. Convex Programming Methods ..... 279

9.3.1. Methods of Feasible Directions ..... 280

9.3.2. The Linearization Method ..... 282

9.3.3. Dual Methods ..... 283

9.3.4. Penalty Methods and Related Methods ..... 288

9.3.5. Methods for Nonsmooth Problems ..... 292

9.3.6. Summary ..... 296

9.4. Nonlinear Programming Methods ..... 296

9.4.1. The Linearization Method ..... 297

9.4.2. Newton-like and Quasi-Newton Methods ..... 298

9.4.3. Other Methods ..... 300
 

10.1. Linear Programming (Theory) ..... 302

10.1.1. Types of Problems ..... 302

10.1.2. Structure of Polyhedral Sets ..... 304

10.1.3. Extremum Conditions ..... 309

10.1.4. Existence, Uniqueness, and Stability of a Solution ..... 312

10.2. Finite Linear Programming Methods ..... 317

10.2.1. The Simplex Method ..... 317

10.2.2. Implementation of the Simplex Method ..... 320

10.2.3. Other Finite Methods ..... 321

10.2.4. Why Does the Simplex Method Work?

10.3. Iterative Methods of Linear Programming ..... 325

10.3.1. The Need for Iterative Methods ..... 325

10.3.2. Iterative Finite Methods ..... 326

10.3.3. Reduction to Nonsmooth Minimization ..... 329

10.3.4. The Lagrange Functions ..... 332

10.3.5. Summary ..... 334

10.4. Quadratic Programming ..... 334

10.4.1. Extremum Conditions ..... 335

10.4.2. Existence, Uniqueness, and Stability of a Solution ..... 337

10.4.3. Finite Methods ..... 338

10.4.4. Iterative Methods ..... 339
 

11.1. Identification Problems ..... 342

11.1.1. Statistical Problems of Parameter Estimation ..... 343

11.1.2. Regression Problems ..... 345

11.1.3. Robust Estimation ..... 347

11.1.4. Recursive Estimation ..... 350

11.1.5. Data Analysis ..... 352

11.1.6. Other Identification Problems ..... 356

11.2. Optimization Problems in Engineering and Economics ..... 358

11.2.1. Optimal Design ..... 358

11.2.2. Optimal Allocation of Resources ..... 360

11.2.3. Optimal Planning ..... 361

11.2.4. Optimization under Uncertainty ..... 364

11.2.5. Extremal Control ..... 366

11.2.6. Optimal Control ..... 367

11.3. Optimization Problems in Mathematics and Physics ..... 371

11.3.1. Optimal Approximation Problems ..... 371

11.3.2. Geometric Extremum Problems ..... 373

11.3.3. Variational Principles in Physics ..... 375
 

12.1. Solution of a Problem ..... 377

12.1.1. The Mathematical "Formalization" of a Problem ..... 377

12.1.2. The Choice of Methods and Codes ..... 379

12.1.3. Evaluation of Solutions ..... 380

12.2. Optimization Software ..... 381

12.2.1. General Requirements ..... 381

12.3. Test Problems and Computational Results ..... 381

12.3.1. Criteria for a Comparative Analysis of Algorithms. Empirical Results ..... 382

12.3.2. Test Problems: General Requirements ..... 383

12.3.3. Unconstrained Minimization of Smooth Functions ..... 384

12.3.4. Unconstrained Minimization of Nonsmooth Functions ..... 391

12.3.5. Nonlinear Programming ..... 393

12.3.6. Linear Programming ..... 398
 

Notes ..... 401

References ..... 415

Index ..... 434