We describe a computationally effective method for generating disjunctive inequalities for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs, and in the limit will generate an inequality as strong as can be produced by the cut-generating nonlinear program suggested by Stubbs and Mehrotra. Using this procedure, we … Read more
Proportional symbol maps are a cartographic tool to assist in the visualization and analysis of quantitative data associated with specific locations, such as earthquake magnitudes, oil well production, and temperature at weather stations. As the name suggests, symbol sizes are proportional to the magnitude of the physical quantities that they represent. We present two novel … Read more
We present two algorithms to solve the Group Lasso problem [Yuan & Lin]. First, we propose a general version of the Block Coordinate Descent (BCD) algorithm for the Group Lasso that employs an efficient approach for optimizing each subproblem. We show that it exhibits excellent performance when the groups are of moderate sizes. For large … Read more
We propose an approach to the timing of markdowns over a finite time horizon that does not require the precise knowledge of the underlying probabilities, instead relying on range forecasts for the arrival rates of the demand processes, and that captures the degree of the manager’s risk aversion through intuitive budget-of-uncertainty functions. These budget functions … Read more
Grothendieck inequalities are fundamental inequalities which are frequently used in many areas of mathematics and computer science. They can be interpreted as upper bounds for the integrality gap between two optimization problems: A difficult semidefinite program with rank-1 constraint and its easy semidefinite relaxation where the rank constrained is dropped. For instance, the integrality gap … Read more
We propose a convex optimization formulation with the nuclear norm and $\ell_1$-norm to find a large approximately rank-one submatrix of a given nonnegative matrix. We develop optimality conditions for the formulation and characterize the properties of the optimal solutions. We establish conditions under which the optimal solution of the convex formulation has a specific sparse … Read more
Minimization with orthogonality constraints (e.g., $X^\top X = I$) and/or spherical constraints (e.g., $\|x\|_2 = 1$) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. … Read more
The question as to whether the Gomory-Chvatal closure of a non-rational polytope is a polytope has been a longstanding open problem in integer programming. In this paper, we answer this question in the affirmative, by combining ideas from polyhedral theory and the geometry of numbers. ArticleDownload View PDF
We consider in this paper quadratic programming problems with cardinality and minimum threshold constraints which arise naturally in various real-world applications such as portfolio selection and subset selection in regression. We propose a new semidefinite program (SDP) approach for computing the “best” diagonal decomposition that gives the tightest continuous relaxation of the perspective reformulation. We … Read more
In this paper, we show that the Chatal-Gomory closure of a compact convex set is a rational polytope. This resolves an open question discussed in Schrijver 1980 and generalizes the same result for the case of rational polytopes (Schrijver 1980), rational ellipsoids (Dey and Vielma 2010) and strictly convex sets (Dadush et. al 2010). In … Read more