semidefinite programming

Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets

Categories Semi-definite Programming Tags , , , , , , , , , , , ,

The article proves sufficient conditions and necessary conditions for SDP representability of convex sets and convex hulls by proposing a new approach to construct SDP representations. The contributions of this paper are: (i) For bounded SDP representable sets $W_1,\cdots,W_m$, we give an explicit construction of an SDP representation for $conv(\cup_{k=1}^mW_k)$. This provides a technique for … Read more

A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part I: Proposed Approach and Application to Semidefinite Programming

Categories Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

Motivated by recent interest in group-symmetry in semidefinite programming, we propose a numerical method for finding a finest simultaneous block-diagonalization of a finite number of matrices, or equivalently the irreducible decomposition of the generated matrix *-algebra. The method is composed of numerical-linear algebraic computations such as eigenvalue computation, and automatically makes full use of the … Read more

Regularization methods for semidefinite programming

Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , ,

This paper studies an alternative technique to interior point methods and nonlinear methods for semidefinite programming (SDP). The approach based on classical quadratic regularizations leads to an algorithm, generalizing a recent method called “boundary point method”. We study the theoretical properties of this algorithm and we show that in practice it behaves very well on … Read more

Fast Computation of Optimal Contact Forces

Categories Convex Optimization, Mechanical Engineering, Second-Order Cone Programming Tags , , ,

We consider the problem of computing the smallest contact forces, with point-contact friction model, that can hold an object in equilibrium against a known external applied force and torque. It is known that the force optimization problem (FOP) can be formulated as a semidefinite programming problem (SDP), or a second-order cone problem (SOCP), and so … Read more

Properties of a Cutting Plane Method for Semidefinite Programming

Categories Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , , ,

We analyze the properties of an interior point cutting plane algorithm that is based on a semi-infinite linear formulation of the dual semidefinite program. The cutting plane algorithm approximately solves a linear relaxation of the dual semidefinite program in every iteration and relies on a separation oracle that returns linear cutting planes. We show that … Read more

A Sequential Convex Semidefinite Programming Algorithm for Multiple-Load Free Material Optimization

Categories Mechanical Engineering, Multidisciplinary Design Optimization, Semi-definite Programming Tags , ,

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

A Branch-and-Cut Algorithm based on Semidefinite Programming for the Minimum k-Partition Problem

Categories Branch and Cut Algorithms, Semi-definite Programming Tags , ,

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

Symmetry in semidefinite programs

Categories Semi-definite Programming Tags , , ,

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

Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Categories Convex and Nonsmooth Optimization, Semi-definite Programming, Statistics Tags , , ,

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

Semidefinite Representation of Convex Sets

Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , , , , , , , , , ,

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