机器学习和凸优化领域大牛Yurii Nesterov 2018年的最新力作。经典凸优化书籍 Introductory Lectures on Convex Optimization: A Basic Course 的再版。原书也可从如下地址下载https://link.springer.com/book/10.1007/978-3-319-91578-4
Moreinformationaboutthisseriesathttp://www.springer.com/series/7393 Yurii nesterov Lectures on convex Optimization Second edition ringer Yurii Nesterov CORE/INMA Catholic University of louvain Louvain-la-Neuve belgium ISSN1931-6828 IsSN 1931-6836 (electronic) Springer Optimization and Its Applications ISBN978-3-31991577-7 ISBN978-3-31991578-4( eBook) https://doi.org/10.1007/978-3-319-91578-4 Library of congress Control Number: 2018949149 Mathematics Subject Classification(2010): 49M15, 49M29, 49N15, 65K05, 65K10, 90C25, 90C30 90C46,90C51,90C52,90c60 o Springer Nature Switzerland AG 2004, 2018 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part 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 dissimilar methodology now known or hereafter developed 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 from the relevant otective laws and regulations and therefore free for general use 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 authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations This springer imprint is published by the registered company Springer Nature Switzerland AG The registered company address is: Gewerbestrasse ll, 6330 Cham, Switzerland To my wife svetlana Preface The idea of writing this book came from the editors of Springer, who suggested that the author should think about a renewal of the book Introductory Lectures on Convex Optimization: Basic Course, which was published by Kluwer in 2003 [39]. In fact, the main part of this book was written in the period 1997-1998, so its material is at least twenty years old. For such a lively field as Convex Optimization, this is indeed a long time However, having started to work with the text, the author realized very quickly that this modest goal was simply unreachable. The main idea of [39] was to present a short one-semester course(12 lectures)on Convex Optimization, which reflected the main algorithmic achievements in the field at the time. Therefore some important notions and ideas, especially related to all kinds of Duality Theory, were eliminated from the contents without any remorse. In some sense, [39] still remains the minimal course representing the basic concepts of algorithmic convex Optimization. Any enlargements to this text would require difficult explanations as to why the selected material is more important than the many other interesting candidates which have been left on the shelf Thus the author came to a hard decision to write a new book which includes all of the material of [39 along with the most important advances in the field during the last two decades. From the chronological point of view, this book covers the period up to the year 2012. Therefore, the newer results on random coordinate descent methods and universal methods complexity results on zero- order algorithms and methods for solving huge-scale problems are still missin However, in our opinion, these very interesting topics have not yet matured enougH for a monographic presentation, especially in the form of lectures From the methodological point of view, the main novelty of this book consists in the wide presence of duality. Now the reader can see the story from both sides Well, just for consistency, we added the results from several last-minute publications, which are important for the topics discussed in the book VIll P rerace primal and dual. As compared to [39], the size of the book is doubled, which looks to be a reasonable price to pay for a comprehensive presentation. Clearly, this book is too big now to be taught during one-semester. However, it fits well a two-semester term. Alternatively, different parts of it can be used in diverse educational programs on modern optimization We discuss possible variants at the end of the introduction In this book we include three topics, which are new to the monographic literature The smoothing technique. This approach has completely changed our under- standing of complexity of nonsmooth optimization problems, which arise in the vast majority of applications. It is based on the algorithmic possibility of approximating a non-differentiable convex function by a smooth one, and minimizing the new objective by fast gradient Methods As compared with standard subgradient methods, the complexity of each iteration of the new schemes does not change. However, the estimate for the number of iterations of these schemes becomes proportional to the square root of this number for the standard methods. Since in practice, these numbers are usually of the order of many thousands, or even millions, the gain in computational time becomes spectacular Global complexity bounds for second-order methods. Second- order methods and their most famous representative, the Newtons Method, are among the oldest schemes in Numerical Analysis. However, their global complexity analysis has only recently been carried out, after the discovery of the Cubic regularization of newton's method for this new variant of classical scheme we can write down the global complexity bounds for different problem classes. Consequently we can now compare global efficiency of different second-order methods and develop accelerated schemes. A completely new feature of these methods is the accumulation of some model of the objective function during the minimization process. at the same time we can derive for them lower complexity bounds and develop optimal second-order methods. Similar modifications can be made for methods solving systems of nonlinear equations Optimization in relative scale. The standard way of defining an approximate solution of an optimization problem consists in introducing absolute accuracy. However, in many engineering applications, it is natural to measure the quality of solution in a relative scale(percent To adjust minimization methods toward this goal, we introduce a special model of objective function and apply efficient preprocessing algorithms for computing an appropriate metric, compatible with the topology of the objective. As a result, we get very efficient optimization methods with a weak dependence of their complexity bounds in the size of input data We hope that this book will be useful for a wide audience, including students with mathematical, economical, and engineering specializations, practitioners of different fields, and researchers in Optimization Theory, Operations Research, and Computer Science. The main lesson of the development of our field in the last few decades is that efficient optimization methods can be developed only by intelligently Preface employing the structure of particular instances of problems. In order to do this, it is always useful to look at successful examples We believe that this book will provide the interested reader with a great deal of information of this type ouvain-la- Neuve, Belgium Yurii Nesterov January 2018 Acknowledgements Through my scientific career, I have had an extraordinary opportunity of being able to have regular scientific discussions with Arkady Nemirovsky. His remarkable mathematical intuition and profound mathematical culture helped me enormously in my scientific research. Boris Polyak has remained my scientific adviser starting from the time of my PhD, for almost four decades. His scientific longevity has set a very stimulating example. I am very thankful to my colleagues A d'Aspremont, A. Antipin, V. Blondel,O. Burdakov, C. Cartis, F. Glineur, C. Gonzaga, R Freund A. Juditsky, H.J. Luthi, B. Mordukhovich, M. Overton, R. Polyak, V. Protasov, J. Renegar, P. Richtarik, R Sepulchre, K. Scheinberg, A. Shapiro, S.Shpirko, Y Smeers. L. Tuncel. P. Vandooren J -Ph. Vial. and r. Weismantel for our regular scientific discussions resulting from time to time in a joint paper. In the recent years, my contact with young researchers P. Dvurechensky, N. Doikov, A. Gasnikov, G Grapiglia, R Hildebrand, A Rodomanov, and V shikhman has been very interesting and stimulating. At the same time. i am convinced that the excellent conditions for research, provided me by Universite Catholique de louvain (UCl), is a result of continuous support(over several decades! from the patriarchs of UCl Jacques Dreze, Michele Gevers, and Laurence Wolsey. To all these people, I express my sincere gratitude The contents of this book have already been presented in several educational courses. I am very thankful to C. Helmberg, R. Freund, B Legat, J. Renegar, H Sendov, A. Tits, M. Todd, L. Tuncel, and P. Weiss for reporting to me a number of misprints in [39]. In the period 201 1-2017 I had the very useful opportunity of presenting some parts of the new material in several advanced courses on Modern Convex Optimization at different universities over the world ( University of liege ENSAE(ParisTech), University of Vienna, Max Planck Institute(Saarbrucken) FIM(ETH Zurich), Ecole Polytechnique, Higher School of Economics(Moscow) Korea Advanced Institute of Science Technology(Daejeon), Chinese Academy of Sciences (Beijing). I am very thankful to all these people and institutions for their interest in my research Finally, only the patience and professionalism of Springer editors Anne-Kathrin Birchley- Brun and Remi lodh has made the publication of this book possible