A superlinear infeasible-interior-point affine scaling algorithm for LCP

被引：7

作者：

Monteiro, RDC

Wright, SJ

机构：

[1] UNIV ARIZONA,DEPT SYST & IND ENGN,TUCSON,AZ 85721

[2] ARGONNE NATL LAB,DIV MATH & COMP SCI,ARGONNE,IL 60439

来源：

SIAM JOURNAL ON OPTIMIZATION | 1996年 / 6卷 / 01期

关键词：

infeasible-interior-point methods; monotone linear complementarity problems; superlinear convergence;

D O I：

10.1137/0806001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present an infeasible-interior-point algorithm for monotone linear complementarity problems in which the search directions are affine scaling directions and the step lengths are obtained from simple formulae that ensure both global and superlinear convergence. By choosing the value of a parameter in appropriate ways, polynomial complexity and convergence with Q-order up to (but not including) two can be achieved. The only assumption made to obtain the superlinear convergence is the existence of a solution satisfying strict complementarity.

引用

页码：1 / 18

页数：18

共 50 条

[21] An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption
Muramatsu, M
Tsuchiya, T
ANNALS OF OPERATIONS RESEARCH, 1996, 62 : 325 - 355
[22] Superlinear convergence of affine-scaling interior-point Newton methods for infinite-dimensional nonlinear problems with pointwise bounds
Ulbrich, M
Ulbrich, S
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2000, 38 (06) : 1938 - 1984
[23] A primal-infeasible interior point algorithm for linearly constrained convex programming
Wang, Yanjin
Fei, Pusheng
CONTROL AND CYBERNETICS, 2009, 38 (03): : 687 - 704
[24] Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption
Heinkenschloss, M
Ulbrich, M
Ulbrich, S
MATHEMATICAL PROGRAMMING, 1999, 86 (03) : 615 - 635
[25] A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones
Yang, Ximei
Zhang, Yinkui
Liu, Hongwei
Pei, Yonggang
NUMERICAL ALGORITHMS, 2016, 72 (04) : 915 - 936
[26] A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones
Ximei Yang
Yinkui Zhang
Hongwei Liu
Yonggang Pei
Numerical Algorithms, 2016, 72 : 915 - 936
[27] Convergence of an infeasible interior-point algorithm from arbitrary positive starting points
Billups, SC
Ferris, MC
SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (02) : 316 - 325
[28] An infeasible interior-point arc-search algorithm for nonlinear constrained optimization
Makoto Yamashita
Einosuke Iida
Yaguang Yang
Numerical Algorithms, 2022, 89 : 249 - 275
[29] An infeasible interior-point arc-search algorithm for nonlinear constrained optimization
Yamashita, Makoto
Iida, Einosuke
Yang, Yaguang
NUMERICAL ALGORITHMS, 2022, 89 (01) : 249 - 275
[30] Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems
Sim, Chee-Khian
OPTIMIZATION METHODS & SOFTWARE, 2024,

← 1 2 3 4 5 →