非单调型变分不等式的投影算法

Projection-type algorithms of variational inequalities are often applied in the field of engineering, which include extragradient method, hyperplane projection method and proximal point method etc. Though do not require derivative or generalized derivative of the involved mapping, these methods require that the mapping be monotone or at least pseudomonotone with respect to the solution set for obtaining global convergence result. Recently, we improve the hyperplane projection method to variational inequalities without assuming any monotonicity on the mapping. As the proximal point method and extragradient method can achieve R-linear convergence, while the hyperplane projection method can only achieve sublinear convergence. Therefore, to devise algorithms of better convergence rate, we will investigate the proximal point method and extragradient method for nonmonotone-type variational inequalities. These algorithms apply to quasiconvex optimization having global optimal solution, so we will study conditions for the existence of global optimal solution of quasiconvex optimization, which is related to the celebrated Frank-Wolfe theorem. Thus, the Frank-Wolfe theorem for quasiconvex optimization and related problems will also be studied in this project.

变分不等式的投影算法是工程领域常用的方法，主要包括外梯度算法、超平面投影算法、临近点算法等。这些算法通常要求映射是单调的或者至少关于解集满足伪单调等单调型条件。对于映射不满足单调型条件的变分不等式，通常需要采取利用映射导数信息的牛顿型方法等。几种投影算法中，超平面投影算法已经被改进到适用于非单调型变分不等式。由于单调型变分不等式的外梯度算法和临近点算法比超平面投影算法有更好的收敛速率，为了研究非单调型变分不等式的有更好收敛率的投影算法，本项目将设计非单调型变分不等式的外梯度投影算法和临近点算法等投影算法，并研究其收敛性和收敛速率。此类方法能够适用于有全局最优解的拟凸优化问题，因此需要研究拟凸优化有全局最优解的充分条件。判断是否有全局最优解是Frank-Wolfe型定理的研究内容，我们将深入研究拟凸优化问题的Frank-Wolfe定理及相关问题。

变分不等式的算法主要包括两种类型，一是需要使用映射（广义）导数信息的牛顿型算法，二是不需要映射导数信息的投影型算法。尽管不需要映射的导数信息，投影型算法通常要求映射的某种单调性。单调映射最早由Minty在1962年提出，被Minty及Browder等著名学者在上世纪60年代深入研究，在偏微分方程和最优化领域有广泛应用。在变分不等式投影算法的发展历程中，对映射单调性的假设由强到弱分别是强单调、单调、伪单调、拟单调四种主要类型。最早的投影算法被著名学者Goldstein提出，其迭代序列的全局收敛性需要假设映射是强单调的。经过学者们深入研究，算法被不断改进，单调性被不断削弱，适用范围被不断拓展。目前伪单调变分不等式的投影算法已经非常成熟，表现在两方面，一是假设条件很弱，另一方面能够证明算法的全局收敛性，即算法所产生的迭代序列是收敛序列而且序列的极限是解。然而，对于范围更广的拟单调变分不等式的投影算法的研究很少，而且大都仅能证明算法所产生的迭代序列的每一个聚点是解，不能证明算法的全局收敛性。投影算法的类型较多，常见的有外梯度投影算法、半空间投影算法、临近点算法等。本项目改进了外梯度投影算法和临近点投影算法，使其既能够适用于拟单调变分不等式，又能够保持算法的全局收敛性。在分析算法的收敛率时，通常需要假设误差界条件。本项目研究了与误差界密切相关的度量正则性问题。度量正则性是一种仅依赖度量而定义的正则性，比传统通过导数定义的正则性更广泛，是最优化领域的重要研究课题，国内外很多著名优化专家都曾研究过度量正则性。本项目研究了度量正则性的扰动理论，改进了2015年发表在优化领域顶级刊物SIAM Journal on Optimization的结果，通过采用不同的证明方法，极大地削弱了其假设条件，但保持结论不削弱。