The central path in linear optimization always converges to the analytic center of the optimal set. This result was extended to semidefinite programming by Goldfarb and Scheinberg (SIAM J. Optim. 8: 871-886, 1998). In this paper we show that this latter result is not correct in the absence of strict complementarity. We provide a counterexample, … Read more
Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and … Read more
We study the asymptotic behavior of the interior-point bounds arising from the work of Yildirim and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. For perturbations of the right-hand side vector and the cost matrix, we show that the interior-point bounds evaluated on the central path using the Monteiro-Zhang … Read more
The authors of this paper recently introduced a transformation \cite{BuMoZh99-1} that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based … Read more
The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities … Read more
Until recently, the study of interior point methods has dominated algorithmic research in semidefinite programming (SDP). From a theoretical point of view, these interior point methods offer everything one can hope for; they apply to all SDP’s, exploit second order information and offer polynomial time complexity. Still for practical applications with many constraints $k$, the … Read more
We derive LMI-characterizations and dual decomposition algorithms for certain matrix cones which are generated by a given set using generalized co-positivity. These matrix cones are in fact cones of non-convex quadratic functions that are nonnegative on a certain domain. As a domain, we consider for instance the intersection of a (upper) level-set of a quadratic … Read more
The matrix variables in a primal-dual pair of semidefinite programs are getting increasingly ill-conditioned as they approach a complementary solution. Multiplying the primal matrix variable with a vector from the eigenspace of the non-basic part will therefore result in heavy numerical cancellation. This effect is amplified by the scaling operation in interior point methods. In … Read more
In this paper we study the limiting behavior of the central path for semidefinite programming. We show that the central path is an analytic function of the barrier parameter even at the limit point, provided that the semidefinite program has a strictly complementary solution. A consequence of this property is that the derivatives – of … Read more
Self-scaled barrier functions are fundamental objects in the theory of interior-point methods for linear optimization over symmetric cones, of which linear and semidefinite programming are special cases. We are classifying all self-scaled barriers over irreducible symmetric cones and show that these functions are merely homothetic transformations of the universal barrier function. Together with a decomposition … Read more