PRACTICAL OPTIMIZATION
Algorithms and Engineering Applications
PRACTICAL OPTIMIZATION
Algorithms and Engineering Applications
Andreas Antoniou
Wu-Sheng Lu
Department of Electrical and Computer Engineering
University of Victoria, Canada
Spri inger
Andreas Antoniou
Department of ECE
University of V ictoria
British Columbia
Canada
aantoniou@shaw.ca
Wu-Sheng Lu
Department of ECE
University of V ictoria
British Columbia
Canada
wslu@ece.uvic,ca
Library of Congress Control Number: 2007922511
Practical Optimization: Algorithms and Engineering Applications
by Andreas Antoniou and Wu-Sheng Lu
ISBN-10: 0-387-71106-6
ISBN-13: 978-0-387-71106-5
e-ISBN-10: 0-387-71107-4
e-ISBN-13: 978-0-387-71107-2
Printed on acid-free paper.
© 2007 Springer Science+Business Media, LLC
All rights reserved. This work may not be translated or copied in whole or in part without the written
permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York,
NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in
connection with any form of information storage and retrieval, electronic adaptation, computer
software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if
they are not identified as such, is not to be taken as an expression of opinion as to whether or not
they are subject to proprietary rights.
9 8 7 6 5 4 3 2 1
springer.com
To
Lynne
and
Chi'Tang Catherine
with our love
About the authors:
Andreas Antoniou received the Ph.D. degree in Electrical Engineering from
the University of London, UK, in 1966 and is a Fellow of the lET 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 lEE (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, the Doctor Honoris 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 Engineer
ing 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 As
sociate 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 Inter
national 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.
Dedication
Biographies of the authors
Preface
Abbreviations
1. THE OPTIMIZATION PROBLEM
Introduction
1.1
1.2 The Basic Optimization Problem
1.3 General Structure of Optimization Algorithms
1.4 Constraints
1.5 The Feasible Region
1.6 Branches of Mathematical Programming
References
Problems
2. BASIC PRINCIPLES
Introduction
2.1
2.2 Gradient Information
2.3 The Taylor Series
2.4 Types of Extrema
2.5 Necessary and Sufficient Conditions for
Local Minima and Maxima
2.6 Classification of Stationary Points
2.7 Convex and Concave Functions
2.8 Optimization of Convex Functions
References
Problems
3. GENERAL PROPERTIES OF ALGORITHMS
Introduction
3.1
3.2 An Algorithm as a Point-to-Point Mapping
3.3 An Algorithm as a Point-to-Set Mapping
3.4 Closed Algorithms
3.5 Descent Functions
3.6 Global Convergence
v
vii
xv
xix
1
1
4
8
10
17
22
24
25
27
27
27
28
31
33
40
51
58
60
60
65
65
65
67
68
71
72
3.7 Rates of Convergence
References
Problems
4. ONE-DIMENSIONAL OPTIMIZATION
Introduction
4.1
4.2 Dichotomous Search
4.3 Fibonacci Search
4.4 Golden-Section Search
4.5 Quadratic Interpolation Method
4.6 Cubic Interpolation
4.7 The Algorithm of Davies, Swann, and Campey
4.8
Inexact Line Searches
References
Problems
5. BASIC MULTIDIMENSIONAL GRADIENT METHODS
Introduction
5.1
5.2 Steepest-Descent Method
5.3 Newton Method
5.4 Gauss-Newton Method
References
Problems
6. CONJUGATE-DIRECTION METHODS
Introduction
6.1
6.2 Conjugate Directions
6.3 Basic Conjugate-Directions Method
6.4 Conjugate-Gradient Method
6.5 Minimization of Nonquadratic Functions
6.6 Fletcher-Reeves Method
6.7 Powell's Method
6.8 Partan Method
References
76
79
79
81
81
82
85
92
95
99
101
106
114
114
119
119
120
128
138
140
140
145
145
146
149
152
157
158
159
168
172