New complexity analysis of a full-Newton step feasible interior-point algorithm for \(P_\ast(\kappa)\)-LCP

DOI10.1007/s11590-014-0800-4zbMath1331.90085OpenAlexW1971375329MaRDI QIDQ497434

Yong-Cai Geng, Sumit K. Garg

Publication date: 24 September 2015

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-014-0800-4

zbMATH Keywords

linear complementarity probleminterior-point methodspolynomial complexityfull-Newton step\(P_\ast(\kappa)\)-matrix

Mathematics Subject Classification ID

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

Related Items (9)

A path-following full Newton-step infeasible interior-point algorithm for \(P_*(\kappa)\)-HLCPs based on a kernel function ⋮ A new search direction for full-Newton step infeasible interior-point method in linear optimization ⋮ A generalized direction in interior point method for monotone linear complementarity problems ⋮ A new full-NT step interior-point method for circular cone optimization ⋮ An interior-point algorithm for \(P_*(\kappa)\)-LCP based on a new trigonometric kernel function with a double barrier term ⋮ A second-order corrector wide neighborhood infeasible interior-point method for linear optimization based on a specific kernel function ⋮ Complexity analysis of a weighted-full-Newton step interior-point algorithm forP_∗(κ)-LCP ⋮ Unnamed Item ⋮ A new full-Newton step interior-point method for \(P_*(\kappa)\)-LCP based on a positive-asymptotic kernel function

Cites Work

• Unnamed Item
• A polynomial interior-point algorithm for monotone linear complementarity problems
• A new complexity analysis for full-Newton step infeasible interior-point algorithm for horizontal linear complementarity problems
• A full-Newton step interior-point algorithm based on modified Newton direction
• Polynomial interior-point algorithms for \(P_*(\kappa )\) horizontal linear complementarity problem
• Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems
• A class of large-update and small-update primal-dual interior-point algorithms for linear optimization
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• Predictor-corrector algorithm for solving \(P_ *(\kappa)\)-matrix LCP from arbitrary positive starting points
• A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem
• A full-Newton step feasible interior-point algorithm for \(P_\ast(\kappa)\)-linear complementarity problems
• Polynomial interior-point algorithm for \(P_\ast(\kappa)\) horizontal linear complementarity problems
• An infeasible primal-dual interior point algorithm for linear programs based on logarithmic equivalent transformation
• Unified Analysis of Kernel-Based Interior-Point Methods for $P_*(\kappa)$-Linear Complementarity Problems
• Engineering and Economic Applications of Complementarity Problems
• A Comparative Study of Kernel Functions for Primal-Dual Interior-Point Algorithms in Linear Optimization
• Interior Point Methods for Sufficient Horizontal LCP in a Wide Neighborhood of the Central Path with Best Known Iteration Complexity
• An O$(\sqrtn L)$ Iteration Primal-dual Path-following Method, Based on Wide Neighborhoods and Large Updates, for Monotone LCP

This page was built for publication: New complexity analysis of a full-Newton step feasible interior-point algorithm for \(P_\ast(\kappa)\)-LCP