Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems

DOI10.1007/S10957-010-9746-6MaRDI QIDQ630020zbMATH OpenOpenAlexWikidataFDO

Authors Chee-Khian Sim

Publication date 10 March 2011

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10957-010-9746-6

zbMATH Keywords

interior point methodslocal convergenceNT directionordinary differential equationssemidefinite linear complementarity problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Interior-point methods (90C51)

Review text

This article studies off-central paths, corresponding to the Nesterov-Todd (NT) direction for the solution of the semidefinite linear complementarity problem. The article begins with a literature overview covering prior work on interior methods, central paths, convergence and the properties of semidefinite programs and monotone semidefinite linear complementarity problems. The second section contains the main definitions and the background assumptions required for this problem. This is followed by the main section of the paper, where the asymptotic behavior of NT paths are studied. Several important theorems are presented in this section with proof, including the necessary and sufficient conditions for when such a path is analytic with respect to \(\mu\) and \(\sqrt\mu\). The paper concludes with a list of relevant articles.

Recommendations

• Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems
• On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems
• Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory
• Existence of Interior Points and Interior Paths in Nonlinear Monotone Complementarity Problems
• A modified damped Newton method for linear complementarity problems

Cites work

• A Note on the Local Convergence of a Predictor-Corrector Interior-Point Algorithm for the Semidefinite Linear Complementarity Problem Based on the Alizadeh--Haeberly--Overton Search Direction
• A Predictor-Corrector Interior-Point Algorithm for the Semidefinite Linear Complementarity Problem Using the Alizadeh--Haeberly--Overton Search Direction
• A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
• A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with \(O(\sqrt nL)\)-iteration complexity
• A Superlinearly Convergent Primal-Dual Infeasible-Interior-Point Algorithm for Semidefinite Programming
• An Interior-Point Method for Semidefinite Programming
• Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems
• Analyticity of weighted central paths and error bounds for semidefinite programming
• Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory
• Asymptotic behavior of the central path for a special class of degenerate SDP problems
• Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path
• Corrector-predictor methods for sufficient linear complementarity problems
• Corrector‐Predictor Methods for Sufficient Linear Complementarity Problems in a Wide Neighborhood of the Central Path
• Error Bounds and Limiting Behavior of Weighted Paths Associated with the SDP Map X1/2SX1/2
• High order infeasible-interior-point methods for solving sufficient linear complementarity problems
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 2158989 (Why is no real title available?)
• scientific article; zbMATH DE number 3109695 (Why is no real title available?)
• Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
• Limiting behavior of the Alizadeh–Haeberly–Overton weighted paths in semidefinite programming
• Limiting behaviour and analyticity of weighted central paths in semidefinite programming
• Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs
• On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP
• On a general class of interior-point algorithms for semidefinite programming with polynomial complexity and superlinear convergence
• On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
• On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP
• On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems
• On the analyticity properties of infeasible-interior point paths for monotone linear complementarity problems
• On the Local Convergence of a Predictor-Corrector Method for Semidefinite Programming
• On the Nesterov--Todd Direction in Semidefinite Programming
• Polynomial Convergence of a New Family of Primal-Dual Algorithms for Semidefinite Programming
• Predictor–corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path
• Primal--Dual Path-Following Algorithms for Semidefinite Programming
• Primal-Dual Interior-Point Methods for Self-Scaled Cones
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Quadratic Convergence in a Primal-Dual Method
• Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp^∗
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Superlinear convergence of a predictor-corrector method for semidefinite programming without shrinking central path neighborhood
• Superlinear convergence of an algorithm for monotone linear complementarity problems, when no strictly complementary solution exists
• Superlinear convergence of interior-point algorithms for semidefinite programming
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
• The Nonlinear Geometry of Linear Programming. III Projective Legendre Transform Coordinates and Hilbert Geometry
• Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem

Cited in

(5)

• On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems
• Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence
• Asymptotic Behavior of Interior-Point Methods: A View From Semi-Infinite Programming
• Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory
• Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem

This page was built for publication: Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems

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