linear programming

SDPT3 – a MATLAB software package for semidefinite-quadratic-linear programming, version 3.0

  • Michael J. Todd
  • Kim-Chuan Toh
  • Reha H. Tütüncü
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , ,

    This software package is a MATLAB implementation of infeasible path-following algorithms for solving conic programming problems whose constraint cone is a product of semidefinite cones, second-order cones, and/or nonnegative orthants. It employs a predictor-corrector primal-dual path-following method, with either the HKM or the NT search direction. The basic code is written in Matlab, but key … Read more

    Semi-infinite linear programming approaches to semidefinite programming problems

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

    Interior point methods, the traditional methods for the $SDP$, are fairly limited in the sizes of problems they can handle. This paper deals with an $LP$ approach to overcome some of these shortcomings. We begin with a semi-infinite linear programming formulation of the $SDP$ and discuss the issue of its discretization in some detail. We … Read more

    On the convergence of the central path in semidefinite optimization

  • Etienne de Klerk
  • Margaréta Halická
  • Cornelis Roos
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    The central path in linear optimization always converges to the analytic center of the optimal set. This result was extended to semidefinite programming by Goldfarb and Scheinberg (SIAM J. Optim. 8: 871-886, 1998). In this paper we show that this latter result is not correct in the absence of strict complementarity. We provide a counterexample, … Read more

    A Linear Programming Approach to Semidefinite Programming Problems

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Combinatorial Optimization, Linear Programming, Semi-definite Programming Tags , , , , ,

    Until recently, the study of interior point methods has dominated algorithmic research in semidefinite programming (SDP). From a theoretical point of view, these interior point methods offer everything one can hope for; they apply to all SDP’s, exploit second order information and offer polynomial time complexity. Still for practical applications with many constraints $k$, the … Read more

    A study of preconditioners for network interior point methods

  • Joaquim J. Júdice
  • João Patrício
  • Luis F. Portugal
  • Mauricio G.C. Resende
  • Geraldo Veiga
    • Categories Network Optimization Tags , , , ,

    We study and compare preconditioners available for network interior point methods. We derive upper bounds for the condition number of the preconditioned matrices used in the solution of systems of linear equations defining the algorithm search directions. The preconditioners are tested using PDNET, a state-of-the-art interior point code for the minimum cost network flow problem. … Read more

    A New and Efficient Large-Update Interior-Point Method for Linear Optimization

  • Jiming Peng
  • Cornelis Roos
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Recently, the authors presented a new large-update primal-dual method for Linear Optimization, whose $O(n^\frac23\,\log\frac{n}{\e})$ iteration bound substantially improved the classical bound for such methods, which is $O\br{n\log\frac{n}{\e}}$. In this paper we present an improved analysis of the new method. The analysis uses some new mathematical tools developed before when we considered a whole family of … Read more

    An Interior-Point Approach to Sensitivity Analysis in Degenerate Linear Programs

  • Michael J. Todd
  • E. Alper Yildirim
    • Categories Linear Programming Tags , ,

    We consider the interior-point approach to sensitivity analysis in linear programming (LP) developed by the authors. We investigate the quality of the interior-point bounds under degeneracy. In the case of a special degeneracy, we show that these bounds have the same nice relationship with the optimal partition bounds as in the nondegenerate case. We prove … Read more

    Hyper-sparsity in the revised simplex method and how to exploit it

  • J. A. Julian Hall
  • Kenneth McKinnon
    • Categories Linear Programming Tags , ,

    The revised simplex method is often the method of choice when solving large scale sparse linear programming problems, particularly when a family of closely-related problems is to be solved. Each iteration of the revised simplex method requires the solution of two linear systems and a matrix vector product. For a significant number of practical problems … Read more

    Warm start strategies in interior-point methods for linear programming

  • Stephen Wright
  • E. Alper Yildirim
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We study the situation in which, having solved a linear program with an interior-point method, we are presented with a new problem instance whose data is slightly perturbed from the original. We describe strategies for recovering a “warm-start” point for the perturbed problem instance from the iterates of the original problem instance. We obtain worst-case … Read more

    A New Class of Polynomial Primal-Dual Methods for Linear and Semidefinite Optimization

  • Cornelis Roos
  • J Peng
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We propose a new class of primal-dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large update method for LO based on the new search direction has a polynomial complexity $O\br{n^{\frac{4}{4+\rho}}\log\frac{n}{\e}}$ iterations where $\rho\in [0,2]$ is a parameter used in the system defining the search direction. If $\rho=0$, … Read more