Linear, Cone and Semidefinite Programming

Think co(mpletely )positive ! Matrix properties, examples and a clustered bibliography on copositive optimization

  • Immanuel M. Bomze
  • Werner Schachinger
  • Gabriele Uchida
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Linear, Cone and Semidefinite Programming

    Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing a linear functional over a convex cone subject to linear constraints), namely the cone of all completely positive symmetric nxn matrices, and its … Read more

    Exact Approaches to Multi-Level Vertical Orderings

  • Markus Chimani
  • Philipp Hungerländer
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , ,

    We present a semide nite programming (SDP) approach for the problem of ordering vertices of a layered graph such that the edges of the graph are drawn as vertical as possible. This Multi-Level Vertical Ordering (MLVO) problem is a quadratic ordering problem and conceptually related to the well-studied problem of Multi-Level Crossing Minimization (MLCM). In contrast … Read more

    Multi-level Verticality Optimization: Concept, Strategies, and Drawing Scheme

  • Markus Chimani
  • Philipp Hungerländer
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , ,

    In traditional multi-level graph drawing – known as Sugiyama’s framework – the number of crossings is considered one of the most important goals. Herein, we propose the alternative concept of optimizing the verticality of the drawn edges. We formally specify the problem, discuss its relative merits, and show that drawings that are good w.r.t. verticality … Read more

    On semidefinite programming bounds for graph bandwidth

  • Etienne de Klerk
  • Marianna Eisenberg-Nagy
  • Renata Sotirov
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, … Read more

    Generalized Bundle Methods for Sum-Functions with Easy” Components: Applications to Multicommodity Network Design

  • Antonio Frangioni
  • Enrico Gorgone
    • Categories Convex and Nonsmooth Optimization, Linear Programming, Network Optimization Tags , , , ,

    We propose a modification to the (generalized) bundle scheme for minimization of a convex nondifferentiable sum-function in the case where some of the components are “easy”, that is, they are Lagrangian functions of explicitly known convex programs with “few” variables and constraints. This happens in many practical cases, particularly within applications to combinatorial optimization. In … Read more

    Positive polynomials on unbounded equality-constrained domains

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Certificates of non-negativity are fundamental tools in optimization. A “certificate” is generally understood as an expression that makes the non-negativity of the function in question evident. Some classical certificates of non-negativity are Farkas Lemma and the S-lemma. The lift-and-project procedure can be seen as a certificate of non-negativity for affine functions over the union of … Read more

    On the Computational Complexity of Membership Problems for the Completely Positive Cone and its Dual

  • Peter J.C. Dickinson
  • Luuk Gijben
    • Categories Linear, Cone and Semidefinite Programming

    Copositive programming has become a useful tool in dealing with all sorts of optimisation problems. It has however been shown by Murty and Kabadi [K.G. Murty and S.N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39, no.2:117–129, 1987] that the strong membership problem for the copositive cone, that is deciding whether … Read more

    Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper, we consider block-decomposition first-order methods for solving large-scale conic semidefinite programming problems. Several ingredients are introduced to speed-up the method in its pure form such as: an aggressive choice of stepsize for performing the extragradient step; use of scaled inner products in the primal and dual spaces; dynamic update of the scaled … Read more

    An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and its Implications to Second-Order Methods

  • Renato D.C. Monteiro
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , , ,

    This paper presents an accelerated variant of the hybrid proximal extragradient (HPE) method for convex optimization, referred to as the accelerated HPE (A-HPE) method. Iteration-complexity results are established for the A-HPE method, as well as a special version of it, where a large stepsize condition is imposed. Two specific implementations of the A-HPE method are … Read more

    A Computational Study and Survey of Methods for the Single-Row Facility Layout Problem

  • Philipp Hungerländer
  • Franz Rendl
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , ,

    The single row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange … Read more