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] Mixed-integer optimization approach to learning association rules for unplanned ICU transfer
Chou, Chun-An
Cao, Qingtao
Weng, Shao-Jen
Tsai, Che-Hung
ARTIFICIAL INTELLIGENCE IN MEDICINE, 2020, 103
[32] Microalgae Production and Maintenance Optimization via Mixed-Integer Model Predictive Control
Martinez-Piazuelo, Juan
Ocampo-Martinez, Carlos
Quijano, Nicanor
Ingimundarson, Ari
IFAC PAPERSONLINE, 2023, 56 (02): : 11100 - 11105
[33] A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
Kobayashi, Ken
Takano, Yuich
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2020, 75 (02) : 493 - 513
[34] An extension of Nelder-Mead method to nonlinear mixed-integer optimization problems
Brea, Ebert
REVISTA INTERNACIONAL DE METODOS NUMERICOS PARA CALCULO Y DISENO EN INGENIERIA, 2013, 29 (03): : 163 - 174
[35] A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
Ken Kobayashi
Yuich Takano
Computational Optimization and Applications, 2020, 75 : 493 - 513
[36] Feature and functional form selection in additive models via mixed-integer optimization
Navarro-Garcia, Manuel
Guerrero, Vanesa
Durban, Maria
del Cerro, Arturo
COMPUTERS & OPERATIONS RESEARCH, 2025, 176
[37] Mixed-Integer Benchmark Problems for Single- and Bi-Objective Optimization
Tusar, Tea
Brockhoff, Dimo
Hansen, Nikolaus
PROCEEDINGS OF THE 2019 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'19), 2019, : 718 - 726
[38] Gene selection and cancer microarray data classification via mixed-integer optimization
Orsenigo, Carlotta
EVOLUTIONARY COMPUTATION, MACHINE LEARNING AND DATA MINING IN BIOINFORMATICS, PROCEEDINGS, 2008, 4973 : 141 - 152
[39] Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation
Wang, Honggang
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 217 (01) : 141 - 148
[40] Modeling with discrete-time recurrent fuzzy systems via mixed-integer optimization
Schwung, Andreas
Adamy, Juergen
FUZZY SETS AND SYSTEMS, 2012, 203 : 1 - 16

← 1 2 3 4 5 →