Solving Obstacle Problem Based on Potential-Reduction Interior Point Algorithm

Abstract:

This text studies a kind of obstacle problem. Combining with difference principle, we transform the original problem into monotone linear complementarity problem, and propose a novel method called potential-reduction interior point algorithm for monotone linear complementarity problem. We establish global and finite convergence of the new method. The reliability and efficiency of the algorithm is demonstrated by the numerical experiments of standard linear complementarity problems and the examples of obstacle problem with free boundary.

• Periodical: Applied Mechanics and Materials (Volumes 29-32)
• Pages: 725-731
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.29-32.725
• Online since: August 2010
• Authors: Long Quan Yong
• Keywords: Monotone Linear Complementarity Problem, Obstacle Problem, Potential-Reduction Interior Point Algorithm

References

[1] S. C Billups and K.G. Murty: Complementarity Problems, Journal of Computational and Applied Mathematics. Vol. 124 (2000), pp.303-318.

DOI: 10.1016/s0377-0427(00)00432-5

[2] R.W. Cottle, J. S Pang, and R E Stone: The Linear Complementarity Problems, Academic Press (1992).

[3] Karmarkar. N. A new polynomial-time Algorithm for linear programming, Combinatorica. Vol. 4 (1984), pp.373-395.

DOI: 10.1007/bf02579150

[4] M. Kojima, N. Megiddo, T. Noma, A. Yoshise: A Primal-dual Interior Point Algorithm for Linear Programming, in: N. Megiddo (Ed. ), Progress in Mathematical Programming; Interior Point Related Methods, Springer Verlag, New York (1989), pp.29-47.

DOI: 10.1007/978-1-4613-9617-8_2

[5] N. Megiddo: Pathways to the optimal set in linear programming, in: N. Megiddo (Ed. ), Progress in Mathematical Programming; Interior Point and Related Methods, Springer Verlag, New York (1989), pp.158-313.

DOI: 10.1007/978-1-4613-9617-8_8

[6] M. Kojima, S. Mizuno, A. Yoshise: A Polynomial-time Algorithm for a Class of Linear Complementarity Problems, Math. Prog. Vol. 44 (1989), pp.1-26.

DOI: 10.1007/bf01587074

[7] M. Kojima, N. Megiddo, S. Mizuno: A Primal-dual Infeasible Interior Point Algorithm for Linear Programming, Math. Prog. Vol. 61 (1993), pp.261-280.

DOI: 10.1007/bf01582151

[8] Y. Zhang: On the Convergence of a Class of Infeasible-Interior-Point Methods for the Horizontal Linear Complementarity Problem, SIMA J. Optim. Vol. 4 (1994), pp.208-227.

DOI: 10.1137/0804012

[9] S.J. Wright: An Infeasible-Interior-Point Algorithm for Linear Complementarily Problems, Math. Prog. Vol. 67 (1994), pp.29-52.

[10] J V Burke, and S Xu: The Global Linear Convergence of a Non-Interior Path Following Algorithm for Linear Complementarity Problems, Mathematics of Operations Research. Vol. 23 (1998), pp.719-734.

DOI: 10.1287/moor.23.3.719

[11] C. Geiger, and C. Kanzow: On the Resolution of Monotone Complementarily Problems, Comput. Optim. Appl. Vol. 15 (1996), pp.5-173.