Nisheeth K. Vishnoi - Algorithms for Convex Optimization

Algorithms for Convex Optimization

In the last few years, algorithms for convex optimization have revolutionized algorithm design, both for discrete and continuous optimization problems. For problems such as maximum flow, maximum matching, and submodular function minimization, the fastest algorithms involve essential methods such as gradient descent, mirror descent, interior point methods, and ellipsoid methods. The goal of this self-contained book is to enable researchers and professionals in computer science, operations research, data science, and machine learning to gain an in-depth understanding of these algorithms. The text emphasizes how to derive key algorithms for convex optimization from first principles and how to establish precise running time bounds. This modern text explains the success of these algorithms in problems of discrete optimization, as well as how these methods have significantly pushed the state of the art of convex optimization itself.

nisheeth k. vishnoi is A. Bartlett Giamatti Professor of Computer Science at Yale University. His research areas include theoretical computer science, optimization, and machine learning. He is a recipient of the Best Paper Award at IEEE FOCS in 2005, the IBM Research Pat Goldberg Memorial Award in 2006, the Indian National Science Academy Young Scientist Award in 2011, and the Best Paper Award at ACM FAccT in 2019. He was elected an ACM Fellow in 2019. He obtained a bachelors degree in computer science and engineering from IIT Bombay and a PhD in algorithms, combinatorics, and optimization from Georgia Institute of Technology.

NISHEETH K. VISHNOI

Yale University

University Printing House, Cambridge CB2 8BS, United Kingdom

One Liberty Plaza, 20th Floor, New York, NY 10006, USA

477 Williamstown Road, Port Melbourne, VIC 3207, Australia

314321, 3rd Floor, Plot 3, Splendor Forum, Jasola District Centre, New Delhi 110025, India

103 Penang Road, #0506/07, Visioncrest Commercial, Singapore 238467

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/9781108482028

DOI: 10.1017/9781108699211

Nisheeth K. Vishnoi 2021

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 2021

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

Library of Congress Cataloging-in-Publication Data

Names: Vishnoi, Nisheeth K., 1976- author.

Title: Algorithms for convex optimization / Nisheeth K. Vishnoi. Description: New York : Cambridge University Press, [2021] | Includes bibliographical references and index.

Identifiers: LCCN 2020052071 (print) | LCCN 2020052072 (ebook) | ISBN 9781108482028 (hardback) | ISBN 9781108741774 (paperback) | ISBN 9781108699211 (epub)

Subjects: LCSH: Mathematical optimization. | Convex functions. | Convex programming.

Classification: LCC QA402.5 .V57 2021 (print) | LCC QA402.5 (ebook) | DDC 515/.882-dc23

LC record available at https://lccn.loc.gov/2020052071

LC record available at https://lccn.loc.gov/2020052072

ISBN 978-1-108-48202-8 Hardback

ISBN 978-1-108-74177-4 Paperback

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 Maya and Vayu

Convex optimization studies the problem of minimizing a convex function over a convex set. Convexity, along with its numerous implications, has been used to come up with efficient algorithms for many classes of convex programs. Consequently, convex optimization has broadly impacted several disciplines of science and engineering.