Compressed Sensing: A Discrete Optimization Approach

We study the Compressed Sensing (CS) problem, which is the problem of finding the most sparse vector that satisfies a set of linear measurements up to some numerical tolerance. CS is a central problem in Statistics, Operations Research and Machine Learning which arises in applications such as signal processing, data compression and image reconstruction. We … Read more

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 into a sparse matrix of perturbations plus a low-rank matrix containing the ground truth. SLR is a fundamental problem in Operations Research and Machine Learning which arises in various applications, including data compression, latent semantic indexing, … Read more

Efficient Joint Object Matching via Linear Programming

Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task in many areas of computer vision. This problem subsumes bipartite graph matching and graph partitioning as special cases and is NP-hard, in general. We develop scalable linear … Read more

On Piecewise Linear Approximations of Bilinear Terms: Structural Comparison of Univariate and Bivariate Mixed-Integer Programming Formulations

Bilinear terms naturally appear in many optimization problems. Their inherent nonconvexity typically makes them challenging to solve. One approach to tackle this difficulty is to use bivariate piecewise linear approximations for each variable product, which can be represented via mixed-integer linear programming (MIP) formulations. Alternatively, one can reformulate the variable products as a sum of … Read more

An Alternative Perspective on Copositive and Convex Relaxations of Nonconvex Quadratic Programs

We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family … Read more

A Polynomial-time Algorithm with Tight Error Bounds for Single-period Unit Commitment Problem

This paper proposes a Lagrangian dual based polynomial-time approximation algorithm for solving the single-period unit commitment problem, which can be formulated as a mixed integer quadratic programming problem and proven to be NP-hard. Tight theoretical bounds for the absolute errors and relative errors of the approximate solutions generated by the proposed algorithm are provided. Computational … Read more

Dual-density-based reweighted $\ell_{1}hBcalgorithms for a class of $\ell_{0}hBcminimization problems

The optimization problem with sparsity arises in many areas of science and engineering such as compressed sensing, image processing, statistical learning and data sparse approximation. In this paper, we study the dual-density-based reweighted $\ell_{1}$-algorithms for a class of $\ell_{0}$-minimization models which can be used to model a wide range of practical problems. This class of … Read more

Solving Heated Oil Pipeline Problems Via Mixed Integer Nonlinear Programming Approach

It is a crucial problem how to heat oil and save running cost for crude oil transport. This paper strictly formulates such a heated oil pipeline problem as a mixed integer nonlinear programming model. Nonconvex and convex continuous relaxations of the model are proposed, which are proved to be equivalent under some suitable conditions. Meanwhile, … Read more

A convex relaxation to compute the nearest structured rank deficient matrix

Given an affine space of matrices L and a matrix \theta in L, consider the problem of finding the closest rank deficient matrix to \theta on L with respect to the Frobenius norm. This is a nonconvex problem with several applications in estimation problems. We introduce a novel semidefinite programming (SDP) relaxation, and we show … Read more

Tightening McCormick Relaxations Toward Global Solution of the ACOPF Problem

We show that a strong upper bound on the objective of the alternating current optimal power flow (ACOPF) problem can significantly improve the effectiveness of optimization-based bounds tightening (OBBT) on a number of relaxations. We additionally compare the performance of relaxations of the ACOPF problem, including the rectangular form without reference bus constraints, the rectangular … Read more