实际优化(算法及工程应用)

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  Classification  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