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 条

[1] Information complexity of mixed-integer convex optimization
Basu, Amitabh
Jiang, Hongyi
Kerger, Phillip
Molinaro, Marco
MATHEMATICAL PROGRAMMING, 2025, 210 (1-2) : 3 - 45
[2] An approximation algorithm for multiobjective mixed-integer convex optimization
Lammel, Ina
Kuefer, Karl-Heinz
Suess, Philipp
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2024, 100 (01) : 321 - 350
[3] A Solver for Multiobjective Mixed-Integer Convex and Nonconvex Optimization
Eichfelder, Gabriele
Stein, Oliver
Warnow, Leo
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2024, 203 (02) : 1736 - 1766
[4] A Prescriptive Machine Learning Approach to Mixed-Integer Convex Optimization
Bertsimas, Dimitris
Kim, Cheol Woo
INFORMS JOURNAL ON COMPUTING, 2023, 35 (06) : 1225 - 1241
[5] A mixed-integer approximation of robust optimization problems with mixed-integer adjustments
Kronqvist, Jan
Li, Boda
Rolfes, Jan
OPTIMIZATION AND ENGINEERING, 2024, 25 (03) : 1271 - 1296
[6] Mixed-Integer Optimization with Constraint Learning
Maragno, Donato
Wiberg, Holly
Bertsimas, Dimitris
Birbil, S. . Ilker
den Hertog, Dick
Fajemisin, Adejuyigbe O.
OPERATIONS RESEARCH, 2025, 73 (02) : 1011 - 1028
[7] Online Mixed-Integer Optimization in Milliseconds
Bertsimas, Dimitris
Stellato, Bartolomeo
INFORMS JOURNAL ON COMPUTING, 2022, 34 (04) : 2229 - 2248
[8] MISO: mixed-integer surrogate optimization framework
Juliane Müller
Optimization and Engineering, 2016, 17 : 177 - 203
[9] Fuzzy Programming for Mixed-Integer Optimization Problems
Lin, Yung-Chin
Lin, Yung-Chien
Su, Kuo-Lan
Lin, Wei-Cheng
Chen, Tsing-Hua
PROCEEDINGS OF THE SIXTEENTH INTERNATIONAL SYMPOSIUM ON ARTIFICIAL LIFE AND ROBOTICS (AROB 16TH '11), 2011, : 261 - 264
[10] MISO: mixed-integer surrogate optimization framework
Mueller, Juliane
OPTIMIZATION AND ENGINEERING, 2016, 17 (01) : 177 - 203

← 1 2 3 4 5 →