linear programming

Warm start strategies in interior-point methods for linear programming

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

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