Direct Newton method for a linear problem of semidefinite programming (Q735655): Difference between revisions

The authors propose a direct Newton method for solving a semidefinite programming problem. The aim is to obtain a convergence rate higher than linear. The method is a generalization of the direct barrier Newton method for linear programming problems. It consists in solving an equation describing the condition of the complementary slackness. More precisely a matrix \(V(X)\) is defined from the slack matrix associated with the constraint of the dual program. The corresponding equation has the form: \(F(X)=X * V(X) =0\) where \(*\) denotes the symmetrized product: \(X*Y = \frac12 (XY+YX)\). Then a solution \(X\) of this equation such that \(X\) and \(V(X)\) are positive semidefinite is a solution of the semidefinite programming problem. In a second part a characterization of the Newton direction as well as of the Newton iterates is obtained and the resulting algorithm is proven to be locally convergent with a quadratic rate.