[Andreas Antoniou]Practical Optimization.pdf

Dedication v Biographies of the authors vii Preface xv Abbreviations xix 1. THE OPTIMIZATION PROBLEM 1 1.1 Introduction 1 1.2 The Basic Optimization Problem 4 1.3 General Structure of Optimization Algorithms 8 1.4 Constraints 10 1.5 The Feasible Region 17 1.6 Branches of Mathematical Programming 22 References 24 Problems 25 2. BASIC PRINCIPLES 27 2.1 Introduction 27 2.2 Gradient Information 27 2.3 The Taylor Series 28 2.4 Types of Extrema 31 2.5 Necessary and Sufficient Conditions for Local Minima and Maxima 33 2.6 Classificatio n of Stationary Points 40 2.7 Convex and Concave Functions 51 2.8 Optimization of Convex Functions 58 References 60 Problems 60 3. GENERAL PROPERTIES OF ALGORITHMS 65 3.1 Introduction 65 3.2 An Algorithm as a Point-to-Point Mapping 65 3.3 An Algorithm as a Point-to-Set Mapping 67 3.4 Closed Algorithms 68 3.5 Descent Functions 71 3.6 Global Convergence 72 3.7 Rates of Convergence 76 References 79 Problems 79 4. ONE-DIMENSIONAL OPTIMIZATION 81 4.1 Introduction 81 4.2 Dichotomous Search 82 4.3 Fibonacci Search 85 4.4 Golden-Section Search 92 4.5 Quadratic Interpolation Method 95 4.6 Cubic Interpolation 99 4.7 The Algorithm of Davies, Swann, and Campey 101 4.8 Inexact Line Searches 106 References 114 Problems 114 5. BASIC MULTIDIMENSIONAL GRADIENT METHODS 119 5.1 Introduction 119 5.2 Steepest-Descent Method 120 5.3 Newton Method 128 5.4 Gauss-Newton Method 138 References 140 Problems 140 6. CONJUGATE-DIRECTION METHODS 145 6.1 Introduction 145 6.2 Conjugate Directions 146 6.3 Basic Conjugate-Directions Method 149 6.4 Conjugate-Gradient Method 152 6.5 Minimization of Nonquadratic Functions 157 6.6 Fletcher-Reeves Method 158 6.7 Powell's Method 159 6.8 Partan Method 168 References 172 XI Problems 172 7. QUASI-NEWTON METHODS 175 7.1 Introduction 175 7.2 The Basic Quasi-Newton Approach 176 7.3 Generation of Matrix Sk 177 7.4 Rank-One Method 181 7.5 Davidon-Fletcher-Powell Method 185 7.6 Broyden-Fletcher-Goldfarb-Shanno Method 191 7.7 Hoshino Method 192 7.8 The Broyden Family 192 7.9 The Huang Family 194 7.10 Practical Quasi-Newton Algorithm 195 References 199 Problems 200 8. MINIMAX METHODS 203 8.1 Introduction 203 8.2 Problem Formulation 203 8.3 Minimax Algorithms 205 8.4 Improved Minimax Algorithms 211 References 228 Problems 228 9. APPLICATIONS OF UNCONSTRAINED OPTIMIZATION 231 9.1 Introduction 231 9.2 Point-Pattern Matching 232 9.3 Inverse Kinematics for Robotic Manipulators 237 9.4 Design of Digital Filters 247 References 260 Problems 262 10. FUNDAMENTALS OF CONSTRAINED OPTIMIZATION 265 10.1 Introduction 265 10.2 Constraints 266 Xll 10.3 Classification of Constrained Optimization Problems 273 10.4 Simple Transformation Methods 277 10.5 Lagrange Multipliers 285 10.6 First-Order Necessary Conditions 294 10.7 Second-Order Conditions 302 10.8 Convexity 308 10.9 Duality 311 References 312 Problems 313 11. LINEAR PROGRAMMING PART I: THE SIMPLEX METHOD 321 11.1 Introduction 321 11.2 General Properties 322 11.3 Simplex Method 344 References 368 Problems 368 12. LINEAR PROGRAMMING PART II: INTERIOR-POINT METHODS 373 12.1 Introduction 373 12.2 Primal-Dual Solutions and Central Path 374 12.3 Primal Affine-Scaling Method 379 12.4 Primal Newton Barrier Method 383 12.5 Primal-Dual Interior-Point Methods 388 References 402 Problems 402 13. QUADRATIC AND CONVEX PROGRAMMING 407 13.1 Introduction 407 13.2 Convex QP Problems with Equality Constraints 408 13.3 Active-Set Methods for Strictly Convex QP Problems 411 13.4 Interior-Point Methods for Convex QP Problems 417 13.5 Cutting-Plane Methods for CP Problems 428 13.6 Ellipsoid Methods 437 References 443 Xlll Problems 444 14. SEMIDEFINITE AND SECOND-ORDER CONE PROGRAMMING 449 14.1 Introduction 449 14.2 Primal and Dual SDP Problems 450 14.3 Basic Properties of SDP Problems 455 14.4 Primal-Dual Path-Following Method 458 14.5 Predictor-Corrector Method 465 14.6 Projective Method of Nemirovski and Gahinet 470 14.7 Second-Order Cone Programming 484 14.8 A Primal-Dual Method for SOCP Problems 491 References 496 Problems 497 15. GENERAL NONLINEAR OPTIMIZATION PROBLEMS 501 15.1 Introduction 501 15.2 Sequential Quadratic Programming Methods 501 15.3 Modified SQP Algorithms 509 15.4 Interior-Point Methods 518 References 528 Problems 529 16. APPLICATIONS OF CONSTRAINED OPTIMIZATION 533 16.1 Introduction 533 16.2 Design of Digital Filters 534 16.3 Model Predictive Control of Dynamic Systems 547 16.4 Optimal Force Distribution for Robotic Systems with Closed Kinematic Loops 558 16.5 Multiuser Detection in Wireless Communication Channels 570 References 586 Problems 588 Appendices 591 A Basics of Linear Algebra 591 A. 1 Introduction 591 XIV A.2 Linear Independence and Basis of a Span 592 A.3 Range, Null Space, and Rank 593 A.4 Sherman-Morrison Formula 595 A.5 Eigenvalues and Eigenvectors 596 A.6 Symmetric Matrices 598 A.7 Trace 602 A.8 Vector Norms and Matrix Norms 602 A.9 Singular-value Decomposition 606 A. 10 Orthogonal Projections 609 A.l 1 Householder Transformations and Givens Rotations 610 A. 12 QR Decomposition 616 A. 13 Cholesky Decomposition 619 A. 14 Kronecker Product 621 A. 15 Vector Spaces of Symmetric Matrices 623 A. 16 Polygon, Polyhedron, Polytope, and Convex Hull 626 References 627 B Basics of Digital Filters 629 B.l Introduction 629 B.2 Characterization 629 B. 3 Time-Domain Response 631 B.4 Stability Property 632 B.5 Transfer Function 633 B.6 Time-Domain Response Using the Z Transform 635 B.7 Z-Domain Condition for Stability 635 B.8 Frequency, Amplitude, and Phase Responses 636 B.9 Design 639 Reference 644 Index 645