内点法

不念不忘少年蓝@ 2022-07-27 16:40 93阅读 0赞

# 文字理解 #

内点法属于约束优化算法。约束优化算法的基本思想是：通过引入效用函数的方法将约束优化问题转换成无约束问题，再利用优化迭代过程不断地更新效用函数，以使得算法收敛。  
内点法（罚函数法的一种）的主要思想是：在可行域的边界筑起一道很高的“围墙”，当迭代点靠近边界时，目标函数徒然增大，以示惩罚，阻止迭代点穿越边界，这样就可以将最优解“档”在可行域之内了。

# 数学定义 #

对于下面的不等式约束的优化问题：

min*f*(*x*),*x*∈*R**n*

*s*.*t**g**i*(*x*)≤0,*i*=1,2,...,*m*

利用内点法进行求解时，构造惩罚函数的一般表达式为

*φ*(*X*,*r*)=*f*(*X*)−*r*∑*i*=1*m*1*g**i*(*X*)

或者

*φ*(*X*,*r*)=*f*(*X*)−*r*∑*i*=1*m*ln\[−*g**i*(*X*)\]

# 算法步骤 #

1.  取初始惩罚因子*r*(0)>0，允许误差*ϵ*>0；
2.  在可行域*D*内选取初始点*X*(0)，令*k*=1；
3.  构造惩罚函数*φ*(*X*,*r*(*k*))，从*X*(*k*−1)点出发用无约束优化方法求惩罚函数*φ*(*X*,*r*(*k*))的极值点(*X*∗,*r*(*k*))；
4.  检查迭代终止准则：如果满足
    
    ∥*X*∗*r*(*k*)−*X*∗*r*(*k*−1)∥≤*ϵ*1=10−5−10−7
    
    或者
    
    ∥*φ*(*X*∗,*r*(*k*))−*φ*(*X*∗,*r*(*k*−1))*φ*(*X*∗,*r*(*k*−1))∥≤*ϵ*2=10−3−10−4
    
    则停止迭代计算，并以(*X*∗,*r*(*k*))作为原目标函数*f*(*X*)的约束最优解，否则转入下一步；
5.  取*r*(*k*\+1)=*c**r*(*k*)，*X*(0)=*X*∗*r*(*k*)，*k*=*k*\+1，转向步骤3。递减系数*c*=0.1−0.5，通常取0.1。

# 内点惩罚函数法特点及其应用 #

*  惩罚函数定义于可行域内，序列迭代点在可行域内不断趋于约束边界上的最优点（这就是称为内点法的原因）
 *  只适合求解具有不等式约束的优化问题

# 内点法求解案例 #

用内点法求下面约束优化问题的最优解，取迭代初始*X*0=\[0,0\]T，惩罚因子的初始值*r*0=1，收敛终止条件∥*X**k*−*X**k*−1∥≤*ε*，*ε*=0.01

min*f*(*X*)=*x*21\+*x*21−*x*1*x*2−10*x*1−4*x*2\+60

s.t.*g*(*X*)=*x*1\+*x*2−8≤0

1.  构造内惩罚函数：*φ*(*X*,*r*)=*x*21\+*x*21−*x*1*x*2−10*x*1−4*x*2\+60−*r*ln(*x*1\+*x*2−8)
2.  用解析法求内惩罚函数的极小值

∇*φ*(*X*,*r*)=\[2*x*1−*x*2−10−*r**x*1\+*x*2−82*x*2−*x*1−4−*r**x*1\+*x*2−8\]

令∇*φ*(*X*,*r*)=0得：2*x*1−*x*2−10−*r**x*1\+*x*2−8=02*x*2−*x*1−4−*r**x*1\+*x*2−8=0

解得：

*X*∗1(*r*)=\[13\+9\+2*r*√29\+9\+2*r*√2\]T

*X*∗2(*r*)=\[13−9\+2*r*√29−9\+2*r*√2\]T