Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence

DOI10.1007/s10589-019-00110-zzbMath1433.90172OpenAlexW2946509859MaRDI QIDQ2007836

Chee-Khian Sim

Publication date: 22 November 2019

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-019-00110-z

zbMATH Keywords

polynomial complexitylocal convergenceNesterov-Todd (NT) directionpredictor-corrector primal-dual path following interior point algorithmsemi-definite linear complementarity problem

Mathematics Subject Classification ID

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

Related Items (1)

On well-structured convex–concave saddle point problems and variational inequalities with monotone operators

Uses Software

• SeDuMi
• SDPT3

Cites Work

• Unnamed Item
• Improved complexity analysis of full Nesterov-Todd step feasible interior-point method for symmetric optimization
• Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems
• Full Nesterov-Todd step infeasible interior-point method for symmetric optimization
• 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
• On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems
• Superlinear convergence of interior-point algorithms for semidefinite programming
• A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming
• The projective method for solving linear matrix inequalities
• Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs
• Extension of primal-dual interior point algorithms to symmetric cones
• Infeasible interior-point method for symmetric optimization using a positive-asymptotic barrier
• Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems
• Improved complexity analysis of full Nesterov-Todd step interior-point methods for semidefinite optimization
• A primal-dual interior-point method based on various selections of displacement step for symmetric optimization
• Long-step path-following algorithm for solving symmetric programming problems with nonlinear objective functions
• Asymptotic behavior of the central path for a special class of degenerate SDP problems
• On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0
• Superlinear Convergence of an Infeasible Predictor-Corrector Path-Following Interior Point Algorithm for a Semidefinite Linear Complementarity Problem Using the Helmberg–Kojima–Monteiro Direction
• Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
• Local Superlinear Convergence of Polynomial-Time Interior-Point Methods for Hyperbolicity Cone Optimization Problems
• Matrix Analysis
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• On the Nesterov--Todd Direction in Semidefinite Programming
• A Superlinearly Convergent Primal-Dual Infeasible-Interior-Point Algorithm for Semidefinite Programming
• 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
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Primal--Dual Path-Following Algorithms for Semidefinite Programming
• Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming
• Primal-Dual Interior-Point Methods for Self-Scaled Cones
• On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
• Polynomial Convergence of a New Family of Primal-Dual Algorithms for Semidefinite Programming
• A Multiple-Cut Analytic Center Cutting Plane Method for Semidefinite Feasibility Problems
• An Interior-Point Method for Semidefinite Programming
• Complexity Analysis of an Interior Cutting Plane Method for Convex Feasibility Problems
• Error Bounds and Limiting Behavior of Weighted Paths Associated with the SDP Map X1/2SX1/2
• A Full-Newton Step O(n) Infeasible Interior-Point Algorithm for Linear Optimization
• Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones
• An Analytic Center Cutting Plane Method for Semidefinite Feasibility Problems
• \(Q\)-superlinear convergence of the iterates in primal-dual interior-point methods

This page was built for publication: Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence