Studies On Algorithms Of Complementarity Problems And Their Applications In Mechanics

The distinguishing feature of a complementarity problem is the set of complementarity conditions, which require that the product of two nonnegative quantities should be zero. Over more than thirty years, this class of problems has become increasingly popular in many fields, such as mathematical programming, economics and engineering. Applications from the field of economics include general Walrasian equilibrium, spatial price equilibria, and game-theoretic models. In engineering, complementarity problems arise in contact mechanics, fracture mechanics, elasto-plastic problems, obstacle and free boundary problems, hydrodynamic lubrication, optimal control problems and traffic equilibrium problems. That is, all the above practical problems can be formulated as complementarity problems and solved by proper algorithms. Economics and mechanics are the two major areas among the numerous applications of complementarity problemsThe present dissertation is mainly devoted to studying algorithms of complementarity problems and their applications in mechanics. The motivation of this thesis is based the following considerations:â—‡ Practical mechanics problems may not satisfy certain restrictive conditions for some existing algorithms for complementarity problems, though they might be very efficient for some mathematical problems. Therefore, on one hand, it is necessary to make a few modifications to some existing algorithms so that they are suitable for solving mechanics problems. On the other hand, we need to develop algorithms directly oriented to characteristics of mechanics problems.â—‡ Applications of modern algorithms in mechanics dropped far behind the algorithmic developments of complementarity problems. We wish the introduction of some new algorithms to solving mechanics problems should play the role of both enriching the solution tools of mechanics and extending the ranges of complimentarity problems, whereby arousing the further interest of researchers from the two fields.In the study of complementarity algorithms, we restrict ourselves to two major classes of them: equation system based algorithms and interior-point algorithms. We wish to develop effective algorithms for practical problems in mechanics, in particularkeeping large-scale and nonlinear complementarity problems in mind.Two smoothing Newton-type algorithms and two smoothing iterative algorithms are given in Chapter 2. In the first two algorithms, the complementarity problem is reformulated to non-smooth (non-differentiable) equations using so-called NCR-functions, and then solved by applying Newton-type methods to the smoothened equations. The third algorithm is a smooth iterative method based on an equivalent fixed-point format of the complementarity problem. The forth algorithm is the same as the third one with an addition of finite termination criteria. Although the latter two algorithms have only linear rate of convergence, they are especially suitable for large-scale and sparse problems, with features of simple formula, small storage, sparsrty preservation and easy implementation.Two improved interior point algorithms are proposed in Chapter 3. They are designed based on the modifications to the standard perturbed system of primal-dual interior-point algorithms from two different angles. The first is based on the algebraically equivalent transformation to the standard centering equation xs = e. We discovered that the Newton equations used by Peng Jiming et al. in their long-step interior point algorithms could be derived by a power transformed perturbed system. Our approach of algebraically equivalent transformation is much simpler than the one proposed by Peng et al. in their algorithms. Inspired by this observation, an interior point algorithm based on power transformation is developed. Another interior algorithm is to employ the "homogenizing" effect of min-max function, where the standard centering equation is replaced by the optimality condition of a new proximity measure function. A self-adjusting mechanism is added to the new pert...