An Introduction to Optimization E-Book

Edwin K. P. Chong

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley-Interscience Series in Discrete Mathematics and Optimization
• Sprache: Englisch
• Veröffentlichungsjahr: 2011

Seitenzahl: 748

Beschreibung

Praise from the Second Edition "...an excellent introduction to optimization theory..." (Journal of Mathematical Psychology, 2002) "A textbook for a one-semester course on optimization theory and methods at the senior undergraduate or beginning graduate level." (SciTech Book News, Vol. 26, No. 2, June 2002) Explore the latest applications of optimization theory and methods Optimization is central to any problem involving decision making in many disciplines, such as engineering, mathematics, statistics, economics, and computer science. Now, more than ever, it is increasingly vital to have a firm grasp of the topic due to the rapid progress in computer technology, including the development and availability of user-friendly software, high-speed and parallel processors, and networks. Fully updated to reflect modern developments in the field, An Introduction to Optimization, Third Edition fills the need for an accessible, yet rigorous, introduction to optimization theory and methods. The book begins with a review of basic definitions and notations and also provides the related fundamental background of linear algebra, geometry, and calculus. With this foundation, the authors explore the essential topics of unconstrained optimization problems, linear programming problems, and nonlinear constrained optimization. An optimization perspective on global search methods is featured and includes discussions on genetic algorithms, particle swarm optimization, and the simulated annealing algorithm. In addition, the book includes an elementary introduction to artificial neural networks, convex optimization, and multi-objective optimization, all of which are of tremendous interest to students, researchers, and practitioners. Additional features of the Third Edition include: * New discussions of semidefinite programming and Lagrangian algorithms * A new chapter on global search methods * A new chapter on multipleobjective optimization * New and modified examples and exercises in each chapter as well as an updated bibliography containing new references * An updated Instructor's Manual with fully worked-out solutions to the exercises Numerous diagrams and figures found throughout the text complement the written presentation of key concepts, and each chapter is followed by MATLAB exercises and drill problems that reinforce the discussed theory and algorithms. With innovative coverage and a straightforward approach, An Introduction to Optimization, Third Edition is an excellent book for courses in optimization theory and methods at the upper-undergraduate and graduate levels. It also serves as a useful, self-contained reference for researchers and professionals in a wide array of fields.

Leseprobe

CONTENTS

Preface

PART I MATHEMATICAL REVIEW

CHAPTER 1METHODS OF PROOF AND SOME NOTATION

1.1 METHODS OF PROOF

1.2 NOTATION

EXERCISES

CHAPTER 2VECTOR SPACES AND MATRICES

2.1 VECTOR AND MATRIX

2.2 RANK OF A MATRIX

2.3 LINEAR EQUATIONS

2.4 INNER PRODUCTS AND NORMS

EXERCISES

CHAPTER 3TRANSFORMATIONS

3.1 LINEAR TRANSFORMATIONS

3.2 EIGENVALUES AND EIGENVECTORS

3.3 ORTHOGONAL PROJECTIONS

3.4 QUADRATIC FORMS

3.5 MATRIX NORMS

EXERCISES

CHAPTER 4CONCEPTS FROM GEOMETRY

4.1 LINE SEGMENTS

4.2 HYPERPLANES AND LINEAR VARIETIES

4.3 CONVEX SETS

4.4 NEIGHBORHOODS

4.5 POLY TOPES AND POLYHEDRA

EXERCISES

CHAPTER 5ELEMENTS OF CALCULUS

5.1 SEQUENCES AND LIMITS

5.2 DIFFERENTIABILITY

5.3 THE DERIVATIVE MATRIX

5.4 DIFFERENTIATION RULES

5.5 LEVEL SETS AND GRADIENTS

5.6 TAYLOR SERIES

EXERCISES

PART II UNCONSTRAINED OPTIMIZATION

CHAPTER 6BASICS OF SET-CONSTRAINED AND UNCONSTRAINED OPTIMIZATION

6.1 INTRODUCTION

6.2 CONDITIONS FOR LOCAL MINIMIZERS

EXERCISES

CHAPTER 7ONE-DIMENSIONAL SEARCH METHODS

7.1 GOLDEN SECTION SEARCH

7.2 FIBONACCI SEARCH

7.3 NEWTON’S METHOD

7.4 SECANT METHOD

7.5 REMARKS ON LINE SEARCH METHODS

EXERCISES

CHAPTER 8GRADIENT METHODS

8.1 INTRODUCTION

8.2 THE METHOD OF STEEPEST DESCENT

8.3 ANALYSIS OF GRADIENT METHODS

EXERCISES

CHAPTER 9NEWTON’S METHOD

9.1 INTRODUCTION

9.2 ANALYSIS OF NEWTON’S METHOD

9.3 LEVENBERG-MARQUARDT MODIFICATION

9.4 NEWTON’S METHOD FOR NONLINEAR LEAST SQUARES

EXERCISES

CHAPTER 10CONJUGATE DIRECTION METHODS

10.1 INTRODUCTION

10.2 THE CONJUGATE DIRECTION ALGORITHM

10.3 THE CONJUGATE GRADIENT ALGORITHM

10.4 THE CONJUGATE GRADIENT ALGORITHM FOR NONQUADRATIC PROBLEMS

EXERCISES

CHAPTER 11QUASI-NEWTON METHODS

11.1 INTRODUCTION

11.2 APPROXIMATING THE INVERSE HESSIAN

11.3 THE RANK ONE CORRECTION FORMULA

11.4 THE DFP ALGORITHM

11.5 THE BFGS ALGORITHM

EXERCISES

CHAPTER 12SOLVING LINEAR EQUATIONS

12.1 LEAST-SQUARES ANALYSIS

12.2 THE RECURSIVE LEAST-SQUARES ALGORITHM

12.3 SOLUTION TO A LINEAR EQUATION WITH MINIMUM NORM

12.4 KACZMARZ’S ALGORITHM

12.5 SOLVING LINEAR EQUATIONS IN GENERAL

EXERCISES

CHAPTER 13UNCONSTRAINED OPTIMIZATION AND NEURAL NETWORKS

13.1 INTRODUCTION

13.2 SINGLE-NEURON TRAINING

13.3 THE BACKPROPAGATION ALGORITHM

EXERCISES

CHAPTER 14GLOBAL SEARCH ALGORITHMS

14.1 INTRODUCTION

14.2 THE NELDER-MEAD SIMPLEX ALGORITHM

14.3 SIMULATED ANNEALING

14.4 PARTICLE SWARM OPTIMIZATION

14.5 GENETIC ALGORITHMS

EXERCISES

PART III LINEAR PROGRAMMING

CHAPTER 15INTRODUCTION TO LINEAR PROGRAMMING

15.1 BRIEF HISTORY OF LINEAR PROGRAMMING

15.2 SIMPLE EXAMPLES OF LINEAR PROGRAMS

15.3 TWO-DIMENSIONAL LINEAR PROGRAMS

15.4 CONVEX POLYHEDRA AND LINEAR PROGRAMMING

15.5 STANDARD FORM LINEAR PROGRAMS

15.6 BASIC SOLUTIONS

15.7 PROPERTIES OF BASIC SOLUTIONS

15.8 GEOMETRIC VIEW OF LINEAR PROGRAMS

EXERCISES

CHAPTER 16SIMPLEX METHOD

16.1 SOLVING LINEAR EQUATIONS USING ROW OPERATIONS

16.2 THE CANONICAL AUGMENTED MATRIX

16.3 UPDATING THE AUGMENTED MATRIX

16.4 THE SIMPLEX ALGORITHM

16.5 MATRIX FORM OF THE SIMPLEX METHOD

16.6 TWO-PHASE SIMPLEX METHOD

16.7 REVISED SIMPLEX METHOD

EXERCISES

CHAPTER 17DUALITY

17.1 DUAL LINEAR PROGRAMS

17.2 PROPERTIES OF DUAL PROBLEMS

EXERCISES

CHAPTER 18NONSIMPLEX METHODS

18.1 INTRODUCTION

18.2 KHACHIYAN’S METHOD

18.3 AFFINE SCALING METHOD

18.4 KARMARKAR’S METHOD

EXERCISES

PART IV NONLINEAR CONSTRAINED OPTIMIZATION

CHAPTER 19PROBLEMS WITH EQUALITY CONSTRAINTS

19.1 INTRODUCTION

19.2 PROBLEM FORMULATION

19.3 TANGENT AND NORMAL SPACES

19.4 LAGRANGE CONDITION

19.5 SECOND-ORDER CONDITIONS

19.6 MINIMIZING QUADRATICS SUBJECT TO LINEAR CONSTRAINTS

EXERCISES

CHAPTER 20PROBLEMS WITH INEQUALITY CONSTRAINTS

20.1 KARUSH-KUHN-TUCKER CONDITION

20.2 SECOND-ORDER CONDITIONS

EXERCISES

CHAPTER 21CONVEX OPTIMIZATION PROBLEMS

21.1 INTRODUCTION

21.2 CONVEX FUNCTIONS

21.3 CONVEX OPTIMIZATION PROBLEMS

21.4 SEMIDEFINITE PROGRAMMING

EXERCISES

CHAPTER 22ALGORITHMS FOR CONSTRAINED OPTIMIZATION

22.1 INTRODUCTION

22.2 PROJECTIONS

22.3 PROJECTED GRADIENT METHODS WITH LINEAR CONSTRAINTS

22.4 LAGRANGIAN ALGORITHMS

22.5 PENALTY METHODS

EXERCISES

CHAPTER 23MULTIOBJECTIVE OPTIMIZATION

23.1 INTRODUCTION

23.2 PARETO SOLUTIONS

23.3 COMPUTING THE PARETO FRONT

23.4 FROM MULTIOBJECTIVE TO SINGLE-OBJECTIVE OPTIMIZATION

23.5 UNCERTAIN LINEAR PROGRAMMING PROBLEMS

EXERCISES

REFERENCES

INDEX

WILEY-INTERSCIENCESERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION

A complete list of titles in this series appears at the end of this volume.

Copyright © 2008 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., Ill River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability /Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic format. For information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Chong, Edwin Kah Pin.An introduction to optimization / Edwin K. P. Chong, Stanislaw H. Zak. —3rd ed.p. cm.Includes bibliographical references and index.ISBN 978-0-471-75800-6 (cloth)1. Mathematical optimization. I. Zak, Stanislaw H. II. Title.QA402.5.C476 2008519.6—dc222007037112

To my wife, Yat-Yee, and to my parents,Paul and Julienne Chong—Edwin K. P Chong

To JMJ; my wife, Mary Ann; and my parents,Janina and Konstanty Żak—Stanislaw H. Żak

Preface

Optimization is central to any problem involving decision making, whether in engineering or in economics. The task of decision making entails choosing among various alternatives. This choice is governed by our desire to make the "best" decision. The measure of goodness of the alternatives is described by an objective function or performance index. Optimization theory and methods deal with selecting the best alternative in the sense of the given objective function.

The area of optimization has received enormous attention in recent years, primarily because of the rapid progress in computer technology, including the development and availability of user-friendly software, high-speed and parallel processors, and artificial neural networks. A clear example of this phenomenon is the wide accessibility of optimization software tools such as the Optimization Toolbox of MATLAB1 and the many other commercial software packages.

There are currently several excellent graduate textbooks on optimization theory and methods (e.g., [3], [35], [39], [47], [81], [82], [97], [116]), as well as undergraduate textbooks on the subject with an emphasis on engineering design (e.g., [1] and [100]). However, there is a need for an introductory textbook on optimization theory and methods at a senior undergraduate or beginning graduate level. The present text was written with this goal in mind. The material is an outgrowth of our lecture notes for a one-semester course in optimization methods for seniors and beginning graduate students at Purdue University, West Lafayette, Indiana. In our presentation, we assume a working knowledge of basic linear algebra and multivariable calculus. For the reader's convenience, a part of this book (Part I) is devoted to a review of the required mathematical background material. Numerous figures throughout the text complement the written presentation of the material. We also include a variety of exercises at the end of each chapter. A solutions manual with complete solutions to the exercises is available from the publisher to instructors who adopt this text. Some of the exercises require using MATLAB. The student edition of MATLAB is sufficiënt for all of the MATLAB exercises included in the text. The MATLAB source listings for the MATLAB exercises are also included in the solutions manual.

The purpose of the book is to give the reader a working knowledge of optimization theory and methods. To accomplish this goal, we include many examples that illustrate the theory and algorithms discussed in the text. However, it is not our intention to provide a cookbook of the most recent numerical techniques for optimization; rather, our goal is to equip the reader with sufficient background for further study of advanced topics in optimization.

The field of optimization is still a very active research area. In recent years, various new approaches to optimization have been proposed. In this text, we have tried to reflect at least some of the flavor of recent activity in the area. For example, we include a discussion of randomized search methods—these include particle swarm optimization and genetic algorithms, topics of increasing importance in the study of complex adaptive systems. There has also been a recent surge of applications of optimization methods to a variety of new problems. An example of this is the use of descent algorithms for the training of feedforward neural networks. An entire chapter in the book is devoted to this topic. The area of neural networks is an active area of ongoing research, and many books have been devoted to this subject. The topic of neural network training fits perfectly into the framework of unconstrained optimization methods. Therefore, the chapter on feedforward neural networks provides not only an example of application of unconstrained optimization methods but also gives the reader an accessible introduction to what is currently a topic of wide interest.

The material in this book is organized into four parts. Part I contains a review of some basic definitions, notations, and relations from linear algebra, geometry, and calculus that we use frequently throughout the book. In Part II we consider unconstrained optimization problems. We first discuss some theoretical foundations of set-constrained and unconstrained optimization, including necessary and sufficient conditions for minimizers and maximizers. This is followed by a treatment of various iterative optimization algorithms, together with their properties. A discussion of global search algorithms is included in this part. We also analyze the least-squares optimization problem and the associated recursive least-squares algorithm. Parts III and IV are devoted to constrained optimization. Part III deals with linear programming problems, which form an important class of constrained optimization problems. We give examples and analyze properties of linear programs, and then discuss the simplex method for solving linear programs. We also provide a brief treatment of dual linear programming problems. We wrap up Part III by discussing some nonsimplex algorithms for solving linear programs: Khachiyan's method, the affine scaling method, and Karmarkar's method. In Part IV we treat nonlinear constrained optimization. Here, as in Part II, we first present some theoretical foundations of nonlinear constrained optimization problems, including convex optimization problems. We then discuss different algorithms for solving constrained optimization problems. We also treat multiobjective optimization.

Although we have made every effort to ensure an error-free text, we suspect that some errors remain undetected. For this purpose, we provide online updated errata that can be found at the Web site for the book, accessible via

http://www.wiley.com/mathematics

We are grateful to several people for their help during the course of writing this book. In particular, we thank Dennis Goodman of Lawrence Livermore Laboratories for his comments on early versions of Part II and for making available to us his lecture notes on nonlinear optimization. We thank Moshe Kam of Drexel University for pointing out some useful references on nonsimplex methods. We are grateful to Ed Silverman and Russell Quong for their valuable remarks on Part I of the first edition. We also thank the students of ECE 580 at Purdue University and ECE 520 and M 520 at Colorado State University for their many helpful comments and suggestions. In particular, we are grateful to Christopher Taylor for his diligent proofreading of early manuscripts of this book. This third edition incorporates many valuable suggestions of users of the first and second editions, to whom we are grateful.

E. K. P. Chong and S. H. ŽakFort Collins, Colorado, and West Lafayette, Indiana

1 MATLAB is a registered trademark of The MathWorks, Inc. For MATLAB product information, contact The MathWorks, Inc., 3 Apple Hill Drive, Natick, MA, 01760-2098 USA. Tel: [phone], Fax: [phone], E-mail: [e-mail], Web: www.mathworks.com

PART I

MATHEMATICAL REVIEW

CHAPTER 1

METHODS OF PROOF AND SOME NOTATION

1.1 METHODS OF PROOF

Consider two statements, “A” and “B,” which could be either true or false. For example, let “A” be the statement “John is an engineering student,” and let “B” be the statement “John is taking a course on optimization.” We can combine these statements to form other statements, such as “A and B” or “A or B.” In our example, “A and B” means “John is an engineering student, and he is taking a course on optimization.” We can also form statements such as “not A,” “not B,” “not (A and B),” and so on. For example, “not A” means “John is not an engineering student.” The truth or falsity of the combined statements depend on the truth or falsity of the original statements, “A” and “B.” This relationship is expressed by means of truth tables; see Tables 1.1 and 1.2.

From the tables, it is easy to see that the statement “not (A and B)” is equivalent to “(not A) or (not B)” (see Exercise 1.3). This is called DeMorgaris law.

In proving statements, it is convenient to express a combined statement by a conditional, such as “A implies B,” which we denote “A⇒B.” The conditional “A⇒B” is simply the combined statement “(not A) or B” and is often also read “A only if B,” or “if A then B,” or “A is sufficient for B,” or “B is necessary for A.”

Table 1.1 Truth Table for “A and B” and “A or B”

Table 1.2 Truth Table for “not A”

Anot AFTTF

Table 1.3 Truth Table for Conditionals and Biconditionals

We can combine two conditional statements to form a biconditional statement of the form “A⇔B,” which simply means “(A⇒B) and (B⇒A).” The statement “A⇔B” reads “A if and only if B,” or “A is equivalent to B,” or “A is necessary and sufficient for B.” Truth tables for conditional and biconditional statements are given in Table 1.3.

It is easy to verify, using the truth table, that the statement “A⇒B” is equivalent to the statement “(not B)=>(not A).” The latter is called the contrajo suive of the former. If we take the contrapositive to DeMorgan’s law, we obtain the assertion that “not (A or B)” is equivalent to “(not A) and (not B).”

Most statements we deal with have the form “A⇒B.” To prove such a statement, we may use one of the following three different techniques:

1. The direct method

2. Proof by contraposition

3. Proof by contradiction or reductio ad absurdum

In the case of the direct method, we start with “A,” then deduce a chain of various consequences to end with “B.”

A useful method for proving statements is proof by contraposition, based on the equivalence of the statements “A⇒B” and “(not B)⇒(not A).” We start with “not B,” then deduce various consequences to end with “not A” as a conclusion.

Another method of proof that we use is proof by contradiction, based on the equivalence of the statements “A⇒B” and “not (A and (not B)).” Here we begin with “A and (not B)” and derive a contradiction.

Occasionally, we use the principle of induction to prove statements. This principle may be stated as follows. Assume that a given property of positive integers satisfies the following conditions:

The number 1 possesses this property.If the number n possesses this property, then the number n +1 possesses it too.

The principle of induction states that under these assumptions any positive integer possesses the property.

The principle of induction is easily understood using the following intuitive argument. If the number 1 possesses the given property, then the second condition implies that the number 2 possesses the property. But, then again, the second condition implies that the number 3 possesses this property, and so on. The principle of induction is a formal statement of this intuitive reasoning.

For a detailed treatment of different methods of proof, see [117].

1.2 NOTATION

Throughout, we use the following notation. If X is a set, then we write x ∈ X to mean that x is an element of X. When an object x is not an element of a set X, we write x ∉ X. We also use the “curly bracket notation” for sets, writing down the first few elements of a set followed by three dots. For example, {x1,x2,x3,...} is the set containing the elements x1,x2,x3, and so on. Alternatively, we can explicitly display the law of formation. For example, {x : x ∈,x > 5} reads “the set of all x such that x is real and x is greater than 5.” The colon following x reads “such that.” An alternative notation for the same set is {x ∈, : x > 5}.

If X and Y are sets, then we write X ⊂ Y to mean that every element of X is also an element of Y. In this case, we say that X is a subset of Y. If X and Y are sets, then we denote by X\Y (“X minus Y”) the set of all points in X that are not in Y. Note that X \ Y is a subset of X. The notation ƒ : X → Y means “ƒ is a function from the set X into the set Y.” The symbol := denotes arithmetic assignment. Thus, a statement of the form x := y means “x becomes y” The symbol means “equals by definition.”

Throughout the text, we mark the end of theorems, lemmas, propositions, and corollaries using the symbol D. We mark the end of proofs, definitions, and examples by.

We use the IEEE style when citing reference items. For example, [77] represents reference number 77 in the list of references at the end of the book.

EXERCISES

1.1 Construct the truth table for the statement “(not B)⇒(not A),” and use it to show that this statement is equivalent to the statement “A⇒B.”

1.2 Construct the truth table for the statement “not (A and (not B)),” and use it to show that this statement is equivalent to the statement “A⇒B.”

1.3 Prove DeMorgan’s law by constructing the appropriate truth tables.

1.4 Prove that for any statements A and B, we have “A ⇔ (A and B) or (A and (not B)).” This is useful because it allows us to prove a statement A by proving the two separate cases “(A and B)” and “(A and (not B)).” For example, to prove that |x| ≥ x for any x ∈ , we separately prove the cases “|x| ≥ x and x ≥ 0” and “|x| ≥ x and x < 0.” Proving the two cases turns out to be easier than proving the statement |x| ≥ x directly (see Section 2.4 and Exercise 2.5).

1.5 (This exercise is adopted from [20, pp. 80–81]) Suppose that you are shown four cards, laid out in a row. Each card has a letter on one side and a number on the other. On the visible side of the cards are printed the symbols

Determine which cards you should turn over to decide if the following rule is true or false: “If there is a vowel on one side of the card, then there is an even number on the other side.”