ISyE Seminar Series: Prof. Amitabh Basu
"Information Complexity of Mixed-integer Convex Optimization"
Amitabh Basu
Professor in the department of Applied Mathematics and Statistics at Johns Hopkins University
About the Seminar:
We consider the problem of minimizing a convex function under convex constraints, where some or all of the decision variables are constrained to be integer, with access to first-order oracles for the objective function and separation oracles for the constraints. We focus on the information complexity of the problem, i.e., the minimum number of oracle calls to solve the problem to a desired accuracy. We will present nearly tight upper and lower bounds for the problem, extending classical results from continuous convex optimization. We also initiate the study of, and obtain the first set of results on, information complexity under oracles that only reveal partial first-order information, e.g., where one can only make a binary query on the function value or (sub)gradient at a given point. Our bounds in these new settings show that these oracles are probably less informative than full first-order oracles for the purpose of optimization. We will close the talk with some open questions.
Research Papers Related to the Talk:
Complexity of optimizing over the integers
Information Complexity of Mixed-integer Convex Optimization
About the Speaker:
Amitabh Basu is a professor in the Dept. of Applied Mathematics and Statistics at Johns Hopkins University. He received his Ph.D. from Carnegie Mellon University in 2010 and did postdoctoral work in the Dept. of Mathematics at the University of California, Davis from 2010-2013. His main research interests are in mathematical optimization and its applications, with an emphasis on problems with a combinatorial or discrete flavor. He serves on the editorial boards of Mathematics of Operations Research, Mathematical Programming, SIAM Journal on Optimization and the MOS-SIAM Series on Optimization. His work has been recognized by the NSF Career award and the Egon Balas Prize from the INFORMS Optimization Society.