内点惩罚函数法

内点罚函数法报告人：杨中源马明亮指导老师：邹斌内点罚函数法基本思想根据原约束优化问题，构造的一个新的定义在可行域内的无约束目标函数，并在可行域内求解新的目标函数（内点惩罚函数）的极值点，而这个点就是原问题的近似解。算法特点其突出特点是：求解时的探索点始终保持在可行域内。数学描述对于如下不等式约束优化问题其中是连续函数可行域为)(),(xgxfi内点罚函数法数学描述根据内点罚函数法的思想，建新的定义域内的无约束目标函数B(x)的两种最重要的形式：和r通常取很小的正数。这样，当x趋近可行域边界时，G(x,r)趋近+∞,此时的x必不是极小值点。否则，r*B(x)趋近于0，G(r,x)的值近似于f(x)。通过这种方式，内点罚函数法就可以保证搜索过程在可行域S内进行，此时的罚函数B(x)又称障碍函数。这里也可以看出，内点罚函数法只适用于不等式约束的情况，对于等式约束，障碍函数无法发挥作用。同理内惩法也取不到位于边界上的解，而只能不断接近。数学描述通过以上推导，利用内点罚函数法，原有不等式约束优化问题就转化为一个在定义域内的无约束优化问题。惩罚因子（障碍因子）的选取r越小，G(x,r)的最优解越接近原问题的最优解，但与外点法类似，r太小将给G(x,r)的计算带来很大的困难，因此仍采用序列无约束极小化方法（SUMT），取r为一个严格单减且趋于零的序列使r随迭代过程递减计算步骤收敛性内点罚函数收敛性定理：设一个非等式约束优化问题中，可行域内部intS非空，且存在最优解，又设对每一个，在intS内存在极小点，并且内点罚函数法产生的全局极小点序列存在子序列收敛到，则是问题的全局最优解。证明：kr),(krxG}{)(kxxx内点罚函数发收敛性内点罚函数法收敛性内点罚函数法收敛性收敛性收敛性内点罚函数法与外点罚函数法的比较1.外点法的初始点可以任意取，内点法的初始点必须取在可行域内2.外点法对等式约束也适用，内点法对等式约束不适用，因为此时没有内点存在。3.外点法只有迭代到最后才能得到可行解；而内点法每一步得到的点都是可行解，这在实际问题中很方便，随时停止迭代，都可以得到原问题的一个近似最优解。4.外点法和内点法对非凸规划均适用。5.内点法与外点法收敛速度的快慢，与罚因子的选取有关，而罚因子只能根据经验来选取。