内点法

内点法

文字理解

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

数学定义

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

minf(x),x∈Rn

s.tgi(x)≤0,i=1,2,...,m

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

φ(X,r)=f(X)−r∑i=1m1gi(X)

或者

φ(X,r)=f(X)−r∑i=1mln[−gi(X)]

算法步骤

取初始惩罚因子r(0)>0，允许误差ϵ>0；在可行域D内选取初始点X(0)，令k=1；构造惩罚函数φ(X,r(k))，从X(k−1)点出发用无约束优化方法求惩罚函数φ(X,r(k))的极值点(X∗,r(k))；检查迭代终止准则：如果满足∥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)的约束最优解，否则转入下一步；取r(k+1)=cr(k)，X(0)=X∗r(k)，k=k+1，转向步骤3。递减系数c=0.1−0.5，通常取0.1。

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

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

内点法求解案例

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

minf(X)=x21+x21−x1x2−10x1−4x2+60

s.t.g(X)=x1+x2−8≤0

构造内惩罚函数：φ(X,r)=x21+x21−x1x2−10x1−4x2+60−rln(x1+x2−8)用解析法求内惩罚函数的极小值

∇φ(X,r)=[2x1−x2−10−rx1+x2−82x2−x1−4−rx1+x2−8]

令∇φ(X,r)=0得：2x1−x2−10−rx1+x2−8=02x2−x1−4−rx1+x2−8=0

解得：

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

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

∵g(X∗1(r))>0

∴ 舍去X∗1(r)

∵φ(X,r)为凸函数

∴ 无约束优化问题的最优解为X∗(r)=X∗2(r)=[13−9+2r√29−9+2r√2]T

求最优解

当r0=1时，X∗(r0)=(4.84172.8417)T，∥X∗(r0)−X0∥=5.6140>ε

当r1=0.1时，X∗(r1)=(4.98342.9834)T，∥X∗(r1)−X∗(r0)∥=0.2004>ε

当r2=0.01时，X∗(r2)=(4.99832.9983)T，∥X∗(r2)−X∗(r1)∥=0.0211>ε

当r3=0.01时，X∗(r3)=(4.99982.9998)T，∥X∗(r3)−X∗(r2)∥=0.0021<ε

即X∗(r3)为最优解

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。