2 内罚函数法.ppt

* * 采用外罚函数法求到的近似最优解一般只近似地满 足约束条件,对于某些实际问题,这样的解是不能 被接受的. 内罚函数法 内罚函数法在这代中总是从可行点出发，并保持在 可行域内部进行搜索．因此，这种方法适用于不等 式约束最优化问题(10.1.4)． 内罚函数法 提出问题 内罚函数法 基本思想 问题(10.1.4)的可行域内部为 i 为了保持迭代点始终含于intS．引入另一种罚函数 罚函数G (x,r)的作用：对企图脱离可行域的点给予惩罚，相当于在 可行域的边界设置了障碍，不让迭代点穿越到可行域之外，因此也 称为障碍函数(barrier function). 内罚函数法 基本思想 两种常用的内罚函数形式 倒数障碍函数 对数障碍函数 问题(10.1.4) 当r 取值充分小时, 问题(10.1.4)转化为问题(10.2.1). 内罚函数法 内罚函数法实施中的问题和说明 在实际计算中，为了利用数值解法，问题(10.2.1)中的罚因子 的值必须取定且适中． (a) 若罚因子太大，则问题(10.2.1)的最优解可能远离问题(10.1.4) 的最优解，计算效率低； (b) 若罚因子过小，则会给问题(10.2.1)的求解带来计算上的 困难． (1)正数列； (2)单调递减趋近于零. 选取罚因子的一般策赂是取定数列 满足 问题(10.1.4) 内罚函数法 内罚函数法实施中的问题和说明 若问题(10.1.4)的最优解含于intS，则当 rk 取到一适当的值时， 问题(10.2.2)的最优解可以达到它； 若问题(10.1.4)的最优解落在 S 的边界上，则随着rk的减小， 问题(10.2.2)的最优解点列将向 S 边界上的该最优解逼近． 这种利用罚函数生成一系列内点逼近原约束问题最优解的方 法称为内罚函数法或SUMT内点法． 内罚函数法 算法步骤 Step 1 Step 2 Step 3 内罚函数法 举例 解 内罚函数法 举例 内罚函数法 举例 内罚函数法 算法说明 (1) 在上述内罚函数法中，问题(10.2.2)实际上仍是约束问题， 且约束条件看上去比问题(10.1.4)的约束条件更复杂．但是， 只要初始迭代点从可行域的内部选取，B(x)的障碍作用会自动 实现，保证问题(10.2.2)的最优解仍会含于int S. 因此，从计算 的角度来看，问题(10.2.2)可当做无约束问题来处理，仅有的 差别是在求极小过程中进行一维搜索时要适当控制步长，以 免迭代点脱离可行域而导致迭代提前结束． (2) 在内罚函数法中必须先知道一个初始内点x0∈int S.. 在实际问 题中，如果初始内点不能凭直观找出时，则必须给出一种求 初始内点的算法. (3) 为了利用内罚函数算法去求解一般的约束非线性最优化问 题, 可以把外罚函数法和内罚函数法结合起来, 形成所谓的混 合罚函数法，其适用范围更广.