A Simple Method for Convex Optimization in the Oracle Model

Daniel Dadush, Christopher Hojny, Sophie Huiberts, Stefan Weltge

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

3 Zitate (Scopus)

Abstract

We give a simple and natural method for computing approximately optimal solutions for minimizing a convex function f over a convex set K given by a separation oracle. Our method utilizes the Frank–Wolfe algorithm over the cone of valid inequalities of K and subgradients of f. Under the assumption that f is L-Lipschitz and that K contains a ball of radius r and is contained inside the origin centered ball of radius R, using O((RL)2ε2·R2r2) iterations and calls to the oracle, our main method outputs a point x∈ K satisfying f(x) ≤ ε+ minz Kf(z). Our algorithm is easy to implement, and we believe it can serve as a useful alternative to existing cutting plane methods. As evidence towards this, we show that it compares favorably in terms of iteration counts to the standard LP based cutting plane method and the analytic center cutting plane method, on a testbed of combinatorial, semidefinite and machine learning instances.

OriginalspracheEnglisch
TitelInteger Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings
Redakteure/-innenKaren Aardal, Laura Sanità
Herausgeber (Verlag)Springer Science and Business Media Deutschland GmbH
Seiten154-167
Seitenumfang14
ISBN (Print)9783031069000
DOIs
PublikationsstatusVeröffentlicht - 2022
Veranstaltung23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 - Eindhoven, Niederlande
Dauer: 27 Juni 202229 Juni 2022

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band13265 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Konferenz

Konferenz23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022
Land/GebietNiederlande
OrtEindhoven
Zeitraum27/06/2229/06/22

Fingerprint

Untersuchen Sie die Forschungsthemen von „A Simple Method for Convex Optimization in the Oracle Model“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren