A sequential linear programming algorithm for solving monotone variational inequalities
A sequential linear programming algorithm for solving monotone variational inequalities
复制标题
DOI：
10.1137/0327064
复制
发表时间：
1989-11
影响因子：
2.2
通讯作者：
P. Marcotte;J. Dussault
中科院分区：
文献类型：
--
作者：
P. Marcotte;J. Dussault
将牛顿算法应用于强单调变分不等式，实现了局部二次收敛。本文介绍了如何对基本牛顿法进行修改，以得到一种通过监测与变分不等式有关的“间隙函数”的单调递减来保证其全局收敛的算法。每一次迭代都是在原-对偶变量空间中求解一个线性规划和一个线性搜索。收敛不依赖于强单调性。然而，在强单调性和几何稳定性的假设下，隐式识别解的活动约束集，并实现二次收敛。
Applied to strongly monotone variational inequalities, Newton’s algorithm achieves local quadratic convergence. In this paper it is shown how the basic Newton method can be modified to yield an algorithm whose global convergence can be guaranteed by monitoring the monotone decrease of the “gap function” associated with the variational inequality. Each iteration consists in the solution of a linear program in the space of primal-dual variables and of a linesearch. Convergence does not depend on strong monotonicity. However, under strong monotonicity and geometric stability assumptions, the set of active constraints at the solution is implicitly identified, and quadratic convergence is achieved.