×

zbMATH — the first resource for mathematics

Implementation of a continuation method for normal maps. (English) Zbl 0873.90093
Summary: This paper presents an implementation of a nonsmooth continuation method of which the idea was originally put forward by J. C. Alexander and others. We show how the method can be computationally implemented and present numerical results for variational inequality problems in up to 96 variables.

MSC:
90C30 Nonlinear programming
49J40 Variational inequalities
49J52 Nonsmooth analysis
Software:
GAMS; PATH Solver
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J.C. Alexander, The topological theory of an embedding method, in: H. Wacker, ed.,Continuation Methods (Academic, New York, 1978) 37–68.
[2] J.C. Alexander, R.B. Kellogg, T.-Y. Li and J.A. Yorke, Piecewise smooth continuation, manuscript (1979).
[3] J.C. Alexander, T.-Y. Li and J.A. Yorke, Piecewise smooth homotopies, in: B.C. Eaves, F.J. Gould, H.-O. Peitgen and M.J. Todd, eds.,Homotapy Methods and Global Convergence (Plenum, New York, 1983) 1–14 · Zbl 0519.55001
[4] E.L. Allgower and K. Georg,Numerical Continuation Methods: An Introduction (Springer, Berlin, 1990). · Zbl 0717.65030
[5] E.L. Allgower and K. Georg, Continuation and path following,Acta Numerica 2 (1993) 1–64. · Zbl 0792.65034 · doi:10.1017/S0962492900002336
[6] E.L. Allgower and K. Georg, Numerical path following, in: P.G. Ciarlet and J.L. Lions, eds.,Handbook of Numerical Analysis (North-Holland, Amsterdam) to appear. · Zbl 0792.65034
[7] S.C. Billups, Algorithms for complementarity problems and generalized equations, Ph.D. Dissertation, Computer Sciences Department, University of Wisconsin-Madison (Madison, WI, 1995).
[8] A. Brooke, D. Kendrick and A. Meeraus,GAMS: A User’s Guide, Release 2.25. The Scientific Press Series (Boyd and Fraser, Danvers, MA, 1992).
[9] S.P. Dirkse and M.C. Ferris, A pathsearch damped Newton method for computing general equilibria. Mathematical Programming Technical Report 94-03, Computer Sciences Department, University of Wisconsin-Madison (Madison, WI, 1994). · Zbl 0868.90012
[10] S.P. Dirkse and M.C. Ferris, The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems.Optimization Methods and Software 5 (1995) 123–156. · doi:10.1080/10556789508805606
[11] B.C. Eaves, A short course in solving equations with PL homotopies, in: R.W. Cottle and C.E. Lemke, eds.,Nonlinear Programming, SIAM-AMS Proceedings, Vol 9, (American Mathematical Society, Providence, RI, 1976). · Zbl 0343.47048
[12] F. Facchinei, A. Fischer and C. Kanzow, A semismooth Newton method for variational inequalities: Theoretical results and preliminary numerical experience, preprint (1996). · Zbl 0980.90101
[13] F. Facchinei and C. Kanzow, A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems,Mathematical Programming 76 (1997) 493–512 (this issue). · Zbl 0871.90096
[14] P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic, London, 1981).
[15] T. Hansen, On the approximation of a competitive equilibrium, Ph.D. Dissertation, Yale University (New Haven, CT, 1968).
[16] T. Hansen and T.C. Koopmans, On the definition and computation of a capital stock invariant under optimization.Journal of Economic Theory 5 (1972) 487–583. · Zbl 0266.90018 · doi:10.1016/0022-0531(72)90052-X
[17] P.T. Harker and J.S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications.Mathematical Programming 48 (1990) 161–220. · Zbl 0734.90098 · doi:10.1007/BF01582255
[18] M. Kojima and Y. Yamamoto, Variable dimension algorithms: Basic theory, interpretations and extensions of some existing methods,Mathematical Programming 24 (1982) 177–215. · Zbl 0509.90070 · doi:10.1007/BF01585103
[19] M. Kojima and S. Shindo, Extensions of Newton and quasi-Newton methods to systems ofPC 1 equations.Journal of the Operations Research Society of Japan 29 (1986) 352–374. · Zbl 0611.65032
[20] J.G. MacKinnon, A technique for the solution of spatial equilibrium models,Journal of Regional Science 16 (1976) 293–307. · doi:10.1111/j.1467-9787.1976.tb00976.x
[21] J.W. Milnor,Topology from the Differentiable Viewpoint (University of Virginia, Charlottesville, VA, 1965). · Zbl 0136.20402
[22] J.J. Moré and S.J. Wright,Optimization Software Guide. Frontiers in Applied Mathematics, Vol. 14 (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1993). · Zbl 0830.65050
[23] J. Outrata and J. Zowe, A Newton method for a class of quasi-variational inequalities,Computational Optimization and Applications 4 (1995) 5–21. · Zbl 0827.49007 · doi:10.1007/BF01299156
[24] J.S. Pang, Solution differentiability and continuation of Newton’s method for variational inequality problems over polyhedral sets,Journal of Optimization Theory and Applications 66 (1990) 121–135. · Zbl 0681.49011 · doi:10.1007/BF00940536
[25] J.S. Pang, Newton’s method for B-differentiable equations,Mathematics of Operations Research 15 (1990) 311–341. · Zbl 0716.90090 · doi:10.1287/moor.15.2.311
[26] J.S. Pang and Z. Wang, Embedding methods for variational inequality and nonlinear complementarity problems, Technical Report 5-26. Department of Mathematical Sciences, The Johns Hopkins University (Baltimore, MD, 1991).
[27] K. Park, New continuation methods for nonlinear programming by converting optimality conditions into nonlinear equations, Technical Report 89-12. Department of Industrial Engineering, University of Wisconsin-Madison (Madison, WI, 1989).
[28] K. Park, Stability and sensitivity analysis based multiple-path continuation method for nonlinear optimization, Technical Report 89-13, Department of Industrial Engineering, University of Wisconsin-Madison (Madison, WI, 1989).
[29] L. Qi and J. Sun, A nonsmooth version of Newton’s method,Mathematical Programming 58 (1993) 353–367. · Zbl 0780.90090 · doi:10.1007/BF01581275
[30] D. Ralph, On branching numbers of normal manifolds,Nonlinear Analysis: Theory, Methods and Applications 22 (1994) 1041–1050. · Zbl 0830.57014 · doi:10.1016/0362-546X(94)90066-3
[31] D. Ralph, Global convergence of damped Newton’s method for nonsmooth equations, via the path search,Mathematics of Operations Research 19 (1994) 352–389. · Zbl 0819.90102 · doi:10.1287/moor.19.2.352
[32] S.M. Robinson, Generalized equations, in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming: The State of the Art. Bonn 1982 (Springer, Berlin, 1983).
[33] S.M. Robinson, Normal maps induced by linear transformations,Mathematics of Operations Research 17 (1992) 691–714. · Zbl 0777.90063 · doi:10.1287/moor.17.3.691
[34] S.M. Robinson, Newton’s method for a class of nonsmooth functions,Set Valued Analysis 2 (1994) 291–305. · Zbl 0804.65062 · doi:10.1007/BF01027107
[35] S.M. Robinson, A reduction method for variational inequalities, preprint, Department of Industrial Engineering, University of Wisconsin-Madison (1995).
[36] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[37] H. Scarf (with the collaboration of T. Hansen),The Computation of Economic Equilibria (Yale University, New Haven, CT, 1973). · Zbl 0311.90009
[38] H. Sellami, A continuation method for normal maps, Ph.D. Dissertation, Departments of Mathematics and Industrial Engineering, University of Wisconsin-Madison (Madison, WI, 1994).
[39] H. Sellami, A homotopy continuation method for solving generalized equations, preprint (1995). · Zbl 0842.68121
[40] H. Sellami and S.M. Robinson, A continuation method for normal maps, Technical Report 93-8, Department of Industrial Engineering, University of Wisconsin-Madison (Madison, WI, 1993). · Zbl 0873.90093
[41] H. Sellami and S.M. Robinson, Homotopies based on nonsmooth equations for solving nonlinear variational inequalities, in: G. Di Pillo and F. Giannessi, eds., Nonlinear Optimization and Applications (Plenum, New York, 1996). · Zbl 0991.90134
[42] B. Xiao and P.T. Harker, A nonsmooth Newton method for variational inequalities, I: Theory,Mathematical Programming 65 (1994) 151–194. · Zbl 0812.65048 · doi:10.1007/BF01581695
[43] B. Xiao and P.T. Harker, A nonsmooth Newton method for variational inequalities, II: Numerical results,Mathematical Programming 65 (1994) 195–216. · Zbl 0812.65049 · doi:10.1007/BF01581696
[44] N. Yamashita and M. Fukushima, Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems,Mathematical Programming 76 (1997) 469–491 (this issue). · Zbl 0872.90102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.