Direct Newton method for a linear problem of semidefinite programming

DOI10.1134/S0081543808060138MaRDI QIDQ735655zbMATH OpenFDO

Authors D. Kharzeev

Publication date 23 October 2009

Published in Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S0081543808060138

zbMATH Keywords

dual variables

Mathematics Subject Classification ID

Semidefinite programming (90C22) Methods of quasi-Newton type (90C53)

Review text

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.

Recommendations

• Primal-dual Newton method with steepest descent for the linear semidefinite programming problem: Newton's system of equations
• On convergence of the dual Newton method for a linear semidefinite programming problem
• A primal interior point method for the linear semidefinite programming problem
• Primal-dual Newton method with steepest descent for the linear semidefinite programming problem: iterative process
• A variant of the dual simplex method for a linear semidefinite programming problem

Cites work

• A primal interior point method for the linear semidefinite programming problem
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• scientific article; zbMATH DE number 1261669 (Why is no real title available?)
• Stable barrier-projection and barrier-Newton methods in linear programming
• The Elimination Matrix: Some Lemmas and Applications

Cited in

(5)

• Primal-dual Newton method with steepest descent for the linear semidefinite programming problem: Newton's system of equations
• scientific article; zbMATH DE number 5926294 (Why is no real title available?)
• On convergence of the dual Newton method for a linear semidefinite programming problem
• Newton's method for minimizing a convex twice differentiable function on a preconvex set
• Some structural properties of a Newton-type method for semidefinite programs

This page was built for publication: Direct Newton method for a linear problem of semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q735655)