I need assistance developing a code using Rstudio for the SQP methods covered in chapter 18 of the following textbook which I have as my study guide https://www.csie.ntu.edu.tw/~r97002/temp/num_optimization.pdf. I am supposed to have it run with some functions. The algorithms for this method are all provided in the textbook.
This is page iii Printer: Opaque this Jorge Nocedal Stephen J. Wright Numerical Optimization Second Edition This is pag Printer: O Jorge Nocedal Stephen J. Wright EECS Department Computer Sciences Department Northwestern University University of Wisconsin Evanston, IL 60208-3118 1210 West Dayton Street USA Madison, WI 53706–1613
[email protected] USA
[email protected] Series Editors: Thomas V. Mikosch University of Copenhagen Laboratory of Actuarial Mathematics DK-1017 Copenhagen Denmark
[email protected] Sidney I. Resnick Cornell University School of Operations Research and Industrial Engineering Ithaca, NY 14853 USA
[email protected] Stephen M. Robinson Department of Industrial and Systems Engineering University of Wisconsin 1513 University Avenue Madison, WI 53706–1539 USA
[email protected] Mathematics Subject Classification (2000): 90B30, 90C11, 90-01, 90-02 Library of Congress Control Number: 2006923897 ISBN-10: 0-387-30303-0 ISBN-13: 978-0387-30303-1 Printed on acid-free paper. C© 2006 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. Printed in the United States of America. (TB/HAM) 9 8 7 6 5 4 3 2 1 springer.com This is page v Printer: Opaque this To Sue, Isabel and Martin and To Mum and Dad This is page vii Printer: Opaque this Contents Preface xvii Preface to the Second Edition xxi 1 Introduction 1 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . 2 Example: A Transportation Problem . . . . . . . . . . . . . . . . . . . 4 Continuous versus Discrete Optimization . . . . . . . . . . . . . . . . . 5 Constrained and Unconstrained Optimization . . . . . . . . . . . . . . 6 Global and Local Optimization . . . . . . . . . . . . . . . . . . . . . . 6 Stochastic and Deterministic Optimization . . . . . . . . . . . . . . . . 7 Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Optimization Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 8 Notes and References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Fundamentals of Unconstrained Optimization 10 2.1 What Is a Solution? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 viii C O N T E N T S Recognizing a Local Minimum . . . . . . . . . . . . . . . . . . . . . . 14 Nonsmooth Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Overview of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Two Strategies: Line Search and Trust Region . . . . . . . . . . . . . . . 19 Search Directions for Line Search Methods . . . . . . . . . . . . . . . . 20 Models for Trust-Region Methods . . . . . . . . . . . . . . . . . . . . . 25 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3 Line Search Methods 30 3.1 Step Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 The Wolfe Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 The Goldstein Conditions . . . . . . . . . . . . . . . . . . . . . . . . . 36 Sufficient Decrease and Backtracking . . . . . . . . . . . . . . . . . . . 37 3.2 Convergence of Line Search Methods . . . . . . . . . . . . . . . . . . . 37 3.3 Rate of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Convergence Rate of Steepest Descent . . . . . . . . . . . . . . . . . . . 42 Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Quasi-Newton Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4 Newton’s Method with Hessian Modification . . . . . . . . . . . . . . . 48 Eigenvalue Modification . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Adding a Multiple of the Identity . . . . . . . . . . . . . . . . . . . . . 51 Modified Cholesky Factorization . . . . . . . . . . . . . . . . . . . . . 52 Modified Symmetric Indefinite Factorization . . . .