Constrained mixed-integer transfer conjecture

Let \ell be a lower bound on the information complexity, with respect to a fixed oracle, for a family of continuous, constrained convex optimization instances. Mixed-integer transfer conjecture. If such a family exists, then for every n1n\geq 1 there exist mixed-integer instances with nn integer variables whose information complexity, with respect to the same oracle, is lower bounded by

Ω(2n).\Omega(2^n\cdot\ell).

This would extend the paper's pure-optimization transfer theorem to constrained problems and would yield the stated feasibility-based mixed-integer lower bounds as a special case. It would also transfer future improved feasibility lower bounds for continuous convex optimization to the mixed-integer setting.

Sources & referencesView supporting material

Primary source

Amitabh Basu, Hongyi Jiang, Phillip Kerger and Marco Molinaro, “Information Complexity of Mixed-integer Convex Optimization”, arXiv:2308.11153 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.