内点法地基本原理以与举例计算

1、一、内点法基本原理内点法的特点是将构造的新的无约束目标函数惩罚函数定义在可行域内，并在可行域内求惩罚函数的极值点，即求解无约束问题时的探索点总是在可行域内部，这样，在求解内点惩罚函数的序列无约束优化问题的过程中，所求得的系列无约束优化问题的解总是可行解，从而在可行域内部逐步逼近原约束优化问题的最优解。内点法是求解不等式约束最优化问题的一种十分有效方法，但不能处理等式约束。因为构造的内点惩罚函数是定义在可行域内的函数，而等式约束优化问题不存在可行域空间，因此，内点法不能用来求解等式约束优化问题。对于目标函数为minf(X)s.t.gu(X)0（u=1,2,3,m）的最优化问题，利用内点法进行求解

2、时，构造惩罚函数的一般表达式为(X,r(k)f(X)r(k)m11gu(X)mm或者(X,rk)f(X)rklngu(X)f(X)rklngu(X)u1u1而对于f(X)受约束于gu(X)0(u1,2,m)的最优化问题，其惩罚函数的一般形式为(X,rk)f(X)rkm1u1gu(X)或(X,rk)f(X)rkmlngu(X)u1k-惩罚因子，是递减的正数序列，即式中，rr0r1r2rkrk10limrk0k通常取rk1.0,0.1,0.01,0.001,。上述惩罚函数表达式的右边第二项，称为惩罚项，有时还称为障碍项。说明：当迭代点在可行域内部时，有(X)0（，），而rk0，则惩罚guu=123

3、4m项恒为正值，当设计点由可行域内部向约束边界移动时，惩罚项的值要急剧增大并趋向无穷大，于是惩罚函数的值也急剧增大直至无穷大，起到惩罚的作用，使其在迭代过程中始终不会触及约束边界。2.内点法的迭代步骤（1）取初始惩罚因子r(0)0，允许误差0；（2）在可行域D内取初始点X0，令k1；（3）构造惩罚函数(X,rk)，从X(k1)点出发用无约束优化方法求解惩罚函数(X,rk)的极值点X(rk)；（4）检查迭代终止准则：如果满足X(rk)X(rk1)1105107或kk1(X,r)(X,r)2103104(X,rk1)则停止迭代计算，并以X(rk)为原目标函数f(X)的约束最优解，否则转入下一步；根

4、据情况，终止准则还可有如下的形式：f(Xk)f(Xk1)或r或mk11gu(X)rkmlngu(X)u15）取rk1Crk,X0X(rk),kk1，转向步骤3）。递减系数C0.10.5，常取0.1，亦可取0.02。采用内点法应注意的几个问题：（1）初始点0的选取X初始点X0必须严格在可行域内，满足所有的约束条件，避免为约束边界上的点。如果约束条件比较简单，可以直接人工输入；若问题比较复杂，可采用随机数的方式产生初始点X0，具体方程参照复合形法介绍。（2）关于初始惩罚因子r(0)的选择。实践经验表明，初始惩罚因子r(0)选的恰当与否，会显著地影响内点法的收敛速度，甚至解题的成败。若r0(X,rk

5、值选得太小，则在新目标函数即惩罚函数)中惩罚项的作用就会很小，这时求(X,rk)的无约束极值，犹如原目标函数f(X)本身的无约束极值，而这个极值点又不大可能接近f(X)的约束极值点，且有跑出可行域的危险。相反，若r0值取得过大，则开始几次构造的惩罚函数(X,rk)的无约束极值点就会离约束边界很远，将使计算效率降低。可取r0150，但多数情况是取r01。通常，当初始点X0是一个严格的内点时，则应使惩罚项m1r0在新目标函u1gu(X0)k0)的作用相当，于是得数(X,r)中所起的作用与原目标函数f(X0r0mf(X)11gu(X0)倘若约束区域是非凸的且初始点X0亦不靠近约束边界，则r0的取值可

6、更小，约为上式算得值的0.10.5倍。开始r(0),1,C在可行域内选取X(0)k=1X(k1)点出发求解：min(X,r(k),得X*(r(k)f(Xk)f(Xk1X(rk)X(rk1r(k1)Cr(k)X*X*(r(k)1f(X*)f(X*(r(k)停止kk1内点法的计算程序框图例题：用内点法求minf(X)x12x22s.t.g(X)1x10（u=1,2,3,m）的约束最优解。（取0.001）解：构造内点惩罚函数为kmklngu(X)x12x22r(k)ln(1x1)(X,r)f(X)ru1用极值条件进行求解2x1r(k)2x20 x1x10，x21联立上式求得*(k)112r(k)*(

7、k)0 x1(r)2，x2(r由于约束条件的限制，可得无约束极值点为12r(k)TX*(r(k)1,02当r(k)取1，0.1,0.01,0时，可得最优解为X*1,0T，f(X*)1编程方式实现：惩罚函数functionf=fun(x,r)f=x(1,1)2+x(2,1)2-r*log(x(1,1)-1);步长的函数functionf=fh(x0,h,s,r)%h为步长%s为方向%r为惩罚因子x1=x0+h*s;f=fun(x1,r);步长寻优函数functionh=fsearchh(x0,r,s)%利用进退法确定高低高区间，利用黄金分割法进行求解h1=0;%步长的初始点st=0.001;%步

8、长的步长h2=h1+st;f1=fh(x0,h1,s,r);f2=fh(x0,h2,s,r);iff1f2h3=h2+st;f3=fh(x0,h3,s,r);whilef2f3h1=h2;h2=h3;h3=h3+st;f2=f3;f3=fh(x0,h3,s,r);endelsest=-st;v=h1;h1=h2;h2=v;v=f1;f1=f2;f2=v;h3=h2+st;f3=fh(x0,h3,s,r);whilef2f3h1=h2;h2=h3;h3=h3+st;f2=f3;f3=fh(x0,h3,s,r);endend%得到高低高的区间a=min(h1,h3);b=max(h1,h3);%利

9、用黄金分割点法进行求解h1=1+0.382*(b-a);h2=1+0.618*(b-a);f1=fh(x0,h1,s,r);f2=fh(x0,h2,s,r);whileabs(a-b)0.0001iff1f2a=h1;h1=h2;f1=f2;h2=a+0.618*(b-a);f2=fh(x0,h2,s,r);elseb=h2;h2=h1;f2=f1;h1=a+0.382*(b-a);f1=fh(x0,h1,s,r);endendh=0.5*(a+b);迭代点的寻优函数functionf=fsearchx(x0,r,epson)x00=x0;m=length(x0);s=zeros(m,1);fori=1:ms(i)=1;h=fsearchh(x0,r,s);x1=x0+h*s;s(i)=0;x0=x1;endwhilenorm(x1-x00)epsonx00=x1;fori=1:ms(i)=1;h=fsearchh(x0,r,s);x1=x0+h*s;s(i)=0;x0=x1;endendf=x1;主程序clearclcx0=2;2;%给定初