A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem
From MaRDI portal
Publication:2175368
DOI10.1007/s13675-019-00116-6OpenAlexW2966970604WikidataQ127373717 ScholiaQ127373717MaRDI QIDQ2175368
Jean-Pierre Dussault, Mathieu Frappier, Gilbert, Jean Charles
Publication date: 29 April 2020
Published in: EURO Journal on Computational Optimization (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01806399/file/dussault-frappier-gilbert-2019-05-25.pdf
linear complementarity problemglobalizationline searchsemismooth Newton methodnondegenerate matrix\textbf{P}-matrixFathi and Murty problemsHarker and Pang algorithmiterative complexityNewton-min algorithm
Newton-type methods (49M15) Numerical methods for variational inequalities and related problems (65K15)
Related Items
A new approach for solving nonlinear algebraic systems with complementarity conditions. Application to compositional multiphase equilibrium problems, Adaptive inexact smoothing Newton method for a nonconforming discretization of a variational inequality, An Algorithmic Characterization of P-matricity II: Adjustments, Refinements, and Validation, Semismooth and smoothing Newton methods for nonlinear systems with complementarity constraints: adaptivity and inexact resolution
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a \(P\)-matrix
- A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems
- NP-completeness of the linear complementarity problem
- A unified approach to interior point algorithms for linear complementarity problems: A summary
- A unified approach to interior point algorithms for linear complementary problems
- Solution of symmetric linear complementarity problems by iterative methods
- A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques
- On finite termination of an iterative method for linear complementarity problems
- A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems
- A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization
- A nonsmooth version of Newton's method
- Minimization of functions having Lipschitz continuous first partial derivatives
- A Comparison of a Moreau--Yosida-Based Active Set Strategy and Interior Point Methods for Constrained Optimal Control Problems
- An Algorithmic Characterization of $P$-Matricity
- A Non-Interior-Point Continuation Method for Linear Complementarity Problems
- Newton's Method for B-Differentiable Equations
- Newton's method for linear complementarity problems
- The Linear Complementarity Problem
- PRACTICAL POLYNOMIAL TIME ALGORITHMS FOR LINEAR COMPLEMENTARITY PROBLEMS
- EXTENSION OF NEWTON AND QUASI-NEWTON METHODS TO SYSTEMS OF PC^1 EQUATIONS
- Computational complexity of LCPs associated with positive definite symmetric matrices
- Computational complexity of complementary pivot methods
- Primal-Dual Strategy for Constrained Optimal Control Problems
- The Primal-Dual Active Set Strategy as a Semismooth Newton Method
- Trust Region Methods
- Inexact semismooth Newton methods for large-scale complementarity problems
- Some Noninterior Continuation Methods for Linear Complementarity Problems
- An Algorithmic Characterization of P-matricity II: Adjustments, Refinements, and Validation
- Newton-Type Methods for Optimization and Variational Problems
- A Partition Theorem for Euclidean n-Space
- Numerical optimization. Theoretical and practical aspects. Transl. from the French
- Complexity of a noninterior path-following method for the linear complementarity problem
