semidefinite programming

On the solution of large-scale SDP problems by the modified barrier method using iterative solvers

  • Michal Kočvara
  • Michael Stingl
    • Categories Semi-definite Programming Tags , ,

    When solving large-scale semidefinite programming problems by second-order methods, the storage and factorization of the Newton matrix are the limiting factors. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable … Read more

    Solving Maximum-Entropy Sampling Problems Using Factored Masks

  • Samuel Burer
  • Jon Lee
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Semi-definite Programming Tags , , , ,

    We present a practical approach to Anstreicher and Lee’s masked spectral bound for maximum-entropy sampling, and we describe favorable results that we have obtained with a Branch-&-Bound algorithm based on our approach. By representing masks in factored form, we are able to easily satisfy a semidefiniteness constraint. Moreover, this representation allows us to restrict the … Read more

    How Far Can We Go With Primal-Dual Interior Point Methods for SDP?

  • Brian Borchers
  • Joseph Young
    • Categories Semi-definite Programming Tags ,

    Primal–dual interior point methods and the HKM method in particular have been implemented in a number of software packages for semidefinite programming. These methods have performed well in practice on small to medium sized SDP’s. However, primal–dual codes have had some trouble in solving larger problems because of the method’s storage requirements. In this paper … Read more

    Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems

  • Robert M. Freund
  • Fernando Ordóñez
  • Kim-Chuan Toh
    • Categories Semi-definite Programming Tags , ,

    We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the … Read more

    Large-scale semidefinite programs in electronic structure calculation

  • Bastiaan J. Braams
  • Mituhiro Fukuda
  • Michael L. Overton
  • Maho Nakata
  • Jerome K. Percus
  • Makoto Yamashita
  • Zhengji Zhao
    • Categories Basic Sciences Applications, Semi-definite Programming Tags , , , , ,

    Employing the variational approach having the two-body reduced density matrix (RDM) as variables to compute the ground state energies of atomic-molecular systems has been a long time dream in electronic structure theory in chemical physics/physical chemistry. Realization of the RDM approach has benefited greatly from recent developments in semidefinite programming (SDP). We present the actual … Read more

    A PTAS for the minimization of polynomials of fixed degree over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Pablo A. Parrilo
    • Categories Approximation Algorithms, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more

    Rigorous Error Bounds for the Optimal Value in Semidefinite Programming

  • D. Chaykin
  • Christian Jansson
  • Christian Keil
    • Categories Convex Optimization, Linear Programming, Semi-definite Programming Tags , , , , , ,

    A wide variety of problems in global optimization, combinatorial optimization as well as systems and control theory can be solved by using linear and semidefinite programming. Sometimes, due to the use of floating point arithmetic in combination with ill-conditioning and degeneracy, erroneous results may be produced. The purpose of this article is to show how … Read more

    Two-Stage Stochastic Semidefinite Programming and Decomposition Based Interior Point Methods

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Semi-definite Programming, Stochastic Programming Tags , , ,

    We introduce two-stage stochastic semidefinite programs with recourse and present a Benders decomposition based linearly convergent interior point algorithms to solve them. This extends the results of Zhao, who showed that the logarithmic barrier associated with the recourse function of two-stage stochastic linear programs with recourse behaves as a strongly self-concordant barrier on the first … Read more

    On generalized branching methods for mixed integer programming

  • Zhifeng Li
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , ,

    In this paper we present a restructuring of the computations in Lenstra’s methods for solving mixed integer linear programs. We show that the problem of finding a good branching hyperplane can be formulated on an adjoint lattice of the Kernel lattice of the equality constraints without requiring any dimension reduction. As a consequence the short … Read more

    Finding good nearly balanced cuts in power law graphs

  • Kevin Lang
    • Categories Graphs and Matroids Tags , , , , ,

    In power law graphs, cut quality varies inversely with cut balance. Using some million node social graphs as a test bed, we empirically investigate this property and its implications for graph partitioning. We use six algorithms, including Metis and MQI (state of the art methods for finding bisections and quotient cuts) and four relaxation/rounding methods. … Read more