Information Complexity of Mixed-Integer Convex Optimization

被引：0

作者：

Basu, Amitabh ^{[1
]}

Jiang, Hongyi ^{[2
]}

Kerger, Phillip ^{[1
]}

Molinaro, Marco ^{[3
,4
]}

机构：

[1] Johns Hopkins Univ, Dept Appl Math & Stat, Baltimore, MD USA

[2] Cornell Univ, Sch Civil & Environm Engn, Ithaca, NY 14853 USA

[3] Microsoft Res, Redmond, WA 98052 USA

[4] Pontificia Univ Catolica Rio de Janeiro, Comp Sci Dept, Rio de Janeiro, Brazil

来源：

INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2023 | 2023年 / 13904卷

基金：

美国国家科学基金会;

关键词：

Mixed-integer optimization; Information complexity;

D O I：

10.1007/978-3-031-32726-1_1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate the information complexity of mixed-integer convex optimization under different kinds of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. Further, we prove the first set of results in the literature (to the best of our knowledge) on information complexity with respect to oracles based on first-order information but restricted to binary queries, and discuss various special cases of interest thereof.

引用

页码：1 / 13

页数：13

共 50 条

[31] Approximate Multiparametric Mixed-Integer Convex Programming
Malyuta, Danylo
Acikmese, Behcet
IEEE CONTROL SYSTEMS LETTERS, 2020, 4 (01): : 157 - 162
[32] Extended Formulations in Mixed-Integer Convex Programming
Lubin, Miles
Yamangil, Emre
Bent, Russell
Vielma, Juan Pablo
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2016, 2016, 9682 : 102 - 113
[33] Feasibility in reverse convex mixed-integer programming
Obuchowska, Wieslawa T.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 218 (01) : 58 - 67
[34] Outer approximation for generalized convex mixed-integer nonlinear robust optimization problems
Kuchlbauer, Martina
OPERATIONS RESEARCH LETTERS, 2025, 60
[35] Distributed Optimization for Convex Mixed-Integer Programs based on Projected Subgradient Algorithm
Sun, Chuangchuang
Dai, Ran
2018 IEEE CONFERENCE ON DECISION AND CONTROL (CDC), 2018, : 2581 - 2586
[36] Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded
Mistry, Miten
Letsios, Dimitrios
Krennrich, Gerhard
Lee, Robert M.
Misener, Ruth
INFORMS JOURNAL ON COMPUTING, 2021, 33 (03) : 1103 - 1119
[37] Note on the complexity of the mixed-integer hull of a polyhedron
Hildebrand, Robert
Oertel, Timm
Weismantel, Robert
OPERATIONS RESEARCH LETTERS, 2015, 43 (03) : 279 - 282
[38] Complexity of Branch-and-Bound and Cutting Planes in Mixed-Integer Optimization — II
Amitabh Basu
Michele Conforti
Marco Di Summa
Hongyi Jiang
Combinatorica, 2022, 42 : 971 - 996
[39] Granularity in Nonlinear Mixed-Integer Optimization
Neumann, Christoph
Stein, Oliver
Sudermann-Merx, Nathan
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2020, 184 (02) : 433 - 465
[40] Granularity in Nonlinear Mixed-Integer Optimization
Christoph Neumann
Oliver Stein
Nathan Sudermann-Merx
Journal of Optimization Theory and Applications, 2020, 184 : 433 - 465

← 1 2 3 4 5 →