In optimization-based classification model selection, for example when using linear programming formulations, a standard approach is to penalize the L1 norm of some linear functional in order to select sparse models. Instead, we propose a novel integer linear program for sparse classifier selection, generalizing the minimum disagreement hyperplane problem whose complexity has been investigated in … Read more
We show that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list here includes: determining the feasibility of a system of bilinear equations, deciding whether a tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or spectral norm; determining a best … Read more
The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into sub-windows, which we call “buckets”. We … Read more
Facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial ([3]) removes unnecessary monomials for an SOS representation. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial. CitationTechnical Report CS-09-02, Department of … Read more
We present a branching scheme for some Vertex Coloring Problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as the graph multicoloring, where each vertex requires a multiplicity of colors, … Read more
In this article we propose an algorithm, NESTA-LASSO, for the LASSO problem (i.e., an underdetermined linear least-squares problem with a one-norm constraint on the solution) that exhibits linear convergence under the restricted isometry property (RIP) and some other reasonable assumptions. Inspired by the state-of-the-art sparse recovery method, NESTA, we rely on an accelerated proximal gradient … Read more
We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize the total weight of their winning sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item for possible inclusion … Read more
The problem of recovering the sparse and low-rank components of a matrix captures a broad spectrum of applications. Authors in [4] proposed the concept of “rank-sparsity incoherence” to characterize the fundamental identifiability of the recovery, and derived practical sufficient conditions to ensure the high possibility of recovery. This exact recovery is achieved via solving a … Read more
Probabilistic or Stochastic programming is a framework for modeling optimization problems that involve uncertainty. The basic idea used in solving stochastic optimization problems has so far been to convert a stochastic model into an equivalent deterministic model and is possible when the right hand side resource vector follows some specific distributions such as normal, lognormal … Read more
Several types of relaxations for binary quadratic polynomial programs can be obtained using linear, second-order cone, or semidefinite techniques. In this paper, we propose a general framework to construct conic relaxations for binary quadratic polynomial programs based on polynomial programming. Using our framework, we re-derive previous relaxation schemes and provide new ones. In particular, we … Read more