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
We study a cutting-plane method for semidefinite optimization problems (SDOs), and supply a proof of the method’s convergence, under a boundedness assumption. By relating the method’s rate of convergence to an initial outer approximation’s diameter, we argue that the method performs well when initialized with a second-order-cone approximation, instead of a linear approximation. We invoke … Read more
A convex form of degree larger than one is always nonnegative since it vanishes together with its gradient at the origin. In 2007, Parrilo asked if convex forms are always sums of squares. A few years later, Blekherman answered the question in the negative by showing through volume arguments that for high enough number of … Read more