势下降算法

势下降算法（potential reduction algorithm），理学-数学-运筹学-线性规划，20世纪80年代后期受卡玛卡算法影响而发展起来的一类内点算法，此类算法基本思想来源于对数罚函数算法。势下降算法主要分为原始势函数下降算法、对偶势函数下降算法和原始对偶势函数下降算法。这三种势函数下降算法的势函数分别为；其中原始势函数下降算法是1990年由C.C.贡萨加(Clovis Caesar Gonzaga,巴西学者,1944-09-06～)提出的，原始对偶势函数下降算法是1991年由叶荫宇(华裔美籍学者,1948～)提出的。对原始势函数下降算法而言，只要当前迭代点足够靠近中心路径，则直接求解该势函数的牛顿迭代步就可以使得势函数下降一个常数，且新的迭代点依然会足够靠近中心路径。对偶势函数下降算法具有类似的性质，但原始对偶势函数下降算法稍微复杂一些，原始对偶势函数的算法如下：假设当前迭代点为，则令；计算，若，则更新为；否则，,更新为，其中。至此就得到新的迭代点，理论上可以证明经过这样一次迭代后，原始对偶势函数至少会下降一个常数，算法具有次迭代复杂性。