罚函数罚与乘子法(精).doc

罚函数法罚函数法是能够处理一般的约束优化问题: min ( ) ( ) 0, 1, 2, ( ) 0, 1, 2, , ii f x h x i k g x j m ??? ???? ????的一类方法。其基本思想是将约束优化问题卑微无约束问题来求解。罚函数是由目标函数和约束函数的某种组合得到的函数,对于等式约束的优化问题 min ( ) ( ) 0, 1, 2, i f x h x i k ??? ???,可以定义如下的罚函数: 21 ( ) ( ) ( ) kii F x f x c h x ?? ??将约束优化问题转化为无约束优化问题;对于不等式约束的优化问题 min ( ) ( ) 0, 1, 2, , i f x g x j m ??? ???可以定义如下的罚函数: 11 ( ) ( ) ( ) mjj F x f x C g x ?? ??对于同时存在等式约束和不等式约束的优化问题,可以去上面两个罚函数的组合。当然罚函数还有其他的取法,但是构造罚函数的思想都是一样的,即使得在可行点罚函数等于原来的目标函数值,在不可行点罚函数等于一个很大的数。外点罚函数法 { } ic ,求罚函数的极小值来逼近原约束问题的最有点。之所以称为外点罚函数法,是因为它是从可行域外部向约束边界逐步靠拢的。 2,。算法步骤用外点罚函数法求解线性约束问题 min ( ) f x Ax b ????的算法过程如下: 1,给定初始点(0)x ,罚参数列{ } ic 及精度 0??,置 1k?; 2,构造罚函数 2 ( ) ( ) F x f x c Ax b ? ??; 3,用某种无约束非线性规划,以( 1) kx ?为初始点求解 min ( ) F x ; 4,设最优解为( ) kx ,若( ) kx 满足某种终止条件,则停止迭代输出( ) kx ,否则令1 k k ? ?,转 2; 罚参数列{ } ic 的选法:通常先选定一个初始常数 1c 和一个比例系数 2??, 则其余的可表示为 11 ii c c ???。终止条件可采用( ) S x ??,其中 2 ( ) S x c Ax b ? ?。 3 算法的 MATLAB 实现 function [x,minf] = minPF(f,x0,A,b,c1,p,var,eps) % 目标函数: f; % 初始点: x0; % 约束矩阵: A; % 约束右端向量: b; % 罚参数的初始常数: c1; % 罚参数的比例系数: p; % 自变量向量 Var ; % 精度: eps ; % 目标函数取最小值时自变量值: x; % 目标函数的最小值: minf ; format long ; if nargin == 7 eps = -4; end k= 0; FE = 0; for i=1:length(b) FE = FE + (var*transpose(A(1,:)) - b(i))^2; end x1 = transpose(x0); x2 = inf; while 1M= c1*p; FF = M*FE; SumF =f+ FF