Algorithms for Convex Optimization
- Length: 200 pages
- Edition: 1
- Language: English
- Publisher: Cambridge University Press
- Publication Date: 2021-10-07
- ISBN-10: 1108482023
- ISBN-13: 9781108482028
- Sales Rank: #5638525 (See Top 100 Books)
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.
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
Donate to keep this site alive
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.