A feasible directions algorithm for nonlinear complementarity problems and applications in mechanics. (English) Zbl 1274.90427
Summary: Complementarity problems are involved in mathematical models of several applications in engineering, economy and different branches of physics. We mention contact problems and dynamics of multiple bodies systems in solid mechanics. In this paper we present a new feasible direction algorithm for nonlinear complementarity problems. This one begins at an interior point, strictly satisfying the inequality conditions, and generates a sequence of interior points that converges to a solution of the problem. At each iteration, a feasible direction is obtained and a line search performed, looking for a new interior point with a lower value of an appropriate potential function. We prove global convergence of the present algorithm and present a theoretical study about the asymptotic convergence. Results obtained with several numerical test problems, and also application in mechanics, are described and compared with other well known techniques. All the examples were solved very efficiently with the present algorithm, employing always the same set of parameters.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 74S30 | Other numerical methods in solid mechanics (MSC2010) |
| 74Pxx | Optimization problems in solid mechanics |
Keywords:
feasible direction algorithm; interior point algorithm; nonlinear complementarity problems; variational formulations in mechanicsReferences:
| [1] | Arora JS (2004) Introduction to optimum design, 2nd edn. Academic, London |
| [2] | Baiocchi C, Capelo A (1984) Variational and quasivariational inequalities. Applications to free-boundary problems. Wiley, Chichester · Zbl 0551.49007 |
| [3] | Bazaraa MS, Shetty CM (1979) Theory and algorithms. Nonlinear programming. Wiley, New York |
| [4] | Chen C, Mangasarian OL (1996) A class of smoothing functions for nonlinear and mixed complementarity problems. Comput Optim Appl 5:97–138 · Zbl 0859.90112 · doi:10.1007/BF00249052 |
| [5] | Chen X, Ye Y (2000) On smoothing methods for the P_0 matrix linear complementarity problem. SIAM J Optim 11:341–363 · Zbl 0994.65077 · doi:10.1137/S1052623498335080 |
| [6] | Christensen PW, Klarbring A , Pang JS, Stroömberg N (1998) Formulation and comparison of algorithms for frictional contact problems. Int J Num Meth Eng 42:145–173 · Zbl 0917.73063 · doi:10.1002/(SICI)1097-0207(19980515)42:1<145::AID-NME358>3.0.CO;2-L |
| [7] | Crank J (1984) Free and moving boundary problems. Oxford University Press, New York · Zbl 0547.35001 |
| [8] | Dennis JE, Schnabel RB (1996) Numerical methods for unconstrained optimization and nonlinear equations. SIAM, Philadelphia · Zbl 0847.65038 |
| [9] | Fathi Y (1979) Computational complexity of LCPs associated with positive definite symmetric matrices. Math Program 17:335–344 · Zbl 0421.90072 · doi:10.1007/BF01588254 |
| [10] | Ferris MC, Kanzow C (2002) Complementarity and related problems: a survey. Handbook of applied optimization. Oxford University Press, New York, pp 514–530 |
| [11] | Ferris MC, Pang JS (1997) Engineering and economic applications of complementarity problems. SIAM Rev 39:669–713 · Zbl 0891.90158 · doi:10.1137/S0036144595285963 |
| [12] | Fischer A (1992) A special newton-type optimization method. Optim 24:269–284 · Zbl 0814.65063 · doi:10.1080/02331939208843795 |
| [13] | Geiger C, Kanzow C (1996) On the resolution of monotone complementarity problems. Comput Optim Appl 5:155–173 · Zbl 0859.90113 · doi:10.1007/BF00249054 |
| [14] | Harker PT (1998) Accelerating the convergence of the diagonal and projection algorithms for finite-dimensional variational inequalities. Math Program 41:29–59 · Zbl 0825.49019 · doi:10.1007/BF01580752 |
| [15] | Herskovits J (1982) Développement d’une méthode númerique pour l’Optimisation non linéaire. Dr. Ing. Thesis, Paris IX University, INRIA-Rocquencourt (in English) |
| [16] | Herskovits J (1986) A two-stage feasible directions algorithm for nonlinear constrained optimization. Math Program 36:19–38 · Zbl 0623.90070 · doi:10.1007/BF02591987 |
| [17] | Herskovits J (1995) A view on nonlinear optimizaton. In: Herskovits J (ed) Advances in structural optimization. Kluwer Academic, Dordrecht, pp 71–117 · Zbl 0856.73045 |
| [18] | Herskovits J (1998) A feasible directions interior point technique for nonlinear optimization. J Optim Theory Appl 99(1):121–146 · Zbl 0911.90303 · doi:10.1023/A:1021752227797 |
| [19] | Herskovits J, Santos G (1998) Feasible arc interior point algorithm for nonlinear optimization. In: Fourth world congress on computational mechanics, (in CD-ROM), Buenos Aires, June–July 1998 |
| [20] | Herskovits J, Leontiev A, Dias G, Santos G (2000) Contact shape optimization: a bilevel programming approach. Struct Multidisc Optim 20:214–221 · doi:10.1007/s001580050149 |
| [21] | Herskovits J, Mappa P, Goulart E, Mota Soares CM (2005) Mathematical programming models and algorithms for engineering design optimization. Comput Methods Appl Mech Eng 194(30–33):3244–3268 · Zbl 1092.74035 · doi:10.1016/j.cma.2004.12.017 |
| [22] | Hock W, Schittkowski K (1981) Test example for nonlinear programming codes. Springer, Berlin Heidelberg New York · Zbl 0452.90038 |
| [23] | Jiang H, Qi L (1997) A new nonsmooth equations approach to nonlinear complementarity problems. SIAM J Control Optim 35(1):178–193 · Zbl 0872.90097 · doi:10.1137/S0363012994276494 |
| [24] | Kanzow C (1994) Some equation-based methods for the nonlinear complementarity problem. Optim Methods Softw 3:327–340 · doi:10.1080/10556789408805573 |
| [25] | Kanzow C (1996) Nonlinear complementarity as unconstrained optimization. J Optim Theory Appl 88:139–155 · Zbl 0845.90120 · doi:10.1007/BF02192026 |
| [26] | Kinderlehrer D, Stampacchia G (1984) An introduction to variational. Oxford University Press, New York · Zbl 0457.35001 |
| [27] | Leontiev A, Huacasi W (2001) Mathematical programming approach for unconfined seepage flow problem. Eng Anal Bound Elem 25:49–56 · Zbl 0990.76067 · doi:10.1016/S0955-7997(00)00067-9 |
| [28] | Leontiev A, Huacasi W, Herskovits J (2002) An optimization technique for the solution of the signorini problem using the boundary element method. Struct Multidisc Optim 24:72–77 · doi:10.1007/s00158-002-0215-1 |
| [29] | Mangasarian OL (1973) Equivalence of the complementarity problem to a system of nonlinear equations. SIAM J Appl Math 31:89–92 · Zbl 0339.90051 · doi:10.1137/0131009 |
| [30] | Mangasarian OL, Solodov MV (1993) Nonlinear complementarity as unconstrainede and constrained minimization. Math Program (Serie B) 62:277–297 · Zbl 0813.90117 · doi:10.1007/BF01585171 |
| [31] | Murphy FH, Sherali HD, Soyster AL (1982) A mathematical programming approach for determining oligopolistic market equilibrium. Math Program 24:92–106 · Zbl 0486.90015 · doi:10.1007/BF01585096 |
| [32] | Murty KG (1988) Limear complementarity, linear and nonlinear programming. Sigma series in applied mathematics, vol 3. Heldermann, Berlin |
| [33] | Petersson J (1995) Behaviourally constrained contact force optimization. Struct Multidisc Optim 9:189–193 · doi:10.1007/BF01743968 |
| [34] | Qi L, Sun D (1998) Nonsmooth equations and smoothing newton methods. Technical Report, School of Mathematics, University of New South Wales, Sydney · Zbl 0957.65042 |
| [35] | Subramanian PK (1993) Gauss-Newton methods for the complementarity problem. J Optim Theory Appl 77:467–482 · Zbl 0792.90082 · doi:10.1007/BF00940445 |
| [36] | Tanoh G, Renard Y, Noll D (2004) Computational experience with an interior point algorithm for large scale contact problems. Optimization Online |
| [37] | Tin-Loi F (1999a) On the numerical solution of a class of unilateral contact structural optimization problems. Struct Multidisc Optim 17:155–161 |
| [38] | Tin-Loi F (1999b) A smoothing scheme for a minimum weight problem in structural plasticity. Struct Multidisc Optim 17:279–285 · doi:10.1007/BF01207004 |
| [39] | Tseng P (1997) An infeasible path-following method for mono tone complementarity problems. SIAM J Optim 7:386–402 · Zbl 0882.90123 · doi:10.1137/S105262349427409X |
| [40] | Vanderplaats G (1999) Numerical optimization techniques for engineering design, 3rd edn. VR&D, Colorado Springs · Zbl 0613.90062 |
| [41] | Wright SJ (1997) Primal-dual interior-point methods. SIAM, Philadelphia · Zbl 0863.65031 |
| [42] | Yamashita N, Fukushima M (1995) On stationary points of the implicit lagrangian for nonlinear complementarity problems. J Optim Theory Appl 84:653–663 · Zbl 0824.90131 · doi:10.1007/BF02191990 |
| [43] | Yamashita N, Dan H, Fukushima M (2004) On the identification of degenerate indices in the nonlinear complementarity problem with the proximal point algorithm. Math Programming 99:377–397 · Zbl 1098.90077 · doi:10.1007/s10107-003-0455-x |
| [44] | Xu S (2000) The global linear convergence of an infeasible non-interior path-following algorithm for complemenarity problems with uniform P-functions. Math Program 87:501–517 · Zbl 0989.90125 · doi:10.1007/s101070050009 |
| [45] | Zouain N, Herskovits J, Borges LA, Feijóo RA (1993) An iterative algorithm for limit analysis with nonlinear yield functions. Int J Solids Struct 30(10):1397–1417 · Zbl 0773.73032 · doi:10.1016/0020-7683(93)90220-2 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
