An Introduction to Optimization WILEY-INTERSCIENCE SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION ADVISORY EDITORS RONALD L GRAHAM University of California at San Diego, U.S.A JAN KAREL LENSTRA Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands JOEL H SPENCER + Institute, New York, New York, U.S.A A complete list of titles in this series appears at the end of this volume An Introduction to Optimization Second Edition EDWIN K P CHONG STANISLAW H ZAK A Wiley-lnterscience Publication JOHN WILEY & SONS, INC New York / Chichester / Weinheim / Brisbane / Singapore / Toronto This text is printed on acid-free paper @ Copyright © 2001 by John Wiley & Sons, Inc All rights reserved 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 Sections 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, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4744 Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 605 Third Avenue, New York, NY 10158-0012, (212) 850-6011, fax (212) 850-6008, E-Mail: PERMREQ @ W1LEY.COM For ordering and customer service, call 1-800-CALL-W1LEY Library of Congress Cataloging in Publication Data is available ISBN: 0-471-39126-3 Printed in the United States of America 10 To my wife, Yat-Yee, and my parents, Paul and Julienne Chong Edwin K P Chong To JMJ, my wife, Mary Ann, and my parents, Janina and Konstanty Zak Stanislaw H Zak This page intentionally left blank Contents Preface xiii Part I Mathematical Review Methods of Proof and Some Notation 1.1 Methods of Proof 1.2 Notation Exercises 1 Vector Spaces and Matrices 2.1 Real Vector Spaces 2.2 Rank of a Matrix 2.3 Linear Equations 2.4 Inner Products and Norms Exercises 5 10 14 16 19 Transformations 3.1 Linear Transformations 3.2 Eigenvalues and Eigenvectors 21 21 22 vii viii CONTENTS 3.3 3.4 3.5 Orthogonal Projections Quadratic Forms Matrix Norms Exercises 25 26 31 35 Concepts 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 39 39 39 42 44 45 47 Elements 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 49 49 55 57 59 60 64 68 Part II Unconstrained Optimization Basics of Set-Constrained and Unconstrained Optimization 6.1 Introduction 6.2 Conditions for Local Minimizers Exercises One-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 73 73 75 83 91 91 95 103 106 108 109 CONTENTS IX Gradient Methods 8.1 Introduction 8.2 The Method of Steepest Descent 8.3 Analysis of Gradient Methods 8.3.1 Convergence 8.3.2 Convergence Rate Exercises 113 113 115 122 122 129 134 Newton'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 139 139 142 145 146 149 10 Conjugate Direction Methods 10.1 Introduction 10.2 The Conjugate Direction Algorithm 10.3 The Conjugate Gradient Algorithm 10.4 The Conjugate Gradient Algorithm for Non-Quadratic Problems Exercises 151 151 153 158 11 Quasi-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 167 167 168 171 176 180 184 12 Solving Ax = b 12.1 Least-Squares Analysis 12.2 Recursive Least-Squares Algorithm 12.3 Solution to Ax = b Minimizing ||x|| 12.4 Kaczmarz's Algorithm 12.5 Solving Ax = b in General Exercises 187 187 196 199 201 204 212 161 164 .. .An Introduction to Optimization WILEY- INTERSCIENCE SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION ADVISORY EDITORS RONALD L GRAHAM University of California at San Diego, U.S.A JAN KAREL... volume An Introduction to Optimization Second Edition EDWIN K P CHONG STANISLAW H ZAK A Wiley- lnterscience Publication JOHN WILEY & SONS, INC New York / Chichester / Weinheim / Brisbane / Singapore... United States of America 10 To my wife, Yat-Yee, and my parents, Paul and Julienne Chong Edwin K P Chong To JMJ, my wife, Mary Ann, and my parents, Janina and Konstanty Zak Stanislaw H Zak This page