In this paper we consider approximation algorithms for a class of quadratic optimization problems that contain orthogonality constraints, i.e. constraints of the form $X^TX=I$, where $X \in {\mathbb R}^{m \times n}$ is the optimization variable. Such class of problems, which we denote by (QP-OC), is quite general and captures several well–studied problems in the literature … Read more
We examine the local convergence of a sequential semidefinite programming approach for solving nonlinear programs with nonlinear semidefiniteness constraints. Known convergence results are extended to slightly weaker second order sufficient conditions and the resulting subproblems are shown to have local convexity properties that imply a weak form of self-concordance of the barrier subproblems. Citation Preprint, … Read more
We present semidefinite relaxations of nonconvex, box-constrained quadratic programming, which incorporate the first- and second-order necessary optimality conditions. We compare these relaxations with a basic semidefinite relaxation due to Shor, particularly in the context of branch-and-bound to determine a global optimal solution, where it is shown empirically that the new relaxations are significantly stronger. We … Read more
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
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
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
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
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
The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension $d$ for … Read more
We describe a major update of our Matlab freeware GloptiPoly for parsing generalized problems of moments and solving them numerically with semidefinite programming. Citation 28 June 2007 Article Download View GloptiPoly 3: moments, optimization and semidefinite programming