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.Ph.D