Optimization: algorithms and consistent approximations

Elijah Polak0387949712, 9780387949710

This book covers algorithms and discretization procedures for the solution of nonlinear progamming, semi-infinite optimization and optimal control problems. Among the important features included are the theory of algorithms represented as point-to-set maps, the treatment of min-max problems with and without constraints, the theory of consistent approximation which provides a framework for the solution of semi-infinite optimization, optimal control, and shape optimization problems with very general constraints, using simple algorithms that call standard nonlinear programming algorithms as subroutines, the completeness with which algorithms are analysed, and chapter 5 containing mathematical results needed in optimization from a large assortment of sources.
Readers will find of particular interest the exhaustive modern treatment of optimality conditions and algorithms for min-max problems, as well as the newly developed theory of consistent approximations and the treatment of semi-infinite optimization and optimal control problems in this framework.
This book presents the first treatment of optimization algorithms for optimal control problems with state-trajectory and control constraints, and fully accounts for all the approximations that one must make in their solution.It is also the first to make use of the concepts of epi-convergence and optimality fuctions in the construction of consistent approximations to infinite dimensional problems.
Graduate students, university teachers and optimization practitioners in applied mathematics, engineering and economics will find this book useful.

---

Table of contents :
Front cover……Page 1
Series……Page 3
Applied Mathematical Sciences (continued following index)……Page 4
Title page……Page 5
Date-line……Page 6
Dedication……Page 7
Preface……Page 9
Contents……Page 13
Conventions and Symbols……Page 19
1.1 Optimality Conditions……Page 23
1.1.1 First- and Second-Order Necessary Conditions……Page 25
1.1.2 Sufficient Conditions……Page 33
1.1.3 The Convex Case……Page 35
1.2 Algorithm Models and Convergence Conditions I……Page 37
1.2.1 Geometry of Descent Methods……Page 38
1.2.2 Basic Algorithm Models……Page 40
1.2.3 The Wolfe and Polak-Sargent-Sebastian Theorems……Page 50
1.2.4 A Trust Region Model……Page 57
1.2.5 Algorithm Implementation Theory……Page 62
1.2.6 Rate of Convergence of Sequences……Page 69
1.2.7 Algorithm Efficiency……Page 75
1.2.8 Notes……Page 76
1.3.1 Method of Steepest Descent……Page 78
1.3.2 Armijo Gradient Method……Page 80
1.3.3 Projected Gradient Method……Page 88
1.4.1 The Local Newton Method……Page 92
1.4.2 Global Newton Method for Convex Functions……Page 98
1.4.3 Discrete Newton Method……Page 101
1.4.4 Global Newton Method for General Functions……Page 104
1.4.5 The Iterated Newton Method……Page 105
1.5 Methods of Conjugate Directions……Page 109
1.5.1 Decomposition of Quadratic Functions……Page 110
1.5.2 Methods of Conjugate Gradients……Page 113
1.5.3 Formal Extension to General Functions……Page 116
1.5.4 The Polak-Ribiere Conjugate Gradient Algorithm……Page 117
1.5.5 The Fletcher-Reeves Conjugate Gradient Method……Page 121
1.5.6 Partial Conjugate Gradient Methods……Page 124
1.5.7 Notes……Page 125
1.6 Quasi-Newton Methods……Page 126
1.6.1 The Variable Metric Concept……Page 127
1.6.2 Secant Methods……Page 129
1.6.3 Symmetric Rank-One Updates……Page 133
1.6.4 Symmetric Rank-Two Updates……Page 137
1.6.5 Finite Convergence on Quadratic Functions……Page 139
1.6.6 Global Convergence on Convex Functions……Page 146
1.6.7 Notes……Page 159
1.7 One-Dimensional Optimization……Page 160
1.7.1 Secant Method Based on Cubic Interpolation……Page 161
1.7.2 The Golden Section Search……Page 168
1.7.3 Method of Sequential Quadratic Interpolations……Page 171
1.8 Newton’s Method for Equations and Inequalities……Page 179
1.8.1 Mangasarian – Fromowitz Constraint Qualification……Page 180
1.8.2 The Local Newton Algorithm……Page 183
1.8.4 Notes……Page 188
2 Finite Min-Max and Constrained Optimization……Page 189
2.1 Optimality Conditions for Min-Max……Page 190
2.1.1 First-Order Conditions……Page 191
2.1.2 Optimality Functions……Page 194
2.1.3 Second-Order Conditions……Page 200
2.2.1 First-Order Optimality Conditions for ICP……Page 207
2.2.2 An Optimality Function for ICP……Page 212
2.2.3 Second-Order Conditions for ICP……Page 215
2.2.4 First-Order Optimality Conditions for IECP……Page 219
2.2.5 Second-Order Optimality Conditions for IECP……Page 226
2.2.6 Notes……Page 236
2.3.1 Algorithm Models for ICP……Page 237
2.3.2 Algorithm Models for IECP……Page 241
2.4.1 The PPP Min-Max Algorithm……Page 244
2.4.2 Rate of Convergence of the PPP Algorithm……Page 246
2.4.3 Algorithms for Search Direction Computation……Page 249
2.4.4 Quadratic Convergence to a Haar Point……Page 259
2.4.5 Box-Constrained Min-Max Algorithm……Page 264
2.4.6 A Barrier Function Method……Page 266
2.4.7 Notes……Page 270
2.5 Newton’s Method for Min-Max Problems……Page 272
2.5.1 The Local Newton Method……Page 273
2.5.2 The Global Newton Method……Page 277
2.5.3 Notes……Page 280
2.6 Phase I – Phase II Methods of Centers……Page 281
2.6.1 Min-Max-Type Phase I – Phase II Methods……Page 282
2.6.2 Rate of Convergence……Page 286
2.6.3 A Barrier Function Method……Page 296
2.6.4 Notes……Page 301
2.7 Penalty Function Algorithms……Page 302
2.7.1 Basic Theory of Penalty Functions……Page 303
2.7.2 Exact Penalty Functions……Page 313
2.7.3 Exact Penalty Function Algorithms……Page 325
2.7.4 Notes……Page 333
2.8.1 Problems with Equality Constraints……Page 337
2.8.2 Problems with Mixed Constraints……Page 346
2.9 Sequential Quadratic Programming……Page 355
2.9.1 Wilson’s Method……Page 356
2.9.2 Pang’s Method……Page 361
2.9.3 The Local Maratos-Mayne-Polak Method for (2)……Page 366
2.9.4 Global MMP Algorithm for (2)……Page 376
2.9.5 The Maratos-Mayne-Polak-Pang Method for (1)……Page 381
2.9.6 Notes……Page 388
3 Semi-Infinite Optimization……Page 390
3.1.1 First-Order Optimality Conditions for SMMP……Page 391
3.1.2 An Optimality Function for SMMP……Page 394
3.1.3 Second-Order Conditions for SMMP……Page 396
3.2 Optimality Conditions for Constrained Semi-Infinite Optimization……Page 400
3.2.1 First-Order Optimality Conditions for SICP……Page 401
3.2.2 An Optimality Function for SICP……Page 403
3.2.3 Second-Order Conditions for SICP……Page 404
3.2.4 First-Order Optimality Conditions for SIECP……Page 407
3.2.5 Second-Order Conditions for SIECP……Page 409
3.3 Theory of Consistent Approximations……Page 411
3.3.1 Epi-convergence and Optimality Functions……Page 412
3.3.2 Penalty Functions……Page 422
3.3.3 Master Algorithm Models……Page 423
3.4 Semi-Infinite Min-Max Algorithms……Page 440
3.4.1 Consistent Approximations……Page 441
3.4.2 Algorithms Based on Algorithm Models 3.3.12 and 3.3.17……Page 445
3.4.3 PPP Rate-Preserving Min-Max Algorithm……Page 448
3.4.4 Newton Rate-Preserving Min-Max Algorithm……Page 453
3.4.5 Method of Outer Approximations……Page 458
3.4.6 Notes……Page 466
3.5 Algorithms for Inequality-Constrained Semi-Infinite Optimization……Page 467
3.5.1 Consistent Approximations……Page 468
3.5.2 Algorithms Based on Algorithm Models 3.3.14 and 3.3.20……Page 471
3.5.3 Method of Outer Approximations……Page 482
3.5.4 Notes……Page 487
3.6 Algorithms for Semi-Infinite Optimization with Mixed Constraints……Page 488
3.6.1 Consistent Approximations……Page 489
3.6.2 Method of Outer Approximations……Page 491
3.6.3 An Exact Penalty Function Algorithm……Page 493
3.6.4 Notes……Page 503
4.1 Canonical Forms of Optimal Control Problems……Page 504
4.1.1 Properties of Defining Functions……Page 508
4.1.2 Transcription into Canonical Form……Page 515
4.1.3 Numerical Integration……Page 516
4.2 Optimality Conditions for Optimal Control……Page 517
4.2.1 Unconstrained Optimal Control……Page 519
4.2.2 Min-Max Optimal Control……Page 524
4.2.3 Optimal Control with Inequality Constraints……Page 533
4.2.4 Optimal Control with Equality Constraints……Page 537
4.2.5 Optimal Control with Equality and Inequality Constraints……Page 551
4.2.6 Notes……Page 554
4.3 Algorithms for Unconstrained Optimal Control……Page 556
4.3.1 Consistent Approximations……Page 557
4.3.2 Problem Reformulation on $mathbb{R}^n times mathbb{R}^{mN}$……Page 563
4.3.3 Algorithms Based on Master Algorithm Model 3.3.12……Page 566
4.3.4 Algorithms Based on Master Algorithm Model 3.3.17……Page 568
4.3.5 Algorithms Based on Master Algorithm Model 3.3.20……Page 570
4.3.6 Implementation of Newton’s Method……Page 578
4.3.7 Notes……Page 582
4.4 Min-Max Algorithms for Optimal Control……Page 584
4.4.1 Consistent Approximations……Page 585
4.4.2 Problem Reformulation on $mathbb{R}^n times mathbb{R}^{mN}$……Page 595
4.4.3 Algorithms Based on Master Algorithm Model 3.3.12……Page 597
4.4.4 Algorithms Based on Master Algorithm Model 3.3.17……Page 601
4.4.5 Algorithms Based on Master Algorithm Model 3.3.20……Page 605
4.4.6 Method of Outer Approximations……Page 609
4.5 Algorithms for Problems with State Constraints I: Inequality Constraints……Page 611
4.5.1 Consistent Approximations……Page 612
4.5.2 Problem Reformulation on $mathbb{R}^n times mathbb{R}^m$……Page 616
4.5.3 Algorithms Based on Master Algorithm Model 3.3.14……Page 618
4.5.4 Algorithms Based on Master Algorithm Model 3.3.27……Page 624
4.5.5 Method of Outer Approximations……Page 628
4.5.6 Notes……Page 630
4.6 Algorithms for Problems with State Constraints II: Equality Constraints……Page 631
4.6.1 Consistent Approximations……Page 632
4.6.2 An Exact Penalty Function Algorithm……Page 643
4.7 Algorithms for Problems with State Constraints III: Equality and Inequality Constraints……Page 652
4.7.1 Consistent Approximations……Page 653
4.7.2 An Exact Penalty Function Algorithm……Page 659
4.7.3 Notes……Page 665
5.1.1 Real Normed Spaces……Page 668
5.1.2 Properties of Continuous Functions……Page 673
5.1.3 Derivatives and Expansion Formulas……Page 677
5.1.4 Directional Derivatives and Subgradients……Page 682
5.1.5 The Implicit Function Theorem……Page 686
5.2 Convex Sets and Convex Functions……Page 687
5.2.1 Convex Sets……Page 688
5.2.2 Convex Functions……Page 690
5.3.1 Outer and Inner Semicontinuity……Page 698
5.3.2 Notes……Page 703
5.4.1 Maximum Theorems……Page 704
5.4.2 Directional Derivatives and Subgradients……Page 707
5.4.3 A Mean-Value Theorem……Page 716
5.5.1 Duality and Discrete Minimax Theorems……Page 718
5.5.2 The von Neumann Theorem……Page 725
5.6 Differential Equations……Page 731
5.6.1 Existence, Uniqueness, and Boundedness of Solutions……Page 733
5.6.2 Lipschitz Continuity and Differentiability of Solutions……Page 736
5.6.3 Discrete-Time Approximations……Page 743
5.6.4 Bounds on Approximation Errors……Page 758
5.6.5 Notes……Page 764
Bibliography……Page 765
Index……Page 795
Applied Mathematical Sciences (continued)……Page 802
Back cover……Page 804