罚函数法和广义lagrange乘子法

毕业论文题目增广拉格朗日乘数法及在其在约束优化问题的应用学院数学科学学院专业信息与计算科学班级计算1001班学生高亚茹学号 20100921032 指导教师邢顺来二〇一四年五月二十五日摘要增广拉格朗日乘子法作为求解约束优化问题的一种重要方法，近年来研究增广拉格朗日乘子法的应用显得更加重要。

本文首要介绍了增广拉格朗日乘子法的产生，通过解释增广拉格朗日乘子法是罚函数法和拉格朗日乘子法的有机结合，引出了现在对增广拉格朗日法的发展状况，概述了增广拉格朗日乘子法基本理论。

然后具体说明了增广拉格朗日法在科学领域上的实际应用，如在供水系统和图像复原的应用，也证明了增广拉格朗日乘子法的实际应用性。

关键词：增广拉格朗日乘子法；罚函数法；供水系统；图像复原ABSTRACTAugmented lagrange multiplier methods as an important method for solving constrained optimization problems, recent studies in applications of augmented lagrange multiplier methods is even more important. This paper describes the generation of primary augmented lagrange multiplier method. By interpreting the augmented lagrangian multiplier methods is the combination of penalty function methods and Lagrange multiplier methods, It is given to a recent development of augmented lagrangian methods. Then is shown the basic theories of augmented lagrangian multiplier methods. Finally it is specified the augmented lagrangian method on the practical applications of scientific fields, such as water supply ystems and image restorations, also proved augmented lagrangian multiplier methods of practical application.Key words：Augmented Lagrange Multiplier Methods；Penalty Function Methods Water Supply Systems ；Image Restorations目录摘要.................................................................................... .I ABSTRACT. (II)1前言 (1)1.1增广拉格朗日函数法的产生与应用 (1)1.2研究增广拉格朗日函数法应用的意义 (1)2增广拉格朗日乘子法 (3)2.1约束非线性规划 (3)2.2罚函数外点法 (4)2.3拉格朗日乘子法....................................... (6)2.4增广拉格朗日乘子法.............................. (7)2.4增广拉格朗日乘子法的计算........................... ................................. 10 3 增广拉格朗日乘子法的应用................................................. ...... (12)3.1供水系统调度的增广拉格朗日函数优化方法.......................... . (12)3.2图像复原的增广拉格朗日函数优化方法 (14)结论........................................................................................... .. (17)参考文献 (18)致谢 (19)1前言1.1 增广拉格朗日函数法的产生与应用在求解有约束条件的优化题目时，有一个重要方法，便是用适合的方法把约束优化问题，转变成无约束优化问题来进行求解。

Lagrange 乘数法Lagrange Multiplier MethodLagrange（拉格朗日，1736～1813）18世纪最伟大的数学家之二，另一位是长他29岁的 Euler（尤拉，1707～1783）。

Euler 赏识 Lagrange，在1766年和 d'Alembert 一起推荐 Lagrange 为（柏林科学院）Euler 的继承人。

在他一生浩瀚的工作中，最为所有数学家熟知的发明就是 Lagrange multiplier（拉格朗日乘数）或Lagrange multiplier method，这是一个求极值的方法。

比方在两个变量的时候，我们要找f(x,y) 的极值，一个必要的条件是：但是如果x,y的范围一开始就被另一个函数g(x,y)=0 所限制，Lagrange 提出以对x和y的偏导数为 0，来代替作为在g(x,y)=0 上面寻找f(x,y) 极值的条件。

式中引入的λ是一个待定的数，称为乘数，因为是乘在g的前面而得名。

首先我们注意，要解的是x,y和λ三个变数，而虽然有三个方程式，原则上是可以解得出来的。

以f(x,y)=x，g(x,y)=x2+y2-1 为例，当x,y被限制在x2+y2-1=0 上活动时，对下面三个方程式求解答案有两组，分别是x=1，y=0，和x=-1，y=0，。

对应的是x2+y2-1=0 这个圆的左、右两个端点。

它们的x坐标分别是 1和 -1，一个是最大可能，另一个是最小可能。

读者可能认为为何不把x2+y2-1=0 这个限制改写为、来代入得到，然后令对θ的微分等于 0 来求解呢？对以上的这个例子而言，当然是可以的，但是如果g(x,y) 是相当一般的形式，而无法以x,y的参数式代入满足，或是再更多变量加上更多限制的时候，旧的代参数式方法通常是失效的注1。

这个方法的意义为何？原来在g(x,y)=0 的时候，不妨把y想成是x的隐函数，而有g(x,y(x))=0，并且f(x,y) 也变成了f(x,y(x))。

接触问题（参考ANSYS的中文帮助文件）当两个分离的表面互相碰触并共切时，就称它们牌接触状态。

在一般的物理意义中，牌接触状态的表面有下列特点：1、不互相渗透；2、能够互相传递法向压力和切向摩擦力；3、通常不传递法向拉力。

接触分类：刚性体－柔性体、柔性体－柔性体实际接触体相互不穿透，因此，程序必须在这两个面间建立一种关系，防止它们在有限元分析中相互穿过。

――罚函数法。

接触刚度――lagrange乘子法，增加一个附加自由度（接触压力），来满足不穿透条件――将罚函数法和lagrange乘子法结合起来，称之为增广lagrange法。

三种接触单元：节点对节点、节点对面、面对面。

接触单元的实常数和单元选项设置：FKN：法向接触刚度。

这个值应该足够大，使接触穿透量小；同时也应该足够小，使问题没有病态矩阵。

FKN值通常在0.1~10之间，对于体积变形问题，用值1.0（默认），对弯曲问题，用值0.1。

FTOLN：最大穿透容差。

穿透超过此值将尝试新的迭代。

这是一个与接触单元下面的实体单元深度（h）相乘的比例系数，缺省为0.1。

此值太小，会引起收敛困难。

ICONT：初始接触调整带。

它能用于围绕目标面给出一个“调整带”，调整带内任何接触点都被移到目标面上；如果不给出ICONT值，ANSYS根据模型的大小提供一个较小的默认值（＜0.03＝PINB：指定近区域接触范围（球形区）。

当目标单元进入pinball区时，认为它处于近区域接触，pinball区是围绕接触单元接触检测点的圆（二维）或球（三维）。

可以用实常数PINB调整球形区（此方法用于初始穿透大的问题是必要的）PMIN和PMAX：初始容许穿透容差。

这两个参数指定初始穿透范围，ANSYS 把整个目标面（连同变形体）移到到由PMIN和PMAX指定的穿透范围内，而使其成为闭合接触的初始状态。

初始调整是一个迭代过程，ANSYS最多使用20个迭代步把目标面调整到PMIN和PMAX范围内，如果无法完成，给出警告，可能需要修改几何模型。

罚方法和拉格朗日乘子法
罚方法和拉格朗日乘子法是优化问题中常用的两种方法。

罚方法通过在目标函数中加入一个罚项来避免约束条件的违反，使得原问题转化为一个无约束问题。

而拉格朗日乘子法则通过构造拉格朗日函数，在其中引入拉格朗日乘子，将约束条件转化为一个等式，从而将原问题转化为一个无约束问题。

两种方法各有优缺点，应根据具体情况选择使用。

在实际应用中，罚方法更加灵活，但可能会导致问题的精度下降；而拉格朗日乘子法则更加稳定，但需要求解约束条件的函数导数，计算量较大。

- 1 -。

Ansys静力学接触分析判断标准
当两个分离的表面互相碰触并共切时，就称它们牌接触状态。

在一般的物理意义中，牌接触状态的表面有下列特点:
1、不互相渗透;
2、能够互相传递法向压力和切向摩擦力;
3、通常不传递法向拉力。

接触分类:刚性体一柔性体、柔性体一柔性体实际接触体相互不穿透，因此，程序必须在这两个面间建立-一种关系，防止它们在有限元分析中相互穿过。

---罚函数法。

接触刚度
--- lagrange乘子法，增加-一个附加自由度(接触压力)，来满足不穿透条件
---将罚函数法和lagrange乘子法结合起来，称之为增广lagrange法。

三种接触单元:节点对节点、节点对面、面对面。

接触单元的实常数和单元选项设置:FKN:法向接触刚度。

这个值应该足够大，使接触穿透量小;同时也应该足够小，使问题没有病态矩阵。

FKN值通常在0.1-10之间，对于体积变形问题，用值 1.0(默认)，对弯曲问题，用值0.1。

拉格朗日乘子法符号一、拉格朗日乘子法的概念与起源拉格朗日乘子法（Lagrange Multipliers）是一种数学优化方法，起源于19世纪法国数学家拉格朗日（Joseph-Louis Lagrange）的研究。

该方法主要用于解决带约束条件的优化问题，广泛应用于工程、经济学、计算机科学等领域。

二、拉格朗日乘子法在优化问题中的应用拉格朗日乘子法的基本思路是：对于一个带约束条件的优化问题，通过引入拉格朗日乘子，将原问题转化为无约束条件的优化问题，进而求解原问题。

设目标函数f(x)，约束条件g(x)满足，求解问题：minimize f(x)subject to g(x)引入拉格朗日乘子λ，构造拉格朗日函数L(x, λ)：L(x, λ) = f(x) + λg(x)求解拉格朗日函数的极小值，即可得到原问题的解。

三、拉格朗日乘子法的符号表示1.目标函数：f(x)2.约束函数：g(x)3.拉格朗日乘子：λ4.拉格朗日函数：L(x, λ)5.优化变量：x四、拉格朗日乘子法的优势与局限优势：1.可以处理带约束条件的优化问题；2.适用于多种领域的优化问题；3.求解过程较为简单。

局限：1.对约束条件有一定的要求，不适用于所有约束类型；2.当约束条件较多时，计算复杂度较高。

五、实际问题中的应用案例1.工程领域：在结构优化、电路设计等方面，通过拉格朗日乘子法求解带约束条件的优化问题；2.经济学领域：在微观经济学中，利用拉格朗日乘子法求解企业或个人的最优决策；3.计算机科学领域：在机器学习和数据挖掘中，利用拉格朗日乘子法解决特征选择和权重调整问题。

综上，拉格朗日乘子法作为一种数学优化方法，具有广泛的应用价值。

罚函数之乘⼦法外罚函数主要⽤于对于等式约束问题的求解，内点法主要是对于不等式问题的求解，⼀般问题中包含等式约束以及不等式约束，故需要使⽤乘⼦法解决问题。

1、乘⼦法概述（1）等式约束乘⼦法描述：min f(x)s.t. g i(x) =0⼴义乘⼦法是拉格朗⽇乘⼦法与罚函数法的结合，构造增⼴函数：φ (x,λ,σ)=f(x)+λT g(x)+1/2σg T(x)g(x)在罚函数的基础上增加了乘⼦项，⾸先在σ⾜够⼤的基础上，获得ϕ的极⼩值，然后在调整λ获得原问题的最优解。

（2）包含等式约束以及不等式约束问题描述：min f(x)s.t. h i(x) =0,i=1,...,lg i(x)≥0,i=1,...m其基本思想是：先引进辅助变量把不等式约束化为等式约束，然后利⽤最优性条件消去辅助变量，主要是通过构造增⼴拉格朗⽇函数，进⾏外迭代与内迭代综合，带⼊乘⼦迭代公式，进⽽得出得出，故针对上述⼀般问题构造拉格朗⽇函数为：4、其代码实现为function [x,mu,lambda,output]=multphr(fun,hf,gf,dfun,dhf,dgf,x0)%功能：⽤乘⼦法解⼀般约束问题：min f(x),s.t. h(x)=0.g(x)>=0%输⼊：x0是初始点，fun，dfun分别是⽬标函数及其梯度；%hf，dhf分别是等式约束（向量）函数及其jacobi矩阵的转置；%gf，dgf分别是不等式约束（向量）函数及其jacobi矩阵的转置；%输出：x是近似最优点，mu，lambda分别是相应于等式约束和不等式% 等式约束的乘⼦向量；output是结构变量，输出近似极⼩值f，迭代次数，内迭代次数等%%%%%%c初始化相关参数%%%%%%%%%%%maxk=500; %最⼤迭代次数sigma=2.0; %罚因⼦eta=2.0; theta=0.8; %PHR算法中的实参数k=0; ink=0; %k,ink分别是外迭代和内迭代次数epsilon=1e-5;%终⽌误差值x=x0;he=feval(hf,x);gi=feval(gf,x);%he=feval(hf,x)=hf(x)n=length(x);l=length(he);m=length(gi);%选取乘⼦向量的初始值mu=0.1*ones(1,1);lambda=0.1*ones(m,1);%ones为⽣成m*n的全1矩阵btak=10; btaold=10; %⽤来检验终⽌条件的两个值while (btak>epsilon & k<maxk)%%%%%%c先求解⽆约束问题%%%%%%%%%%%%调⽤BFGS算法程序求解⽆约束⼦问题[x,v,ik]=bfgs('mpsi','dmpsi',x0,fun,hf,gf,dfun,dhf,dgf,mu,lambda,sigma);%%其中x为最优点，val为最优值，ik为迭代次数 ink=ink+ik;he=feval(hf,x);gi=feval(gf,x);%%%%%%%%%%计算btak%%%%%%%%%%%btak=0.0;for(i=1:l),btak=btak+he(i)^2; endfor(i=1:m)temp=min(gi(i),lambda(i)/sigma);btak=btak+temp^2;endbtak=sqrt(btak);if btak>epsilon%%%%%%%%%%%更新罚参数%%%%%%%%%%%if(k>=2 & btak>theta*btaold)sigma=eta*sigma;end%%%%%%%%%%%更新乘⼦向量%%%%%%%%%%%%for(i=1:l),mu(i)=mu(i)-sigma*he(i);endfor(i=1:m)%lambda(i)=max(0.0,lambda(i)-sigma*gi(i));lambda(i)=max(0.0,lambda(i)-gi(i));endend%%%%%%%%%%%迭代%%%%%%%%%%%%k=k+1;btaold=btak;x0=x;endf=feval(fun,x);output.fval=f;output.iter=k;output.inner_iter=ink;output.bta=btak;BFGS算法部分：function [x,val,k]=bfgs(fun,gfun,x0,varargin)%功能：⽤BFGS算法求解⽆约束问题：minf（x）%输⼊：x0是初始点，fun，gfun分别是⽬标函数及其梯度%varargin是输⼊的可变参数变量，简单调⽤bfgs时可以忽略，其他程序调⽤则尤为重要%输出：x为最优点，val为最优值，k时迭代次数maxk=500;%给出最⼤迭代次数rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=length(x0);Bk=eye(n);%Bk=feval('Hess',x0)while(k<maxk)gk=feval(gfun,x0,varargin{:});%计算梯度if(norm(gk)<epsilon),break;end%检验终⽌准则dk=-Bk\gk;%解⽅程组，计算搜索⽅向m=0;mk=0;while(m<20)%搜索求步长newf=feval(fun,x0+rho^m*dk,varargin{:});oldf=feval(fun,x0,varargin{:});if(newf<oldf+sigma*rho^m*gk'*dk)mk=m;break;endm=m+1;end%bfgs校正x=x0+rho^mk*dk;sk=x-x0;yk=feval(gfun,x,varargin{:})-gk;if(yk'*sk>0)Bk=Bk-(Bk*sk*sk'*Bk)/(sk'*Bk*sk)+(yk*yk')/(yk'*sk);endk=k+1;x0=x;endval=feval(fun,x0,varargin{:});主函数部分为：%⽬标函数⽂件function f=f1(x)f=(x(1)-2.0)^2+(x(2)-1.0)^2;%等式约束条件function he=h1(x)he=x(1)-2.0*x(2)+1.0;%不等式约束条件function gi=g1(x)gi=-0.25*x(1)^2-x(2)^2+1;%⽬标函数的梯度⽂件function g=df1(x)g=[2.0*(x(1)-2.0),2.0*(x(2)-1.0)]';%等式函数的Jacobi（转置）矩阵⽂件function dhe=dh1(x)dhe=[1.0,-2.0]';%不等式约束函数的Jacobi矩阵（转置矩阵）function dgi=dg1(x)dgi=[-0.5*x(1),-2.0*x(2)]';命令⾏指令为：x0=[3,3]'[x,mu,lambda,output]=multphr('f1','h1','g1','df1','dh1','dg1',x0)输出结果如下：。