Semi-definite Programming

A Computational Study of a Gradient-Based Log-Barrier Algorithm for a Class of Large-Scale SDPs

  • Samuel Burer
  • Renato D.C. Monteiro
  • Yin Zhang
    • Categories Combinatorial Optimization, Semi-definite Programming, Unconstrained Optimization Tags , , , ,

    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

    New Results on Quadratic Minimization

  • Yinyu Ye
  • Shuzhong Zhang
    • Categories Quadratic Programming, Semi-definite Programming Tags , ,

    In this paper we present several new results on minimizing an indefinite quadratic function under quadratic/linear constraints. The emphasis is placed on the case where the constraints are two quadratic inequalities. This formulation is known as {\em the extended trust region subproblem}\/ and the computational complexity of this problem is still unknown. We consider several … Read more

    Solving standard quadratic optimization problems via linear, semidefinite and copositive programming

  • Immanuel M. Bomze
  • Etienne de Klerk
    • Categories Combinatorial Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    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

    A Linear Programming Approach to Semidefinite Programming Problems

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Combinatorial Optimization, Linear Programming, Semi-definite Programming Tags , , , , ,

    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

    Avoiding numerical cancellation in the interior point method for solving semidefinite programs

  • Jos F. Sturm
    • Categories Semi-definite Programming Tags

    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

    Analyticity of the central path at the boundary point in semidefinite programming

  • Margaréta Halická
    • Categories Semi-definite Programming Tags , ,

    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 barriers for irreducible symmetric cones

  • Raphael Hauser
  • Yongdo Lim
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    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

    Lagrangian dual interior-point methods for semidefinite programs

  • Mituhiro Fukuda
  • Masakazu Kojima
  • Masayuki Shida
    • Categories Convex Optimization, Second-Order Cone Programming, Semi-definite Programming Tags , , , , , , , ,

    This paper proposes a new predictor-corrector interior-point method for a class of semidefinite programs, which numerically traces the central trajectory in a space of Lagrange multipliers. The distinguished features of the method are full use of the BFGS quasi-Newton method in the corrector procedure and an application of the conjugate gradient method with an effective … Read more

    Implementation Issues in CSDP

  • Brian Borchers
    • Categories Semi-definite Programming Tags ,

    CSDP is a software package that implements the XZ primal–dual interior point method for semidefinite programming. In this method there are a number of computationally intensive steps including the construction of the Schur complement matrix $O$, the factorization of $O$, multiplications of matrices of size $n$ and Cholesky factorizations of matrices of size $n$. Profiling … Read more

    A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-rank Factorization

  • Samuel Burer
    • Categories Semi-definite Programming Tags , ,

    In this paper, we present a nonlinear programming algorithm for solving semidefinite programs (SDPs) in standard form. The algorithm’s distinguishing feature is a change of variables that replaces the symmetric, positive semidefinite variable X of the SDP with a rectangular variable R according to the factorization X = RR^T. The rank of the factorization, i.e., … Read more