|
PRACTICAL OPTIMIZATION: Algorithms and Engineering Applications The rapid advancements in the efficiency of digital computers and the evolution of reliable software for numerical computation during the past three decades have led to an astonishing growth in the theory, methods, and algorithms of numerical optimization. This body of knowledge has, in turn, motivated widespread applications of optimization methods in many disciplines, e.g., engineering, business, and science, and led to problem solutions that were considered intractable not too long ago. Although excellent books are available that treat the subject of optimization with great mathematical rigor and precision, there appears to be a need for a book that provides a practical treatment of the subject aimed at a broader audience ranging from college students to scientists and industry professionals. This book has been written to address this need. It treats unconstrained and constrained optimization in a unified manner and places special attention on the algorithmic aspects of optimization to enable readers to apply the various algorithms and methods to specific problems of interest. To facilitate this process, the book provides many solved examples that illustrate the principles involved, and includes, in addition, two chapters that deal exclusively with applications of unconstrained and constrained optimization methods to problems in the areas of pattern recognition, control systems, robotics, communication systems, and the design of digital filters. For each application, enough background information is provided to promote the understanding of the optimization algorithms used to obtain the desired solutions. Chapter 1 gives a brief introduction to optimization and the general structure of optimization algorithms. Chapters 2 to 9 are concerned with unconstrained optimization methods. The basic principles of interest are introduced in Chapter 2. These include the first-order and second-order necessary conditions for a point to be a local minimizer, the second-order sufficient conditions, and the optimization of convex functions. Chapter 3 deals with general properties of algorithms such as the concepts of descent function, global convergence, and rate of convergence. Chapter 4 presents several methods for one-dimensional optimization, which are commonly referred to as line searches. The chapter also deals with inexact line-search methods that have been found to increase the efficiency in many optimization algorithms. Chapter 5 presents several basic gradient methods that include the steepest descent, Newton, and Gauss-Newton methods. Chapter 6 presents a class of methods based on the concept of conjugate directions such as the conjugate-gradient, Fletcher-Reeves, Powell, and Partan methods. An important class of unconstrained optimization methods known as quasi-Newton methods is presented in Chapter 7. Representative methods of this class such as the Davidon-Fletcher-Powell and Broydon-Fletcher-Goldfarb-Shanno methods and their properties are investigated. The chapter also includes a practical, efficient, and reliable quasi-Newton algorithm that eliminates some problems associated with the basic quasi-Newton method. Chapter 8 presents minimax methods that are used in many applications including the design of digital filters. Chapter 9 presents three case studies in which several of the unconstrained optimization methods described in Chapters 4 to 8 are applied to point pattern matching, inverse kinematics for robotic manipulators, and the design of digital filters. Chapters 10 to 16 are concerned with constrained optimization methods. Chapter 10 introduces the fundamentals of constrained optimization. The concept of Lagrange multipliers, the first-order necessary conditions known as Karush-Kuhn-Tucker conditions, and the duality principle of convex programming are addressed in detail and are illustrated by many examples. Chapters 11 and 12 are concerned with linear programming (LP) problems. The general properties of LP and the simplex method for standard LP problems are addressed in Chapter 11. Several interior-point methods including the primal affine-scaling, primal Newton-barrier, and primal dual-path following methods are presented in Chapter 12. Chapter 13 deals with quadratic and general convex programming. The so-called active-set methods and several interior-point methods for convex quadratic programming are investigated. The chapter also includes the so-called cutting plane and ellipsoid algorithms for general convex programming problems. Chapter 14 presents two special classes of convex programming known as semidefinite and second-order cone programming, which have found interesting applications in a variety of disciplines. Chapter 15 treats general constrained optimization problems that do not belong to the class of convex programming; special emphasis is placed on several sequential quadratic programming methods that are enhanced through the use of efficient line searches and approximations of the Hessian matrix involved. Chapter 16, which concludes the book, examines several applications of constrained optimization for the design of digital filters, for the control of dynamic systems, for evaluating the force distribution in robotic systems, and in multiuser detection for wireless communication systems. The book also includes two appendices, A and B, which provide additional support material. Appendix A deals in some detail with the relevant parts of linear algebra to consolidate the understanding of the underlying mathematical principles involved whereas Appendix B provides a concise treatment of the basics of digital filters to enhance the understanding of the design algorithms included in Chaps. 8, 9, and 16. The book can be used as a text for a sequence of two one-semester courses on optimization. The first course comprising Chaps. 1 to 7, 9, and part of Chap. 10 may be offered to senior undergraduate or first-year graduate students. The prerequisite knowledge is an undergraduate mathematics background of calculus and linear algebra. The material in Chaps. 8 and 10 to 16 may be used as a text for an advanced graduate course on minimax and constrained optimization. The prerequisite knowledge for this course is the contents of the first optimization course. The book is supported by online solutions of the end-of-chapter problems under password as well as by a collection of MATLAB programs for free access by the readers of the book, which can be used to solve a variety of optimization problems. These materials can be downloaded from the book's website: http://www.ece.uvic.ca/~optimization We are grateful to many of our past students at the University of Victoria, in particular, Drs. M. L. R. de Campos, S. Netto, S. Nokleby, D. Peters, and Mr. J. Wong who took our optimization courses and have helped improve the manuscript in one way or another; to Chi-Tang Catherine Chang for typesetting the first draft of the manuscript and for producing most of the illustrations; to R. Nongpiur for checking a large part of the index; and to P. Ramachandran for proofreading the entire manuscript. We would also like to thank Professors M. Ahmadi, C. Charalambous, P. S. R. Diniz, Z. Dong, T. Hinamoto, and P. P. Vaidyanathan for useful discussions on optimization theory and practice; Tony Antoniou of Psicraft Studios for designing the book cover; the Natural Sciences and Engineering Research Council of Canada for supporting the research that led to some of the new results described in Chapters 8, 9, and 16; and last but not least the University of Victoria for supporting the writing of this book over a number of years. Andreas Antoniou and Wu-Sheng Lu
|