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] Polyhedral approximation in mixed-integer convex optimization
    Lubin, Miles
    Yamangil, Emre
    Bent, Russell
    Vielma, Juan Pablo
    MATHEMATICAL PROGRAMMING, 2018, 172 (1-2) : 139 - 168
  • [3] Polyhedral approximation in mixed-integer convex optimization
    Miles Lubin
    Emre Yamangil
    Russell Bent
    Juan Pablo Vielma
    Mathematical Programming, 2018, 172 : 139 - 168
  • [4] 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
  • [5] 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
  • [6] Sparse convex optimization toolkit: a mixed-integer framework
    Olama, Alireza
    Camponogara, Eduardo
    Kronqvist, Jan
    OPTIMIZATION METHODS & SOFTWARE, 2023, 38 (06): : 1269 - 1295
  • [7] Mixed-Integer Convex Representability
    Lubin, Miles
    Zadik, Ilias
    Vielma, Juan Pablo
    INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2017, 2017, 10328 : 392 - 404
  • [8] Mixed-Integer Convex Representability
    Lubin, Miles
    Vielma, Juan Pablo
    Zadik, Ilias
    MATHEMATICS OF OPERATIONS RESEARCH, 2022, 47 (01) : 720 - 749
  • [9] Mixed-Integer Convex Optimization for DC Microgrid Droop Control
    Jabr, Rabih A.
    IEEE TRANSACTIONS ON POWER SYSTEMS, 2021, 36 (06) : 5901 - 5908
  • [10] Linearization and parallelization schemes for convex mixed-integer nonlinear optimization
    Meenarli Sharma
    Prashant Palkar
    Ashutosh Mahajan
    Computational Optimization and Applications, 2022, 81 : 423 - 478
12345