Constrained mixed-integer transfer conjecture
Constrained mixed-integer transfer conjecture
Let 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 there exist mixed-integer instances with integer variables whose information complexity, with respect to the same oracle, is lower bounded by
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.