Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems

  • Michael J. Todd
  • Kim-Chuan Toh
  • Reha H. Tütüncü
    • Categories Semi-definite Programming Tags , , , ,

    We propose a primal-dual path-following Mehrotra-type predictor-corrector method for solving convex quadratic semidefinite programming (QSDP) problems. For the special case when the quadratic term has the form $\frac{1}{2} X \bul (UXU)$, we compute the search direction at each iteration from the Schur complement equation. We are able to solve the Schur complement equation efficiently via … Read more

    SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Global Optimization, Optimization Software and Modeling Systems, Semi-definite Programming Tags , , , , ,

    SparesPOP is a MATLAB implementation of a sparse semidefinite programming (SDP) relaxation method proposed for polynomial optimization problems (POPs) in the recent paper by Waki et al. The sparse SDP relaxation is based on a hierarchy of LMI relaxations of increasing dimensions by Lasserre, and exploits a sparsity structure of polynomials in POPs. The efficiency … Read more

    Solving Large-Scale Semidefinite Programs in Parallel

  • Madhu Nayakkankuppam
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We describe an approach to the parallel and distributed solution of large-scale, block structured semidefinite programs using the spectral bundle method. Various elements of this approach (such as data distribution, an implicitly restarted Lanczos method tailored to handle block diagonal structure, a mixed polyhedral-semidefinite subdifferential model, and other aspects related to parallelism) are combined in … Read more

    On Augmented Lagrangian methods with general lower-level constraints

  • Roberto Andreani
  • Ernesto G. Birgin
  • José Mario Martínez
  • María Laura Schuverdt
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    Augmented Lagrangian methods with general lower-level constraints are considered in the present research. These methods are useful when efficient algorithms exist for solving subproblems where the constraints are only of the lower-level type. Two methods of this class are introduced and analyzed. Inexact resolution of the lower-level constrained subproblems is considered. Global convergence is proved … Read more

    Packing circles in a square: new putative optima obtained via global optimization

  • Bernardetta Addis
  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization, Global Optimization Applications, Stochastic Approaches Tags , ,

    The problem of finding the optimal placement of $N$ identical, non overlapping, circles with maximum radius in the unit square is a well known challenge both in classical geometry and in optimization. A database of putative optima is currently maintained at \url{www.packomania.com}. Recently, through clever use of an extremely simple global optimization method, we succeeded … Read more

    Adaptive Barrier Strategies for Nonlinear Interior Methods

  • Jorge Nocedal
  • Richard A. Waltz
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    This paper considers strategies for selecting the barrier parameter at every iteration of an interior-point method for nonlinear programming. Numerical experiments suggest that adaptive choices, such as Mehrotra’s probing procedure, outperform static strategies that hold the barrier parameter fixed until a barrier optimality test is satisfied. A new adaptive strategy is proposed based on the … Read more

    Reduction of symmetric semidefinite programs using the regular *-representation

  • Etienne de Klerk
  • Dmitrii V. Pasechnik
  • Alexander Schrijver
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , ,

    We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix *-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending … Read more

    Semidefinite Programming Based Approaches to Home-away Assignment Problems in Sports Scheduling

  • Tomomi Matsui
  • Ryuhei Miyashiro
  • Akiko Yoshise
  • Ayami Suzuka
    • Categories Approximation Algorithms

    For a given schedule of a round-robin tournament and a matrix of distances between homes of teams, an optimal home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance. We propose a technique to transform the problem to MIN RES CUT. We apply Goemans and Williamson’s 0.878-approximation algorithm for MAX … Read more

    A linear programming reformulation of the standard quadratic optimization problem

  • Etienne de Klerk
  • Dmitrii V. Pasechnik
    • Categories Global Optimization Theory, Linear Programming, Linear, Cone and Semidefinite Programming Tags , ,

    The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note we show that the SQO problem may be reformulated as an (exponentially sized) linear program. CitationCentER … 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