Efficient convex optimization with oracles

DOI10.1007/978-3-662-59204-5_10MaRDI QIDQ3295271zbMATH OpenOpenAlexFDO

Authors Yin Tat Lee, Aaron Sidford, Santosh S. Vempala

Publication date 8 July 2020

Published in Bolyai Society Mathematical Studies (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-59204-5_10

zbMATH Keywords

convex optimizationreductionsseparationmembership

Mathematics Subject Classification ID

Convex programming (90C25) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• A simple method for convex optimization in the oracle model
• A new algorithm for minimizing convex functions over convex sets
• A cutting plane algorithm for convex programming that uses analytic centers
• Integer convex minimization by mixed integer linear optimization
• Solving convex programs by random walks

Cites work

• A new approach to computing maximum flows using electrical flows
• Algorithms for approximate calculation of the minimum of a convex function from its values
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Area-convexity, \(\ell_\infty\) regularization, and undirected multicommodity flow
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Exploratory distributions for convex functions
• Geometric algorithms and combinatorial optimization
• Random gradient-free minimization of convex functions
• Sharp \(L^1\)-Poincaré inequalities correspond to optimal hypersurface cuts
• Simulated Annealing for Convex Optimization
• Solving convex programs by random walks

Cited in

(9)

• Integer conic function minimization based on the comparison oracle
• Quantum algorithm design: techniques and applications
• A simple method for convex optimization in the oracle model
• On the oracle complexity of smooth strongly convex minimization
• Solving convex programs by random walks
• Simulated annealing for convex optimization: rigorous complexity analysis and practical perspectives
• Proximal-ACCPM: a versatile oracle based optimisation method
• Approximating convex functions via non-convex oracles under the relative noise model
• A simple method for convex optimization in the oracle model

This page was built for publication: Efficient convex optimization with oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3295271)