linear programming

A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function

  • Jiming Peng
  • Tamás Terlaky
  • Yun-Bin Zhao
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    It is well known that the so-called first-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior-point methods (IPMs) for linear optimization (LO) problems. However, the best known iteration complexity of this type of methods is $O\br{n \log\frac{(x^0)^Ts^0}{\varepsilon}}$. It is of interests to investigate whether the complexity … Read more

    Asymptotic Behavior of Continuous Trajectories for Primal-Dual Potential-Reduction Methods

  • Reha H. Tütüncü
    • Categories Linear Programming Tags , , , ,

    This article considers continuous trajectories of the vector fields induced by primal-dual potential-reduction algorithms for solving linear programming problems. It is known that these trajectories converge to the analytic center of the primal-dual optimal face. We establish that this convergence may be tangential to the central path, tangential to the optimal face, or in between, … Read more

    Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
  • Jerome W. O'Neal
    • Categories Linear Programming, Network Optimization Tags , , , , , , ,

    Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more

    Smoothed Analysis of Interior-Point Algorithms: Termination

  • Daniel Spielman
  • Shang-Hua Teng
    • Categories Linear Programming Tags , , ,

    We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar’s interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma ))$. In contrast, the best known bound … Read more

    Semidefinite programming and integer programming

  • Monique Laurent
  • Franz Rendl
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We survey how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems. CitationPreliminary version appeared as Report PNA-R0210, CWI, Amsterdam, April 2002. To appear as Chapter in the Handbook on Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel, eds., Elsevier Publishers.ArticleDownload View PDF

    An Active-Set Algorithm for Nonlinear Programming Using Linear Programming and Equality Constrained Subproblems

  • Richard H. Byrd
  • Nicholas I. M. Gould
  • Jorge Nocedal
  • Richard A. Waltz
    • Categories Constrained Nonlinear Optimization, Optimization Software Benchmark Tags , , , , ,

    This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained … Read more

    Using selective orthonormalization to update the analytic center after the addition of multiple cuts

  • John E. Mitchell
  • Srinivasan Ramaswamy
    • Categories Convex Optimization, Cutting Plane Approaches, Nonsmooth Optimization Tags , , , ,

    We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope in Euclidean n-space. This is an important issue that arises at every `stage’ in a cutting plane algorithm. If q cuts are to be added, with q no larger than n, … Read more

    Implementation of Interior Point Methods for Mixed Semidefinite and Second Order Cone Optimization Problems

  • Jos F. Sturm
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    There is a large number of implementational choices to be made for the primal-dual interior point method in the context of mixed semidefinite and second order cone optimization. This paper presents such implementational issues in a unified framework, and compares the choices made by different research groups. This is also the first paper to provide … Read more

    The Inverse Optimal Value Problem

  • Shabbir Ahmed
  • Yongpei Guan
    • Categories Global Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost coefficients, determine a cost-coefficient vector such that the corresponding optimal objective value of the linear program is closest to the given value. The above problem, referred here as the inverse optimal value … Read more

    Safe bounds in linear and mixed-integer programming

  • Arnold Neumaier
  • Oleg Shcherbina
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , , , , , , , , , ,

    Current mixed-integer linear programming solvers are based on linear programming routines that use floating point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. It is shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in … Read more