In this paper, we study the sparse integer least squares problem (SILS), an NP-hard variant of least squares with sparse {0, 1, -1}-vectors. We propose an l1-based SDP relaxation, and a randomized algorithm for SILS, which computes feasible solutions with high probability with an asymptotic approximation ratio 1/T^2 as long as the sparsity constant σ … Read more
Currently, the simplex method and the interior point method are indisputably the most popular algorithms for solving linear programs, LPs. Unlike general conic programs, LPs with a finite optimal value do not require strict feasibility in order to establish strong duality. Hence strict feasibility is seldom a concern, even though strict feasibility is equivalent to … Read more
We study the computational complexity of the optimal transport problem that evaluates the Wasserstein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in the maximum of the number of atoms of the two distributions. However, if the components of either random vector … Read more
We consider the NP-hard problem of approximating a tensor with binary entries by a rank-one tensor, referred to as rank-one Boolean tensor factorization problem. We formulate this problem, in an extended space of variables, as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the … Read more
Semidefinite programming (SDP) problems typically utilize the constraint that X-xx’ is PSD to obtain a convex relaxation of the condition X=xx’, where x is an n-vector. In this paper we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xx’. This branching technique is related to previous work of Saxeena, … Read more
In this paper we study the well-known Chvátal-Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of … Read more
We propose an algorithm for computing the projection of a symmetric second-order tensor onto the cone of negative semidefinite symmetric tensors with respect to the inner product defined by an assigned positive definite symmetric fourth-order tensor C. The projection problem is written as a semidefinite programming problem and an algorithm based on a primal-dual path-following … Read more
In this paper, we present a polynomial-time barrier algorithm for solving multi-stage stochastic convex semidefinite optimization based on the Lagrangian dual method which relaxes the nonanticipativity constraints. We show that the barrier Lagrangian dual functions for our setting form self-concordant families with respect to barrier parameters. We also use the barrier function method to improve … Read more
A novel approach based on a specialized interior-point method (IPM) is presented for solving large-scale stochastic multistage continuous optimization problems, which represent the uncertainty in strategic multistage and operational two-stage scenario trees, the latter being rooted at the strategic nodes. This new solution approach considers a split-variable formulation of the strategic and operational structures, for … Read more
We introduce the hub network design problem with congestion, capacity, and stochastic demand considerations (HNDC), which generalizes the classical hub location problem in several directions. In particular, we extend state-of-the-art by integrating capacity acquisition decision and congestion cost effect into the problem and allowing dynamic routing for origin-destination pairs. Connecting strategic and operational level decisions, … Read more