Introduction to Continuous Optimization

This second edition introduces several areas and items that were not included in the first edition, as well as several corrections. A brief summary of these changes are given next.Chapter 1 includes a discussion on the diet problem, inaddition to that on the staff planning problem, in order to very early on introduce linear programming. Figure 1.1 now has the terminating box ``Implementation\u27\u27, whereas the original one had an infinite loop! Chapter 3 has been enriched by several new results onseparating and supporting hyperplanes, and the associated theory of convex cones and their polar sets. Thanks to this study of separating hyperplanes,Theorem 5.17 on the necessity of the Fritz John conditions now hasa complete proof. The end of Chapter 5 alsoincludes a summary of the fascinating story of the development of theKarush--Kuhn--Tucker conditions. The sensitivity analysis in linearprogramming has been expanded with a discussion in Section 10.5.3 onthe addition of a variable or a constraint, as well as an introduction tocolumn generation based on the example of the minimum cost multi-commoditynetwork flow problem (Section 10.6).Chapter 11 includes a brief discussion onGauss--Newton methods for least-squares problems.Chapter 12 has changed its name from ``Optimization overconvex sets\u27\u27 to ``Feasible-direction methods,\u27\u27 in order to reflect the factthat the scope is now wider---from essentially polyhedral sets to generalclosed sets (which, however, most often will be assumed to be convex). Inparticular, we have added new sections on algorithms defined by closed descentmaps---an algorithm principle which was devised and analyzed mainly in the1960s, and which is a quite elegant means to describe iterative methods. Wealso utilize this principle to contrast established convergent methods (suchas the Frank--Wolfe method) and failed attempts (such as the algorithm ofZoutendijk). We have also added a brief discussion on reduced gradientmethods, which are relatives to the simplex method; they are---in theiroriginal statement---not convergent, but a small adjustment results in aclosed descent map and hence a convergent method.Exercises and their solutions are now placed at the end of the book, ratherthan at the end of each chapter.The first edition from 2005 has been used in teaching of several courses atChalmers University of Technology and the University of Gothenburg. We wish tothank all the students who have given us remarks on the book. We would alsolike to thank Dr. Kin Cheong Sou for remarks and corrections on the firstedition