Collaborative Proposal: Scaling up MINLPs via Branch-and-Bound and First Order Methods with applicat
Abstract
In this project we investigate new methods and algorithms for solving large-scale mixed integer nonlinear programs (MINLPs), inspire,d by key problems arising in structured statistical learning with combinatorial structures. Indeed, many problems in statistical lea,rning can be posed as constrained optimization tasks involving both continuous and discrete variables, posing outstanding challenges, from an optimization perspective. Recent research has shown the promise of mixed integer optimization for addressing some of these,problems. However, as constrained statistical learning problems become mainstream, and datasets grow big and wide, there is an urgen,t need to create principled optimization methodology to reliably solve MINLPs that scale well and apply to more general settings. Th,is project will explore synergies across convex optimization, discrete optimization and statistical learning. In order to solve MINL,Ps at scales beyond what is currently possible, we consider the study and improvement of the branch-and-bound (BnB) paradigm. In par,ticular, the key optimization techniques that we plan to explore are: (i) Improving (and also appropriate selection of) structure-aw,are large-scale first order methods (FOMs) to solve convex relaxations at each node within a BnB framework. Such an integration of F,OM and BnB into a coherent framework could eventually help to solve MINLPs at scales much larger than what is currently possible. (i,i) Explore the effect of different formulations for MINLPs. This topic is better understood in the case of MILPs, however not much w,ork has been done in the case of MINLPs. (iii) Design techniques to exploit the underlying statistical assumptions of data for the M,INLPs arising from statistical learning applications (iv) Evaluate various critical supporting components and methodologies (such as, heuristics, branching rules, gradient screening methods, etc.) of a BnB framework, so as to dramatically improve the performance of, the final BnB algorithm.A success in this proposal is poised to lead to new methodological advances in algorithms for MINLPs. This,will consequently make significant advances in optimization theory and practice, and enrich the statistician s toolkit for principle,d computational tools that are currently lacking.Approved for Public Release
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 08, 2022
- Source ID
- N000142212665
Entities
People
- Rahul Mazumder
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy