Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExact semidefinite programming bounds for packing problems
181
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we give an algorithm to round the floating point output of a semidefinite programming solver to a solution over the rationals or a quadratic extension of the rationals. We apply this to get sharp bounds for packing problems, and we use these sharp bounds to prove that certain optimal packing configurations are unique up to rotations. In particular, we show that the configuration coming from the $mathsf{E}_8$ root lattice is the unique optimal code with minimal angular distance $pi/3$ on the hemisphere in $mathbb R^8$, and we prove that the three-point bound for the $(3, 8, vartheta)$-spherical code, where $vartheta$ is such that $cos vartheta = (2sqrt{2}-1)/7$, is sharp by rounding to $mathbb Q[sqrt{2}]$. We also use our machinery to compute sharp upper bounds on the number of spheres that can be packed into a larger sphere.
rate research
Read More
The average kissing number of $mathbb{R}^n$ is the supremum of the average degrees of contact graphs of packings of finitely many balls (of any radii) in $mathbb{R}^n$. We provide an upper bound for the average kissing number based on semidefinite programming that improves previous bounds in dimensions $3, ldots, 9$. A very simple upper bound for the average kissing number is twice the kissing number; in dimensions $6, ldots, 9$ our new bound is the first to improve on this simple upper bound.
In this paper, we show that the bundle method can be applied to solve semidefinite programming problems with a low rank solution without ever constructing a full matrix. To accomplish this, we use recent results from randomly sketching matrix optimization problems and from the analysis of bundle methods. Under strong duality and strict complementarity of SDP, our algorithm produces primal and the dual sequences converging in feasibility at a rate of $tilde{O}(1/epsilon)$ and in optimality at a rate of $tilde{O}(1/epsilon^2)$. Moreover, our algorithm outputs a low rank representation of its approximate solution with distance to the optimal solution at most $O(sqrt{epsilon})$ within $tilde{O}(1/epsilon^2)$ iterations.
In this paper we examine a symmetric tensor decomposition problem, the Gramian decomposition, posed as a rank minimization problem. We study the relaxation of the problem and consider cases when the relaxed solution is a solution to the original problem. In some instances of tensor rank and order, we prove generically that the solution to the relaxation will be optimal in the original. In other cases, we present interesting examples and approaches that demonstrate the intricacy of this problem.
We propose an algorithm for solving nonlinear convex programs defined in terms of a symmetric positive semidefinite matrix variable $X$. This algorithm rests on the factorization $X=Y Y^T$, where the number of columns of Y fixes the rank of $X$. It is thus very effective for solving programs that have a low rank solution. The factorization $X=Y Y^T$ evokes a reformulation of the original problem as an optimization on a particular quotient manifold. The present paper discusses the geometry of that manifold and derives a second order optimization method. It furthermore provides some conditions on the rank of the factorization to ensure equivalence with the original problem. The efficiency of the proposed algorithm is illustrated on two applications: the maximal cut of a graph and the sparse principal component analysis problem.
We obtain new restrictions on the linear programming bound for sphere packing, by optimizing over spaces of modular forms to produce feasible points in the dual linear program. In contrast to the situation in dimensions 8 and 24, where the linear programming bound is sharp, we show that it comes nowhere near the best packing densities known in dimensions 12, 16, 20, 28, and 32. More generally, we provide a systematic technique for proving separations of this sort.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
