A scaled Gauss-Newton Primal–Dual Search Direction for Semidefinite Optimization

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

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