A Simple Method for Convex Optimization in the Oracle Model

Daniel Dadush; Christopher Hojny; Sophie Huiberts; Stefan Weltge

doi:10.1007/978-3-031-06901-7_12

A Simple Method for Convex Optimization in the Oracle Model

Daniel Dadush
, Christopher Hojny
, Sophie Huiberts
, Stefan Weltge (Corresponding author)

Combinatorial Optimization

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

4 Downloads (Pure)

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) ≤ ε+ min _z _∈ _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.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization
Subtitle of host publication	23rd International Conference, IPCO 2022 Eindhoven, The Netherlands, June 27-29,2022 Proceedings
Editors	Karen Aardal, Laura Sanità
Place of Publication	Cham
Publisher	Springer
Pages	154-167
Number of pages	14
ISBN (Electronic)	978-3-031-06901-7
ISBN (Print)	978-3-031-06900-0
DOIs	https://doi.org/10.1007/978-3-031-06901-7_12
Publication status	Published - 27 May 2022
Event	The 23rd Conference on Integer Programming and Combinatorial Optimization - Eindhoven University of Technology, Eindhoven, Netherlands Duration: 27 Jun 2022 → 29 Jun 2022 Conference number: 23 https://www.ipco2022.com/home

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Volume	13265
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	The 23rd Conference on Integer Programming and Combinatorial Optimization
Abbreviated title	IPCO 2022
Country/Territory	Netherlands
City	Eindhoven
Period	27/06/22 → 29/06/22
Internet address	https://www.ipco2022.com/home

Keywords

convex optimization
cutting plane method
separation oracle

Access to Document

10.1007/978-3-031-06901-7_12

pdfFinal published version, 371 KBLicence: TAVERNE

Cite this

Dadush, D., Hojny, C., Huiberts, S., & Weltge, S. (2022). A Simple Method for Convex Optimization in the Oracle Model. In K. Aardal, & L. Sanità (Eds.), Integer Programming and Combinatorial Optimization: 23rd International Conference, IPCO 2022 Eindhoven, The Netherlands, June 27-29,2022 Proceedings (pp. 154-167). (Lecture Notes in Computer Science (LNCS); Vol. 13265). Springer. https://doi.org/10.1007/978-3-031-06901-7_12

Dadush, Daniel ; Hojny, Christopher ; Huiberts, Sophie et al. / A Simple Method for Convex Optimization in the Oracle Model. Integer Programming and Combinatorial Optimization: 23rd International Conference, IPCO 2022 Eindhoven, The Netherlands, June 27-29,2022 Proceedings. editor / Karen Aardal ; Laura Sanità. Cham : Springer, 2022. pp. 154-167 (Lecture Notes in Computer Science (LNCS)).

@inproceedings{3e33bf85fba3414d82b11690feb32e56,

title = "A Simple Method for Convex Optimization in the Oracle Model",

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{\textendash}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) ≤ ε+ min z ∈ 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.",

keywords = "convex optimization, cutting plane method, separation oracle",

author = "Daniel Dadush and Christopher Hojny and Sophie Huiberts and Stefan Weltge",

year = "2022",

month = may,

day = "27",

doi = "10.1007/978-3-031-06901-7\_12",

language = "English",

isbn = "978-3-031-06900-0",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "154--167",

editor = "Karen Aardal and Laura Sanit{\`a}",

booktitle = "Integer Programming and Combinatorial Optimization",

address = "Germany",

note = "The 23rd Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 ; Conference date: 27-06-2022 Through 29-06-2022",

url = "https://www.ipco2022.com/home",

}

Dadush, D, Hojny, C, Huiberts, S & Weltge, S 2022, A Simple Method for Convex Optimization in the Oracle Model. in K Aardal & L Sanità (eds), Integer Programming and Combinatorial Optimization: 23rd International Conference, IPCO 2022 Eindhoven, The Netherlands, June 27-29,2022 Proceedings. Lecture Notes in Computer Science (LNCS), vol. 13265, Springer, Cham, pp. 154-167, The 23rd Conference on Integer Programming and Combinatorial Optimization, Eindhoven, Netherlands, 27/06/22. https://doi.org/10.1007/978-3-031-06901-7_12

A Simple Method for Convex Optimization in the Oracle Model. / Dadush, Daniel; Hojny, Christopher; Huiberts, Sophie et al.
Integer Programming and Combinatorial Optimization: 23rd International Conference, IPCO 2022 Eindhoven, The Netherlands, June 27-29,2022 Proceedings. ed. / Karen Aardal; Laura Sanità. Cham: Springer, 2022. p. 154-167 (Lecture Notes in Computer Science (LNCS); Vol. 13265).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 - Conference code: 23

PY - 2022/5/27

Y1 - 2022/5/27

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) ≤ ε+ min z ∈ 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) ≤ ε+ min z ∈ 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 - https://www.scopus.com/pages/publications/85131940277

U2 - 10.1007/978-3-031-06901-7_12

DO - 10.1007/978-3-031-06901-7_12

M3 - Conference contribution

SN - 978-3-031-06900-0

T3 - Lecture Notes in Computer Science (LNCS)

SP - 154

EP - 167

BT - Integer Programming and Combinatorial Optimization

A2 - Aardal, Karen

A2 - Sanità, Laura

PB - Springer

CY - Cham

T2 - The 23rd Conference on Integer Programming and Combinatorial Optimization

Y2 - 27 June 2022 through 29 June 2022

ER -

Dadush D, Hojny C, Huiberts S, Weltge S. A Simple Method for Convex Optimization in the Oracle Model. In Aardal K, Sanità L, editors, Integer Programming and Combinatorial Optimization: 23rd International Conference, IPCO 2022 Eindhoven, The Netherlands, June 27-29,2022 Proceedings. Cham: Springer. 2022. p. 154-167. (Lecture Notes in Computer Science (LNCS)). doi: 10.1007/978-3-031-06901-7_12

A Simple Method for Convex Optimization in the Oracle Model

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this