In this paper we propose and analyze inexact and stochastic versions of the CGALP algorithm developed in the authors’ previous paper, which we denote ICGALP, that allows for errors in the computation of several important quantities. In particular this allows one to compute some gradients, proximal terms, and/or linear minimization oracles in an inexact fashion … Read more
This paper focuses on the parametric analysis of a conic linear optimization problem with respect to the perturbation of the objective function along many fixed directions. We introduce the concept of the primal and dual conic linear inequality representable sets, which is very helpful for converting the correlation of the parametric conic linear optimization problems … Read more
Many convex optimization problems can be represented through conic extended formulations with auxiliary variables and constraints using only the small number of standard cones recognized by advanced conic solvers such as MOSEK 9. Such extended formulations are often significantly larger and more complex than equivalent conic natural formulations, which can use a much broader class … Read more
Optimal matrices for problems involving the matrix numerical radius often have fields of values that are disks, a phenomenon associated with partial smoothness. Such matrices are highly structured: we experiment in particular with the proximal mapping for the radius, which often maps n-by-n random matrix inputs into a particular manifold of disk matrices that has … Read more
In this paper, we consider binary quadratically constrained quadratic problems and propose a new approach to generate stronger bounds than the ones obtained using the Semidefinite Programming relaxation. The new relaxation is based on the Boolean Quadric Polytope and is solved via a Dantzig-Wolfe Reformulation in matrix space. For block-decomposable problems, we extend the relaxation … Read more
In this paper, we study the convex quadratic optimization problem with indicator variables. For the bivariate case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the bivariate case as a building block, we derive … Read more
It is well known that the convex hull of {(x,y,xy)}, where (x,y) is constrained to lie in a box, is given by the Reformulation-Linearization Technique (RLT) constraints. Belotti et al. (2010) and Miller et al. (2011) showed that if there are additional upper and/or lower bounds on the product z=xy, then the convex hull can … Read more
We consider the least squares regression problem, penalized with a combination of the L0 and L2 norms (a.k.a. L0 L2 regularization). Recent work presents strong evidence that the resulting L0-based estimators can outperform popular sparse learning methods, under many important high-dimensional settings. However, exact computation of L0-based estimators remains a major challenge. Indeed, state-of-the-art mixed … Read more
Two-stage stochastic models give rise to very large optimization problems. Several approaches have been devised for efficiently solving them, including interior-point methods (IPMs). However, using IPMs, the linking columns associated to first-stage decisions cause excessive fill-in for the solution of the normal equations. This downside is usually alleviated if variable splitting is applied to first-stage … Read more
We consider the problem of fitting a polynomial function to a set of data points, each data point consisting of a feature vector and a response variable. In contrast to standard polynomial regression, we require that the polynomial regressor satisfy shape constraints, such as monotonicity, Lipschitz-continuity, or convexity. We show how to use semidefinite programming … Read more