用外点法求解非线性约束最优化问题(共12页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
题目：用外点法求解非线性约本算法。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业

它的基本思路是通过目标函数加上惩罚项，这种惩罚体现在求解过程中，对于企图违反约束的那些迭代点，给与很大的目标函数值，迫使这一系列无约束问题的极小值点或者无限的向可行集逼近，或者一直保持在可行集内移动，直到收敛于原来约束问题的极小值点。
先考虑不含等式约束的非线性规划问题：
(1)
构造一个函数：
现把，则当时，，当时，，即有： (2)
再构造函数： 求解无约束极值问题：
(3)
若(3)有极小值，则由(2)可看出，这时应有，即点，因而不仅是问题(3)的最优解，同时也是原问题(1)的最优解。从而把约束极值问题(1)的求解变为无约束极值问题(3)的求解。
但是，用上述方法构造的函数在处不连续，更没有导数。为了求解方便，将该函数修改为：
修改后的函数在处的导数等于0，而且，对任意的t都连续。当时仍有，当时有：，而可改为：
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
或等价地：
问题(3)就变为： (4)
如果原规划问题(1)有最优解，则式(4)的最优解为原问题(1)的最优解或近似最优解。若,则是原问题的最优解，这是因为对任意的有：
即当时有：。即使,它也会相当接近于式(1)的约束条件的边界。这是因为：若为式(4)的最优解，则在M相当大的情况下，只可能使相当小，即相当靠近约束域R的边界。
函数称为罚函数，其中第二项称为惩罚项，M称为罚因子。
实际计算时，总是先给定一个初始点和初始罚因子，求解无约束极值问题(4)：，若其最优解，则它已是(1)的最优解；否则，以为新的起始点，加大罚因子，取，重新求解(4)。如此循环，或者存在某个，使得的最优解，即是式(1)的最优解；或者存在的一个无穷大序列：，随着M值的增大，罚函数中的惩罚项所起的作用增大，的最优解与约束域R的距离越来越近。当趋于无穷大时，最优点序列就从R的外部趋于R的边界点。即趋于原问题(1)最优解。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业

外点法的迭代步骤：
第1步 选取初始点，取(可取)，给定 >0，令k=1；
第2步 求无约束极值问题的最优解：，其中；
第3步 若对某一个有，则取，其中～10，置k=k+1,转(2)；否则，迭代终止，取。
由以上计算步骤可知，外点罚函数法迭代终止时，求得的是目标函数驻点的一个近似点。
三、题目举例
用外点罚函数法求解约束非线性规划问题：，.+
设初始取为=(1,1),迭代到满足允许误差=。
四、问题求解

构造罚函数
所以
对于不满足约束条件的点，有：
令：，得：
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业


得的解为：
即 ， (**)
首先进行第一次迭代
给定初始点，同时取代入公式(**)
得，
进行第二次迭代
取C=10，得代入公式(**)
得，
进行第三次迭代
代入公式(**)得，
进行第四次迭代
代入公式（**）得，
至此满足了精度要求，迭代终止，所得原问题的最优近似解为：

精选优质文档