非线性优化问题.ppt

《非线性优化问题.ppt》由会员分享，可在线阅读，更多相关《非线性优化问题.ppt（162页珍藏版）》请在三一办公上搜索。

1、第三专题 非线性优化问题,1、非线性优化模型的建立2、非线性优化模型的寻优,非线性优化模型的建立,确定决策变量确定目标（决策准则）确定约束条件,实例分析,（1）投资决策问题（P88)（2）曲线拟合问题 在实验数据处理或统计资料分析中，常常遇到这样的问题：如何利用有关变量的实验数据（资料）去确定这些变量间的函数关系。例如，已知某物体的温度 与时间 之间有如下形式的经验函数关系：其中 是待定参数。通过测试获得n 组温度与时间之间的实验数据，试确定参数 使理论曲线尽可能地与 n个测试点拟合。,非线性规划问题的共同特征,都是求一个目标函数在一组约束条件下 的极值问题。在目标函数或约束条件中，至少有一个

2、是变量的非线性函数。,非线性规划问题,一般形式：向量形式：,非线性优化问题的寻优,相关概念及理论一维最优化方法多维无约束最优化方法多维有约束最优化方法,非线性规划的相关概念及理论,一阶导数、二阶导数和n元函数的Taylor公式,定义4,设函数,定义在凸集,上，,若对任意的,及任意的,都有：,则称函数,为凸集,上的凸函数,定义5,严格凸函数,注：,将上述定义中的不等式反向，可以得到,凹函数的定义,凸函数,例1：,设,试证明,在,上是严格凸函数,证明:,设,且,都有：,因此,在,上是严格凸函数,例2：,试证线性函数是,证明:,设,上的凸函数,则,所以,是凸函数,类似可以证明,是凹函数,凸函数的几何

3、性质,对一元函数,在几何上,表示连接,的线段,表示在点,处的,函数值,所以一元凸函数表示连接函数图形上任意两点,的线段总是位于曲线弧的上方,凸函数的性质,（）,设,（）,设,函数，,是凸集,上的凸函数，,实数,则,也是,上的凸函数,是凸集,上的凸,实数,则,也是,上的凸函数,（）,设,是凸集,上的凸函数，,是实数，,则水平集,是凸集,下面的图形给出了凸函数,的等值线的图形，可以看出水平集是凸集,凸函数的判定,定理1,设,上，,令,则:,(1),是定义在凸集,是凸集,上的凸函数的充要条件是对,任意的,一元函数,为,上的凸函数.,(2),设,若,在,上为严格,凸函数，,则,在,上为严格凸函数,该定

4、理的几何意义是：凸函数上任意两点之,间的部分是一段向下凸的弧,一阶条件,定理2.1,设在凸集,上,可微，,则：,在,上为凸函数的充要条件是对任意的,都有：,定理2.2,严格凸函数(充要条件),二阶条件,定理3,设在开凸集,内,二阶可微，则,(1),是,内的凸函数的充要条件为，,在,内任一点,处，,的海色矩阵,半正定,其中：,二阶条件,定理3,设在开凸集,内,(2),若在,内,正定,则,在,内,二阶可微，则,是严格凸函数,注:,反之不成立,例：,显然是严格凸的，,但在点,处,不是正定的,凸规划,定义6,设,为凸集，,为,上的凸函数，,则称规划问题,为凸规划问题,定理4,(1),凸规划问题的任一局

5、部极小点,是,整体极小点，全体极小点组成凸集,(2),若,是凸集,上的严格凸函数，,且凸规划问题,整体极小点存在，,则整体极小点是唯一的,非线性规划的最优性条件,最优性条件：是指非线性规划模型的最优解所要满足的必要和充分条件。无约束最优性条件 约束最优性条件,无约束最优性条件,一（单）元函数的最优性条件,（）,若,（）,为,的局部极小点，,则,若,则,为,的严格局部极小点；,若,（）,为,的局部极小点，,则：,多元函数的一阶必要条件（P106-107),定理1:,若,为,的局部极小点，,且在,内,一阶连续可导，,则,注:,(1),仅仅是必要条件，而非充分条件,(2),满足,的点称为驻点,驻点分

6、为：极小点，极大点，鞍点,多元函数的二阶充分条件,定理2:,若在,内,二阶连续可导，,且,正定,则,为严格局部,极小点,注:,如果,负定,则,为严格局部极大点,二阶必要条件和充要条件,定理3:,若,为,的局部极小点，,且在,内,二阶连续可导，,则,半正定,定理4:,设,在,上是凸函数且有一阶连续,偏导数，,则,为,的整体极小点的充要,条件是,例1：,利用极值条件解下列问题：,解：,令,即：,得到驻点：,函数,的海色阵：,由此，,在点,处的海色阵依次为：,由于矩阵,不定，,则,不是极小点,负定，,则,不是极小点，,实际上它是极大点,正定，,则,是局部极小点,约束最优性条件(p133-p136),

7、定义1:,有效约束：,若(*)中的一个可行点,使得,某个不等式约束,变成等式，,即,则,称为关于,的有效(积极）约束,非有效约束：,若对,则,称为,关于,的非有效(无效）约束,有效集：,定义2:,锥：,的子集，,如果它关于正的数乘运算,是封闭的,如果锥也是凸集，则称为凸锥,凸锥关于加法和正的数乘运算是封闭的,一阶必要条件,定理3.5:,(Kuhn-Tucker一阶必要条件)(1951),设,在,（K-T条件）,一阶必要条件,定理1:,(Kuhn-Tucker一阶必要条件),（互补松弛条件）,例2：,验证 是否满足Kuhn-Tucker条件：,试验证最优点,为KT点,解：,令,所以,即：,所以：

8、,是KT点,Lagrange函数及K-T条件,在一定凸性下的最优性的充分条件,一维最优化方法（线性搜索方法）,已知,并且求出了,处的可行下降方向,从,出发，,沿方向,求目标函数的最优解，,或者选取,使得：,问题描述,即,设其最优解为,（叫精确步长因子），,所以线性搜索是求解一元函数,的最优化问,题（也叫一维最优化问题）。,我们来求解：,于是得到一个新点：,一般地，线性搜索算法分成两个阶段：,第一阶段确定包含理想的步长因子,（或问题最优解）的搜索区间；,第二阶段采用某种分割技术或插值方法,缩小这个区间。,搜索区间：,搜索区间求取方法,进退法：一种简单的确定初始搜索区间方法.基本思想：是从一点出发

9、，按一定步长，试图确定出函数值呈现“高-低-高”的三点，即 这里。具体地说，就是给出初始点，初始步长，若，则下一步从新点 出发，加大步长，再向前搜索，直到目标函数上升为止。,若，则下一步仍以 为出发点，沿反方向同样搜索，直到目标函数上升就停止。这样便得到一个搜索区间。这种方法叫进退法。计算步骤：见P96计算框图:见P97,黄金分割法（0.618法）,基本思想：它通过对试探点的函数值进行比较，使得包含极小点的区间不断缩短，当区间长度小到精度范围之内时，可以粗略地认为区间上各点的函数值均接近于极小值。,设,在,上为下单峰函数，,即有唯一,的极小点,在,左边,严格下降，,在,右边,严格上升。,在,内

10、任取,若,则,若,则,单峰函数：,黄金分割法,黄金分割法,若第一次选取的试点为,则下一步保留,的区间为,或,两者的机会是均等的,因此我们选取试点时希望,设,则,另外，我们希望如果缩小的区间包含原来的,试点，则该试点在下一步被利用若保留的区,我们希望原来的,间为,前一次的试点,在这个区间内,在缩小的区间内成为,新的,我们根据这条件 来计算,计算,的公式为：,因此我们希望：,即：,化简得：,若保留区间为,我们得到的结果是,一致的,该方法称为黄金分割法，实际计算取：,所以黄金分割法又称为0.618法,黄金分割法每次缩小区间的比例是一致的，,每次将区间长度缩小到原来的0.618倍,黄金分割法的算法步骤

11、,Step1,给定,以及,令,Step2,Step3,转Step.,令,转Step.,若,则,停；,否则,转Step.,Step4,若,则,转Step3.,黄金分割法的算法步骤,Step5,若,则,转Step3.,若,则,转Step3.,例1（黄金分割法）,用黄金分割法求函数,在区间,上的极小点。,要求最终区间长度不大于,原始区间长度的0.08倍,解：,函数,在区间,上为下单峰函数，,第一次迭代：,缩短后区间为,第二次迭代：,缩短后区间为,Fibonacci法,为了尽快得到结果，希望区间缩小的尽量小。,如果在区间只有一个试点，我们无法将区间缩小。,如果知道两个试点,根据,的大,小关系，,可以得

12、到缩小的区间,或者,它与0.618法的主要区别之一在于：搜索区间长度的缩短率不是采用0.618，而是采用Fibonacci数。,下面我们考虑任给一个,另外一种思维方式为，,的单峰区间,如果给定试点的个数,如何使最后确定,最优值的区间尽量的小。,按什么方式取点，,求,次函数值之后，,可最多将多长的原始区间,长度缩小为,设,为试点个数为,最终区间,长度为,时、,原始区间,的最大可能长度。,的包含,设最初两个试点为,和,若极小点在,内，,至多还有,个试点，,则,若极小点在,内，,包括,在内可以有,个试点，,则,因此，,如果我们采取合适的技巧，可以使得：,另外，,显然，,从而,满足差分方程：,此为Fi

13、bonacci数列，一般写为：,若原始区间为,要求最终区间长度,则,由此可确定,区间缩短之后与,之前的比依次为：,确定之后，最初两个试点分别为：,关于,对称,由于,上述过程完成了依次迭代，新区间仍记为,若已经进行了,次迭代，,第,次迭代时，,还有,个试点（包括已经计算过的函数值的一个）,注意：,（）若在一定的误差范围内，,则认为,在,内。,（）最后的两个试点的选取方式：,例3.1（Fibonacci法）,用Fibonacci法求函数,在区间,上的极小点。,要求最终区间长度不大于,原始区间长度的0.08倍,解：,函数,在区间,上为下单峰函数，,由,可知,应取,Fibonacci算法与0.618法

14、几乎完全相同。,第一次迭代：,缩短后区间为,第二次迭代：,缩短后区间为,第三次迭代：,缩短后区间为,第四次迭代：,缩短后区间为,第五次迭代：,取最优解,Fibonacci方法评价,Fibonacci法的优点,（）如果缩小的区间包含原来的试点，则该,试点在下一步被利用；,（）效率最高，有限个试点的情况下，可将,最优点所在的区间缩小到最小,Fibonacci法的缺点,（）搜索前先要计算搜索的步数；,（）每次搜索试点计算的公式不一致,1、黄金分割法（0.618法）与Fibonacci法,的区别与联系是什么？,2、请读者自己写出算法和程序,二分法,若,的导数存在且容易计算，,则线性搜索,的速度可以得到

15、提高,下面的二分法每次将,区间缩小至原来的二分之一,设,为下单峰函数，,若,在,内,具有连续的一阶导数，,且,取,若,则,为极小点；,若,则以,代替,若,则以,代替,二分法每次迭代都将区间缩短一半，故二分法的收敛速度也是线性的，收敛比为1/2。,。,计算步骤：见P105 计算框图:见P106,多维无约束最优化方法,最速下降法(阻尼)牛顿法共轭梯度法,最速下降法,问题提出,问题：,在点,处，,沿什么方向,下降最快?,分析：,考查：,显然当,时，,取极小值,因此：,结论：,负梯度方向使,下降最快，,亦即最速,下降方向,最速下降法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,

16、计算下降方向,Step4:,计算步长因子,Step5:,令,转步.,问题：,设,是正定二次函数,由精确的线搜索确定的,特别当：,例1：,用最速下降法求解：,解：,分析：,(1),因此：,最速下降法是整体收敛的，,且是线性收敛的,(2),两个相邻的搜索方向是正交的,收敛性分析,定理1:,设,在,上存在且一致连续，,则最速下降法产生的序列,满足或者对某个,有,或者,证明：,对于最速下降法，,由以上定理立得,收敛性分析,定理2:,设,二次连续可微，,且,其中,是个正常数，,对任何给定的初始点,最速下降算法或有限终止，,或者,或者,证明：,用以上的结论：,最速下降法优点,(1),程序设计简单，计算量小

17、，存储量小，,对初始点没有特别要求,(2),有着很好的整体收敛性，即使对一般的,目标函数，它也整体收敛,最速下降法缺点,最速下降法是线性收敛的，并且有时是,很慢的线性收敛,原因：,仅反映,在,处,的局部性质,相继两次迭代中搜索,方向是正交的,小结,最速下降法是基本算法之一，而非有效,的实用算法,最速下降法的本质是用线性函数来近似,目标函数，,要想得到快速算法，需要考,虑对目标函数的高阶逼近,牛顿法,基本思想,利用目标函数,在点,处的二阶Taylor,展开式去近似目标函数，,用二次函数的极小点,去逼近目标函数的极小点,算法构造,问题：,设,二阶连续可微，,海色阵,正定,如何从,因为,正定，,则,

18、有唯一极小点，,用这个,极小点作为,所以要求：,即：,因此：,这就是牛顿法迭代公式,注：,这里,牛顿法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,否则计算,Step4:,令,转步.,并且求解方程,得出,例1：,用牛顿法求解：,解：,牛顿法收敛定理,定理1:,设,二次连续可微，,是,的局,部极小点，,正定,假定,的海色阵,满足Lipschitz条件，即存在,使得对于所有,有：,其中,是海色阵,的,元素,则当,充分靠近,时，,对于一切,牛顿迭代有意义，,迭代序列,收敛到,并且具有二阶收敛速度,牛顿法优点,(1),(2),对正定二次函数，迭代一次就可以得到,极小点,如果,正

19、定且初始点选取合适，,算法,二阶收敛,牛顿法缺点,(1),(2),对多数问题算法不是整体收敛的,每次都需要计算,计算量大,(3),每次都需要解,方程组有时奇异或病态的，,无法确定,或,不是下降方向,(4),收敛到鞍点或极大点的可能性并不小,阻尼牛顿法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,否则计算,Step4:,沿,并且求解方程,得出,进行线搜索，,得出,Step5:,令,转Step2.,阻尼牛顿法收敛定理,定理2:,设,二阶连续可微，,又设对任意的,存在常数,使得,在,上满足：,则在精确线搜索条件下，,阻尼牛顿法产生的点列,满足：,(1),当,是有限点列时，,其

20、最后一个点为,的唯一极小点,(2),当,是无限点列时，,收敛到,的唯一极小点,阻尼牛顿法收敛定理,定理3:,设,二阶连续可微，,又设对任意的,存在常数,使得,在,上满足：,则在Wolfe不精确线搜索条件下，,阻尼牛顿法,产生的点列,满足：,且,收敛到,的唯一极小点,例2：,用阻尼牛顿法求解：,解：,显然,不是正定的，,但：,于是，,沿方向,进行线搜索，,得其极小点,从而迭代不能继续下去,带保护的牛顿法算法,给出,Step1:,若,为奇异的，转Step8，否则，,Step2:,令,Step3:,若,为奇异的，转Step8，否则，,则转Step8，否则，,Step4:,若,则转Step9，否则，,

21、Step5:,沿方向,进行线搜索，,求出,并令,Step6:,若,停；,Step7:,令,转Step1；,Step8:,令,转Step5；,Step9:,令,转Step5.,例3：,用带保护的牛顿法求解：,解：,显然,不是正定的，,但：,于是，,因为，,故令，,沿,进行线搜索得：,第二次迭代：,而：,使,故令,沿,进行线搜索，,得出,于是:,此时:,共轭梯度法,问题1:,如何建立有效的算法？,从二次模型到一般模型,问题2:,什么样的算法有效呢？,二次终止性(经过有限次迭代必达到极小点的性质）,算法特点,（）建立在二次模型上，具有二次终止性,（）有效的算法，克服了最速下降法的慢,收敛性，又避免了

22、牛顿法的计算量大和局部收,性的缺点,（）算法简单，易于编程，需存储空间小等,优点，是求解大规模问题的主要方法,共轭方向及其性质,定义1:,设,是,中任一组,非零向量，,如果：,则称,是关于,共轭的,注：,若,则是正交的，因此共轭是,正交的推广,定理1:,设,为,阶正定阵，,非零向量组,关于,共轭，,则必线性无关,推论1:,设,为,阶正定阵，,非零向量组,关于,共轭，,则向量构成,的一组基,推论2:,设,为,阶正定阵，,非零向量组,关于,共轭，,若向量,与,关于,共轭，,则,求 的极小点的方法共轭方向法算法,Step1:,给出,计算,和初始下降方向,Step2:,如果,停止迭代,Step3:,计

23、算,使得,使得：,转Step2.,共轭方向法基本定理,定义2:,设,维向量组,线性无关，,向量集合,为,与,生成的,维超平面,引理1:,设,是连续可微的严格凸函数，,维向量组,线性无关，,则：,是,在,上,唯一极小点的充要条件是：,定理2:,设,为,阶正定阵，,向量组,关于,共轭，,对正定二次函数,由任意,开始，,依次进行,次精确线搜索：,则：,（）,（）,是,在,上的极小点,推论:,当,时，,为正定二次函数在,上的极小点,共轭梯度法,记：,左乘,并使,得：,（Hestenes-Stiefel公式）,取：,是一种特殊的共轭方向法,共轭梯度法基本性质,定理3:,对于正定二次函数，,采用精确线搜索

24、,的共轭梯度法在,步后终止，,且对,成立下列关系式：,（共轭性）,（正交性）,（下降条件）,系数的其他形式,（）FR公式,（1964）,（2）PRP公式,（1969）,FR共轭梯度法算法,Step1:,给出,Step2:,如果,停,Step5:,转Step2.,计算,Step4:,Step3:,由精确线搜索求,计算,例4：,用FR共轭梯度法求解：,解：,化成,形式,(1),(2),例5：,用FR共轭梯度法求解：,解：,化成,形式,(1),(2),注意：FR方法中初始搜索方向必须取最速下降方向，才满足二次终止性。,FR共轭梯度法收敛定理,定理4:,假定,在有界水平集,上连续可微，,且有下界，,那

25、么采用精确线搜索下的,FR共轭梯度法产生的点列,至少有一个聚点,是驻点，即：,(1),当,是有穷点列时，,其最后一个点是,的驻点,(2),当,是无穷点列时，,它必有聚点，,且任一,聚点都是,的驻点,再开始FR共轭梯度法算法,Step1:,给出,Step2:,计算,如果,停，,Step4:,否则,Step3:,由精确线搜索求,并令：,计算,若,令,转Step2;,如果,停.,Step5:,若,令,转step2.,Step6:,计算,Step7:,如果,令,转step2,否则,转step3.,作业,用FR共轭梯度法求解：,多维约束最优化方法,惩罚函数法 SUMT:序列无约束极小化方法(Sequen

26、tial Unconstrained Minimization Technique)乘子法,外点法（二次罚函数方法）,内点法（内点障碍罚函数法）,罚函数法,基本思想,设法将约束问题求解转化为无约束问题求解,具体说：,根据约束的特点，构造某种惩罚函数，,然后把它加到目标函数中去，将约束问题的,求解化为一系列无约束问题的求解,惩罚策略：,企图违反约束的迭代点给予很大的,目标函数值,迫使一系列无约束问题的极小点或,者无限地靠近可行域，或者一直保持在可行域,内移动，直到收敛到极小点,外罚函数法（外点法）,引例：,求解等式约束问题:,解:,图解法求出最优解,构造：,但是,性态极坏，,无法用有效的无约束,

27、优化算法求解,设想构造：,其中,是很大的正数,求解此无约束问题得：,当,时，,有：,等式约束问题,构造：,其中,为参数，称为罚因子,分析：,当,不是可行解时，,越大，,惩罚越重,因此当,充分大时，,应充分小,即,的极小点应充分逼近可行域，,进而,逼近(1)的最优解,不等式约束问题,构造：,分析：,当,不是可行解时，,越大，,惩罚越重,因此当,充分大时，,应充分小,即,的极小点应充分逼近可行域，,进而,逼近(2)的最优解,一般约束问题,构造：,其中：,例1：,用外罚函数法求解：,解：,即：,因此：,令：,得：,最优值：,当,时：,注：,(1),往往不满足约束条件，,都是,从可行域外部趋向于,的,

28、因此叫外罚函数法,(2),通过求解一系列无约束最优化问题来求,解约束最优化问题的方法，,又称为序列无约束,极小化技术SUMT.,外罚函数法,又称SUMT外点法,外罚函数法算法步骤,Step1:,给出,(可是不可行点)，,罚因子,放大系数,Step2:,以,为初始点求无约束问题：,得,Step3:,若,则,停；,否则转step4,Step4:,令,转step2.,例2：,用SUMT外点法求解：,取,求解,迭代过程见下表：,收敛性分析,引理1：,对于由SUMT外点法产生的点列,则有：,设,收敛性分析,定理1：,设约束问题(3)和无约束问题(4)的整体,最优解为,和,对正数序列,且,则由SUMT外点

29、法产生的点列,的,任何聚点,必是(3)的整体最优解,证：,不妨设,因为,和,分别为(3)和(4)的整体最优解，,且,所以有：,为单调有界序列，,设其极限为,亦为单调有界序列，,设其极限为,且,连续；,即,为可行解,为最优解；,连续；,即,为(3)的整体最优解,外罚函数法评价,(1),如果有了求解无约束问题的好算法，利用,外罚函数法求解约束问题很方便,(2),每个近似解,往往不是可行解，这是某,些实际问题所无法接受的,内罚函数法可以解决,(3),由收敛性定理,取越大越好，,而,越大将,造成增广目标函数,的Hesse阵条件数越,大，趋于病态，给无约束问题求解增加很大困,难，甚至无法求解乘子法可解决

30、这个问题,内罚函数法,惩罚策略：,在可行域的边界上筑起一道很高的,“围墙”，当迭代点靠近边界时，目标函数值,陡然增大，以示惩罚，阻止迭代点穿越边界，,这样就可以把最优解“挡”在可行域内了,注：,惩罚策略只适合于不等式约束问题，,并且要求可行域的内点集非空,不等式约束问题,构造：,其中：,或,分析：,为可行域的内点时，,为有限正数，,几乎不受惩罚；,接近边界时，,趋于无穷大，,施以很重的惩罚；,迫使极小点落在可行域内，,最终逼近极小点,例3：,用内罚函数法求解：,解：,令：,所以,当,时，,注：,一般,最优解很难用解析法求出，,需采用序列无约束最优化方法,内罚函数法算法,Step1:,给出,(要

31、求是可行点)，,罚因子,缩小系数,Step2:,以,为初始点求无约束问题：,得,Step3:,若,则,停；,否则转step4,Step4:,令,转step2.,例4：,用SUMT内点法求解：,取,迭代结果见下表：,收敛性分析,引理2：,对于由SUMT内点法产生的点列,总有：,定理2：,设可行域,的内点集,非空，,在,上存在极小点,对严格单减正数列,且,则由SUMT内点法产生的点列,的任何聚点,是约束问题(2)的最优解,证：,由于,由引理2知,单调减少且下有界，,于是它有极限，记作,即：,若能证明：,则可得：,再由,的连续性，可得：,即,是(2)的最优解,再证：,由,的连续性知，,对于任意小的正

32、数,存在,取满足,的,使得：,由,知，,对于同一个,存在,当,时,又因为,乘子法,引例：,求解等式约束问题:,解:,最优解,分析：,对于任何,关于,的极小点是不存在的,正因为如此，才引进外罚函数法的,问题：,能否找到某个,使,恰好是,的无约束极小呢？回答是否定的,设想：,能否在不改变最优解的前提下，,以某个,在最优解,处梯度为零的函数来取代,呢？,启发：,(增广Lagrange函数),通过求解增广Lagrange函数的序列无约束问题,来获得原约束问题的解,等式约束问题的乘子法,其中,和,二阶连续可微,设,为Lagrange乘子向量，,则对应Lagrange,函数为：,设,是,的极小点，,是相应

33、的乘子向量,(1)可等价为：,启发：,采用外罚函数法,构造：,我们将证明：,适当大时，,是,极小点,但,是未知的，,在求,的同时，,采用迭代法求出,这是乘子法的基本思想,定理：,设,与,满足,为问题(1)的严格局部,极小点的二阶充分条件，,则存在,使对所有,为,的严格局部极小点；,反之，,若,且,对某个,是无约束问题,(5)的局部极小点，,则,是约束问题(1)的局部,极小点.,算法构造,采用迭代法求点列,使,设已有,和,则由一阶最优性条件有：,要求,和,且,采用：,或：,例5：,用乘子法求解：,解：,增广Lagrange函数为：,令：,得：,所以：,乘子迭代公式为：,即：,取：,所以：,设,对上式取极限有：,得：,得：,也可不取特定值，直接对上式求极限,等式约束的乘子法(PH算法),Step1:,给出,Step2:,以,为初始点求无约束问题：,得,Step3:,若,则,停；,否则转step4,Step4:,当,及放大系数,转step5;否则,转step5;,Step5:,令,转step2.,作业,(1)用外罚函数法求解：,(2)用内罚函数法求解：,