Chance constrained programming is an effective and convenient approach to control risk in decision making under uncertainty. However, due to unknown probability distributions of random parameters, the solution obtained from a chance constrained optimization problem can be biased. In practice, instead of knowing the true distribution of a random parameter, only a series of historical … Read more
In this paper we provide a systematic way to construct the robust counterpart of a nonlinear uncertain inequality that is concave in the uncertain parameters. We use convex analysis (support functions, conjugate functions, Fenchel duality) and conic duality in order to convert the robust counterpart into an explicit and computationally tractable set of constraints. It … Read more
We show that the maximal cp-rank of $n\times n$ completely positive matrices is attained at a positive-definite matrix on the boundary of the cone of $n\times n$ completely positive matrices, thus answering a long standing question. We also show that the maximal cp-rank of $5\times 5$ matrices equals six, which proves the famous Drew-Johnson-Loewy conjecture … Read more
In this paper, we consider the $l_0$ norm minimization problem with linear equation and nonnegativity constraints. By introducing the concept of generalized $Z$-matrix for a rectangular matrix, we show that this $l_0$ norm minimization with such a kind of measurement matrices and nonnegative observations can be exactly solved via the corresponding $l_p$ ($0
This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after … Read more
We give theorems that can be used to upper bound the densities of packings of different spherical caps in the unit sphere and of translates of different convex bodies in Euclidean space. These theorems extend the linear programming bounds for packings of spherical caps and of convex bodies through the use of semidefinite programming. We … Read more
This paper describes a new approach for computing nonnegative matrix factorizations (NMFs) with linear programming. The key idea is a data-driven model for the factorization, in which the most salient features in the data are used to express the remaining features. More precisely, given a data matrix X, the algorithm identifies a matrix C that … Read more
We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction … Read more
The set of polynomials which are nonnegative over a subset of the nonnegative orthant (we call them set semidefinite) have many uses in optimization. A common example of this type of set is the set of copositive matrices, where effectively we are considering nonnegativity over the entire nonnegative orthant and we limit the polynomials to … Read more
The positive semidefinite (psd) rank of a polytope is the smallest $k$ for which the cone of $k \times k$ real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, … Read more