Giuseppe Calafiore and Laurent Ghaoui - Optimization Models

Emphasizing practical understanding over the technicalities of specific algorithms, this elegant textbook is an accessible introduction to the field of optimization, focusing on powerful and reliable convex optimization techniques. Students and practitioners will learn how to recognize, simplify, model and solve optimization problems and apply these basic principles to their own projects.

A clear and self-contained introduction to linear algebra, accompanied by relevant real-world examples, demonstrates core mathematical concepts in a way that is easy to follow, and helps students to understand their practical relevance.

Requiring only a basic understanding of geometry, calculus, probability and statistics, and striking a careful balance between accessibility and mathematical rigor, it enables students to quickly understand the material, without being overwhelmed by complex mathematics.

Accompanied by numerous end-of-chapter problems, an online solutions manual for instructors, and examples from a diverse range of fields including engineering, data science, economics, finance, and management, this is the perfect introduction to optimization for both undergraduate and graduate students.

GIUSEPPE C. CALAFIORE is an Associate Professor at Dipartimento di Automatica e Informatica, Politecnico di Torino, and a Research Fellow of the Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy.

LAURENT EL GHAOUI is a Professor in the Department of Electrical Engineering and Computer Science, and the Department of Industrial Engineering and Operations Research, at the University of California, Berkeley.

Giuseppe C. Calafiore

Politecnico di Torino

Laurent El Ghaoui

University of California, Berkeley

University Printing House, Cambridge CB2 8BS, United Kingdom

Cambridge University Press is part of the University of Cambridge.

It furthers the Universitys mission by disseminating knowledge in the pursuit of education, learning and research at the highest international levels of excellence.

www.cambridge.org

Information on this title: www.cambridge.org/9781107050877

Cambridge University Press 2014

This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press.

First published 2014

Printed in the United States of America by Sheridan Books, Inc.

A catalogue record for this publication is available from the British Library

ISBN 978-1-107-05087-7 Hardback

Internal design based on tufte-latex.googlecode.com

Licensed under the Apache License, Version 2.0 (the License); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0.

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an as is basis, without warranties or conditions of any kind, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Additional resources for this publication at www.cambridge.org/optimizationmodels

Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

Dedicated to my parents, and to Charlotte.
G. C.

Dedicated to Louis, Alexandre and Camille.
L. El G.

OPTIMIZATION REFERS TO a branch of applied mathematics concerned with the minimization or maximization of a certain function, possibly under constraints. The birth of the field can perhaps be traced back to an astronomy problem solved by the young Gauss. It matured later with advances in physics, notably mechanics, where natural phenomena were described as the result of the minimization of certain energy functions. Optimization has evolved towards the study and application of algorithms to solve mathematical problems on computers.

Today, the field is at the intersection of many disciplines, ranging from statistics, to dynamical systems and control, complexity theory, and algorithms. It is applied to a widening array of contexts, including machine learning and information retrieval, engineering design, economics, finance, and management. With the advent of massive data sets, optimization is now viewed as a crucial component of the nascent field of data science.

In the last two decades, there has been a renewed interest in the field of optimization and its applications. One of the most exciting developments involves a special kind of optimization, convex optimization. Convex models provide a reliable, practical platform on which to build the development of reliable problem-solving software. With the help of user-friendly software packages, modelers can now quickly develop extremely efficient code to solve a very rich library of convex problems. We can now address convex problems with almost the same ease as we solve a linear system of equations of similar size. Enlarging the scope of tractable problems allows us in turn to develop more efficient methods for difficult, non-convex problems.

These developments parallel those that have paved the success of numerical linear algebra. After a series of ground-breaking works on computer algorithms in the late 80s, user-friendly platforms such as Matlab or R, and more recently Python, appeared, and allowed generations of users to quickly develop code to solve numerical problems. Today, only a few experts worry about the actual algorithms and techniques for solving numerically linear systems with a few thousands of variables and equations; the rest of us take the solution, and the algorithms underlying it, for granted.

Optimization, more precisely, convex optimization, is at a similar stage now. For these reasons, most of the students in engineering, economics, and science in general, will probably find it useful in their professional life to acquire the ability to recognize, simplify, model, and solve problems arising in their own endeavors, while only few of them will actually need to work on the details of numerical algorithms. With this view in mind, we titled our book Optimization Models, to highlight the fact that we focus on the art of understanding the nature of practical problems and of modeling them into solvable optimization paradigms (often, by discovering the hidden convexity structure in the problem), rather than on the technical details of an ever-growing multitude of specific numerical optimization algorithms. For completeness, we do provide two chapters, one covering basic linear algebra algorithms, and another one extensively dealing with selected optimization algorithms; these chapters, however, can be skipped without hampering the understanding of the other parts of this book.

Several textbooks have appeared in recent years, in response to the growing needs of the scientific community in the area of convex optimization. Most of these textbooks are graduate-level, and indeed contain a good wealth of sophisticated material. Our treatment includes the following distinguishing elements.