Practical Optimization: Algorithms and Engineering Applications

by Andreas Antoniou, Wu-Sheng Lu

Overview

This textbook provides a hands-on treatment of the subject of optimization. A comprehensive set of problems and exercises makes it suitable for use in one or two semesters of an advanced undergraduate course or a first-year graduate course. Each half of the book contains a full semester’s worth of complementary 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.

In this second edition the authors have added sections on recent innovations, techniques, and methodologies.

Product Details

ISBN-13:	9781071608432
Publisher:	Springer-Verlag New York, LLC
Publication date:	10/19/2021
Series:	Texts in Computer Science
Sold by:	Barnes & Noble
Format:	eBook
File size:	77 MB
Note:	This product may take a few minutes to download.

About the Author

Prof. Andreas Antoniou received his Ph.D. in Electrical Engineering from the University of London in 1966 and is a Fellow of the IET and IEEE. He served as the founding Chair of the Dept. of Electrical and Computer Engineering at the University of Victoria, 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 Trans. 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 Intl. Symp. 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, a Doctor Honoris Causa from the Metsovio National Technical University of Athens, Greece, n 2002, and the IEEE Circuits and Systems Society 2005 Technical Achievement Award.

Prof. Wu-Sheng Lu received his B.S. degree in Mathematics from Fudan University, Shanghai, China in 1964, an M.E. degree in Automation from the East China Normal University, Shanghai in 1981, and an M.S. degree in Electrical Engineering and his Ph.D. in Control Science from the University of Minnesota, Minneapolis, n 1983 and 1984, respectively. He was a postdoctoral fellow at the University of Victoria, Canada in 1985 and a visiting Asst. Professor with the University of Minnesota in 1986. Since 1987 he has been with the University of Victoria where he is a full professor. His current teaching and research interests are digital signal processing and the application of optimization methods. He is the coauthor with Prof. Antoniouof 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 Trans. 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 Intl. J. of Multidimensional Systems and Signal Processing. He is a Fellow of the Engineering Institute of Canada and the IEEE.

Table of Contents

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

Editorial Reviews

From the reviews: “Textbook on optimization that provides broad coverage of algorithmic techniques of optimization as well as applications of these techniques to problems in electrical engineering. … The applications presented in the book motivate the development of the algorithms and provide material for exercises. This is a very good way to introduce this audience to optimization. … This textbook is appropriate for its intended audience of graduate students in electrical engineering … .” (Brian Borchers, SIGACT News, Vol. 40 (1), 2010)

From the Publisher