UNITEXT 108 Pablo Pedregal Optimization and Approximation UNITEXT - La Matematica per il 3+2 Volume 108 Editor-in-chief Alfio Quarteroni Series editors L. Ambrosio P. Biscari C. Ciliberto C. De Lellis M. Ledoux V. Panaretos W.J. Runggaldier More information about this series at http://www.springer.com/series/5418 Pablo Pedregal Optimization and Approximation 123 PabloPedregal Department ofMathematics Universidad deCastilla-La Mancha CiudadReal Spain ISSN 2038-5714 ISSN 2532-3318 (electronic) UNITEXT- La Matematica peril3+2 ISSN 2038-5722 ISSN 2038-5757 (electronic) ISBN978-3-319-64842-2 ISBN978-3-319-64843-9 (eBook) DOI 10.1007/978-3-319-64843-9 LibraryofCongressControlNumber:2017949160 ©SpringerInternationalPublishingAG2017 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilarmethodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authorsortheeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinor for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface There seems to be an ever-increasing need to get to the basic mathematics behind applications as quickly as possible. Optimization is one such body of ideas that permeatesallofScienceandEngineering.Quiteoften,interestedreaders wholook at optimization ideas in a utilitarian way find that they need to dive into textbooks requiringalotofformal traininginordertofindthebasic conceptsandtechniques that they are seeking. This is quite frustrating at times, for all they require is a well-founded and educated intuition that will endow them with a basic under- standingandsomeaffordablecomputationaltoolstotackleproblemsinpractice.In addition, even if a person is solely interested in a particular body of ideas in Optimization,he/shemayneedtoknowalittleofeverythingsoastogainanoverall mental picture. Real-life applications may demand identification of the nature of problems,theframeworkinwhichtheycanbetreated,somesimplecomputational methods to deal with equivalent toy models, etc. Once this initial fundamental information has been appropriately defined, further specialized literature may have to be sought. This text aims, as one way among various possibilities, to endow readerswithsuchabasicoverallbackgroundinOptimizationthatmayenablethem to identify a problem as a mathematical program, linear or nonlinear, or as a continuousoptimizationsituation,intheformofeither avariationalproblemoran optimal control case. It is also my experience that students who discover that it is virtuallyimpossibletosolvebyhandeventhemoreinnocent-lookingoptimization problems become frustrated when they realize that in order to play with approxi- matedsolutionsofsimplevariationsofthosesituations,theywillneedtowaituntil much more has been learned about how to approximate optimal solutions. To propose one basic, systematic, and coherent solution for this approximation issue acrossallmainareasofOptimizationisalsoamainmotivationforthistext.Itisjust oneaffordablepossibilityamongmanyothers,withnointentionofcompetingwith more sophisticated and accurate methods in the computational arena. I describe some simple, yet non-entirely trivial, procedures to approximate optimal solutions of easy problems so that students may experience the joy of seeing with their own eyes optimal solutions of problems. There are, as just pointed out, other good and reasonable possibilities and solutions for this computational issue. v vi Preface I feel this book is unique in that it makes an attempt to integrate all those main fieldsthatsharesufficientfeaturestobeplacedundertheumbrellaofOptimization, a huge area of work in which many people are making progress on a daily basis. But there are so many distinct elements among those subareas that it is scarcely possibletomakeadeepanalysis,withinasingletext,thatcoversallofthem.Inthis sense, our treatment is basic and elementary but, as already pointed out in the preceding paragraph, it seeks to draw an overall picture of the interconnection among the main parts of Optimization that may be helpful to students. The book will be of help to students of Science and Engineering, at both undergraduateandgraduatelevel,whoforthefirsttimeneedtoacquaintthemselves with thebasic principlesof all areas of Optimization. Inparticular, thebook ought to suffice for the content of typical courses in Science and Engineering majors. Familiarity with basic linear algebra, multivariate calculus, and basic differential equations is a fundamental prerequisite. Senior researchers whose main field of expertise is not Optimization, but who need to understand the basic theory and eventually to use approximation techniques for the problems in which they are interested, may also find these pages useful. I warn experts in some of the areas briefly covered in the text that they may find the coverage a little disappointing since the treatment of each area is too basic to be of interest for specialists. Some material or concepts that are regarded as fundamental in some subfields of Optimizationmaybemissingfromthisbook.Letmeagainstressthatmyintention hasbeentoprovideonebasic,cross-cuttingsourcerelevanttoallimportantareasin Optimization. This obviously means that it is not possible to attain great depth within individual chapters. The text may serve several purposes: (cid:129) Itcanenabletheusertoavoidallissuesaboutapproximationtechniquesandto focus on basic analytical ideas in all chapters. (cid:129) It can enable the user to concentrate on mathematical programming problems, including issues about approximation, either by using the ideas in the text concerning simulation in practice or by utilizing other software packages. (cid:129) It may be used as the basis for a course focusing on continuous optimization problems, including approximation techniques. (cid:129) It can serve other specific purposes when time is scarce and there is a need to concentrate on narrower objectives. ItmaybetakenasthebasictextbookforanOptimizationcourseforanyScience or Engineering major, and also for Master’s courses. The text has a modular structure in the sense that even separate individual sections may serve as short introductions to specific topics or techniques, depending on needs. I have paid a lot of attention to exercises as I believe them to be a fundamental part of a text aiming to support basic learning in any field of mathematics. New ideas and motivations have been associated with exercises in an attempt to make them more inspiring and enlightening. I have divided the exercises into three dis- tinctcategories:thosesupportingmainanalyticalconcepts,thoseaimingtoprovide Preface vii basic training, andthose ofamore advanced nature.About160exerciseswith full solutions are gathered in the final chapter. Most of these exercises have been tried out in the Optimization course that the author and other colleagues have taught in theMathDepofUCLMoverthepast15years.Inthisregard,particularthanksgo to E. Aranda, J.C. Bellido and A. Donoso. I do not claim to have gathered all possibleproblemsforsuchanintroductorycourse.Icouldhardlydoso,asthereare hundredsofexamplesscatteredthroughouttheliterature.Mygoal,rather,hasbeen to propose enough exercises to ensure that they enable the reader to achieve a reasonably mature grasp of the main concepts I have tried to convey. Whenever possible, I have made an attempt to inspire further investigation through some of them. I have given the source of problems whenever known, but I cannot guarantee to have done so in a systematic way; thus, readers may know other sources for some of the problems that have not been indicated in the text. Many of the problems can be found in other textbooks, so I do not claim the slightest originality here. Needless to say, anyone using this book as a source text can proposemanyotherexercisestostudents.Asamatteroffact,manyotherexercises can be found in the bibliography I have selected. Concerning references, I have not tried to be exhaustive, and some interesting resources are probably missing. My aim has been to provide a limited number of well-chosen items so as to encourage further investigation or to identify where to look for deeper answers to more advanced questions. Each part has its own final bibliography section, though some are common to several parts. I would also like to take this opportunity to thank the members of the Editorial Board of the series UNITEXT, and particularly A. Quarteroni, for their help and assistance in the reviewing process for the manuscript and for suggesting very appropriateimprovementswhichhaveledtothisfinalform.Mygratitudealsogoes to Francesca Bonadei and Angela Vanegas from Springer, whose constant support made the whole process an easy journey. Ciudad Real Pablo Pedregal June 2017 Contents 1 Overview .. .... .... .... ..... .... .... .... .... .... ..... .... 1 1.1 Importance of Optimization Problems.. .... .... .... ..... .... 1 1.2 Optimization.... .... ..... .... .... .... .... .... ..... .... 2 1.2.1 Unconstrained Optimization and Critical Points ..... .... 2 1.2.2 Constrained Optimization . .... .... .... .... ..... .... 3 1.2.3 Variational Problems. .... .... .... .... .... ..... .... 4 1.2.4 Optimal Control Problems. .... .... .... .... ..... .... 4 1.3 Approximation .. .... ..... .... .... .... .... .... ..... .... 5 1.4 Structure and Use of the Book... .... .... .... .... ..... .... 7 Part I Mathematical Programming 2 Linear Programming. .... ..... .... .... .... .... .... ..... .... 11 2.1 Some Motivating Examples . .... .... .... .... .... ..... .... 11 2.2 Structure of Linear Programming Problems . .... .... ..... .... 14 2.3 Sensitivity and Duality..... .... .... .... .... .... ..... .... 19 2.4 A Final Clarifying Example. .... .... .... .... .... ..... .... 22 2.5 Final Remarks .. .... ..... .... .... .... .... .... ..... .... 25 2.6 Exercises .. .... .... ..... .... .... .... .... .... ..... .... 26 2.6.1 Exercises to Support the Main Concepts.. .... ..... .... 26 2.6.2 Practice Exercises... .... .... .... .... .... ..... .... 29 2.6.3 Case Studies.. ..... .... .... .... .... .... ..... .... 30 3 Nonlinear Programming.. ..... .... .... .... .... .... ..... .... 33 3.1 Some Motivating Examples . .... .... .... .... .... ..... .... 33 3.2 Structure of Non-linear Programming Problems.. .... ..... .... 37 3.3 Optimality Conditions. ..... .... .... .... .... .... ..... .... 38 3.4 Convexity.. .... .... ..... .... .... .... .... .... ..... .... 47 3.5 Duality.... .... .... ..... .... .... .... .... .... ..... .... 52 3.6 Final Remarks .. .... ..... .... .... .... .... .... ..... .... 55 ix x Contents 3.7 Exercises .. .... .... ..... .... .... .... .... .... ..... .... 56 3.7.1 Exercises to Support the Main Concepts.. .... ..... .... 56 3.7.2 Practice Exercises... .... .... .... .... .... ..... .... 58 3.7.3 Case Studies.. ..... .... .... .... .... .... ..... .... 61 4 Numerical Approximation ..... .... .... .... .... .... ..... .... 63 4.1 Practical Numerical Algorithms for Unconstrained Minimization ... .... ..... .... .... .... .... .... ..... .... 64 4.1.1 The Direction . ..... .... .... .... .... .... ..... .... 64 4.1.2 Step Size. .... ..... .... .... .... .... .... ..... .... 65 4.2 A Perspective for Constrained Problems Based on Unconstrained Minimization .. .... .... .... .... ..... .... 67 4.2.1 The Algorithm for Several Constraints ... .... ..... .... 70 4.2.2 An Important Issue for the Implementation.... ..... .... 72 4.3 Some Selected Examples ... .... .... .... .... .... ..... .... 73 4.4 Final Remarks .. .... ..... .... .... .... .... .... ..... .... 78 4.5 Exercises .. .... .... ..... .... .... .... .... .... ..... .... 78 4.5.1 Exercises to Support the Main Concepts.. .... ..... .... 78 4.5.2 Computer Exercises.. .... .... .... .... .... ..... .... 81 4.5.3 Case Studies.. ..... .... .... .... .... .... ..... .... 83 References.. .... .... .... ..... .... .... .... .... .... ..... .... 85 Part II Variational Problems 5 Basic Theory for Variational Problems... .... .... .... ..... .... 89 5.1 Some Motivating Examples . .... .... .... .... .... ..... .... 89 5.2 Existence of Optimal Solutions... .... .... .... .... ..... .... 94 5.3 Optimality Conditions Under Smoothness .. .... .... ..... .... 96 5.4 Constraints . .... .... ..... .... .... .... .... .... ..... .... 101 5.5 Final Remarks .. .... ..... .... .... .... .... .... ..... .... 104 5.6 Exercises .. .... .... ..... .... .... .... .... .... ..... .... 104 5.6.1 Exercises to Support the Main Concepts.. .... ..... .... 104 5.6.2 Practice Exercises... .... .... .... .... .... ..... .... 108 5.6.3 Case Studies.. ..... .... .... .... .... .... ..... .... 111 6 Numerical Approximation of Variational Problems . .... ..... .... 115 6.1 Importance of the Numerical Treatment.... .... .... ..... .... 115 6.2 Approximation Under Smoothness.... .... .... .... ..... .... 115 6.2.1 The Descent Direction.... .... .... .... .... ..... .... 116 6.3 Approximation Under Constraints. .... .... .... .... ..... .... 119 6.4 Some Examples . .... ..... .... .... .... .... .... ..... .... 121 6.5 The Algorithm in Pseudocode Form... .... .... .... ..... .... 128 6.6 Exercises .. .... .... ..... .... .... .... .... .... ..... .... 130 6.6.1 Exercises to Support the Main Concepts.. .... ..... .... 130 6.6.2 Computer Exercises.. .... .... .... .... .... ..... .... 131