information complexity

Information Complexity of Mixed-integer Convex Optimization

  • Amitabh Basu
  • Hongyi Jiang
  • Phillip Kerger
  • Marco Molinaro
    • Categories (Mixed) Integer Nonlinear Programming, Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    We investigate the information complexity of mixed-integer convex optimization under different types 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. This is derived … Read more

    Complexity of optimizing over the integers

  • Amitabh Basu
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization Tags , ,

    In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like “input”, “size” and “complexity” in the context of general mathematical optimization, avoiding context dependent definitions which is one of the … Read more