Semi-definite Programming

A semidefinite programming heuristic for quadratic programming problems with complementarity constraints

  • Stephen E. Braun
  • John E. Mitchell
    • Categories Complementarity and Variational Inequalities, Finance and Economics, Semi-definite Programming Tags , ,

    The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these … Read more

    Quadratic Convergence of a Squared Smoothing Newton Method for Nonsmooth Matrix Equations and Its Applications in Semidefinite Optimization Problems

  • Liqun Qi
  • Jie Sun
  • Defeng Sun
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Semi-definite Programming Tags ,

    We study a smoothing Newton method for solving a nonsmooth matrix equation that includes semidefinite programming and the semidefinte complementarity problem as special cases. This method, if specialized for solving semidefinite programs, needs to solve only one linear system per iteration and achieves quadratic convergence under strict complementarity. We also establish quadratic convergence of this … Read more

    A unifying framework for several cutting plane algorithms for semidefinite programming

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Nonsmooth Optimization, Semi-definite Programming, Semi-infinite Programming Tags , , ,

    Cutting plane methods provide the means to solve large scale semidefinite programs (SDP) cheaply and quickly. They can also conceivably be employed for the purposes of re-optimization after branching, or the addition of cutting planes. We give a survey of various cutting plane approaches for SDP in this paper. These cutting plane approaches arise from … Read more

    A Conic Programming Approach to Generalized Tchebycheff Inequalities

  • Javier F. Peña
  • Luis F. Zuluaga
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    Consider the problem of finding optimal bounds on the expected value of piece-wise polynomials over all measures with a given set of moments. We show that this problem can be studied within the framework of conic programming. Relying on a key approximation result for conic programming, we show that these bounds can be numerically computed … Read more

    SDPARA : SemiDefinite Programming Algorithm PARAllel Version

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , , ,

    Abstract: The SDPA (SemiDefinite Programming Algorithm) is known as efficient computer software based on primal-dual interior-point method for solving SDPs (Semidefinite Programs). In many applications, however, some SDPs become larger and larger, too large for the SDPA to solve on a single processor. In execution of the SDPA applied to large scale SDPs, the computation … Read more

    Semidefinite optimization, a spectral approach

  • M.A. van Bossum
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , , , , , ,

    This thesis is about mathematical optimization. Mathematical optimization involves the construction of methods to solve optimization problems, which can arise from real-life problems in applied science, when they are mathematically modeled. Examples come from electrical design, engineering, control theory, telecommunication, environment, finance, and logistics. This thesis deals especially with semidefinite optimization problems. Semidefinite programming is … Read more

    Implementation and Evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , , ,

    The SDPA (SemiDefinite Programming Algorithm) is a software package for solving general SDPs(SemiDefinite Programs). It is written in C++ with the help of {\it LAPACK} for numerical linear algebra for dense matrix computation. The purpose of this paper is to present a brief description of the latest version of the SDPA and its high performance … Read more

    The Trust Region Subproblem and Semidefinite Programming

  • Charles Fortin
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming, Unconstrained Optimization Tags , , ,

    The trust region subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g. function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it determines the step in trust region algorithms for function minimization. Trust region algorithms are popular for … Read more

    A Simplified/Improved HKM Direction for Certain Classes of Semidefinite Programming

  • Franz Rendl
  • Renata Sotirov
  • Henry Wolkowicz
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

    Semidefinite Programming (SDP) provides strong bounds for many NP-hard combinatorial problems. Arguably the most popular/efficient search direction for solving SDPs using a primal-dual interior point (p-d i-p) framework is the {\em HKM direction}. This direction is a Newton direction found from the linearization of a symmetrized version of the optimality conditions. For many of the … Read more