Algorithms for convex optimization / Nisheeth K. Vishnoi.

Format:

Book

Author/Creator:

Vishnoi, Nisheeth K., 1976- author.

Language:

English

Subjects (All):

Mathematical optimization.

Convex programming.

Convex functions.

Physical Description:

1 online resource (xvi, 323 pages) : digital, PDF file(s).

Edition:

1st ed.

Place of Publication:

Cambridge : Cambridge University Press, 2021.

Summary:

In the last few years, Algorithms for Convex Optimization have revolutionized algorithm design, both for discrete and continuous optimization problems. For problems like 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, 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.

Contents:

Cover

Half-title

Title page

Copyright information

Dedication

Contents

Preface

Acknowledgments

Notation

1 Bridging Continuous and Discrete Optimization

1.1 An Example: The Maximum Flow Problem

1.2 Linear Programming

1.3 Fast and Exact Algorithms via Interior Point Methods

1.4 Ellipsoid Method beyond Succinct Linear Programs

2 Preliminaries

2.1 Derivatives, Gradients, and Hessians

2.2 Fundamental Theorem of Calculus

2.3 Taylor Approximation

2.4 Linear Algebra, Matrices, and Eigenvalues

2.5 The Cauchy-Schwarz Inequality

2.6 Norms

2.7 Euclidean Topology

2.8 Dynamical Systems

2.9 Graphs

2.10 Exercises

3 Convexity

3.1 Convex Sets

3.2 Convex Functions

3.3 The Usefulness of Convexity

3.4 Exercises

4 Convex Optimization and Efficiency

4.1 Convex Programs

4.2 Computational Models

4.3 Membership Problem for Convex Sets

4.4 Solution Concepts for Optimization Problems

4.5 The Notion of Polynomial Time for Convex Optimization

4.6 Exercises

5 Duality and Optimality

5.1 Lagrangian Duality

5.2 The Conjugate Function

5.3 KKT Optimality Conditions

5.4 Proof of Strong Duality under Slater's Condition

5.5 Exercises

6 Gradient Descent

6.1 The Setup

6.2 Gradient Descent

6.3 Analysis When the Gradient Is Lipschitz Continuous

6.4 Application: The Maximum Flow Problem

6.5 Exercises

7 Mirror Descent and the Multiplicative Weights Update

7.1 Beyond the Lipschitz Gradient Condition

7.2 A Local Optimization Principle and Regularizers

7.3 Exponential Gradient Descent

7.4 Mirror Descent

7.5 Multiplicative Weights Update

7.6 Application: Perfect Matching in Bipartite Graphs

7.7 Exercises

8 Accelerated Gradient Descent

8.1 The Setup

8.2 Main Result on Accelerated Gradient Descent.

8.3 Proof Strategy: Estimate Sequences

8.4 Construction of an Estimate Sequence

8.5 The Algorithm and Its Analysis

8.6 An Algorithm for Strongly Convex and Smooth Functions

8.7 Application: Linear System of Equations

8.8 Exercises

9 Newton's Method

9.1 Finding a Root of a Univariate Function

9.2 Newton's Method for Multivariate Functions

9.3 Newton's Method for Unconstrained Optimization

9.4 First Take on the Analysis

9.5 Newton's Method as Steepest Descent

9.6 Analysis Based on a Local Norm

9.7 Analysis Based on the Euclidean Norm

9.8 Exercises

10 An Interior Point Method for Linear Programming

10.1 Linear Programming

10.2 Constrained Optimization via Barrier Functions

10.3 The Logarithmic Barrier Function

10.4 The Central Path

10.5 A Path-Following Algorithm for Linear Programming

10.6 Analysis of the Path-Following Algorithm

10.7 Exercises

11 Variants of Interior Point Method and Self-Concordance

11.1 The Minimum Cost Flow Problem

11.2 An IPM for Linear Programming in Standard Form

11.3 Application: The Minimum Cost Flow Problem

11.4 Self-Concordant Barriers

11.5 Linear Programming Using Self-Concordant Barriers

11.6 Semidefinite Programming Using Self-Concordant Barriers

11.7 Convex Optimization Using Self-Concordant Barriers

11.8 Exercises

12 Ellipsoid Method for Linear Programming

12.1 0-1-Polytopes with Exponentially Many Constraints

12.2 Cutting Plane Methods

12.3 Ellipsoid Method

12.4 Analysis of Volume Drop and Efficiency for Ellipsoids

12.5 Application: Linear Optimization over 0-1-Polytopes

12.6 Exercises

13 Ellipsoid Method for Convex Optimization

13.1 Convex Optimization Using the Ellipsoid Method?

13.2 Application: Submodular Function Minimization

13.3 Application: The Maximum Entropy Problem.

13.4 Convex Optimization Using the Ellipsoid Method

13.5 Variants of Cutting Plane Method

13.6 Exercises

Bibliography

Index.

Notes:

Title from publisher's bibliographic system (viewed on 27 Sep 2021).

ISBN:

1-108-63399-4

1-108-75737-5

1-108-69921-9

OCLC:

1285170944