【作者】 许鸿儒；

【导师】 曾金平；

【作者基本信息】 湖南大学 ， 应用数学， 2009， 博士

【摘要】 变分不等式与互补问题广泛应用于阐述与研究机械,工程,物理,金融,最优控制数学模型以及交通运输中出现的各种平衡模型等。因此,研究其快速数值解法是十分有意义的。近几十年来,变分不等式与互补问题在数值解法方面取得了巨大的进展,这方面的研究成果层出不穷。本文讨论了求解几类变分不等式与互补问题的有效算法。实际中出现的科学问题往往计算规模大,而且精度要求高。这就要求我们能够设计出新的更有效的算法来解决这些问题。随着并行计算机的出现,并行计算成为解决这类问题的一种很重要的手段。多重分裂方法是并行求解线性或非线性方程组的重要数值计算方法之一。其特点是将原问题转化为几个子问题进行并行求解。本文将这类方法推广到求解对称仿射二阶锥互补问题(SOCCP)。我们在进行矩阵分裂时考虑了矩阵的特殊结构,诸如稀疏性,块结构性。在每一次迭代过程中,每个处理器分别处理一个由分裂得到的子问题,然后再将每个处理器得到的结果加权相加作为下一次迭代的初始值。在子问题的求解中,我们使用了似MAOR方法。数值结果表明多重分裂方法用于求解对称仿射SOCCP是十分有效的。区域分解法是上世纪八十年代崛起的新算法。其思想是将计算区域分为若干子区域,将原问题的求解转化为相应子区域上子问题的求解。它是求解变分不等式与互补问题的一类重要算法。本文探讨了求解带M—函数的非线性互补问题的两水平加性Schwarz算法。这种方法基于某种判断准则,将计算区域分为两个子区域。一个子区域上含有障碍子问题,而在另一个子区域上仅需求解非线性方程组。我们得到算法的有限步收敛性结论。数值实验表明该算法是十分有效的。根据不同的解的等价最优性条件,对于一般T—单调算子的单边及双边障碍问题,我们提出了不同的有效集算法。这两种算法的本质都是基于某种策略,将区域分解为有效和非有效的两个部分。然后在非有效集上求解一个简化的非线性方程组。和PSOR及Schwarz算法不同的是,有效集算法不需要求解额外的线性或非线性子问题。我们将这类算法和PSOR及Schwarz算法做了比较,算例表明有效集算法是非常高效的。近年来,变分不等式已经开始向各个方向推广,出现了诸如广义变分不等式,混合变分不等式,广义似变分不等式等。其中很重要的一类推广是变分不等式系统。我们考虑了一类广义似变分不等式系统(SGVLIP)的数值解,提出和SGVLIP相关的逼近问题,证明了逼近问题解的存在性。基于这些逼近问题,构造了求解SGVLIP的算法,证明了SGVLIP解的存在唯一性以及算法的收敛性。针对一类非线性变分不等式系统(SNVI),我们研究了其相关辅助问题,建立了辅助问题解的存在性定理。基于这些辅助问题,构造了求解SNVI的算法,证明了SNVI解的存在性以及算法的收敛性。最后,我们讨论了Banach空间中混合非线性变分不等式系统(SMNVI)的数值算法。我们先引入适定次可微泛函的η—逼近映射的概念,利用η—逼近映射的性质,提出了求解SMNVI的一些迭代算法,并证明了算法的收敛性。更多还原

【Abstract】 Variational inequality and complementarity problems have a lot of applications in many fields, such as mechanism, engineering, physics, finance, optimal control theory mathematical models and equilibrium models arised from traffic transportation. Hence, it is meaningful to study the efficient numerical methods for solving variational inequality and complementarity problem. In the past decades, great progress has been made in the study of numerical algorithms and this kind of research emerges in endlessly. In this thesis, we construct and analyze some efficient numerical methods for solving variational inequality and complementarity problem.Many problems arised in science and engineering are often large scale, and require high precision. Hence, we need to design some new and more efficient algorithms for such problems. With the use of parallel computer, it is a very important way to solve those problems in parallel. Multisplitting method is an important theoretical tool for solving linear or nonlinear equations in parallel. Its feature is to decompose a large scale problem into several subproblems and solve those subproblems in parallel. In Chapter 2, we extend this method for solving symmetrical affine second order cone complementarity problem (SOCCP). The multisplitting method we constructed for SOCCP exploits particular features of matrices such as the sparsity and the block structure. In each iteration of the method, each processor deals with a subproblem obtained from one matrix splitting respectively. After that, the results from each processor are summed with weight as the initial value for the next iteration. Moreover, we consider an MAOR-like method to solve the subproblems. Numerical results showed that multisplitting is effective for solving symmetrical affine SOCCP.Domain decomposition method was developed in 1980s. Its main point is to divide the domain into several small subdomains, and to solve the subproblems in related subdomains. It is a very important numerical method for solving variational inequality and complementarity problem. In Chapter 3, we develop and analyze a two-level additive Schwarz method for nonlinear complementarity problem (NCP) with an M-function. Based on certain criterion, this method divides the domain into two subdomains which contain obstacle subproblem and nonlinear equations subproblem, respectively. The advantage of this method is that it offers the possibility of making use of fast nonlinear solvers for the genuinely nonlinear obstacle problems. We prove that this method converges in finite number of iterations. Numerical results show that the method is efficient.According to different optimality conditions of the solution, we study different active set strategies for unilateral and bilateral obstacle problems with a T-monotone operator in Chapter 4. Based on certain criterions, active set strategies can decompose the index set into active set and inactive set, then solve a reduced nonlinear system in inactive set. Contrary to the PSOR and Schwarz methods, no additional linear or nonlinear subproblem solvers are needed. In numerical experiments, we compare active set strategies with PSOR and Schwarz method, and numerical results indicate that active set strategies are valid.In recent years, variational inequality has been extended to various directions, such as generalized variational inequality, mixed variational inequality, generalized variational-like inequality and so on. One of the most important extension is system of variational inequalities. In Chapter 5, we consider a system of generalized variational-like inequalities problems (SGVLIP). Firstly, some approximate problems related to SGVLIP are proposed. The existence theorem of solution of approximate problems is obtained. Then algorithms based on these approximate problems are constructed for the SGVLIP and the convergence of the algorithms are also discussed. In Chapter 6, we study a kind of system of nonlinear variational inequalities (SNVI) and its related auxiliary problems in real Hilbert space. Existence theorems for SNVI and the auxiliary problems are established. Furthermore, by exploiting existence theorem, algorithms for SNVI are constructed and the convergence of the algorithm is discussed. In Chapter 7, we consider the numerical solution of system of mixed nonlinear variational inequalities (SMNVI) in Banach space. The definition ofη—proximal mapping for a proper subdifferentiable functional is introduced. Using the properties ofη—proximal mapping, some iterative algorithms for solving SMNVI are constructed and convergence theorem is also established.更多还原