We describe a classof measures on second-order cones as a push-forward of the Cartesian product of a probabilistic measure on positive semi-line corresponding to Gamma distribution and the uniform measure on the sphere Citation report, Department of Mathematics, University of Notre Dame, July, 2011 Article Download View Sampling with respect to a class of measures … Read more
We derive a new semidefinite programming relaxation for the general graph partition problem (GPP). Our relaxation is based on matrix lifting with matrix variable having order equal to the number of vertices of the graph. We show that this relaxation is equivalent to the Frieze-Jerrum relaxation [A. Frieze and M. Jerrum. Improved approximation algorithms for … Read more
Consider a homogeneous multifold convex conic system $$ Ax = 0, \; x\in K_1\times \cdots \times K_r $$ and its alternative system $$ A\transp y \in K_1^*\times \cdots \times K_r^*, $$ where $K_1,\dots, K_r$ are regular closed convex cones. We show that there is canonical partition of the index set $\{1,\dots,r\}$ determined by certain complementarity … Read more
Kitahara and Mizuno get upper bounds for the maximum number of different basic feasible solutions generated by Dantzig�s simplex method. In this paper, we obtain lower bounds of the maximum number. Part of the results in this paper are shown in a paper by the authors as a quick report without proof. They present a … Read more
The problem of finding a minimum l^1-norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit. We propose a heuristic optimality check as a general tool for l^1-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an … Read more
We show that any nonconvex quadratically constrained quadratic program(QCQP) can be represented as a generalized copositive program. In fact,we provide two representations. The first is based on the concept of completely positive (CP) matrices over second order cones, while the second is based on CP matrices over the positive semidefinte cone. Our analysis assumes that … Read more
The rank function $\rank(\cdot)$ is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of $\rank(\cdot)$, and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the … Read more
Examples of weakly infeasible semidefinite programs are useful to test whether semidefinite solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre’s semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible semidefinite programs. Such examples could be used to test … Read more
We show that the simplex method can be interpreted as a cutting-plane method, assumed that a special pricing rule is used. This approach is motivated by the recent success of the cutting-plane method in the solution of special stochastic programming problems. We compare the classic Dantzig pricing rule and the rule that derives from the … Read more
In the paper we prove that any nonconvex quadratic problem over some set $K\subset \mathbb{R}^n$ with additional linear and binary constraints can be rewritten as linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and … Read more