2023年内点法.docx

《2023年内点法.docx》由会员分享，可在线阅读，更多相关《2023年内点法.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023年内点法 内点法在求解非线性问题中的应用 1、内点法求解线性规划问题 本科时学过运筹学，线性规划是运筹学中的一个重要分支，研究较早，发展较快，应用广泛，方法也比较成熟。单纯形法是求解线性规划问题的通用方法，我认为用单纯形法在求解线性规划问题时是很有效的。单纯形法的基本思想是在顶点上找到最优解：先找出一个基本可行解，即可行域的一个极点，判断是否是最优解，若是，则问题就得到解决；否则，则要设法寻找另一个极点，使新的极点的目标值优于前一个极点。因为基本可行解的个数有限，所以经过有限次迭代，一定可以得到问题的最优解。如果问题无最优解也可以用这种方法判别。 用单纯形法求解线性规划问题所需的迭代次

2、数主要取决于约束条件的个数。用单纯形法求解线性规划问题可能会出现极端情况，就是对于具有n个变量的问题，要最多寻找2n-1次才可获得最优解。当变量太多时，2n-1呈现指数型，数值太大，此时用单纯形法求解线性规划问题计算时间太长，计算量太大。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，很方便也很实用。 但是单纯形法不是很经济的算法，于是就有数学家提出了改进的单纯形法。 为了改进单纯形法每次迭代中积累起来的进位误差，美国数学家G.B.丹齐克提出改进单纯形法。改进单纯形法的基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，

3、再由此确定检验数。这样做不但可以减少迭代中的累积误差，提高计算精度，而且还减少了在计算机上的存储量。 单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，检验它的判别数是否全部非负。如果所有的判别数非负，基可行解就是最优解。如果存在负判别数，则迭代到另一个基可行解。单纯形法迭代过程中始终保持基解的可行性，但不能保证对偶规划解的可行性。而对偶单纯形法则是从满足对偶可行性条件出发，通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。在保持对偶可行性的前提下，一旦基解成为可行解，也就是最优解了。 单纯形法及其变型一直是实际应用中极其有效的计算方法。但是

4、，在实际计算中单纯形法有不少缺点。随着约束条件和变量数目的增加，迭代次数也迅速增加, 在最坏情况下, 单纯形法的迭代次数会按指数上升, 收敛很慢。1979 年, Khachian 提出了线性规划问题的第一个多项式时间算法椭球法, 取得了理论上的重大突破。但是由于受有限精度计算的限制, 椭球法的应用效果还不能与单纯形法相比拟。 现代内点理论的基本思想是：起点在“宇宙中心”，用梯度法从起点寻找一个下降方向，因为从起点走出去第一步效果最好，则设法使每一次走出去都是第一步（用非线性的投影变换有回到新的宇宙中心，就不会碰到边界）。Karmarkar 提出的内点法是建立在单纯形结构之上的,但与单纯形法沿着

5、可行域边界寻优不同,内点法从初始内点出发, 沿着最速下降方向, 从可行域内部直接走向最优解。内点法是在可行域内部寻优, 对于大规模线性规划问题, 当约束条件和变量数目增加时, 内点法的迭代次数变化较少。内点法是一种具有多项式时间复杂性的线性规划算法，其收敛性和计算速度均优于单纯形法，计算时间比单纯形法快50倍。内点法在形式上与经典障碍法等价，而且对于线性、非线性问题可以统一解法。 近年来的内点算法主要有三大类： （1）投影尺度法 ,它是Karmarkar算法的原型。这个方法要求问题具有特殊的单纯形结构和最优目标值为零, 在实际计算过程中, 需要用复杂的变换将实际问题转换为这种标准形式。因此,

6、投影尺度法在实际中应用较少。 （2）仿射尺度法，这是一种已经比较成熟和广泛的算法。目前原仿射尺度法和对偶仿射尺度法虽然应用较多, 但这两种方法的多项式时间复杂性还不能从理论上得到证明。 （3）路径跟踪法,又称为跟踪中心轨迹法。这种方法将对数壁垒函数与牛顿法结合起来应用到线性规划问题, 并且已经从理论上证明具有多项式时间复杂性。路径跟踪法收敛迅速, 鲁棒性强, 对初值的选择不敏感,现在已经被推广应用到二次规划领域,正被进一步发展为从复杂性角度研究一般非线性规划的内点算法,是目前最有发展潜力的一类内点算法。 内点法在收敛性、计算速度等方面具有单纯形法无法替代的优势, 因此人们纷纷采用仿射尺度法和路

7、径跟踪法研究各种大规模、复杂的线性规划问题, 并将其推广应用于求解各种二次规划和非线性规划问题。近年来, 仿射尺度法和路径跟踪法在求解电力系统优化问题中也得到广泛的应用, 如水库优化调度、安全约束的经济调度、安全控制、状态估计、静态电压稳定分析、实时电价计算、无功优化和最优潮流等。但投影尺度法的应用相对较少。 2、非线性最优化算法 无约束最优化方法主要有最速下降法、Newton法、共轭方向法、拟Newton法（如DFP算法、BFGS法）、Powell法等。 最速下降法的本质是用线性函数去近似目标函数因迭代路线呈锯齿形，收敛速度很慢，不是好的实用算法。Newton法有很快的收敛速度，但它只是局部

8、收敛的，只有当初始点充分接近极小点时，才能保证收敛。但若初始点离极小点较远，则不能保证迭代点列收敛，甚至不能保证目标函数单调下降。还有一个严重的问题是，即使Newton法收敛，也不一定受了到极小点。Newton法的优点和缺点都很突出，它本身并不很实用，但是可以在保留优点的情况下对Newton法进行改进，如Gill-Murrar稳定Newton法和信赖域算法。共轭方向法的收敛速度介于最速下降法和Newton法之间，既能克服最速下降法的慢收敛性，又避免了Newton法的计算量大和具有局部收敛性的缺点，是比较有效的算法。共轭方向法中的共轭梯度法存储量小，可以用来求解大规模无约束问题。 在约束最优化问

9、题上，由于无约束问题的求解目前已经有许多有效的算法，人们就设法将约束问题的求解转化为无约束问题的求解。具体来说，就是根据约束的特点，构造某种“惩罚”函数，然后把它加到目标函数中去，将约束问题的求解转化为一系列无约束问题的求解。所谓“惩罚”，就是给予那些在无约束问题求解过程中试图“违反”约束的迭代点给予很多的目标函数值，对于极小化而言就是一种惩罚了，它可以迫使一系列无约束问题的极小点或者无限地靠近可行域，或者一直保持在可行域内移动，直到迭代点列收敛到原约束问题的极小点。 这方面有不少算法，比如外罚函数法、内罚函数法、乘子法。如果有了求无约束问题的好算法和程序，则用外罚函数法求解约束问题是很方便的

10、。但是，外罚函数法有两个主要缺点。它的每个近似最优解往往不是可行解，这是某些实际问题所不能接受的。另外，如果要求有好的收敛性，则罚因子取得越大越好，而罚因子的增大将造成增广目标函数的Hee矩阵的条件数增大，趋向于病态，给无约束问题的求解增加了很大的难度，甚至无法求解。 内罚函数法为了使迭代点总是可行点，在可行域的边界上筑起一道很高的“围墙”，当迭代点靠近边界时，目标函数值突然增大，以示惩罚，阻止迭代点穿越边界，把最优解“挡”在可行域内。这种方法只能适用于不等式约束问题，并且要求可行域的内点集非空，否则每个可行点都是边界点，都要被加上无穷大的惩罚，这时候惩罚失去了意义，使方法无效。 内罚函数法要

11、求初始点为可行域的内点，需要相当的工作量，它也不能处理等式约束。外罚函数法适于解既含等式约束又含不等式约束的优化问题，初始点可以使可行域外部的点，但却不能保证近似最优解是可行的。人们往往将内罚函数法和外罚函数法结合起来使用，得到混合罚函数法。乘子法则不要求罚因子趋于无穷大，克服了罚函数法的病态性质，它比罚函数法优越，收敛速度要快得多，是求解约束最优化问题的最好算法之一。 而直接处理约束优化问题的算法有投影梯度法和简约梯度法等，后来简约梯度法发展成广义简约梯度法，成为求解一般非线性规划问题的最有效的算法之一。简约梯度法是将线性规划的单纯形法推广到带线性约束的非线性规划问题上。它利用线性约束条件将

12、问题的某些变量用一组独立变量表示，可以大大降低问题的维数，并且利用简约梯度直接构造出下降可行方向，然后进行线性搜索，逐步地逼近问题的最优解。 3、内点法求解非线性规划问题 现代内点法解非线性规划问题的基本思想是，把原问题转换为只有等式约束和简单的不等式约束的等价问题，求等价问题的一阶最优性条件，对一阶最优性条件进行扰动，并Newton法解非线性的扰动KKT条件，得到搜索方向。基于扰动KKT条件的原始对偶内点算法在处理大规模非线性规划问题时，比对数障碍函数的内点算法更有效。它具有多项式时间复杂性，迭代次数不随问题规模的增大而显著增加。而且它对初始点的要求不严格，具有二次收敛性和鲁棒性。 具有多项

13、式时间复杂性的Karmarkar 内点法提出若干年来, 不但将线性规划领域的研究工作推向一个新的高潮, 而且对于非线性优化问题的处理也显示出强大的生命力和广阔的应用前景。目前, 仿射尺度算法和路径跟踪法在求解电力系统各种优化问题中已取得很大进展。尤其是路径跟踪法具有收敛性好、计算迅速、鲁棒性好、处理病态问题能力强等优点, 在求解电力系统优化问题中得到广泛的应用。 在最优化方法中，路径跟踪法被直接应用于求解非线性规划模型。路径跟踪法可以应用于无功调度问题的非线性规划模型，对于大规模电力系统, 路径跟踪法所需的迭代次数很少, 而且在事故情况下, 只要以原优化值为初始点, 经过几次迭代算法仍会重新收

14、敛,由此可知路径跟踪法具有良好的数值稳定性。路径跟踪法处理不等式约束的能力，超过了求解非线性规划模型的牛顿算法,这是因为牛顿法中的不等式约束处理必须引入启发式的试迭代, 影响了计算速度和数值稳定性。 影响路径跟踪法性能的几个主要因素有初始点的确定、迭代步长的选取和壁垒参数的调整等。对于初始点的确定，各变量的初值只要在各自的取值范围之内即可启动算法, 并不需要繁琐的求解初始内点过程。一般是原变量、对偶变量各自采用统一的步长, 或者全部的原变量和对偶变量均采用同一个步长。上述两种方法虽然可行, 但由于不同物理特性和量纲的各变量在优化过程中所起作用和变化轨迹各不相同, 因此可以对按不同物理含义分类的原变量、对偶变量分别取迭代步长。在求解线性规划模型时,壁垒参数与对偶间隙之间存在着严格的数学关系,但在求解非线性规划模型时, 只能建立起壁垒参数与补偿间隙之间的关系式。 内点法 距点法作图步骤 三点法 五点法教案 真题考点法规 行政法重点法条 西点法则读后感 数字盘点法院工作 公务员重点法条 不动点法,特征根法总结