Integer and Matrix Optimization: A Nonlinear Approach

Many important problems from the operations research and statistics literatures exhibit either (a) logical relations between continuous variables x and binary variables z of the form "x=0 if z=0'', or (b) rank constraints. Indeed, start-up costs in machine scheduling and financial transaction costs exhibit logical relations, while important problems such as reduced rank regression and matrix completion contain rank constraints. These constraints are commonly viewed as separate entities and studied by separate subfields—integer and global optimization respectively—who propose entirely different strategies for optimizing over them. In this thesis, we adopt a different perspective on logical and rank constraints. We interpret both constraints as purely algebraic ones: logical constraints are nonlinear constraints of the form x=z o x for x continuous and z binary (meaning z²=z), while rank constraints, Rank(X) ≤ k, are nonlinear constraints of the form X=YX intersected with a linear constraint tr(Y) ≤ k for an orthogonal projection matrix Y (meaning Y²=Y). Under this lens, we show that regularization drives the computational tractability of problems with both logical and rank constraints. The first three chapters propose a unified framework to address a class of mixed-integer problems. In numerical experiments, we establish that a general-purpose strategy that combines cutting-plane, rounding, and local search methods, solves these problems faster and at a larger scale than state-of-the-art methods. Our approach solves network design problems with 100s of nodes and provides solutions up to 40% better than the state-of-the-art; sparse portfolio selection problems with up to 3,200 securities; and sparse PCA problems with up to 5,000 covariates. The last two chapters extend this framework to model rank constraints via orthogonal projection matrices. By leveraging regularization and duality, we design outer-approximation algorithms to solve low-rank problems to certifiable optimality, compute lower bounds via their semidefinite relaxations, and provide near-optimal solutions through rounding and local search techniques. By invoking matrix perspective functions, we also propose a new class of semidefinite-representable convex relaxations for low-rank problems which outperform the popular nuclear norm penalty.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Cory-Wright, Ryan

Advisor dc:contributor.advisor

• Bertsimas, Dimitris J.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/144644

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/144644