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
Interior point methods for semidefinite optimization (SDO) have recently been studied intensively, due to their polynomial complexity and practical efficiency. Most of these methods are extensions of linear optimization (LO) algorithms. Unlike in the LO case, there are several different ways of constructing primal-dual search directions in SDO. The usual scheme is to apply linearization … Read more
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