惩罚函数的内点法

惩罚函数的内点法

2013-2014 (1) 专业课程实践论文

内点法

一、算法理论

内点法总是从可行域的内点出发，并保持在可行域内进行搜索，因此这种方法适用于只有不等式约束条件的问题

内点法据图计算步骤： 1．给定初x0intD，允许误差0，初始参数r10缩小系数

（0,1），k1；

（k-1）2．以x为初始点，求解问题

Min f(x)rkB(x) S.t. xint D

3．若rkB(x(k))则停，得近似解x(k)；否则令rk1rk,kk1回2.

二、算法框图

求满足 g ( x (0) ( 0) i)0,i1,2,.....,m的x

0k；0；

从x出发，求 G(x(k1)m(k) i1,)minG(x,)f(x)i(gi (x)) max{gi(x(k1))}~0i (k1) x(k)a0(x(k1)x)x(k) f(x(k1))~f(x(k)) 改变约束~1 ||x(k1)-x(k) ||~1 输出停 ；k1k clc

m=zeros(1,50); a=zeros(1,50); b=zeros(1,50); f0=zeros(1,50); syms x1 x2 e;

m(1)=1;c=0.2;a(1)=2;b(1)=-3;

三、算法程序

f=x1^2+x2^2-e*(1/(2*x1+x2-2)+1/(1-x1));

f0(1)=15; fx1=diff(f,'x1'); fx2=diff(f,'x2'); fx1x1=diff(fx1,'x1'); fx1x2=diff(fx1,'x2'); fx2x1=diff(fx2,'x1'); fx2x2=diff(fx2,'x2'); for k=1:100

x1=a(k);x2=b(k);e=m(k); for n=1:100 f1=subs(fx1); f2=subs(fx2); f11=subs(fx1x1); f12=subs(fx1x2); f21=subs(fx2x1); f22=subs(fx2x2);

if(double(sqrt(f1^2+f2^2))<=0.002)

a(k+1)=double(x1);b(k+1)=double(x2);f0(k+1)=double(subs(f)); break; else

X=[x1 x2]'-inv([f11 f12;f21 f22])*[f1 f2]'; x1=X(1,1);x2=X(2,1); end end

if(double(sqrt((a(k+1)-a(k))^2+(b(k+1)-b(k))^2))<=0.001)&&(double(abs((f0(k+1)-f0(k))/f0(k)))<=0.001) a(k+1) b(k+1) k

f0(k+1) break; else

m(k+1)=c*m(k); end end

四、算法实现

例1. 利用内点法求解minx21x22

s.t 2x1x220 x110

解：改变算法中f=x1^2+x2^2-e*(1/(2*x1+x2-2)+1/(1-x1)); 回车完成结果 复制粘贴代码，回车出现结果

例2. 利用内点法求解

min x1x2

22s.t　 x1x230 x10

解：改变算法中f=x1^2-x2^2-e*(1/(x1+x2-3)+1/(-x1)); 回车完成结果

例3. 利用内点法求解

min 2x1x2

22s.t　 x14x20 x2x10

解：改变算法中f=2*x1^2-x2^2-e*(1/(x1+4*x2)+1/(x2-x1)); 回车完成结果

例4. 利用内点法求解

min 3x1x2

22s.t　 2x1x20 x2x10

解：改变算法中f=3*x1^2+x2^2-e*(1/(2*x1+x2)+1/(x2-x1)); 回车完成结果