Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach

We study the Sparse Plus Low Rank decomposition problem (SLR), which is the problem of decomposing a corrupted data matrix D into a sparse matrix Y containing the perturbations plus a low rank matrix X. SLR is a fundamental problem in Operations Research and Machine Learning arising in many applications such as data compression, latent … Read more

A new perspective on low-rank optimization

A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable convex relaxations. We invoke the matrix perspective function — the matrix analog of the perspective function — and characterize explicitly … Read more

Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints

We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy $Y^2 = Y$, the matrix analog of binary variables that satisfy $z^2 = z$, to model rank constraints. By leveraging regularization and strong duality, we prove that this modeling paradigm yields tractable convex optimization … Read more

Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality

Sparse principal component analysis (PCA) is a popular dimensionality reduction technique for obtaining principal components which are linear combinations of a small subset of the original features. Existing approaches cannot supply certifiably optimal principal components with more than $p=100s$ of variables. By reformulating sparse PCA as a convex mixed-integer semidefinite optimization problem, we design a … Read more

On Polyhedral and Second-Order-Cone Decompositions of Semidefinite Optimization Problems

We study a cutting-plane method for semidefinite optimization problems (SDOs), and supply a proof of the method’s convergence, under a boundedness assumption. By relating the method’s rate of convergence to an initial outer approximation’s diameter, we argue that the method performs well when initialized with a second-order-cone approximation, instead of a linear approximation. We invoke … Read more

A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints

We propose a unified framework to address a family of classical mixed-integer optimization problems with logically constrained decision variables, including network design, facility location, unit commitment, sparse portfolio selection, binary quadratic optimization, sparse principal component analysis and sparse learning problems. These problems exhibit logical relationships between continuous and discrete variables, which are usually reformulated linearly … Read more

A Scalable Algorithm for Sparse Portfolio Selection

The sparse portfolio selection problem is one of the most famous and frequently-studied problems in the optimization and financial economics literatures. In a universe of risky assets, the goal is to construct a portfolio with maximal expected return and minimum variance, subject to an upper bound on the number of positions, linear inequalities and minimum … Read more

On stochastic auctions in risk-averse electricity markets with uncertain supply

This paper studies risk in a stochastic auction which facilitates the integration of renewable generation in electricity markets. We model market participants who are risk averse and reflect their risk aversion through coherent risk measures. We uncover a closed-form characterization of a risk-averse generator’s optimal pre-commitment behaviour for a given real-time policy, both with and … Read more

Payment Mechanisms for Electricity Markets with Uncertain Supply

This paper provides a framework for deriving payment mechanisms for intermittent, flexible and inflexible electricity generators who are dispatched according to the optimal solution of a stochastic program that minimizes the expected cost of generation plus deviation. The first stage corresponds to a pre-commitment decision, and the second stage corresponds to real-time generation that adapts … Read more