Chvatal (1980) has given a simple example of a knapsack problem for which a branch-and-bound algorithm using domination and linear relaxations to eliminate subproblems will use an exponential number of steps in the best case. In this short note it is shown that Chvatals result remains true when the LP relaxation is replaced with a … Read more
We propose a convex-optimization-based framework for computation of invariant measures of polynomial dynamical systems and Markov processes, in discrete and con- tinuous time. The set of all invariant measures is characterized as the feasible set of an infinite-dimensional linear program (LP). The objective functional of this LP is then used to single-out a specific measure … Read more
We study the problem of finding the Lowner-John ellipsoid, i.e., an ellipsoid with minimum volume that contains a given convex set. We reformulate the problem as a generalized copositive program, and use that reformulation to derive tractable semidefinite programming approximations for instances where the set is defined by affine and quadratic inequalities. We prove that, … Read more
We consider the problem of approximating numerically the moments and the supports of measures which are invariant with respect to the dynamics of continuousand discrete-time polynomial systems, under semialgebraic set constraints. First, we address the problem of approximating the density and hence the support of an invariant measure which is absolutely continuous with respect to … Read more
We study distributionally robust chance-constrained programming (DRCCP) optimization problems with data-driven Wasserstein ambiguity sets. The proposed algorithmic and reformulation framework applies to distributionally robust optimization problems subjected to individual as well as joint chance constraints, with random right-hand side and technology vector, and under two types of uncertainties, called uncertain probabilities and continuum of realizations. … Read more
This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. … Read more
In this paper, we determine the automorphism group of the p-cones (p\neq 2) in dimension greater than two. In particular, we show that the automorphism group of those p-cones are the positive scalar multiples of the generalized permutation matrices that fix the main axis of the cone. Next, we take a look at a problem … Read more
We study semidefinite programs (SDPs) with positive duality gaps, i.e., different optimal values in the primal and dual problems. the primal and dual problems differ. These SDPs are considered extremely pathological, they are often unsolvable, and they also serve as models of more general pathological convex programs. We first fully characterize two variable SDPs with … Read more
The MaxCut SDP is one of the most well-known semidefinite programs, and it has many favorable properties. One of its nicest geometric/duality properties is the fact that the vertices of its feasible region correspond exactly to the cuts of a graph, as proved by Laurent and Poljak in 1995. Recall that a boundary point x … Read more
In this paper, we propose a new framework to implement interior point method (IPM) in order to solve some very large scale linear programs (LP). Traditional IPMs typically use Newton’s method to approximately solve a subproblem that aims to minimize a log-barrier penalty function at each iteration. Due its connection to Newton’s method, IPM is … Read more