An Efficient Algorithm for Linear Complementarity Problems

Li Pu Zhang; Ying Hong Xu

doi:10.4028/www.scientific.net/AMR.204-210.687

Paper Titles

Molecular Cloning and Phylogenetic Analysis of the Duck Enteritis Virus UL55 Gene
p.663

Effects of Antioxidant Enzymes of Ascorbate-Glutathione Cycle in Soybean (Glycine Max) Leaves Exposed to Ozone
p.672

A Fuzzy Trust Management Based on Outlier Identification for P2P
p.678

A Scaled Central Path for Linear Optimization
p.683

An Efficient Algorithm for Linear Complementarity Problems
p.687

Construction of Corruption Early Warning Mechanism
p.691

Nonlinear Optimization of Structure and Calibration for Scattered Triangulation Laser Displacement Measurement
p.695

Double Closed-Loop Control System of Bi-Direction Current Source Inverter
p.699

The Pruning Strategy of Decision Tree of SMT Assembling Quality Control Based on Data Mining
p.704

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 204-210An Efficient Algorithm for Linear Complementarity...

An Efficient Algorithm for Linear Complementarity Problems

Abstract:

Through some modifications on the classical-Newton direction, we obtain a new searching direction for monotone horizontal linear complementarity problem. By taking the step size along this direction as one, we set up a full-step primal-dual interior-point algorithm for monotone horizontal linear complementarity problem. The complexity bound for the algorithm is derived, which is the best-known for linear complementarity problem.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 204-210)

Pages:

687-690

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.204-210.687

Citation:

Cite this paper

Online since:

February 2011

Authors:

Li Pu Zhang, Ying Hong Xu

Keywords:

Complexity Bound, Full-Newton Step, Horizontal Linear Complementarity Problem, Interior-Point Algorithm

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] J.E. Bonnans and C.C. Gonzaga, Convergence of interior point algorithms for the monotone linear complementarity problem, Math. Oper. Res., 21(1)(1993), pp.1-15.

DOI: 10.1287/moor.21.1.1

Google Scholar

[2] S. Bellavia, B. Morini, Global convergence enhancement of classical line search interior point methods for MCPs, J. Comput. Appl. Math, 151(1)(2003), pp.171-199.

DOI: 10.1016/s0377-0427(02)00745-8

Google Scholar

[3] M. Kojima, N. Megiddo, T. Noma, A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science, Vol. 538, Springer-Verlag, New York, (1991).

DOI: 10.1007/3-540-54509-3

Google Scholar

[4] Y. Zhang, On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM J. Optim, 4(1)(1994), pp.208-227.

DOI: 10.1137/0804012

Google Scholar

[5] C. Roos, T. Terlaky, J. -Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach. John Wiley and Sons, Chichester, UK, 1997 (2nd Edition, Springer, 2006).

Google Scholar