Linear, Cone and Semidefinite Programming

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

    How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds.

  • Antoine Deza
  • Eissa Nematollahi
  • Tamás Terlaky
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , ,

    By refining a variant of the Klee-Minty example that forces the central path to visit all the vertices of the Klee-Minty n-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is O(2^{n}n^{\frac{5}{2}}), we prove that solving this n-dimensional linear optimization problem requires at least $2^n-1$ … Read more

    Lowner’s Operator and Spectral Functions in Euclidean Jordan Algebras

  • Jie Sun
  • Defeng Sun
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We study analyticity, differentiability, and semismoothness of Lowner’s operator and spectral functions under the framework of Euclidean Jordan algebras. In particular, we show that many optimization-related classical results in the symmetric matrix space can be generalized within this framework. For example, the metric projection operator over any symmetric cone defined in a Euclidean Jordan algebra … Read more

    Computational Experience with Rigorous Error Bounds for the Netlib Linear Programming Library

  • Christian Jansson
  • Christian Keil
    • Categories Linear Programming Tags , , , ,

    The Netlib library of linear programming problems is a well known suite containing many real world applications. Recently it was shown by Ordonez and Freund that 71% of these problems are ill-conditioned. Hence, numerical difficulties may occur. Here, we present rigorous results for this library that are computed by a verification method using interval arithmetic. … Read more

    Sums of Random Symmetric Matrices and Applications

  • Arkadi Nemirovski
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , ,

    Let B_i be deterministic symmetric m\times m matrices, and \xi_i be independent random scalars with zero mean and “of order of one” (e.g., \xi_i are Gaussian with zero mean and unit standard deviation). We are interested in conditions for the “typical norm” of the random matrix S_N = \xi_1B_1+…+\xi_NB_N to be of order of 1. … Read more

    A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming

  • Gun Srijuntongsiri
  • Stephen A. Vavasis
    • Categories Second-Order Cone Programming Tags

    In this paper, we show a way to exploit sparsity in the problem data in a primal-dual potential reduction method for solving a class of semidefinite programs. When the problem data is sparse, the dual variable is also sparse, but the primal one is not. To avoid working with the dense primal variable, we apply … Read more

    Magnetic Resonance Tissue Density Estimation using Optimal SSFP Pulse-Sequence Design

  • Christopher Anand
  • Renata Sotirov
  • Tamás Terlaky
  • Zhuo Zheng
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , ,

    In this paper, we formulate a nonlinear, nonconvex semidefinite optimization problem to select the steady-state free precession (SSFP) pulse-sequence design variables which maximize the contrast to noise ratio in tissue segmentation. The method could be applied to other pulse sequence types, arbitrary numbers of tissues, and numbers of images. To solve the problem we use … Read more

    New variant on the Mizuno-Todd-Ye predictor-corrector algorithm

  • Marianna Eisenberg-Nagy
  • Tibor Illés
    • Categories Applications - OR and Management Sciences, Linear, Cone and Semidefinite Programming Tags , , , ,

    We analyze a version of the Mizuno-Todd-Ye predictor-corrector interior point algorithm for the P_*(\kappa)-matrix linear complementarity problem (LCP). We assume the existence of a strictly positive feasible solution. Our version of the Mizuno-Todd-Ye predictor-corrector algorithm is a generalization of Potra’s (2002) conclusions on the LCP with P_*(\kappa)-matrices. To derive a formulation of the complexity for … Read more

    Convergent relaxations of polynomial matrix inequalities and static output feedback

  • Didier Henrion
  • Jean-Bernard Lasserre
    • Categories Control Applications, Semi-definite Programming Tags , , ,

    Using a moment interpretation of recent results on sum-of-squares decompositions of non-negative polynomial matrices, we propose a hierarchy of convex linear matrix inequality (LMI) relaxations to solve non-convex polynomial matrix inequality (PMI) optimization problems, including bilinear matrix inequality (BMI) problems. This hierarchy of LMI relaxations generates a monotone sequence of lower bounds that converges to … Read more