Practical Optimization

by Antoniou, Andreas; Lu, Wu-Sheng

• ISBN13: 9780387711065
• ISBN10: 0387711066
• Format: Hardcover
• Copyright: 2007-03-12
• Publisher: Springer-Verlag New York Inc

Summary

Practical Optimization: Algorithms and Engineering Applications provides a hands-on treatment of the subject of optimization. A comprehensive set of problems and exercises makes the book suitable for use in one or two semesters of a first-year graduate course or an advanced undergraduate course. Each half of the book contains a full semester's worth of complimentary yet stand-alone material. The practical orientation of the topics chosen and a wealth of useful examples also make the book suitable as a reference work for practitioners in the field. Advancements in the efficiency of digital computers and the evolution of reliable software for numerical computation during the past three decades have led to a rapid growth in the theory, methods, and algorithms of numerical optimization. This body of knowledge has motivated widespread applications of optimization methods in many disciplines, e.g., engineering, business, and science, and has subsequently led to problem solutions that were considered intractable not too long ago. Key Features: extensively class-tested provides a complete teaching package with MATLAB exercises and online solutions to end-of-chapter problems includes recent methods of emerging interest such as semidefinite programming and second-order cone programming presents a unified treatment of unconstrained and constrained optimization uses a practical treatment of optimization accessible to broad audience, from college students to scientists and industry professionals provides a thorough appendix with background theory so non-experts can understand how applications are solved from point of view of optimization

Author Biography

Andreas Antoniou received the Ph.D. degree in Electrical Engineering from the University of London, UK, in 1966 and is a Fellow of the IET and IEEE. He served as the founding Chair of the Department of Electrical and Computer Engineering at the University of Victoria, B.C., Canada, and is now Professor Emeritus in the same department. He is the author of Digital Filters: Analysis, Design, and Applications (McGraw-Hill, 1993) and Digital Signal Processing: Signals, Systems, and Filters (McGraw-Hill, 2005). He served as Associate Editor/Editor of IEEE Transactions on Circuits and Systems from June 1983 to May 1987, as a Distinguished Lecturer of the IEEE Signal Processing Society in 2003, as General Chair of the 2004 International Symposium on Circuits and Systems, and is currently serving as a Distinguished Lecturer of the IEEE Circuits and Systems Society. He received the Ambrose Fleming Premium for 1964 from the IEEE (best paper award), the CAS Golden Jubilee Medal from the IEEE Circuits and Systems Society, the B.C. Science Council Chairman's Award for Career Achievement for 2000, theDoctorHonoris Causa degree from the Metsovio National Technical University of Athens, Greece, in 2002, and the IEEE Circuits and Systems Society 2005 Technical Achievement Award.Wu-Sheng Lu received the B.S. degree in Mathematics from Fudan University, Shanghai, China, in 1964, the M.E. degree in Automation from the East China Normal University, Shanghai, in 1981, the M.S. degree in Electrical Engineering and the Ph.D. degree in Control Science from the University of Minnesota, Minneapolis, in 1983 and 1984, respectively. He was a post-doctoral fellow at the University of Victoria, Victoria, BC, Canada, in 1985 and Visiting Assistant Professor with the University of Minnesota in 1986. Since 1987, he has been with the University of Victoria where he is Professor. His current teaching and research interests are in the general areas of digital signal processing and application of optimization methods. He is the co-author with A. Antoniou of Two-Dimensional Digital Filters (Marcel Dekker, 1992). He served as an Associate Editor of the Canadian Journal of Electrical and Computer Engineering in 1989, and Editor of the same journal from 1990 to 1992. He served as an Associate Editor for the IEEE Transactions on Circuits and Systems, Part II, from 1993 to 1995 and for Part I of the same journal from 1999 to 2001 and from 2004 to 2005. Presently he is serving as Associate Editor for the International Journal of Multidimensional Systems and Signal Processing. He is a Fellow of the Engineering Institute of Canada and the Institute of Electrical and Electronics Engineers.

Table of Contents

Dedication	p. v
Biographies of the authors	p. vii
Preface	p. xv
Abbreviations	p. xix
The Optimization Problem	p. 1
Introduction	p. 1
The Basic Optimization Problem	p. 4
General Structure of Optimization Algorithms	p. 8
Constraints	p. 10
The Feasible Region	p. 17
Branches of Mathematical Programming	p. 22
References	p. 24
Problems	p. 25
Basic Principles	p. 27
Introduction	p. 27
Gradient Information	p. 27
The Taylor Series	p. 28
Types of Extrema	p. 31
Necessary and Sufficient Conditions for Local Minima and Maxima	p. 33
Classification of Stationary Points	p. 40
Convex and Concave Functions	p. 51
Optimization of Convex Functions	p. 58
References	p. 60
Problems	p. 60
General Properties of Algorithms	p. 65
Introduction	p. 65
An Algorithm as a Point-to-Point Mapping	p. 65
An Algorithm as a Point-to-Set Mapping	p. 67
Closed Algorithms	p. 68
Descent Functions	p. 71
Global Convergence	p. 72
Rates of Convergence	p. 76
References	p. 79
Problems	p. 79
One-Dimensional Optimization	p. 81
Introduction	p. 81
Dichotomous Search	p. 82
Fibonacci Search	p. 85
Golden-Section Search	p. 92
Quadratic Interpolation Method	p. 95
Cubic Interpolation	p. 99
The Algorithm of Davies, Swann, and Campey	p. 101
Inexact Line Searches	p. 106
References	p. 114
Problems	p. 114
Basic Multidimensional Gradient Methods	p. 119
Introduction	p. 119
Steepest-Descent Method	p. 120
Newton Method	p. 128
Gauss-Newton Method	p. 138
References	p. 140
Problems	p. 140
Conjugate-Direction Methods	p. 145
Introduction	p. 145
Conjugate Directions	p. 146
Basic Conjugate-Directions Method	p. 149
Conjugate-Gradient Method	p. 152
Minimization of Nonquadratic Functions	p. 157
Fletcher-Reeves Method	p. 158
Powell's Method	p. 159
Partan Method	p. 168
References	p. 172
Problems	p. 172
Quasi-Newton Methods	p. 175
Introduction	p. 175
The Basic Quasi-Newton Approach	p. 176
Generation of Matrix S[subscript k]	p. 177
Rank-One Method	p. 181
Davidon-Fletcher-Powell Method	p. 185
Broyden-Fletcher-Goldfarb-Shanno Method	p. 191
Hoshino Method	p. 192
The Broyden Family	p. 192
The Huang Family	p. 194
Practical Quasi-Newton Algorithm	p. 195
References	p. 199
Problems	p. 200
Minimax Methods	p. 203
Introduction	p. 203
Problem Formulation	p. 203
Minimax Algorithms	p. 205
Improved Minimax Algorithms	p. 211
References	p. 228
Problems	p. 228
Applications of Unconstrained Optimization	p. 231
Introduction	p. 231
Point-Pattern Matching	p. 232
Inverse Kinematics for Robotic Manipulators	p. 237
Design of Digital Filters	p. 247
References	p. 260
Problems	p. 262
Fundamentals of Constrained Optimization	p. 265
Introduction	p. 265
Constraints	p. 266
Classification of Constrained Optimization Problems	p. 273
Simple Transformation Methods	p. 277
Lagrange Multipliers	p. 285
First-Order Necessary Conditions	p. 294
Second-Order Conditions	p. 302
Convexity	p. 308
Duality	p. 311
References	p. 312
Problems	p. 313
Linear Programming Part I: The Simplex Method	p. 321
Introduction	p. 321
General Properties	p. 322
Simplex Method	p. 344
References	p. 368
Problems	p. 368
Linear Programming Part II: Interior-Point Methods	p. 373
Introduction	p. 373
Primal-Dual Solutions and Central Path	p. 374
Primal Affine-Scaling Method	p. 379
Primal Newton Barrier Method	p. 383
Primal-Dual Interior-Point Methods	p. 388
References	p. 402
Problems	p. 402
Quadratic and Convex Programming	p. 407
Introduction	p. 407
Convex QP Problems with Equality Constraints	p. 408
Active-Set Methods for Strictly Convex QP Problems	p. 411
Interior-Point Methods for Convex QP Problems	p. 417
Cutting-Plane Methods for CP Problems	p. 428
Ellipsoid Methods	p. 437
References	p. 443
Problems	p. 444
Semidefinite and Second-Order Cone Programming	p. 449
Introduction	p. 449
Primal and Dual SDP Problems	p. 450
Basic Properties of SDP Problems	p. 455
Primal-Dual Path-Following Method	p. 458
Predictor-Corrector Method	p. 465
Projective Method of Nemirovski and Cabinet	p. 470
Second-Order Cone Programming	p. 484
A Primal-Dual Method for SOCP Problems	p. 491
References	p. 496
Problems	p. 497
General Nonlinear Optimization Problems	p. 501
Introduction	p. 501
Sequential Quadratic Programming Methods	p. 501
Modified SQP Algorithms	p. 509
Interior-Point Methods	p. 518
References	p. 528
Problems	p. 529
Applications of Constrained Optimization	p. 533
Introduction	p. 533
Design of Digital Filters	p. 534
Model Predictive Control of Dynamic Systems	p. 547
Optimal Force Distribution for Robotic Systems with Closed Kinematic Loops	p. 558
Multiuser Detection in Wireless Communication Channels	p. 570
References	p. 586
Problems	p. 588
Appendices	p. 591
Basics of Linear Algebra	p. 591
Introduction	p. 591
Linear Independence and Basis of a Span	p. 592
Range, Null Space, and Rank	p. 593
Sherman-Morrison Formula	p. 595
Eigenvalues and Eigenvectors	p. 596
Symmetric Matrices	p. 598
Trace	p. 602
Vector Norms and Matrix Norms	p. 602
Singular-Value Decomposition	p. 606
Orthogonal Projections	p. 609
Householder Transformations and Givens Rotations	p. 610
QR Decomposition	p. 616
Cholesky Decomposition	p. 619
Kronecker Product	p. 621
Vector Spaces of Symmetric Matrices	p. 623
Polygon, Polyhedron, Polytope, and Convex Hull	p. 626
References	p. 627
Basics of Digital Filters	p. 629
Introduction	p. 629
Characterization	p. 629
Time-Domain Response	p. 631
Stability Property	p. 632
Transfer Function	p. 633
Time-Domain Response Using the Z Transform	p. 635
Z-Domain Condition for Stability	p. 635
Frequency, Amplitude, and Phase Responses	p. 636
Design	p. 639
Reference	p. 644
Index	p. 645
Table of Contents provided by Ingram. All Rights Reserved.