TY - GEN
T1 - A Simple Method for Convex Optimization in the Oracle Model
AU - Dadush, Daniel
AU - Hojny, Christopher
AU - Huiberts, Sophie
AU - Weltge, Stefan
N1 - Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - convex optimization
KW - cutting plane method
KW - separation oracle
UR - http://www.scopus.com/inward/record.url?scp=85131940277&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-06901-7_12
DO - 10.1007/978-3-031-06901-7_12
M3 - Conference contribution
AN - SCOPUS:85131940277
SN - 9783031069000
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 154
EP - 167
BT - Integer Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings
A2 - Aardal, Karen
A2 - Sanità, Laura
PB - Springer Science and Business Media Deutschland GmbH
T2 - 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022
Y2 - 27 June 2022 through 29 June 2022
ER -