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 条

[21] Parallel Global Optimization for Non-convex Mixed-Integer Problems
Barkalov, Konstantin
Lebedev, Ilya
SUPERCOMPUTING (RUSCDAYS 2019), 2019, 1129 : 98 - 109
[22] Learning Mixed-Integer Convex Optimization Strategies for Robot Planning and Control
Cauligi, Abhishek
Culbertson, Preston
Stellato, Bartolomeo
Bertsimas, Dimitris
Mac Schwager
Pavone, Marco
2020 59TH IEEE CONFERENCE ON DECISION AND CONTROL (CDC), 2020, : 1698 - 1705
[23] Single Leg Dynamic Motion Planning with Mixed-Integer Convex Optimization
Ding, Yanran
Li, Chuanzheng
Park, Hae-Won
2018 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS), 2018, : 7391 - 7396
[24] A Global Optimization Algorithm for Non-Convex Mixed-Integer Problems
Gergel, Victor
Barkalov, Konstantin
Lebedev, Ilya
LEARNING AND INTELLIGENT OPTIMIZATION, LION 12, 2019, 11353 : 78 - 81
[25] Automatic Reformulations for Convex Mixed-Integer Nonlinear Optimization: Perspective and Separability
Sharma, Meenarli
Mahajan, Ashutosh
Leibniz International Proceedings in Informatics, LIPIcs, 2022, 233
[26] Mixed-integer nonlinear optimization
Belotti, Pietro
Kirches, Christian
Leyffer, Sven
Linderoth, Jeff
Luedtke, James
Mahajan, Ashutosh
ACTA NUMERICA, 2013, 22 : 1 - 131
[27] Mixed-integer dynamic optimization
Allgor, RJ
Barton, PI
COMPUTERS & CHEMICAL ENGINEERING, 1997, 21 : S451 - S456
[28] Mixed-integer dynamic optimization
Allgor, R.J.
Barton, P.I.
Computers and Chemical Engineering, 1997, 21 (SUPPL. 1):
[29] Complexity of branch-and-bound and cutting planes in mixed-integer optimization
Basu, Amitabh
Conforti, Michele
Di Summa, Marco
Jiang, Hongyi
MATHEMATICAL PROGRAMMING, 2023, 198 (01) : 787 - 810
[30] Complexity of branch-and-bound and cutting planes in mixed-integer optimization
Amitabh Basu
Michele Conforti
Marco Di Summa
Hongyi Jiang
Mathematical Programming, 2023, 198 : 787 - 810

← 1 2 3 4 5 →