Linear, Cone and Semidefinite Programming

A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part I: Proposed Approach and Application to Semidefinite Programming

  • Yoshihiro Kanno
  • Masakazu Kojima
  • Kazuo Murota
  • Sadayoshi Kojima
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    Motivated by recent interest in group-symmetry in semidefinite programming, we propose a numerical method for finding a finest simultaneous block-diagonalization of a finite number of matrices, or equivalently the irreducible decomposition of the generated matrix *-algebra. The method is composed of numerical-linear algebraic computations such as eigenvalue computation, and automatically makes full use of the … Read more

    Regularization methods for semidefinite programming

  • Jérôme Malick
  • Janez Povh
  • Franz Rendl
  • Angelika Wiegele
    • Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , ,

    This paper studies an alternative technique to interior point methods and nonlinear methods for semidefinite programming (SDP). The approach based on classical quadratic regularizations leads to an algorithm, generalizing a recent method called “boundary point method”. We study the theoretical properties of this algorithm and we show that in practice it behaves very well on … Read more

    Properties of a Cutting Plane Method for Semidefinite Programming

  • John E. Mitchell
  • Kartik Krishnan Sivaramakrishnan
    • Categories Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , , ,

    We analyze the properties of an interior point cutting plane algorithm that is based on a semi-infinite linear formulation of the dual semidefinite program. The cutting plane algorithm approximately solves a linear relaxation of the dual semidefinite program in every iteration and relies on a separation oracle that returns linear cutting planes. We show that … Read more

    Fast Computation of Optimal Contact Forces

  • Stephen Boyd
  • Ben Wegbreit
    • Categories Convex Optimization, Mechanical Engineering, Second-Order Cone Programming Tags , , ,

    We consider the problem of computing the smallest contact forces, with point-contact friction model, that can hold an object in equilibrium against a known external applied force and torque. It is known that the force optimization problem (FOP) can be formulated as a semidefinite programming problem (SDP), or a second-order cone problem (SOCP), and so … Read more

    The continuous d-step conjecture for polytopes

  • Antoine Deza
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Linear, Cone and Semidefinite Programming, Polyhedra Tags , , , , ,

    The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension $d$ for … Read more

    SDLS: a Matlab package for solving conic least-squares problems

  • Didier Henrion
  • Jérôme Malick
    • Categories Convex Optimization, Optimization Software and Modeling Systems, Semi-definite Programming

    This document is an introduction to the Matlab package SDLS (Semi-Definite Least-Squares) for solving least-squares problems over convex symmetric cones. The package is shortly presented through the addressed problem, a sketch of the implemented algorithm, the syntax and calling sequences, a simple numerical example and some more advanced features. The implemented method consists in solving … Read more

    A Sequential Convex Semidefinite Programming Algorithm for Multiple-Load Free Material Optimization

  • Michal Kočvara
  • Günter Leugering
  • Michael Stingl
    • Categories Mechanical Engineering, Multidisciplinary Design Optimization, Semi-definite Programming Tags , ,

    A new method for the efficient solution of free material optimization problems is introduced. The method extends the sequential convex programming (SCP) concept to a class of optimization problems with matrix variables. The basic idea of the new method is to approximate the original optimization problem by a sequence of subproblems, in which nonlinear functions … Read more

    Optimization by the Fixed-Point Method, Version 2.17

  • Jalaluddin Abdullah
    • Categories Constrained Nonlinear Optimization, Linear Programming Tags , , ,

    Abstract: After developing necessary background theory, the original primal and dual are specified, and the invariant primal and dual LP’s are defined. Pairs of linear mappings are defined which establish an effectively one-to-one correspondences between solutions to the original and invariant problems. The invariant problems are recast as a fixed-point problem and precise solution conditions … Read more

    On hyperbolicity cones associated with elementary symmetric polynomials

  • Yuriy Zinchenko
    • Categories Linear, Cone and Semidefinite Programming

    Elementary symmetric polynomials can be thought of as derivative polynomials of $E_n(x)=\prod_{i=1,\ldots,n} x_i$. Their associated hyperbolicity cones give a natural sequence of relaxations for $\Re^n_+$. We establish a recursive structure for these cones, namely, that the coordinate projections of these cones are themselves hyperbolicity cones associated with elementary symmetric polynomials. As a consequence of this … Read more