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] Binary decision rules for multistage adaptive mixed-integer optimization
Bertsimas, Dimitris
Georghiou, Angelos
MATHEMATICAL PROGRAMMING, 2018, 167 (02) : 395 - 433
[22] A Mixed-Integer Optimization Strategy for Oil Supply in Distribution Complexes
Mas, Rodrigo
Pinto, Jose M.
OPTIMIZATION AND ENGINEERING, 2003, 4 (1-2) : 23 - 64
[23] Binary decision rules for multistage adaptive mixed-integer optimization
Dimitris Bertsimas
Angelos Georghiou
Mathematical Programming, 2018, 167 : 395 - 433
[24] A genetic mixed-integer optimization of neural network hyper-parameters
Spurlock, Kyle
Elgazzar, Heba
JOURNAL OF SUPERCOMPUTING, 2022, 78 (12) : 14680 - 14702
[25] A Two-Timescale Duplex Neurodynamic Approach to Mixed-Integer Optimization
Che, Hangjun
Wang, Jun
IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, 2021, 32 (01) : 36 - 48
[26] Failure Mitigation and Restoration in Interdependent Networks via Mixed-Integer Optimization
Chen, Cheng-Lung
Zheng, Qipeng P.
Veremyev, Alexander
Pasiliao, Eduardo L.
Boginski, Vladimir
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING, 2021, 8 (02): : 1293 - 1304
[27] A genetic mixed-integer optimization of neural network hyper-parameters
Kyle Spurlock
Heba Elgazzar
The Journal of Supercomputing, 2022, 78 : 14680 - 14702
[28] Review and comparison of algorithms and software for mixed-integer derivative-free optimization
Ploskas, Nikolaos
Sahinidis, Nikolaos V.
JOURNAL OF GLOBAL OPTIMIZATION, 2022, 82 (03) : 433 - 462
[29] OUTLIER DETECTION IN TIME SERIES VIA MIXED-INTEGER CONIC QUADRATIC OPTIMIZATION
Gomez, Andres
SIAM JOURNAL ON OPTIMIZATION, 2021, 31 (03) : 1897 - 1925
[30] Review and comparison of algorithms and software for mixed-integer derivative-free optimization
Nikolaos Ploskas
Nikolaos V. Sahinidis
Journal of Global Optimization, 2022, 82 : 433 - 462

← 1 2 3 4 5 →