Warm-Start Strategies in Interior-Point Methods for Linear Programming
SIAM Journal on OptimizationPublished 1 January 2002
E. Alper Yıldırım, Stephen J. Wright
Citations153
SJR quartileQ1
SJR score1.39
SNIP1.79
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Worst-case estimates of the number of iterations required to converge to a solution of the perturbed instance from the warm-start points are obtained, showing that these estimates depend on the size ofThe perturbation and on the conditioning and other properties of the problem instances.
Abstract
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 estimates of the number of iterations required to converge to a solution of the perturbed instance from the warm-start points, showing that these estimates depend on the size of the perturbation and on the conditioning and other properties of the problem instances.
Keywords
Computer ScienceMathematics
Society for Industrial and Applied Mathematics eBooksPrimal-Dual Interior-Point Methods
2,365 Citations1997Stephen J. Wright
This chapter discusses Primal Method Primal-Dual Methods, Path-Following Algorithm, and Infeasible-Interior-Point Algorithms, and their applications to Linear Programming and Interior-Point Methods.
Mathematical ProgrammingLinear programming, complexity theory and elementary functional analysis
237 Citations1995James Renegar
This work proposes analyzing interior-point methods using notions of problem-instance size which are direct generalizations of the condition number of a matrix which are appropriate in the context of semi-definite programming.
SIAM Journal on OptimizationIncorporating Condition Measures into the Complexity Theory of Linear Programming
177 Citations1995James Renegar
This work is an attempt to begin developing a complexity theory in which problem instance data is allowed to consist of real, even irrational, numbers and yet computations are of finite precision.
Operations ResearchA Characterization of Stability in Linear Programming
115 Citations1977Stephen M. Robinson
It is proved that a necessary and sufficient condition for the primal and dual solution sets of a solvable, finite-dimensional linear programming problem to be stable under small but arbitrary perturbations in the data of the problem is that both of these sets be bounded.
Mathematical ProgrammingWarm start of the primal-dual method applied in the cutting-plane scheme
94 Citations1998Jacek Gondzio
A practical warm-start procedure is described for the infeasible primal-dual interior-point method (IPM) employed to solve the restricted master problem within the cutting-plane method.
Mathematical ProgrammingSolving combinatorial optimization problems using Karmarkar's algorithm
82 Citations1992John E. Mitchell, Michael J. Todd
The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.
Annals of Operations ResearchSolving real-world linear ordering problems using a primal-dual interior point cutting plane method
61 Citations1996John E. Mitchell, Brian Borchers
A cutting plane algorithm for solving the linear ordering problem is described, which uses the primaldual interior point method to solve the linear programming relaxations.
Mathematical ProgrammingSensitivity analysis in linear programming and semidefinite programming using interior-point methods
45 Citations2001E. Alper Yıldırım, Michael D. Todd
It is shown that the bounds obtained using interior-point methods compare nicely with the bounds arising from using the optimal basis for linear programming for the unique, nondegenerate solution case in LP.
Mathematical ProgrammingCondition measures and properties of the central trajectory of a linear program
44 Citations1998Manuel Núñez, Robert M. Freund
Given a data instanced=(A, b, c) of a linear program, it is shown that certain properties of solutions along the central trajectory of the linear program are inherently related to the condition number C(d), which is a scale-invariant reciprocal of a closely-related measure ρ(d) called the “distance to ill-posedness”.
Mathematical ProgrammingA potential-function reduction algorithm for solving a linear program directly from an infeasible “warm start”
39 Citations1991Robert M. Freund
The algorithm is shown under suitable conditions to achieve a constant decrease in the potential function and so achieves a constant decrease in the duality gap (and hence also in the infeasibility) in O(n) iterations.
SIAM Journal on OptimizationCondition Numbers, the Barrier Method, and the Conjugate-Gradient Method
35 Citations1996James Renegar
It is shown that the condition numbers of the systems of linear equations arising during application of an interior-point method can be nicely bounded in terms of a quantity which is naturally interpreted as the condition number of the system of inequalities to which the method is being applied.
SIAM Journal on Matrix Analysis and ApplicationsOn Linear Least-Squares Problems with Diagonally Dominant Weight Matrices
35 Citations1996Anders Forsgren
The solution of the unconstrained weighted linear least-squares problem is known to be a convex combination of the basic solutions formed by the nonsingular subsystems if the weight matrix is diagonal andpositive definite, which implies that the norm of this solution is uniformly bounded for any diagonal and positive definite weight matrix.
Computational Optimization and ApplicationsWarm Start and ε-Subgradients in a Cutting Plane Scheme for Block-Angular Linear Programs
28 Citations1999J. Gondizo, J.‐P. Vial
The proposed approach has been implemented within the context of two optimization codes freely available for research use: the Analytic Center Cutting Plane Method—interior point based decomposition algorithm and the Higher Order Primal-Dual Method—general purpose interior point LP solver.
Karmarkar's algorithm and combinatorial optimization problems
18 Citations1988John E. Mitchell
This dissertation considers how Karmarkar's algorithm should be used in a cutting plane approach for solving combinatorial problems and develops methods which identify cutting planes before the optimal solution to the current relaxation is found.
USSR Computational Mathematics and Mathematical PhysicsStability conditions for linear programming problems
10 Citations1981S. A. Ashmanov