The Gauss-Newton direction in semidefinite programming

DOI10.1080/10556780108805808MaRDI QIDQ3146531zbMATH OpenOpenAlexFDO

Authors Masakazu Muramatsu, Franz Rendl, Robert J. Vanderbei, Henry Wolkowicz, Serge G. Kruk

Publication date 12 September 2002

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/10556780108805808

zbMATH Keywords

Newton directionprimal-dual interior point methodssearch directionssemi-definite programming

Mathematics Subject Classification ID

Semidefinite programming (90C22) Interior-point methods (90C51)

Review text

In this paper a new family of search directions for primal-dual interior point methods for semi-definite programming is introduced. The approach proposed for the search direction is different to the one used by Alizadeh, Haeberly and Overton (AHO). Instead of projecting onto the symmetric space, the modified perturbed optimality conditions are viewed here as a nonlinear operator to which the Gauss Newton (GN) method is applied. This results in an over-determined system of equations and in a new family of directions based on the least squares solutions of this system. Some properties of the GN direction are shown. For instance it is proved that the direction: is well-defined, coincides with the standard direction in the LP case, coincides with AHO on the central path in the SDP case and is invariant under orthonormal scaling of the data and affine scaling of the space. Since the efficient calculation of the presented GN direction is a difficult problem, the authors present a constrained GN-direction that is easier to calculate but still maintains most of the properties of the GN direction. In addition, several directions are compared within the same interior-point algorithm to assess the accuracy of the resulting solutions and the effectiveness of the new approach. The conditioning of the system of equations used allows a numerically robust implementation, as exhibited by the given numerical results.

Recommendations

• A study of search directions in primal-dual interior-point methods for semidefinite programming
• Some new search directions for primal-dual interior point methods in semidefinite programming
• Convergence of a short-step primal-dual algorithm based on the Gauss-Newton direction
• A scaled Gauss--Newton primal-dual search direction for semidefinite optimization
• A robust algorithm for semidefinite programming

Cited in

(12)

• Strengthened existence and uniqueness conditions for search directions in semidefinite program\-ming
• A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion
• Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming
• Convergence of a short-step primal-dual algorithm based on the Gauss-Newton direction
• A scaled Gauss--Newton primal-dual search direction for semidefinite optimization
• Sensor network localization, Euclidean distance matrix completions, and graph realization
• Primal-Dual Interior-Point Methods for Semidefinite Programming in Finite Precision
• A robust algorithm for semidefinite programming
• Solving semidefinite programs using preconditioned conjugate gradients
• Error bounds and singularity degree in semidefinite programming
• Semidefinite programming and combinatorial optimization
• Semidefinite programming for discrete optimization and matrix completion problems

Describes a project that uses

Uses Software

• SDPA
• SDPpack
• SDPHA

This page was built for publication: The Gauss-Newton direction in semidefinite programming

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