This document is an introduction to the Matlab package SDLS (Semi-Definite Least-Squares) for solving least-squares problems over convex symmetric cones. The package is shortly presented through the addressed problem, a sketch of the implemented algorithm, the syntax and calling sequences, a simple numerical example and some more advanced features. The implemented method consists in solving … Read more
A new method for the efficient solution of free material optimization problems is introduced. The method extends the sequential convex programming (SCP) concept to a class of optimization problems with matrix variables. The basic idea of the new method is to approximate the original optimization problem by a sequence of subproblems, in which nonlinear functions … Read more
Traditionally, optimality and uniqueness of an (n,N,t) spherical code is proved using linear programming bounds. However, this approach does not apply to the parameter (4,10,1/6). We use semidefinite programming bounds instead to show that the Petersen code (which are the vertices of the 4-dimensional second hypersimplex or the midpoints of the edges of the regular … Read more
We consider the classical problem of estimating a density on $[0,1]$ via some maximum entropy criterion. For solving this convex optimization problem with algorithms using first-order or second-order methods, at each iteration one has to compute (or at least approximate) moments of some measure with a density on $[0,1]$, to obtain gradient and Hessian data. … Read more
Let L_n be the n-dimensional second order cone. A linear map from R^m to R^n is called positive if the image of L_m under this map is contained in L_n. For any pair (n,m) of dimensions, the set of positive maps forms a convex cone. We construct a linear matrix inequality of size (n-1)(m-1) that … Read more
The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution of this paper is the design and implementation of a branch-and-cut algorithm based on semidefinite … Read more
This paper is a tutorial in a general and explicit procedure to simplify semidefinite programming problems which are invariant under the action of a group. The procedure is based on basic notions of representation theory of finite groups. As an example we derive the block diagonalization of the Terwilliger algebra in this framework. Here its … Read more
The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, … Read more
Let $S =\{x\in \re^n:\, g_1(x)\geq 0, \cdots, g_m(x)\geq 0\}$ be a semialgebraic set defined by multivariate polynomials $g_i(x)$. Assume $S$ is convex, compact and has nonempty interior. Let $S_i =\{x\in \re^n:\, g_i(x)\geq 0\}$, and $\bdS$ (resp. $\bdS_i$) be the boundary of $S$ (resp. $S_i$). This paper, as does the subject of semidefinite programming (SDP), concerns … Read more
We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB – a quadratic assignment problem … Read more