Linear, Cone and Semidefinite Programming

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

    A Simple Variant of the Mizuno-Todd-Ye Predictor-Corrector Algorithm and its Objective-Function-Free Complexity

  • Tomonari Kitahara
  • Takashi Tsuchiya
    • Categories Linear Programming Tags , , , ,

    In this paper, we propose a simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming problem (LP). Our variant executes a natural finite termination procedure at each iteration and it is easy to implement the algorithm. Our algorithm admits an objective-function free polynomial-time complexity when it is applied to LPs whose dual feasible region … Read more

    Inner approximations for polynomial matrix inequalities and robust stability regions

  • Didier Henrion
  • Jean-Bernard Lasserre
    • Categories Robust Optimization, Semi-definite Programming Tags , , , , ,

    Following a polynomial approach, many robust fixed-order controller design problems can be formulated as optimization problems whose set of feasible solutions is modelled by parametrized polynomial matrix inequalities (PMI). These feasibility sets are typically nonconvex. Given a parametrized PMI set, we provide a hierarchy of linear matrix inequality (LMI) problems whose optimal solutions generate inner … Read more

    The Second Order Directional Derivative of Symmetric Matrix-valued Functions

  • Xiantao Xiao
  • Liwei Zhang
  • Ning Zhang
    • Categories Linear, Cone and Semidefinite Programming

    This paper focuses on the study of the second-order directional derivative of a symmetric matrix-valued function of the form $F(X)=P\mbox{diag}[f(\lambda_1(X)),\cdots,f(\lambda_n(X))]P^T$. For this purpose, we first adopt a direct way to derive the formula for the second-order directional derivative of any eigenvalue of a matrix in Torki \cite{Tor01}; Second, we establish a formula for the (parabolic) … Read more

    How bad is a gradient algorithm for linear programming?

  • Peter A. Bruijs
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming

    In their 1972 paper ‘How good is the simplex algorithm ?’ Klee and Minty present a class of problems the simplex algorithm for linear programming (LP) is not able to solve in a polynomial way. Later developments have resulted in algorithms by Khachiyan and Karmarkar that do solve LP in a polynomial way, although the … Read more

    High accuracy solution of large scale semidefinite programs

  • Thomas Davi
  • Florian Jarre
    • Categories Semi-definite Programming Tags , ,

    We present a first order approach for solving semidefinite programs. Goal of this approach is to compute a solution of the SDP up to high accuracy in spite of using only partial second order information. We propose a hybrid approach that uses an accelerated projection method to generate an approximate solution and then switches to … Read more

    Solving large scale problems over the doubly nonnegative cone

  • Thomas Davi
  • Florian Jarre
    • Categories Semi-definite Programming Tags , , , ,

    The recent approach of solving large scale semidefinite programs with a first order method by minimizing an augmented primal-dual function is extended to doubly nonnegative programs. Regularity of the augmented primal-dual function is established under the condition of uniqueness and strict complementarity. The application to the doubly nonnegative cone is motivated by the fact that … Read more

    On Solving Biquadratic Optimization via Semidefinite Relaxation

  • Yuning Yang
  • Qingzhi Yang
    • Categories Semi-definite Programming Tags , , ,

    In this paper, we study a class of biquadratic optimization problems. We first relax the original problem to its semidefinite programming (SDP) problem and discuss the approximation ratio between them. Under some conditions, we show that the relaxed problem is tight. Then we consider how to approximately solve the problems in polynomial time. Under several … Read more