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
Author
Abstract
Suggested Citation
DOI: 10.1007/s13675-019-00116-6
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- Frank Curtis & Zheng Han & Daniel Robinson, 2015. "A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization," Computational Optimization and Applications, Springer, vol. 60(2), pages 311-341, March.
- J. Burke & S. Xu, 2002. "Complexity of a Noninterior Path-Following Method for the Linear Complementarity Problem," Journal of Optimization Theory and Applications, Springer, vol. 112(1), pages 53-76, January.
- Jong-Shi Pang, 1990. "Newton's Method for B-Differentiable Equations," Mathematics of Operations Research, INFORMS, vol. 15(2), pages 311-341, May.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- Vu, Duc Thach Son & Ben Gharbia, Ibtihel & Haddou, Mounir & Tran, Quang Huy, 2021. "A new approach for solving nonlinear algebraic systems with complementarity conditions. Application to compositional multiphase equilibrium problems," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 190(C), pages 1243-1274.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- H. Xu & B. M. Glover, 1997. "New Version of the Newton Method for Nonsmooth Equations," Journal of Optimization Theory and Applications, Springer, vol. 93(2), pages 395-415, May.
- D. H. Li & N. Yamashita & M. Fukushima, 2001. "Nonsmooth Equation Based BFGS Method for Solving KKT Systems in Mathematical Programming," Journal of Optimization Theory and Applications, Springer, vol. 109(1), pages 123-167, April.
- Long, Qiang & Wu, Changzhi & Wang, Xiangyu, 2015. "A system of nonsmooth equations solver based upon subgradient method," Applied Mathematics and Computation, Elsevier, vol. 251(C), pages 284-299.
- Da Tian, 2015. "An exterior point polynomial-time algorithm for convex quadratic programming," Computational Optimization and Applications, Springer, vol. 61(1), pages 51-78, May.
- Enrico Bettiol & Lucas Létocart & Francesco Rinaldi & Emiliano Traversi, 2020. "A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs," Computational Optimization and Applications, Springer, vol. 75(2), pages 321-360, March.
- Da Tian, 2014. "An entire space polynomial-time algorithm for linear programming," Journal of Global Optimization, Springer, vol. 58(1), pages 109-135, January.
- Jong-Shi Pang & Defeng Sun & Jie Sun, 2003. "Semismooth Homeomorphisms and Strong Stability of Semidefinite and Lorentz Complementarity Problems," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 39-63, February.
- Zhang, Xiang & Li, Lingfei & Zhang, Gongqiu, 2021. "Pricing American drawdown options under Markov models," European Journal of Operational Research, Elsevier, vol. 293(3), pages 1188-1205.
- Assalé Adjé, 2021. "Quadratic Maximization of Reachable Values of Affine Systems with Diagonalizable Matrix," Journal of Optimization Theory and Applications, Springer, vol. 189(1), pages 136-163, April.
- Shenglong Hu & Guoyin Li, 2021. "$${\text {B}}$$ B -subdifferentials of the projection onto the matrix simplex," Computational Optimization and Applications, Springer, vol. 80(3), pages 915-941, December.
- H. Xu & X. W. Chang, 1997. "Approximate Newton Methods for Nonsmooth Equations," Journal of Optimization Theory and Applications, Springer, vol. 93(2), pages 373-394, May.
- Pablos, Blanca & Gerdts, Matthias, 2021. "Substructure exploitation of a nonsmooth Newton method for large-scale optimal control problems with full discretization," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 190(C), pages 641-658.
- Lorenzo Stella & Andreas Themelis & Panagiotis Patrinos, 2017. "Forward–backward quasi-Newton methods for nonsmooth optimization problems," Computational Optimization and Applications, Springer, vol. 67(3), pages 443-487, July.
- Roman Sznajder & M. Seetharama Gowda, 1998. "Nondegeneracy Concepts for Zeros of Piecewise Smooth Functions," Mathematics of Operations Research, INFORMS, vol. 23(1), pages 221-238, February.
- L. W. Zhang & Z. Q. Xia, 2001. "Newton-Type Methods for Quasidifferentiable Equations," Journal of Optimization Theory and Applications, Springer, vol. 108(2), pages 439-456, February.
- Oleg Burdakov & Oleg Sysoev, 2017. "A Dual Active-Set Algorithm for Regularized Monotonic Regression," Journal of Optimization Theory and Applications, Springer, vol. 172(3), pages 929-949, March.
- J. M. Peng, 1997. "Global Method for Monotone Variational Inequality Problems with Inequality Constraints," Journal of Optimization Theory and Applications, Springer, vol. 95(2), pages 419-430, November.
- Michael Patriksson, 2004. "Sensitivity Analysis of Traffic Equilibria," Transportation Science, INFORMS, vol. 38(3), pages 258-281, August.
- J. H. Wu, 1998. "Long-Step Primal Path-Following Algorithm for Monotone Variational Inequality Problems," Journal of Optimization Theory and Applications, Springer, vol. 99(2), pages 509-531, November.
More about this item
Keywords
Iterative complexity; Linear complementarity problem; Fathi and Murty problems; Globalization; Harker and Pang algorithm; Line search; Newton-min algorithm; Nondegenerate matrix; P-matrix; Semismooth Newton method;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:eurjco:v:7:y:2019:i:4:d:10.1007_s13675-019-00116-6. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.