罚函数罚与乘子法（1）

1、精选优质文档-倾情为你奉上罚函数法罚函数法是能够处理一般的约束优化问题：的一类方法。其基本思想是将约束优化问题卑微无约束问题来求解。罚函数是由目标函数和约束函数的某种组合得到的函数，对于等式约束的优化问题，可以定义如下的罚函数：将约束优化问题转化为无约束优化问题；对于不等式约束的优化问题可以定义如下的罚函数：对于同时存在等式约束和不等式约束的优化问题，可以去上面两个罚函数的组合。当然罚函数还有其他的取法，但是构造罚函数的思想都是一样的，即使得在可行点罚函数等于原来的目标函数值，在不可行点罚函数等于一个很大的数。外点罚函数法1.算法原理外点罚函数法是通过一系列罚因子，求罚函数的极小值来逼近原约束

2、问题的最有点。之所以称为外点罚函数法，是因为它是从可行域外部向约束边界逐步靠拢的。2，。算法步骤用外点罚函数法求解线性约束问题的算法过程如下：1，给定初始点，罚参数列及精度，置；2，构造罚函数；3，用某种无约束非线性规划，以为初始点求解；4，设最优解为，若满足某种终止条件，则停止迭代输出，否则令，转2；罚参数列的选法：通常先选定一个初始常数和一个比例系数，则其余的可表示为。终止条件可采用，其中。3 算法的MATLAB实现function x,minf = minPF(f,x0,A,b,c1,p,var,eps)% 目标函数：f；% 初始点： x0;% 约束矩阵： A；% 约束右端向量：b；%

3、罚参数的初始常数： c1;% 罚参数的比例系数： p；% 自变量向量 Var；% 精度： eps；% 目标函数取最小值时自变量值： x;% 目标函数的最小值：minf；format long;if nargin = 7 eps = 1.0e-4;endk = 0;FE = 0;for i=1:length(b) FE = FE + (var*transpose(A(1,:) - b(i)2;endx1 = transpose(x0);x2 = inf; while 1 M = c1*p; FF = M*FE; SumF = f + FF; x2,minf = minNT(SumF,transp

4、ose(x1),var); if norm(x2 - x1)<=eps x = x2; break; else c1 = M; x1 = x2; endendminf = Funval(f,var,x);format short;4.算法举例用外点罚函数法求下面的优化问题：其中取，初始点取。解：由题已知，则每一步迭代需求解的罚函数为：在MATLAB命令窗口中输入：>> f = 0.5*t2+s2/4;>> A=1 1;b=1;>> c1=0.05;p=2;>> x,minf=minPF(f,0 0,A,b,c1,p,t s)所得结果为：&g

5、t;> x=0.3333 0.6666minf = 0.1666对于一般的等式约束问题也可以用外点罚函数法解决：function x,minf = minGeneralPF(f,x0,h,c1,p,var,eps)format long;if nargin = 6 eps = 1.0e-4;endk = 0;FE = 0;for i=1:length(h) FE = FE + (h(i)2;endx1 = transpose(x0);x2 = inf; while 1 M = c1*p; FF = M*FE; SumF = f + FF; x2,minf = minNT(SumF,tra

6、nspose(x1),var); if norm(x2 - x1)<=eps x = x2; break; else c1 = M; x1 = x2; endendminf = Funval(f,var,x);format short;例 用通用罚函数法求下面的优化问题： 其中取，初始点取为。外点罚函数法除了可以求含等式约束的优化问题外，还可以求混合约束的优化问题，不过其罚函数形式要修正。通过引入罚函数可以转化为无约束优化问题。function x,minf = minConPF(f,x0,g,h,c1,p,var,eps) format long;if nargin = 7 eps =

7、 1.0e-4;endk = 0;FE = 0;for i=1:length(h) FE = FE + (h(i)2; endx1 = transpose(x0);x2 = inf; while 1 M = c1*p; FF = M*FE; gx = Funval(g,var,x1); gF = 0; for i=1:length(h) if gx(i) < 0 gF = gF + M*(g(i)2); %构造罚函数 end end SumF = f + FF + gF; x2,minf = minNT(SumF,transpose(x1),var); %用牛顿法求解无约束规划问题 if

8、 norm(x2 - x1)<=eps x = x2; break; else c1 = M; x1 = x2; endendminf = Funval(f,var,x);format short;内点罚函数法1.算法原理内点罚函数法的所有迭代过程均在可行域内进行，它每次迭代得到的点都是可行点，内点罚函数法的基本思想是用可行域内的点列来逼近最优解。2，。算法步骤用内点罚函数法求解线性约束问题的算法过程如下：1，给定初始点，罚因子，缩小系数及精度，置；2，构造增广目标函数，其中；3，用某种无约束非线性规划，以为初始点求解；设最优解为，若，则终止迭代输出，否则令，转2；3 算法的MATLAB

9、实现function x,minf = minNF(f,x0,g,u,v,var,eps)format long;if nargin = 6 eps = 1.0e-4;endk = 0;FE = 0;for i=1:length(g) FE = FE + 1/g(i); %构造罚函数endx1 = transpose(x0);x2 = inf;while 1 FF = u*FE; SumF = f + FF; x2,minf = minNT(SumF,transpose(x1),var); %用牛顿法求解无约束规划 Bx = Funval(FE,var,x2); if u*Bx < ep

10、s %精度判断 if norm(x2 - x1)<=eps x = x2; break; else u = v*u; %参数修正 x1 = x2; end else if norm(x2 - x1)<=eps x = x2; break; else u = v*u; %参数修正 x1 = x2; end endendminf = Funval(f,var,x);format short; 4 算法举例 其中取，初始点取为。>> syms t s;>> f = t2+s2;>> g=t+s-1;2*t-s-2;>> x, minf=mi

11、nNF(f, 3 1, g, 8, 0.5,t s)x=1.0002 0.0001minf= 1.0004乘子法1.算法原理外点罚函数法和内点罚函数法的均要求罚因子趋于无穷才能得到目标函数的最优解，但是罚因子太大的话会引起计算的困难，为克服这一缺陷就产生了乘子法。2，算法步骤用乘子法求解约束优化问题的算法过程如下：1，给定初始点，初始乘子向量，罚因子及放大系数，及精度，参数，置；2，构造目标函数；3，用某种无约束非线性规划，以为初始点求解；设最优解为，4，若，则终止迭代输出，否则转2；5，若，则令，否则保持不变，转66，令 置，转2，3 算法的MATLAB实现function x,minf =

12、 minFactor(f,x0,h,v,M,alpha,gama,var,eps)format long;if nargin = 8 eps = 1.0e-4;endFE = 0;for i=1:length(h) FE = h(i)2;endx1 = transpose(x0);x2 = inf; while 1 FF = M*FE/2; Fh = v*h; SumF = f + FF - Fh; x2,minf = minNT(SumF,transpose(x1),var); Hx2 = Funval(h,var,x2); Hx1 = Funval(h,var,x1); if norm(Hx2) < eps x = x2; break; else if Hx2/Hx1 >= gama M = alpha*M; x1 = x2; else v = v - M*transpose(Hx2); x1 = x2; end endendminf =