We provide a complete classification of the extreme rays of the $6 \times 6$ copositive cone ${\cal COP}^6$. We proceed via a coarse intermediate classification of the possible minimal zero support set of an exceptional extremal matrix $A \in {\cal COP}^6$. To each such minimal zero support set we construct a stratified semi-algebraic manifold in … Read more
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show … Read more
In this paper, we solve a class of two-stage distributionally robust optimization problems which have the property of supermodularity. We exploit the explicit upper bounds on the expectation of supermodular functions and derive the worst-case distribution for the robust counterpart. This enables us to develop an efficient method to derive an exact optimal solution of … Read more
Among many approaches to increase the computational efficiency of semidefinite programming (SDP) relaxation for quadratic constrained quadratic programming problems (QCQPs), exploiting the aggregate sparsity of the data matrices in the SDP by Fukuda et al. (2001) and second-order cone programming (SOCP) relaxation have been popular. In this paper, we exploit the aggregate sparsity of SOCP … Read more
The minimum cut problem, MC, and the special case of the vertex separator problem, consists in partitioning the set of nodes of a graph G into k subsets of given sizes in order to minimize the number of edges cut after removing the k-th set. Previous work on this topic uses eigenvalue, semidefinite programming, SDP, … Read more
A fundamental problem arising in many areas of machine learning is the evaluation of the likelihood of a given observation under different nominal distributions. Frequently, these nominal distributions are themselves estimated from data, which makes them susceptible to estimation errors. We thus propose to replace each nominal distribution with an ambiguity set containing all distributions … Read more
Nonlinear symmetric cone programming (NSCP) generalizes important optimization problems such as nonlinear programming, nonlinear semidefinite programming and nonlinear second-order cone programming (NSOCP). In this work, we present two new optimality conditions for NSCP without constraint qualifications, which implies the Karush-Kuhn-Tucker conditions under a condition weaker than Robinson’s constraint qualification. In addition, we show the relationship … Read more
We study the problem of computing the tightest upper and lower bounds on the probability that the sum of n dependent Bernoulli random variables exceeds an integer k. Under knowledge of all pairs of bivariate distributions denoted by a complete graph, the bounds are NP-hard to compute. When the bivariate distributions are specified on a … Read more
The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two … Read more
Quantifying extra functions, herein referred to as outcome functions, over optimal solutions of an optimization problem can provide decision makers with additional information on a system. This bears more importance when the optimization problem is subject to uncertainty in input parameters. In this paper, we consider linear programming problems in which input parameters are described … Read more