A Gentle Introduction to Optimization

1 A Gentle Introduction to OptimizationOptimization is an essential technique for solving problems in areas asdiverse as accounting, computer science and engineering. Assuming onlybasic linear algebra and with a clear focus on the fundamental concepts, thistextbook is the perfect starting point for first- and second-year undergraduatestudents from a wide range of backgrounds and with varying levels of , real-world examples motivate the theory 140 exercises, ranging from the routine to the more advanced, givereaders the opportunity to try out the skills they gain in each are available for instructors as well as algorithms forcomputational chapters allow instructors and students to tailor thematerial to their own needs and make the book suitable for for further reading help students to take the next step tomore advanced courses in has been thoroughly tried and tested by the authors, whotogether have 40 years of teaching GUENIN is Professor in the Department of Combinatorics andOptimization at the University of Waterloo.

2 He received a Fulkerson Prizeawarded jointly by the Mathematical Programming Society and the AmericanMathematical Society in 2003. He is also the recipient of a Premier sResearch Excellence Award in 2001 from the Government of Ontario,Canada. Guenin currently serves on the Editorial Board of the SIAM Journalof Discrete K NEMANN is Professor in the Department of Combinatorics andOptimization at the University of Waterloo. He received an IBM CorporationFaculty Award in 2005, and an Early Researcher Award from theGovernment of Ontario, Canada, in 2007. He served on the programcommittees of several major conferences in Mathematical Optimization andComputer Science, and is a member of the editorial board of Elsevier sSurveys in Operations Research and Management TUN EL is Professor in the Department of Combinatorics andOptimization at the University of Waterloo. In 1999 he received a Premier sResearch Excellence Award from the Government of Ontario, Canada.

3 Morerecently, he received a Faculty of Mathematics Award for Distinction inTeaching from the University of Waterloo in 2012. Tun el currently serveson the Editorial Board of the SIAM Journal on Optimization and as anAssociate Editor of Mathematics of Operations Gentle Introduction toOptimizationB. GUENINJ. K NEMANNL. TUN ELUniversity of Waterloo, OntarioUniversity Printing House, Cambridge CB2 8BS, United KingdomCambridge University Press is part of the University of furthers the University s mission by disseminating knowledge in the pursuit of education,learning and research at the highest international levels of on this title: B. Guenin, J. K nemann and L. Tun el 2014 This publication is in copyright. Subject to statutory exception and to the provisions ofrelevant collective licensing agreements, no reproduction of any part may take placewithout the written permission of Cambridge University published 2014 Printed in Spain by Grafos SA, Arte sobre papelA catalogue record for this publication is available from the British LibraryLibrary of Congress Cataloging-in-Publication DataGuenin, B.

4 (Bertrand)A Gentle Introduction to Optimization / B. Guenin, J. K nemann, L. Tun el, University ofWaterloo, cmIncludes bibliographical 978-1-107-05344-1 (Hardback)ISBN 978-1-107-65879-0 (Paperback)1. Mathematical Optimization . I. K nemann, J. (Jochen) II. Tuncel, Levent, 1965- III. Title: Introduction to dc23 2014008067 ISBN 978-1-107-05344-1 HardbackISBN 978-1-107-65879-0 PaperbackAdditional resources for this publication at University Press has no responsibility for the persistence or accuracy of URLsfor external or third-party internet websites referred to in this publication, and does notguarantee that any content on such websites is, or will remain, accurate or first problems on path cost perfect programs cost perfect path a tech a closest point feasible in an a central feasible solution of an of the reading and notes2 Solving linear linear linear programs with optimal equality simplex and canonical simplex example with an optimal unbounded the feasible two phase simplex algorithm an via tableaus* region of LPs and interpretation of the simplex reading and notes3 Duality through shortest path intuitive lower general argument weak the intuitive lower of the cost perfect matching in bipartite intuitive lower general argument weak the intuitive lower of the perfect matchings in bipartite graphs* reading and notes4 Duality geometric characterization of lemma* reading and notes5 Applications of duality* algorithm for primal dual is good.

5 At least maximum-flow minimum-cut unimodular to st-flows6 Solving integer programs versus linear planes and the simplex and salesman problem and a separation algorithm* reading and notes7 Nonlinear nonlinear programs are very versus 0,1 integer small-dimensional functions and sets and feasible convex conditions for the differentiable conditions for and Karush Kuhn Tucker conditions based on Optimization Karush Kuhn Tucker theorem for nonconvex problems relaxation approach to nonconvex problems* method for linear programs* polynomial-time interior-point algorithm* reading and notesAppendix A Computational is a fast (resp. slow) algorithm? big O size and running and exponential of fast and slow algorithms in this classes NP, co-NP and class class class as versus hard problemsReferencesIndexPrefaceDesire to improve drives many human activities. Optimization can be seen asa means for identifying better solutions by utilizing a scientific andmathematical approach.

6 In addition to its widespread applications, Optimization is an amazing subject with very strong connections to manyother subjects and deep interactions with many aspects of computation andtheory. The main goal of this textbook is to provide an attractive, modern,and accessible route to learning the fundamental ideas in Optimization for alarge group of students with varying backgrounds and abilities. The onlybackground required for the textbook is a first-year linear algebra course(some readers may even be ready immediately after finishing high school).However, a course based on this book can serve as a header course for alloptimization courses. As a result, an important goal is to ensure that thestudents who successfully complete the course are able to proceed to moreadvanced Optimization goal of ours was to create a textbook that could be used by a largegroup of instructors, possibly under many different circumstances.

7 To adegree, we tested this over a four-year period. Including the three of us, 12instructors used the drafts of the book for two different courses. Students invarious programs (majors), including accounting, business, softwareengineering, statistics, actuarial science, operations research, appliedmathematics, pure mathematics, computational mathematics, computerscience, combinatorics and Optimization , have taken these courses. Webelieve that the book will be suitable for a wide range of students(mathematics, mathematical sciences including computer science,engineering including software engineering, and economics). To accomplishour goals, we operated with the following motivate the subject/algorithm/theorem (leading by modern,relatable examples which expose important aspects of thesubject/algorithm/theorem). the text as concise and as focused as possible (this meant, that someof the more advanced or tangential topics are either treated in advancedsections or in starred exercises).

8 Sure that some of the pieces are modular so that an instructor or areader can choose to skip certain parts of the text smoothly. (Please seethe potential usages of the book below.)In particular, for the derivation and overall presentation of the simplexmethod, we focused on the main ideas rather than gritty details (which in ouropinion and experience, distract from the beauty and power of the method aswell as the upcoming generalizations of the underlying ideas).We emphasized the unifying notion of relaxation in our discussion ofduality, integer programming, and combinatorial Optimization as well asnonlinear Optimization . We also emphasized the power and usefulness ofprimal dual approaches as well as convexity in deriving algorithms,understanding the theory, and improving the usage of Optimization strived to enhance understanding by weaving in geometric notions,interpretations, and ideas starting with the first chapter, Introduction , and allthe way through to the last chapter (Nonlinear Optimization ) in a cohesiveand consistent made sure that the themes of efficiency of algorithms and goodcertificates of correctness as well as their relevance were present.

9 Weincluded a brief Introduction to the relevant parts of computationalcomplexity in the of these ideas come to a beautiful meeting point in the last chapter,Nonlinear Optimization . First of all, we develop the ideas only based on linearalgebraic and geometric notions, capitalizing on the strength built throughlinear programming (geometry, halfspaces, duality) and discrete Optimization (relaxation). We arrive at the powerful Karush Kuhn Tucker Theoremwithout requiring more background in continuous mathematics and thank Yu Hin (Gary) Au, Joseph Cheriyan, Bill Cook, Bill Cunningham,Ricardo Fukasawa, Konstantinos Georgiou, Stephen New, Clinton Reddekop,Patrick Roh, Laura Sanita and Nick Wormald for very useful suggestions,corrections and ideas for exercises. We also thank the Editor, David Tranah,for very useful suggestions, and for his support and alternative ways of using the bookWe designed the textbook so that starred sections/chapters can be skippedwithout any trouble.

10 In Chapter 3 it is sufficient to pick only one of the twomotivating problems (the shortest path or the minimum cost matchingproblem). Moreover, there are many seamless ways of using the textbook, weoutline some of them a high-paced, academically demanding course, cover the materialfrom beginning to end by inserting the Appendix (Computationalcomplexity) between Chapter 2 or 3, or 4 or in order Chapters 1,2,3,4,5,6,7 (do not cover the Appendix).For an audience mostly interested in modeling and applications, coverChapters 1,2,3,6, an audience with prior knowledge of the simplex method, coverChapters 1,3,4,5,6, a slow-paced course based only on linear programming, coverChapters 1,2,3, a course based only on linear programming, cover Chapters1,2,3,4,5 (possibly with the Appendix included).For a course based only on linear programming and discreteoptimization, cover chapters 1,2,3,4,5,6 (possibly with the Appendixincluded).