linear programming

Algebraic Tail Decay of Condition Numbers for Random Conic Systems under a General Family of Input Distributions

  • Raphael Hauser
  • Tobias Muller
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We consider the conic feasibility problem associated with linear homogeneous systems of inequalities. The complexity of iterative algorithms for solving this problem depends on a condition number. When studying the typical behaviour of algorithms under stochastic input one is therefore naturally led to investigate the fatness of the distribution tails of the random condition number … Read more

    Dynamic Enumeration of All Mixed Cells

  • Masakazu Kojima
  • Tomohiko Mizutani
  • Akiko Takeda
    • Categories 0-1 Programming, Branch and Cut Algorithms, Polyhedra Tags , , , ,

    The polyhedral homotopy method, which has been known as a powerful numerical method for computing all isolated zeros of a polynomial system, requires all mixed cells of the support of the system to construct a family of homotopy functions. Finding the mixed cells is formulated in terms of a linear inequality system with an additional … Read more

    Exact regularization of linear programs

  • Michael P. Friedlander
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    We show that linear programs (LPs) admit regularizations that either contract the original (primal) solution set or leave it unchanged. Any regularization function that is convex and has compact level sets is allowed–differentiability is not required. This is an extension of the result first described by Mangasarian and Meyer (SIAM J. Control Optim., 17(6), pp. … Read more

    Existence of Equilibrium for Integer Allocation Problems

  • Somdeb Lahiri
    • Categories Game Theory, Linear Programming Tags , , , ,

    In this paper we show that if all agents are equipped with discrete concave production functions, then a feasible price allocation pair is a market equilibrium if and only if it solves a linear programming problem, similar to, but perhaps simpler than the one invoked in Yang (2001). Using this result, but assuming discrete concave … Read more

    Further Development of Multiple Centrality Correctors for Interior Point Methods

  • Marco Colombo
  • Jacek Gondzio
    • Categories Linear Programming Tags , , ,

    This paper addresses the role of centrality in the implementation of interior point methods. Theoretical arguments are provided to justify the use of a symmetric neighbourhood. These are translated into computational practice leading to a new insight into the role of re-centering in the implementation of interior point methods. Arguments are provided to show that … Read more

    On warm starts for interior methods

  • Anders Forsgren
    • Categories Constrained Nonlinear Optimization Tags , , ,

    An appealing feature of interior methods for linear programming is that the number of iterations required to solve a problem tends to be relatively insensitive to the choice of initial point. This feature has the drawback that it is difficult to design interior methods that efficiently utilize information from an optimal solution to a “nearby” … Read more

    A strong bound on the integral of the central path curvature and its relationship with the iteration complexity of primal-dual path-following LP algorithms

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , , , , , , , ,

    The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and … Read more

    Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems

  • Zsolt Csizmadia
  • Tibor Illés
  • Bilen Filiz
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We define a variant of Anstreicher and Terlaky’s (1994) monotonic build-up (MBU) simplex algorithm for linear feasibility problems. Under a nondegeneracy assumption weaker than the normal one, the complexity of the algorithm can be given by $m\Delta$, where $\Delta$ is a constant determined by the input data of the problem and $m$ is the number … Read more

    Postponing the Choice of the Barrier Parameter in Mehrotra-Type Predictor-Corrector Algorithms

  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In \cite{SPT} the authors considered a variant of Mehrotra’s predictor-corrector algorithm that has been widely used in several IPMs based optimization packages. By an example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, that itself implies the inefficiency of … Read more

    An Exact Primal-Dual Penalty Method Approach to Warmstarting Interior-Point Methods for Linear Programming

  • Hande Benson
  • David F. Shanno
    • Categories Linear Programming Tags , , ,

    One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal-dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set … Read more