An Introduction to Optimization - Chong and Zak.pdf

【实例简介】
最优化导论 英文版
WILEY-INTERSCIENCE SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION ADVISORY EDITORS RONALD L GRAHAM U.S.A JAN KAREL LENSTRA Department of Mathematics and Computer Science. Eindhoven University of Technology, Eindhoven The Netherlands JOELH. SPENCER Courant institure. 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。 CHONG STANISLAW H,之AK A Wiley-Interscience Publication John WILEY &e sons, iNC. New York /Chichester Weinheim Brisbane Singapore/Toronto This text is printed on acid-free paper. 6 Copyright e 2000 1 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 I>epartment, John wiley sons, Inc., 605 Third Avenue, New York NYI81580012,(212)850-6011,fax(212)850-6008,EMa:PRMR上QaWL上YCOM For ordering and customer service, call 1-800-CALL-WiLEY Library of congress cataloging in Publication data is available sBN:0-471-39126-3 Printed in the United states of america 109876543 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 Parti mathematical review 1 Methods of proof and some notation 1.1 Methods of proof 1.2 Notation Exercises 2 Vector Spaces and Matrices 2.1 Real vector Spaces 2.2 Rank of a matrix 10 2.3 Linear Equations 14 2.4 Inner Products and norms 16 E Excises 19 3 Transformations 21 3.1 Linear transformations 21 3.2 Eigenvalues and Eigenvectors 22 viI CONTENTS 3.3 Orthogonal Projections 25 3.4 Quadratic Forms 26 3.5 Matrix norms 31 Exercises 35 4 Concepts from Geometry 39 4.1 Line segments 39 4.2 Hyperplanes and linear varieties 39 4.3 Convex Sets 42 4.4 Neighborhoods 44 4.5 Polytopes and polyhedra 45 Exercises 47 5 Elements of calculus 5.1 Sequences and Limits 49 5.2 Differentiability 55 5.3 The Derivative matrix 57 5.4 Differentiation rules 59 5.5 Level sets and gradients 60 5.6 Taylor Series 64 Exercises Part II Unconstrained Optimization 6 Basics of Set-Constrained and Unconstrained Optimization 73 6.1 Introduction 73 6.2 Conditions for local minimizers 75 Exercises 83 7 One-Dimensional search Methods 7.1 Golden section search 91 7. 2 Fibonacci Search 95 7.3 Newton’ s Method 103 7.4 Secant Method l06 7.5 Remarks on line search methods 108 Exercises 109 CONTENTS ix 8 Gradient methods 113 8.1 Introduction 113 8.2 The Method of Steepest Descent 15 8.3 Analysis of Gradient Methods 122 8.3.1 Convergence 122 8.3.2 Convergence Rate 129 Exercises 134 9 Newton's method 139 9.1 Introduction 139 9.2 Analysis of Newton's Method 142 9.3 Levenberg-Marquardt modification 145 9.4 Newton's Method for Nonlinear Least-Squares 146 Exercises 149 10 Conjugate Direction Methods 151 10.1 Introduction 151 10.2 The Conjugate Direction Algorithm 153 10.3 The Conjugate Gradient Algorithm 158 10.4 The Conjugate Gradient Algorithm for Non-Quadratic Problems 161 Exercises 164 11 Quasi-Newton Methods 167 11. Introduction 167 11.2 Approximating the Inverse Hessian 168 11. 3 The rank One Correction Formula l71 11. 4 The dFP algorithm 176 11.5 The BFGS algorithm 180 Exercises 184 12 Solving A =6 187 12.1 Least-Squares analysis 187 12.2 Recursive Least-Squares Algorithm 196 12. 3 Solution to Aa=b Minimizing ecll 199 12.4 Kaczmarz's algorithm 201 12.5 Solving Aa =b in General 204 Exercises 212 【实例截图】
【核心代码】