cvxopt.txt

while the mathematics of convex optimization has been studied for about a century several related recent developments have stimulated new interest in the topic the first is the recognition that interior point methods to solve linear programming problems can be used to solve convex optimization problems as well these new methods allow us to solve certain new classes of convex optimization problems such as semidefinite programs and second order cone programs almost as easily as linear programs the second development is the discovery that convex optimization problems are more prevalent in practice than was previously thought many applications have been discovered in areas such as automatic control systems estimation and signal processing communications and networks electronic circuit design data analysis and modeling statistics and finance convex optimization has also found wide application in combinatorial optimization and global optimization where it is used to find bounds on the optimal value as well as approximate solutions we believe that many other applications of convex optimization are still waiting to be discovered there are great advantages to recognizing or formulating a problem as a convex optimization problem the most basic advantage is that the problem can then be solved very reliably and efficiently using interior point methods or other special methods for convex optimization these solution methods are reliable enough to be embedded in a computer aided design or analysis tool or even a real time reactive or automatic control system there are also theoretical or conceptual advantages of formulating a problem as a convex optimization problem the associated dual problem for example often has an interesting interpretation in terms of the original problem and sometimes leads to an efficient or distributed method for solving it for many general purpose optimization methods the typical approach is to just try out the method on the problem to be solved the full benefits of convex optimization in contrast only come when the problem is known ahead of time to be convex of course many optimization problems are not convex and it can be difficult to recognize the ones that are or to reformulate a problem so that it is convex developing a working knowledge of convex optimization can be mathematically demanding especially for the reader interested primarily in applications in our experience mostly with graduate students in electrical engineering and computer science the investment often pays off well and sometimes very well there are several books on linear programming and general nonlinear programming that focus on problem formulation modeling and applications several other books cover the theory of convex optimization or interior point methods and their complexity analysis this book is meant to be something in between a book on general convex optimization that focuses on problem formulation and modeling we should also mention what this book is not it is not a text primarily about convex analysis or the mathematics of convex optimization several existing texts cover these topics well nor is the book a survey of algorithms for convex optimization instead we have chosen just a few good algorithms and describe only simple stylized versions of them which however do work well in practice we make no attempt to cover the most recent state of the art in interior point or other methods for solving convex problems our coverage of numerical implementation issues is also highly simplified but we feel that it is adequate for the potential user to develop working implementations and we do cover in some detail techniques for exploiting structure to improve the efficiency of the methods we also do not cover in more than a simplified way the complexity theory of the algorithms we describe we do however give an introduction to the important ideas of self concordance and complexity analysis for interior point methods this book is meant for the researcher scientist or engineer who uses mathematical optimization or more generally computational mathematics this includes naturally those working directly in optimization and operations research and also many others who use optimization in fields like computer science economics finance statistics data mining and many fields of science and engineering our primary focus is on the latter group the potential users of convex optimization and not the less numerous experts in the field of convex optimization the only background required of the reader is a good knowledge of advanced calculus and linear algebra if the reader has seen basic mathematical analysis  norms convergence elementary topology and basic probability theory he or she should be able to follow every argument and discussion in the book we hope that preface readers who have not seen analysis and probability however can still get all of the essential ideas and important points prior exposure to numerical computing or optimization is not needed since we develop all of the needed material from these areas in the text or appendices we hope that this book will be useful as the primary or alternate textbook for several types of courses we have been using drafts of this book for graduate courses on linear nonlinear and convex optimization with engineering applications at stanford we are able to cover most of the material though not in detail in a one quarter graduate course a one semester course allows for a more leisurely pace more applications more detailed treatment of theory and perhaps a short student project a two quarter sequence allows an expanded treatment of the more basic topics such as linear and quadratic programming which are very useful for the applications oriented student or a more substantial student project this book can also be used as a reference or alternate text for a more traditional course on linear and nonlinear optimization or a course on control systems or other applications area that includes some coverage of convex optimization as the secondary text in a more theoretically oriented course on convex optimization it can be used as a source of simple practical examples