The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both … Read more
For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact for QCQPs with bipartite graph structures. The exact optimal solutions are obtained by examining the dual SDP relaxation and the rank of the optimal solution of this dual SDP relaxation under strong duality. … Read more
In this paper, we study the sparse integer least squares problem (SILS), an NP-hard variant of least squares with sparse {0, 1, -1}-vectors. We propose an l1-based SDP relaxation, and a randomized algorithm for SILS, which computes feasible solutions with high probability with an asymptotic approximation ratio 1/T^2 as long as the sparsity constant σ … Read more
Semidefinite programming (SDP) problems typically utilize the constraint that X-xx’ is PSD to obtain a convex relaxation of the condition X=xx’, where x is an n-vector. In this paper we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xx’. This branching technique is related to previous work of Saxeena, … Read more
In this paper we study the well-known Chvátal-Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of … Read more
In this paper, we present a polynomial-time barrier algorithm for solving multi-stage stochastic convex semidefinite optimization based on the Lagrangian dual method which relaxes the nonanticipativity constraints. We show that the barrier Lagrangian dual functions for our setting form self-concordant families with respect to barrier parameters. We also use the barrier function method to improve … Read more
We propose the first computationally tractable framework to solve multi-stage stochastic optimal power flow (OPF) problems in alternating current (AC) power systems. To this end, we use recent results on dual convex semi-definite programming (SDP) relaxations of OPF problems in order to adapt the stochastic dual dynamic programming (SDDP) algorithm for problems with a Markovian … Read more
In this paper we consider the problem of finding bounds on the prices of options depending on multiple assets without assuming any underlying model on the price dynamics, but only the absence of arbitrage opportunities. We formulate this as a generalized moment problem and utilize the well-known Moment-Sum-of-Squares (SOS) hierarchy of Lasserre to obtain bounds … Read more
Separating two finite sets of points in a Euclidean space is a fundamental problem in classification. Customarily linear separation is used, but nonlinear separators such as spheres have been shown to have better performances in some tasks, such as edge detection in images. We exploit the relationships between the more general version of the spherical … Read more
De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $\alpha(G)$ of a graph $G$ and conjectured exactness at order $\alpha(G)-1$: $\vartheta^{(\alpha(G)-1)}(G)=\alpha(G)$. These bounds rely on the conic approximations $\mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $\text{COP}_n$. A difficulty in the convergence analysis of $\vartheta^{(r)}$ is the bad behaviour … Read more