基于自适应投影方法的伪单调变分不等式求解算法研究

0 下载量 95 浏览量 更新于2024-09-08 1 收藏 196KB PDF 举报
改进的求解伪单调变分不等式的自适应算法 本文提出了一个自适应投影方法来解决伪单调变分不等式(VI)问题,该方法具有新的搜索方向。该方法可以看作是He等人和Yan等人方法的扩展。我们证明了新的搜索方向的降低性质,从而保证了收敛性。在相对宽松的连续和伪单调条件下,我们证明了所提方法的全局收敛性。最后,我们提供了数值实验来illustrate所提方法的效率。 知识点一:伪单调变分不等式 伪单调变分不等式是指满足以下不等式的变分不等式: Ω ∈ *, x ∈ Ω, F(x, x*) ≥ 0 其中,Ω 是一个闭合凸集,F 是一个从 Ω 到 R 的函数。 知识点二:自适应投影方法 自适应投影方法是一种常用的求解变分不等式的方法。该方法的基本思想是通过迭代地投影来近似解。我们的方法引入了一个新的搜索方向,以提高收敛速度。 知识点三:降低性质 降低性质是指搜索方向的负梯度方向,它可以保证算法的收敛性。在我们的方法中,我们证明了新的搜索方向的降低性质,从而保证了收敛性。 知识点四:全局收敛性 全局收敛性是指算法在相对宽松的条件下收敛到最优解。在我们的方法中,我们证明了在相对宽松的连续和伪单调条件下,所提方法的全局收敛性。 知识点五:数值实验 数值实验是验证算法效率的重要方法。在我们的实验中,我们提供了多组实验结果,表明所提方法的效率和可靠性。 知识点六:变分不等式问题 变分不等式问题是指寻找一个向量 x,使得以下不等式成立: Ω ∈ *, x ∈ Ω, F(x, x*) ≥ 0 变分不等式问题广泛应用于优化问题、控制理论、经济学等领域。 知识点七:投影方法 投影方法是一种常用的求解变分不等式的方法。该方法的基本思想是通过迭代地投影来近似解。我们的方法引入了一个新的搜索方向,以提高收敛速度。 知识点八:伪单调函数 伪单调函数是指满足以下不等式的函数: F(x, x*) ≥ 0 伪单调函数广泛应用于优化问题、控制理论、经济学等领域。 知识点九:自适应算法 自适应算法是一种常用的优化算法。该算法可以根据问题的特点自动调整参数,以提高收敛速度和稳定性。我们的方法就是一种自适应算法,它可以根据问题的特点自动调整搜索方向和步长。
2012-11-29 上传
通过引入步长线性搜索,SQP算法在一定的假设条件下可以具有全局和局部超线性收敛性。然而在传统的SQP算法中,其二次规划子问题可能不相容,也就是子问题可行集是空集。 为了解决这个不足,备种技术相继被提出。特别是Panier和Tits在[9]中提出的一种可行SQP(FSQP,www.Yifanglunwen.com)算法,其保证山东科技大学硕士学位论文每次迭代都得到可行点,从而避免了上述问题。然而FSQP算法仍然要求每次迭代求解一个二次规划子问题,使得算法的复杂度和计算量仍然较大。在这种情况下便产生了对QP一free算法的研究,因为它的子问题只包含更易求解且计算量相对较小的线性系统。 1988年,panier,Tits和Herskovits在[10]中提出一种求解不等式约束优化lb]题的QP一free算法。该算法每次迭代只要求求解两个不同的线性方程组和一个线性平方问题。从那时起,QP一free算法成为非线性约束优化领域的研究热点之一。 QP一free算法具有SQP算法的一些优点,例如收敛速度快,算法结构简单等。此外它还有其它一些良好性质,例如其子问题通常只包含同系数的线性方程组,并且这些方程组在一定的假设条件下都是可解的。 然而,从理论和实用的角度来看,现有的QP一free算法仍存在两个主要问题有待解决。首先,为了确保局部快速收敛性并防止Maratos效应,严格互补松弛条件要被假设成立。然而在一般情况下,该条件很难被检验。 其次,求解等式和不等式约束优化问题的QP一free算法一般要求所有等式和有效不等式约束的梯度向量线性无关。但每当等式约束个数多于两个或者总约束个数超过空间维数时,该线性无关条件经常失效。在这种情况下,病态wachier一Biegler现象(参见[4』)就会在算法中发生。Tits等最近在〔2]中提出了一种双重内点算法,在保证收敛性质不受影响的前提下,该算法大大减弱了以上线性无关条件。 通过一段时间的发展,存在于早期QP一free算法中的一些缺点己经正在被解决。例如,起初的一些QP一free算法只能证明迭代点列的任一聚点是原问题的稳定点,在一些附加假设条件下,如所有稳定点是孤立的,才能证明这些聚点是原问题KKT点。 这个问题在Z.Gao,G.He和F.Wu的关于序列线性方程组算法的文章中得到解决。另外,一些QP一free算法的子问题线性系统在严格互补松弛条件不成立时可能出现病态。这将导致乘子逼近序列出现分歧以致收敛性失败。通过应用Fiseher一Burmeister非线性互补问题函数,H.Qi和L.Qi在【17]中对以前的QP一free算法做了有效的改进,使得迭代矩阵的一致非奇异性得到保证。在大多数QP一free算法中,其子问题的维数通常是满的。因此,当应用于大规模约束问题时,计算量会相应大大增加。Y.Yang和L.Qi在Faeehinei一FISeher一Kanzow KKT识别技术的基础上,http://www.yifanglunwen.com/post/46.html对不等式约束优化问题提出一种QP一free算法。 在其每次迭论文摘要代中,只有有效工作集中的约束参与计算。 在本文中,我们在Facchinei一Fischer一Kanzow KKT点有效约束集识别技术的基础上提出了三个具有强收敛性的QP一free算法。第一个是求解不等式约束优化问题(NLPI)的可行点算法。在该算法中我们引入如下有效约束集识别函数:。