内点法的基本原理以及举例计算

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

2、题，利用内点法进行求解时,构造惩罚函数得一般表达式为或者而对于m(X,r(k) f(X) r(k)(X,r k) f(X) rf (X)受约束于gu(X)1u i gu (X)mln gu(X)|f(X)u 10(u(X,rkmr k ln gu(X)u 11,2,k ,m)得最优化问题，其惩罚函数得一般形式为)f (X)'1i gu(X)(X,rk)f (X)mln gu(X)u 1式中,惩罚因子,就是递减得正数序列,rk1 L 0通常取r1.0,0.1,0.01,0.001 K。上述惩罚函数表达式得右边第二项，称为惩罚项，有时还称为障碍项。说明：当迭代点在可行域内部时，有 gu(X

3、) 0 ( u =1, 2, 3, 4,m),而r k 0,则惩罚项恒为正值，当设计点由可行域内部向约束边界移动时，惩罚项得值要急剧增大并趋向无穷大，于就是惩罚函数得值也急剧增大直至无穷大，起到惩罚得作用，使其在迭代过程中始终不会触及约束边界。2、内点法得迭代步骤(1 )取初始惩罚因子r(0)0 ,允许误差0 ；(2)在可行域D内取初始点，令 k 1 ；(3)构造惩罚函数(X,r从X(k 1)点出发用无约束优化方法求解惩罚函数kk(X,r )得极值点X (r )；(4 )检查迭代终止准则：如果满足X (rkX (rk1)1 10 5 10 7(X ,r k(X ,rk1)(X ,r k1 )2

4、 10 3 10 4k则停止迭代计算，并以 X (r )为原目标函数f (X)得约束最优解，否则转入下一步;根据情况，终止准则还可有如下得形式：|f(X k) f(X k1 )|或gu(1X)In |gu(X)|m kru 1k 1k05)取 r Cr ,XkX (r ), k k 1，转向步骤3)。递减系数C0.1 0.5，常取0、1，亦可取0、02。采用内点法应注意得几个问题:(1)初始点X 0得选取初始点X 0必须严格在可行域内，满足所有得约束条件，避免为约束边界上得点。如果约束条件比较简单， 可以直接人工输入； 若问题比较复杂，可采用随机数得方式产 生初始点X 0，具体方程参照复合形法

5、介绍。(2)关于初始惩罚因子r(0)得选择。实践经验表明，初始惩罚因子r(0)选得恰当与否,会显著地影响内点法得收敛速度，甚至解题得成败。0k若r值选得太小，则在新目标函数即惩罚函数(X,r )中惩罚项得作用就会很小，k这时求(X , r )得无约束极值，犹如原目标函数f(X)本身得无约束极值，而这个极值点又不大可能接近f(X)得约束极值点，且有跑出可行域得危险。相反，若r 0值取得过大，则开始几次构造得惩罚函数(X, r )得无约束极值点就会离约束边界很远，将使计算效率降低。可取r 0 150,但多数情况就是取r0 1。mI通常，当初始点X 0就是一个严格得内点时，则应使惩罚项r0在新目标U

6、1 gu(X 0)0于就是得函数(X,r )中所起得作用与原目标函数f(X )得作用相当,倘若约束区域就是非凸得且初始点0得取值可更小,约为上式算得值得0、10、5倍。开始内点法得计算程序框图例题：用内点法求minf (X) Xi22X2s、t、g（x） 1Xi(u=1,2,3,m得约束最优解。解：构造内点惩罚函数为（取0、 001)k(X,r ) f(X)mlnu 1gu(x)x；x；r(k) ln (1x1)用极值条件进行求解2x1(k)rX 12x20联立上式求得x*(r(k)11 2严，x；(r*) 02由于约束条件得限制，可得无约束极值点为X*(r(k)T1,1 2r(k)2当r(k

7、)取1, 0、1,0、01,宀0时，可得最优解为X1,0T，f(X )1编程方式实现：1. 惩罚函数function f=fun(x,r)f=x(1,1)A2+x(2,1)A2-r*log(x(1,1)-1);2. 步长得函数fun ctio n f=fh(x0,h,s,r)%h为步长%s为方向%r为惩罚因子x1=x0+h*s;f=fun (x1,r);3. 步长寻优函数fun ctio n h=fsearchh(x0,r,s)%用进退法确定高低高区间，利用黄金分割法进行求解h1=0;%步长得初始点st=0、001; %步长得步长h2=h1+st;f1=fh(x0,h1,s,r);f2=fh(

8、x0,h2,s,r);if f1>f2h3=h2+st;f3=fh(x0,h3,s,r);while f2>f3h仁 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);while f2>f3h1=h2;h2=h3; h3=h3+st;f2=f3;f3=fh(x0,h3,s,r);end end %得到高低高得区间 a=min(h1,h3); b=max(h1,h3); %利用黄金分割点法进行求解 h

9、1=1+0、382*(b-a); h2=1+0、618*(b-a); f1=fh(x0,h1,s,r); f2=fh(x0,h2,s,r);while abs(a-b)>0 、 0001if f1>f2a=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);4、迭代点得寻优函数 function f=fsearchx(x0,r,epson) x00=x0;m=length(x0); s=zeros(m,1); for i=1:ms(i)=1;h=fsearchh(x0,r,s); x1=x0+h*s;s(i)=0;x0=x1;endwhile norm(x1-x00)>epson x00=x1;for i=1:ms(i)=1;h=fsearchh(x0,r,s); x1=x0+h*s;s(i)=0;x0=x1;endendf=x1;5、主程序clearclcx0=2;2; % 给定初始点 r=1;c=0、 1;epson=0 、 001; x1=f