A continuous deformation algorithm for variational inequality problems on polytopes
Tóm tắt
A continuous deformation algorithm is proposed for solving a variational inequality problem on a polytopeK. The algorithm embeds the polytopeK intoK× [0, ∞) and starts by applying a variable dimension algorithm onK× {0} until an approximate solution is found onK× {0}. Then by tracing the path of solutions of a system of equations the algorithm virtually follows a path of approximate solution inK× [0, ∞). When the path inK× [0, ∞) returns to level 0, i.e.,K× {0}, the variable dimension algorithm is again used until a new approximate solution is found onK× {0}. The setK× [0, ∞) is triangulated so that the approximate solution on the path improves the accuracy as the level increases. A contrivance for a practical implementation of the algorithm is proposed and tested for some test problems.
Tài liệu tham khảo
E. Allgower and K. Georg, “Simplicial and continuation method for approximating fixed points and solutions of systems of equations,”SIAM Review 22 (1980) 28–85.
M.N. Broadie and B.C. Eaves, “A variable rate refining triangulation,”Mathematical Programming 38 (1987) 161–202.
Y. Dai, G. van der Laan, A.J.J. Talman and Y. Yamamoto, “A simplicial algorithm for the nonlinear stationary point problem on an unbounded polyhedron,”SIAM Journal on Optimization 1 (1991) 151–165.
L.C.W. Dixon, “Conjugate directions without linear searches,”Journal of the Institute of Mathematics and its Applications 11 (1973) 317–328.
T.M. Doup,Simplicial Algorithms on the Simplotope, Lecture Notes on Economics and Mathematical System (Springer, Berlin, 1989).
T.M. Doup and A.J.J. Talman, “A new variable dimension simplicial algorithm to find equilibria in the product space of unit simplices,”Mathematical Programming 37 (1987) 319–355.
B.C. Eaves, “Homotopies for computation of fixed points,”Mathematical Programming 3 (1972) 1–22.
B.C. Eaves,A Short Course in Solving Equations with PL Homotopies, SIAM-AMS Proceedings No. 9 (1976) pp. 73–143.
B.C. Eaves and R. Saigal, “Homotopies for computation of fixed points on unbounded regions,”Mathematical Programming 3 (1972) 225–237.
M. Kojima, “An introduction to variable dimension algorithms for solving systems of equations,” in: E.L. Allgower, K. Glashoff and H.-O. Peitgen, eds.,Numerical Solution of Nonlinear Equations (Springer, Berlin, 1981) pp. 199–237.
M. Kojima and Y. Yamamoto, “Variable dimension algorithms: basic theory, interpretations and extensions of some existing methods,”Mathematical Programming 24 (1982) 177–215.
H.W. Kuhn, “Approximate search for fixed points,” in:Computing Methods in Optimization Problems 2 (Academic Press, New York, 1969).
G. van der Laan and A.J.J. Talman, “A restart algorithm for computing fixed points without an extra dimension,”Mathematical Programming 17 (1979) 74–84.
G. van der Laan and A.J.J. Talman, “A new subdivision for computing fixed points with a homotopy algorithm,”Mathematical Programming 19 (1980) 78–89.
S. Shamir, “A homotopy fixed point algorithm with an arbitrary integer refinement factor,” preprint, Stanford University (Stanford, CA, 1979).
L.S. Shapley, “On balanced games without side payments,” in: T.C. Hu and S.M. Robinson, eds.,Mathematical Programming (Academic Press, New York, 1973) pp. 261–290.
A.J.J. Talman and Y. Yamamoto, “A simplicial algorithm for stationary point problems,”Mathematics of Operations Research 14 (1989) 383–399.
M.J. Todd,The Computation of Fixed Points and Applications, Lecture Notes in Economics and Mathematical Systems (Springer, New York, 1976).
Y. Yamamoto, “Fixed point algorithms for stationary point problems,” in: M. Iri and K. Tanabe, eds.,Mathematical Programming, Recent Developments and Applications (Kluwer Academic Publishers, Dordrecht, The Netherlands, 1989) pp. 283–307.
Z.F. Yang, K.Z. Chen and Z.L. Liang, “A simplicial homotopy algorithm for computing zero points on polytopes,” preprint, Department of Applied Mathematics, Xidian University (Xi'an, China, 1989).