A New Class of Polynomial Primal-Dual Methods for Linear and Semidefinite Optimization
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