广义方程若干算法的收敛性分析

发布时间：2019-04-27 01:58

【摘要】：本文主要研究广义方程的求解问题.对非光滑型广义方程,提出了精确和非精确的非光滑型算法,同时在一定的假设条件下,分析了算法的收敛性；对于光滑的欠定型广义方程,提出了广义高斯-牛顿迭代法,分析了其收敛性.主要内容分两章.在第二章中,结合文[64]中广义牛顿迭代法和文[50]中广义Jacobian-based牛顿迭代法,提出求解非光滑型广义方程的精确和非精确算法.这些算法都是用广义Jacobian矩阵代替Frechet导数得到的.在函数半光滑的条件下,对这两种算法我们分别给出不同的假设条件,证明了算法的半局部收敛性包括线性收敛,超线性收敛,平方收敛以及l+p阶收敛.进一步,在证明算法的局部收敛性结果的同时,给出了解的存在性和唯一性结果.最后,将精确方法应用于变分不等式问题,同时举出一个具体的例子进行数值实验,数值结果说明了精确算法的可行性和收敛性.在第三章中,我们考虑欠定型广义方程,即：函数的Frechet导数所对应的矩阵为行满秩的情形.由于在此情形下,用广义牛顿迭代法得不到唯一的迭代点,因此我们考虑广义高斯-牛顿迭代法,即求每一步迭代过程中范数最小的解.考虑到对大规模问题,用精确的算法求解范数最小的解时难度比较大,所以我们只考虑函数的Frechet导数所对应的矩阵为行满秩的情况.由于函数是光滑的,且我们是在有限维空间内进行研究,这就保证了迭代过程中广义方程范数最小解的存在性,同时也说明我们的算法是良定义的.在Frechet导数满足经典Lipschitz条件下,结合优函数的技巧,得到了Kantorovich型定理,同时得到了其局部收敛性结果.进一步,当函数条件减弱为满足L-平均的Lipschitz条件下,证明了算法的半局部收敛性和局部收敛性.最后,作为应用我们将结果应用于一些特殊情形,如：函数满足经典的Lipschitz条件时得到了Kantorovich型准则；函数满足γ-条件下的收敛结果和函数在解析条件下的Smale点估计定理.
[Abstract]:In this paper, the problem of solving generalized equations is studied. For non-smooth generalized equations, a precise and imprecise non-smooth algorithm is proposed. Under certain assumptions, the convergence of the algorithm is analyzed. In this paper, a generalized Gao Si-Newton iterative method is proposed for smooth underdefined generalized equations, and its convergence is analyzed. The main contents are divided into two chapters. In the second chapter, combined with the generalized Newton iterative method in [64] and the generalized Jacobian-based Newton iterative method in [50], the exact and imprecise algorithms for solving non-smooth generalized equations are proposed. These algorithms are obtained by using generalized Jacobian matrix instead of Frechet derivative. Under the condition that the function is semi-smooth, we give different hypotheses for the two algorithms, and prove that the semi-local convergence of the algorithm includes linear convergence, superlinear convergence, square convergence and l p-order convergence. Furthermore, while proving the local convergence result of the algorithm, the existence and uniqueness of the solution are given. Finally, the exact method is applied to variational inequality problem, and a concrete example is given to carry on the numerical experiment. The numerical results show the feasibility and convergence of the exact algorithm. In chapter 3, we consider an underdefined generalized equation where the matrix corresponding to the Frechet derivative of a function is a row full rank. In this case, the generalized Newton iteration method can not get the unique iteration point, so we consider the generalized Gao Si-Newton iteration method, that is, to find the minimum norm solution in each iteration process. For large-scale problems, the exact algorithm is difficult to solve the minimum norm solution, so we only consider the case where the matrix corresponding to the Frechet derivative of the function is a row-full rank. Because the function is smooth and we study it in the finite dimensional space, this ensures the existence of the minimum solution of the norm of the generalized equation in the iterative process, and also shows that our algorithm is well-defined. Under the condition that the Frechet derivative satisfies the classical Lipschitz condition, the Kantorovich type theorem is obtained and the local convergence result is obtained by combining the technique of the optimal function. Furthermore, the semi-local convergence and local convergence of the algorithm are proved when the function condition is weakened to satisfy the L-means Lipschitz condition. Finally, as an application, we apply the results to some special cases, such as: the Kantorovich type criterion is obtained when the function satisfies the classical Lipschitz condition; the convergence result of the function satisfies the 纬-condition and the Smale point estimation theorem of the function under the analytic condition.
【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O241.6

【相似文献】