论文部分内容阅读
一直以来,最优化理论在运筹学中扮演着重要的角色,其被广泛的运用于经济、军事、国防等领域。实际生活中,很多问题可以归结为最优化问题,其中分裂可行性问题是一类比较常见的优化问题,其源于工程实践,后在生物学、医学、军事、图像恢复等领域有着重要的运用。研究员针对该问题提出了一些有效可行的算法。在这些算法中,投影算法在构造和可行性方面表现优异,因此其被广泛用于求解分裂可行性问题。本文通过对传统算法进行深入研究,提出了三种新的投影算法,改善了算法的执行效率并拓宽算法的应用范围。 首先,由于变分不等式问题可以等价为分裂可行性问题这一特性,本文提取求解变分不等式的修正外梯度算法思想,并应用于求解分裂可行性问题。进一步改进了不精确投影算法的步长,并证明了新投影算法全局收敛。新的算法有下面几个特点:不用求解矩阵的逆和最大特征值、减少算法求解步骤、降低了迭代时间。除此之外,在处理大规模问题时,新算法较旧算法效率提高了10%左右。 其次,本文将算法的求解范围从单集合推广到多集合。对算法步长作了修正,并用Armijo-like搜索方法所获取的可变步长替代固定步长,从而不用计算矩阵的范数和特征值。实验结果表明,新算法可以减少迭代的次数,提高收敛的效率。 最后,本文将解决分裂可行性问题的算法扩展到Hilbert空间,证明了其操作可行性,通过从上一步求出的步长附近选取下一步步长,减小了计算量,提高了算法执行效率。对Hilbert空间下的多集合分裂可行性问题在实际生活的应用作了进一步推广。