非线性优化问题ppt课件

第三专题 非线性优化问题n1、非线性优化模型的建立n2、非线性优化模型的寻优n第三专题 非线性优化问题1、非线性优化模型的建立非线性优化模型的建立n确定决策变量n确定目标（决策准则）n确定约束条件n非线性优化模型的建立确定决策变量实例分析（1）投资决策问题（P88)（2）曲线拟合问题 在实验数据处理或统计资料分析中，常常遇到这样的问题：如何利用有关变量的实验数据（资料）去确定这些变量间的函数关系。例如，已知某物体的温度 与时间 之间有如下形式的经验函数关系：其中 是待定参数。通过测试获得n 组温度与时间之间的实验数据 ，试确定参数 使理论曲线尽可能地与 n个测试点拟合。n实例分析（1）投资决策问题（P88)非线性规划问题的共同特征非线性规划问题的共同特征n 都是求一个目标函数在一组约束条件下 的极值问题。n在目标函数或约束条件中，至少有一个是变量的非线性函数。n非线性规划问题的共同特征 都是求一个目标函数在一组约束条件下非线性规划问题非线性规划问题n一般形式：n向量形式：n非线性规划问题一般形式：非线性优化问题的寻优n相关概念及理论n一维最优化方法n多维无约束最优化方法n多维有约束最优化方法n非线性优化问题的寻优相关概念及理论非线性规划的相关概念及理论n一阶导数、二阶导数和n元函数的Taylor公式n非线性规划的相关概念及理论一阶导数、二阶导数和n元函数的Tan非线性优化问题ppt课件n非线性优化问题ppt课件定义4设函数定义在凸集上，若对任意的及任意的都有：则称函数为凸集上的凸函数定义5 严格凸函数注：将上述定义中的不等式反向，可以得到凹函数的定义凸函数n定义4设函数定义在凸集上，若对任意的及任意的都有：则称函数为例1：设试证明在上是严格凸函数证明:设且都有：因此在上是严格凸函数n例1：设试证明在上是严格凸函数证明:设且都有：因此在上是严例2：试证线性函数是证明:设上的凸函数则所以是凸函数类似可以证明是凹函数n例2：试证线性函数是证明:设上的凸函数则所以是凸函数类似凸函数的几何性质对一元函数在几何上表示连接的线段表示在点处的函数值所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方n凸函数的几何性质对一元函数在几何上表示连接的线段表示在点处n非线性优化问题ppt课件凸函数的性质（）设（）设函数，是凸集上的凸函数，实数则也是上的凸函数是凸集上的凸实数则也是上的凸函数（）设是凸集上的凸函数，是实数，则水平集是凸集n凸函数的性质（）设（）设函数，是凸集上的凸函数，实数则也下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集n下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集凸函数的判定定理1 设上，令则:(1)是定义在凸集是凸集上的凸函数的充要条件是对任意的一元函数为上的凸函数.(2)设若在上为严格凸函数，则在上为严格凸函数n凸函数的判定定理1设上，令则:(1)是定义在凸集是凸集上的凸该定理的几何意义是：凸函数上任意两点之间的部分是一段向下凸的弧n该定理的几何意义是：凸函数上任意两点之间的部分是一段向下凸的一阶条件定理2.1设在凸集上可微，则：在上为凸函数的充要条件是对任意的都有：定理2.2严格凸函数(充要条件)n一阶条件定理2.1设在凸集上可微，则：在上为凸函数的充要条件二阶条件定理定理3 3设在开凸集内二阶可微，则(1)是内的凸函数的充要条件为，在内任一点处，的海色矩阵半正定,其中：n二阶条件定理3设在开凸集内二阶可微，则(1)是内的凸函数的充二阶条件定理3设在开凸集内(2)若在内正定,则在内二阶可微，则是严格凸函数注:反之不成立例：显然是严格凸的，但在点处不是正定的n二阶条件定理3设在开凸集内(2)若在内正定,则在内二阶可微，凸规划凸规划定义6 设为凸集，为上的凸函数，则称规划问题为凸规划问题定理4(1)凸规划问题的任一局部极小点是整体极小点，全体极小点组成凸集(2)若是凸集上的严格凸函数，且凸规划问题整体极小点存在，则整体极小点是唯一的n凸规划定义6设为凸集，为上的凸函数，则称规划问题为凸规划问题非线性规划的最优性条件非线性规划的最优性条件 最优性条件：是指非线性规划模型的最优解所要满足的必要和充分条件。n无约束最优性条件无约束最优性条件 n约束最优性条件约束最优性条件 n非线性规划的最优性条件 最优性条件：是指非线性规无约束最优性条件无约束最优性条件n无约束最优性条件一（单）元函数的最优性条件（）若（）为的局部极小点，则若则为的严格局部极小点；若（）为的局部极小点，则：n一（单）元函数的最优性条件（）若（）为的局部极小点，则若多元函数的一阶必要条件（P106-107)定理1:若为的局部极小点，且在内一阶连续可导，则注:(1)仅仅是必要条件，而非充分条件(2)满足的点称为驻点驻点分为：极小点，极大点，鞍点n多元函数的一阶必要条件（P106-107)定理1:若为的局部多元函数的二阶充分条件定理2:若在 内 二阶连续可导，且 正定,则 为严格局部 极小点 注:如果 负定,则 为严格局部极大点 n多元函数的二阶充分条件定理2:若在 内 二阶连续可导，二阶必要条件和充要条件定理3:若为的局部极小点，且在内二阶连续可导，则半正定定理4:设在上是凸函数且有一阶连续偏导数，则为的整体极小点的充要条件是n二阶必要条件和充要条件定理3:若为的局部极小点，且在内二阶连例1：利用极值条件解下列问题：解：令即：得到驻点：n例1：利用极值条件解下列问题：解：令即：得到驻点：函数的海色阵：由此，在点处的海色阵依次为：n函数的海色阵：由此，在点处的海色阵依次为：由于矩阵不定，则不是极小点负定，则不是极小点，实际上它是极大点正定，则是局部极小点n由于矩阵不定，则不是极小点负定，则不是极小点，实际上它是极约束最优性条件约束最优性条件(p133-p136)n约束最优性条件(p133-p136)定义1:有效约束：若(*)中的一个可行点使得某个不等式约束变成等式，即则称为关于 的有效(积极）约束非有效约束：若对则称为关于的非有效(无效）约束有效集：定义2:锥：的子集，如果它关于正的数乘运算是封闭的 如果锥也是凸集，则称为凸锥凸锥关于加法和正的数乘运算是封闭的n定义1:有效约束：若(*)中的一个可行点使得某个不等式约束变一阶必要条件定理3.5:(Kuhn-Tucker一阶必要条件)(1951)设在（K-T条件）条件）n一阶必要条件定理3.5:(Kuhn-Tucker一阶必要条件一阶必要条件定理1:(Kuhn-Tucker一阶必要条件)（互补松弛条件）（互补松弛条件）n一阶必要条件定理1:(Kuhn-Tucker一阶必要条件)n非线性优化问题ppt课件例2：验证 是否满足Kuhn-Tucker条件：试验证最优点为KT点n例2：验证 是否满足Kuhn-Tucker条件：试验证最优解：令所以即：所以：是KT点n解：令所以即：所以：是KT点Lagrange函数及K-T条件nLagrange函数及K-T 条件在一定凸性下的最优性的充分条件在一定凸性下的最优性的充分条件n在一定凸性下的最优性的充分条件一维最优化方法（线性搜索方法）一维最优化方法（线性搜索方法）已知并且求出了处的可行下降方向从出发，沿方向求目标函数的最优解，或者选取使得：问题描述即即n一维最优化方法（线性搜索方法）已知并且求出了处的可行下降方向设其最优解为（叫精确步长因子），所以线性搜索是求解一元函数的最优化问题（也叫一维最优化问题）。我们来求解：于是得到一个新点：n设其最优解为（叫精确步长因子），所以线性搜索是求解一元函数的一般地，线性搜索算法分成两个阶段：第一阶段确定包含理想的步长因子（或问题最优解）的搜索区间；第二阶段采用某种分割技术或插值方法缩小这个区间。搜索区间：搜索区间：n一般地，线性搜索算法分成两个阶段：第一阶段确定包含理想的步长搜索区间求取方法搜索区间求取方法 n进退法：进退法：一种简单的确定初始搜索区间方法.n基本思想：基本思想：是从一点出发，按一定步长，试图确定出函数值呈现“高-低-高”的三点，即 这里 。具体地说，就是给出初始点 ，初始步长 ，若 ，则下一步从新点 出发，加大步长，再向前搜索，直到目标函数上升为止。n搜索区间求取方法 进退法：一种简单的确定初始搜索区间方法.若 ，则下一步仍以 为出发点，沿反方向同样搜索，直到目标函数上升就停止。这样便得到一个搜索区间。这种方法叫进退法。n计算步骤：见计算步骤：见P96n计算框图计算框图:见见P97n 若 n非线性优化问题ppt课件黄金分割法（黄金分割法（0.6180.618法）法）n基本思想：它通过对试探点的函数值进行比较，使得包含极小点的区间不断缩短，当区间长度小到精度范围之内时，可以粗略地认为区间上各点的函数值均接近于极小值。n黄金分割法（0.618法）基本思想：设在上为下单峰函数，即有唯一的极小点在左边严格下降，在右边严格上升。在内任取若则若则单峰函数：黄金分割法黄金分割法n设在上为下单峰函数，即有唯一的极小点在左边严格下降，在右边严黄金分割法若第一次选取的试点为则下一步保留的区间为或两者的机会是均等的因此我们选取试点时希望设则另外，我们希望如果缩小的区间包含原来的试点，则该试点在下一步被利用若保留的区n黄金分割法若第一次选取的试点为则下一步保留的区间为或两者的机我们希望原来的间为前一次的试点在这个区间内在缩小的区间内成为新的我们根据这条件 来计算计算的公式为：因此我们希望：即：n我们希望原来的间为前一次的试点在这个区间内在缩小的区间内成化简得：若保留区间为我们得到的结果是一致的 该方法称为黄金分割法，实际计算取：所以黄金分割法又称为0.618法黄金分割法每次缩小区间的比例是一致的，每次将区间长度缩小到原来的0.618倍n化简得：若保留区间为我们得到的结果是一致的该方法称为黄金分 黄金分割法的算法步骤Step1给定以及令Step2Step3转Step.令转Step.若则停；否则转Step.Step4 若则转Step3.n 黄金分割法的算法步骤Step1给定以及令Step2Step黄金分割法的算法步骤Step5 若则转Step3.若则转Step3.n黄金分割法的算法步骤Step5若则转Step3.若则转Ste例1（黄金分割法）用黄金分割法求函数在区间上的极小点。要求最终区间长度不大于原始区间长度的0.08倍解：函数在区间上为下单峰函数，n例1（黄金分割法）用黄金分割法求函数在区间上的极小点。要求最第一次迭代：缩短后区间为第二次迭代：缩短后区间为n第一次迭代：缩短后区间为第二次迭代：缩短后区间为迭代次数0.5281.4721.7512.695否-0.0560.5282.0591.751否0.5280.8881.7511.901否0.3050.5281.7881.751否0.5280.6651.7511.777否0.4430.5281.7531.751否0.5280.5801.7511.757是n迭代0.5281.4721.7512.695否-0.05Fibonacci法为了尽快得到结果，希望区间缩小的尽量小。如果在区间只有一个试点，我们无法将区间缩小。如果知道两个试点根据的大 小关系，可以得到缩小的区间或者 它与0.618法的主要区别之一在于：搜索区间长度的缩短率不是采用0.618，而是采用Fibonacci数。nFibonacci法为了尽快得到结果，希望区间缩小的尽量小。下面我们考虑任给一个另外一种思维方式为，的单峰区间如果给定试点的个数如何使最后确定最优值的区间尽量的小。按什么方式取点，求次函数值之后，可最多将多长的原始区间长度缩小为设为试点个数为最终区间长度为时、原始区间的最大可能长度。的包含n下面我们考虑任给一个另外一种思维方式为，的单峰区间如果给定试设最初两个试点为和若极小点在内，至多还有个试点，则若极小点在内，包括在内可以有个试点，则因此，如果我们采取合适的技巧，可以使得：另外，显然，n设最初两个试点为和若极小点在内，至多还有个试点，则若极小点在从而满足差分方程：此为Fibonacci数列，一般写为：n从而满足差分方程：此为Fibonacci数列，一般写为：若原始区间为要求最终区间长度则由此可确定区间缩短之后与之前的比依次为：确定之后，最初两个试点分别为：关于对称由于 n若原始区间为要求最终区间长度则由此可确定区间缩短之后与之前的上述过程完成了依次迭代，新区间仍记为若已经进行了次迭代，第次迭代时，还有个试点（包括已经计算过的函数值的一个）注意注意：（）若在一定的误差范围内，则认为在内。（）最后的两个试点的选取方式：n上述过程完成了依次迭代，新区间仍记为若已经进行了次迭代，第次例3.1（Fibonacci法）用Fibonacci法求函数在区间上的极小点。要求最终区间长度不大于原始区间长度的0.08倍解：函数在区间上为下单峰函数，由可知应取Fibonacci算法与算法与0.618法几乎完全相同法几乎完全相同。n例3.1（Fibonacci法）用Fibonacci法求函数第一次迭代：缩短后区间为n第一次迭代：缩短后区间为第二次迭代：缩短后区间为n第二次迭代：缩短后区间为第三次迭代：缩短后区间为第四次迭代：缩短后区间为n第三次迭代：缩短后区间为第四次迭代：缩短后区间为第五次迭代：取最优解n第五次迭代：取最优解Fibonacci方法评价Fibonacci法的优点（）如果缩小的区间包含原来的试点，则该试点在下一步被利用；（）效率最高，有限个试点的情况下，可将最优点所在的区间缩小到最小nFibonacci方法评价Fibonacci法的优点（）如Fibonacci法的缺点（）搜索前先要计算搜索的步数；（）每次搜索试点计算的公式不一致1、黄金分割法（、黄金分割法（0.618法）与法）与Fibonacci法法的区别与联系是什么？的区别与联系是什么？2、请读者自己写出算法和程序、请读者自己写出算法和程序 nFibonacci法的缺点（）搜索前先要计算搜索的步数；（二分法二分法若的导数存在且容易计算，则线性搜索的速度可以得到提高 下面的二分法每次将区间缩小至原来的二分之一设为下单峰函数，若在内具有连续的一阶导数，且n二分法若的导数存在且容易计算，则线性搜索的速度可以得到提高取若则为极小点；若则以代替若则以代替 二分法每次迭代都将区间缩短一半，故二分法的收敛速度也是线性的，收敛比为1/2。n 计算步骤：见计算步骤：见P105n 计算框图计算框图:见见P106n取若则为极小点；若则以代替若则以代替 二分法每次迭代多维无约束最优化方法多维无约束最优化方法n最速下降法最速下降法n(阻尼阻尼)牛顿法牛顿法n共轭梯度法共轭梯度法n多维无约束最优化方法最速下降法最速下降法最速下降法n最速下降法问题提出问题：在点处，沿什么方向下降最快?分析：考查：显然当时，取极小值因此：结论：负梯度方向使下降最快，亦即最速下降方向n问题提出问题：在点处，沿什么方向下降最快?分析：考查：显然当最速下降法算法Step1:给出Step2:计算如果停Step3:计算下降方向Step4:计算步长因子Step5:令转步.n最速下降法算法Step1:给出Step2:计算如果停Ste问题：设是正定二次函数,由精确的线搜索确定的特别当：n问题：设是正定二次函数,由精确的线搜索确定的特别当：例1：用最速下降法求解：解：n例1：用最速下降法求解：解：分析：(1)因此：最速下降法是整体收敛的，且是线性收敛的(2)两个相邻的搜索方向是正交的n分析：(1)因此：最速下降法是整体收敛的，且是线性收敛的(n非线性优化问题ppt课件收敛性分析定理1:设在上存在且一致连续，则最速下降法产生的序列满足或者对某个有或者证明：对于最速下降法，由以上定理立得n收敛性分析定理1:设在上存在且一致连续，则最速下降法产生的序收敛性分析定理2:设二次连续可微，且其中是个正常数，对任何给定的初始点最速下降算法或有限终止，或者或者证明：用以上的结论：n收敛性分析定理2:设二次连续可微，且其中是个正常数，对任何给最速下降法优点(1)程序设计简单，计算量小，存储量小，对初始点没有特别要求(2)有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛n最速下降法优点(1)程序设计简单，计算量小，存储量小，对初始最速下降法缺点最速下降法是线性收敛的，并且有时是很慢的线性收敛原因：仅反映在处的局部性质相继两次迭代中搜索方向是正交的n最速下降法缺点最速下降法是线性收敛的，并且有时是很慢的线性收小结最速下降法是基本算法之一，而非有效的实用算法最速下降法的本质是用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近n小结最速下降法是基本算法之一，而非有效的实用算法最速下降法牛顿法牛顿法n牛顿法基本思想利用目标函数在点处的二阶Taylor展开式去近似目标函数，用二次函数的极小点去逼近目标函数的极小点n基本思想利用目标函数在点处的二阶Taylor展开式去近似目标算法构造问题：设二阶连续可微，海色阵正定如何从因为正定，则有唯一极小点，用这个极小点作为n算法构造问题：设二阶连续可微，海色阵正定如何从因为正定，则所以要求：即：因此：这就是牛顿法迭代公式注：这里n所以要求：即：因此：这就是牛顿法迭代公式注：这里牛顿法算法Step1:给出Step2:计算如果停Step3:否则计算Step4:令转步.并且求解方程得出n牛顿法算法Step1:给出Step2:计算如果停Step3例1：用牛顿法求解：解：n例1：用牛顿法求解：解：牛顿法收敛定理定理定理1:设二次连续可微，是的局部极小点，正定 假定的海色阵满足Lipschitz条件，即存在使得对于所有有：其中是海色阵的元素 则当充分靠近时，对于一切牛顿迭代有意义，迭代序列收敛到并且具有二阶收敛速度n牛顿法收敛定理定理1:设二次连续可微，是的局部极小点，正定牛顿法优点(1)(2)对正定二次函数，迭代一次就可以得到极小点如果正定且初始点选取合适，算法二阶收敛n牛顿法优点(1)(2)对正定二次函数，迭代一次就可以得到极小牛顿法缺点(1)(2)对多数问题算法不是整体收敛的每次都需要计算计算量大(3)每次都需要解方程组有时奇异或病态的，无法确定或不是下降方向(4)收敛到鞍点或极大点的可能性并不小n牛顿法缺点(1)(2)对多数问题算法不是整体收敛的每次都需阻尼牛顿法算法Step1:给出Step2:计算如果停Step3:否则计算Step4:沿并且求解方程得出进行线搜索，得出Step5:令转Step2.n阻尼牛顿法算法Step1:给出Step2:计算如果停Ste阻尼牛顿法收敛定理定理定理2:设二阶连续可微，又设对任意的存在常数使得在上满足：则在精确线搜索条件下，阻尼牛顿法产生的点列满足：(1)当是有限点列时，其最后一个点为的唯一极小点(2)当是无限点列时，收敛到的唯一极小点n阻尼牛顿法收敛定理定理2:设二阶连续可微，又设对任意的存在常阻尼牛顿法收敛定理定理定理3:设二阶连续可微，又设对任意的存在常数使得在上满足：则在Wolfe不精确线搜索条件下，阻尼牛顿法产生的点列满足：且收敛到的唯一极小点n阻尼牛顿法收敛定理定理3:设二阶连续可微，又设对任意的存在常例2：用阻尼牛顿法求解：解：显然不是正定的，但：于是，沿方向进行线搜索，得其极小点从而迭代不能继续下去n例2：用阻尼牛顿法求解：解：显然不是正定的，但：于是，沿方向带保护的牛顿法算法给出Step1:若为奇异的，转Step8，否则，Step2:令Step3:若为奇异的，转Step8，否则，则转Step8，否则，Step4:若则转Step9，否则，Step5:沿方向进行线搜索，求出并令n带保护的牛顿法算法给出Step1:若为奇异的，转Step8，Step6:若停；Step7:令转Step1；Step8:令转Step5；Step9:令转Step5.nStep6:若停；Step7:令转Step1；Step8:令例3：用带保护的牛顿法求解：解：显然不是正定的，但：于是，因为，故令，沿进行线搜索得：n例3：用带保护的牛顿法求解：解：显然不是正定的，但：于是，因第二次迭代：而：使故令沿进行线搜索，得出于是:此时:n第二次迭代：而：使故令沿进行线搜索，得出于是:此时:共轭梯度法共轭梯度法n共轭梯度法问题1:如何建立有效的算法？从二次模型到一般模型问题2:什么样的算法有效呢？二次终止性(经过有限次迭代必达到极小点的性质）n问题1:如何建立有效的算法？从二次模型到一般模型问题2:什么算法特点（）建立在二次模型上，具有二次终止性（）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点（）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法n算法特点（）建立在二次模型上，具有二次终止性（）有效的共轭方向及其性质定义1:设是中任一组非零向量，如果：则称是关于共轭的注：若则是正交的，因此共轭是正交的推广n共轭方向及其性质定义1:设是中任一组非零向量，如果：则称是关定理1:设为阶正定阵，非零向量组关于共轭，则必线性无关推论1:设为 阶正定阵，非零向量组关于共轭，则向量构成的一组基推论2:设为阶正定阵，非零向量组关于共轭，若向量与关于共轭，则n定理1:设为阶正定阵，非零向量组关于共轭，则必线性无关推论求 的极小点的方法共轭方向法算法Step1:给出计算和初始下降方向Step2:如果停止迭代Step3:计算使得Step4:采用某种共轭方向法计算使得：Step5:令转Step2.n求 的极小点的方法共轭方向法算共轭方向法基本定理定义2:设维向量组线性无关，向量集合为与生成的维超平面n共轭方向法基本定理定义2:设维向量组线性无关，向量集合为与生引理1:设是连续可微的严格凸函数，维向量组线性无关，则：是在上唯一极小点的充要条件是：n引理1:设是连续可微的严格凸函数，维向量组线性无关，则：是在定理2:设为 阶正定阵，向量组关于共轭，对正定二次函数由任意开始，依次进行次精确线搜索：则：（）（）是在上的极小点推论:当时，为正定二次函数在上的极小点n定理2:设为阶正定阵，向量组关于共轭，对正定二次函数由任意开共轭梯度法记：左乘并使得：（Hestenes-Stiefel公式）取：是一种特殊的共轭方向法是一种特殊的共轭方向法n共轭梯度法记：左乘并使得：（Hestenes-Stiefel共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的共轭梯度法在步后终止，且对成立下列关系式：（共轭性）（正交性）（下降条件）n共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的系数的其他形式（）FR公式（1964）（2）PRP公式（1969）n系数的其他形式（）FR公式（1964）（2）PRP公式（1FR共轭梯度法算法Step1:给出Step2:如果停Step5:转Step2.计算计算Step4:Step3:由精确线搜索求计算nFR共轭梯度法算法Step1:给出Step2:如果停Ste例4：用FR共轭梯度法求解：解：化成形式(1)n例4：用FR共轭梯度法求解：解：化成形式(1)(2)n(2)n非线性优化问题ppt课件例5：用FR共轭梯度法求解：解：化成形式(1)n例5：用FR共轭梯度法求解：解：化成形式(1)(2)n(2)注意：注意：FR方法中初始搜索方向必须取最速下降方方法中初始搜索方向必须取最速下降方向，才满足二次终止性。向，才满足二次终止性。n注意：FR方法中初始搜索方向必须取最速下降方向，才满足二次终FR共轭梯度法收敛定理定理定理4:假定在有界水平集上连续可微，且有下界，那么采用精确线搜索下的FR共轭梯度法产生的点列至少有一个聚点是驻点，即：(1)当是有穷点列时，其最后一个点是的驻点(2)当是无穷点列时，它必有聚点，且任一聚点都是的驻点nFR共轭梯度法收敛定理定理4:假定在有界水平集上连续可微，且再开始FR共轭梯度法算法Step1:给出Step2:计算如果停，Step4:否则Step3:由精确线搜索求并令：计算若令转Step2;如果停.n再开始FR共轭梯度法算法Step1:给出Step2:计算如果Step5:若令转step2.Step6:计算Step7:如果令转step2,否则 转step3.nStep5:若令转step2.Step6:计算Step7:如作业用FR共轭梯度法求解：n作业用FR共轭梯度法求解：多维约束最优化方法多维约束最优化方法n惩罚函数法惩罚函数法 SUMT:SUMT:序列无约束极小化方法序列无约束极小化方法 (Sequential Unconstrained Minimization Technique)n乘子法乘子法外点法（二次罚函数方法）内点法（内点障碍罚函数法）n多维约束最优化方法外点法（二次罚函数方法）内点法（内点障碍罚函数法罚函数法n罚函数法基本思想设法将约束问题求解转化为无约束问题求解具体说：根据约束的特点，构造某种惩罚函数，然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解惩罚策略：企图违反约束的迭代点给予很大的目标函数值 迫使一系列无约束问题的极小点或者无限地靠近可行域，或者一直保持在可行域内移动，直到收敛到极小点n基本思想设法将约束问题求解转化为无约束问题求解具体说：根据外罚函数法（外点法）引例：求解等式约束问题:解:图解法求出最优解构造：但是性态极坏，无法用有效的无约束优化算法求解n外罚函数法（外点法）引例：求解等式约束问题:解:图解法求出最设想构造：其中是很大的正数求解此无约束问题得：当时，有：n设想构造：其中是很大的正数求解此无约束问题得：当时，有：等式约束问题构造：其中为参数，称为罚因子分析：当 不是可行解时，越大，惩罚越重 因此当充分大时，应充分小即的极小点应充分逼近可行域，进而逼近(1)的最优解n等式约束问题构造：其中为参数，称为罚因子分析：当不是可行解不等式约束问题构造：分析：当 不是可行解时，越大，惩罚越重 因此当充分大时，应充分小即的极小点应充分逼近可行域，进而逼近(2)的最优解n不等式约束问题构造：分析：当不是可行解时，越大，惩罚越重因一般约束问题构造：其中：n一般约束问题构造：其中：例1：用外罚函数法求解：解：即：因此：n例1：用外罚函数法求解：解：即：因此：令：得：最优值：当时：n令：得：最优值：当时：注：(1)往往不满足约束条件，都是从可行域外部趋向于的 因此叫外罚函数法(2)通过求解一系列无约束最优化问题来求解约束最优化问题的方法，又称为序列无约束极小化技术SUMT.外罚函数法,又称SUMT外点法n注：(1)往往不满足约束条件，都是从可行域外部趋向于的因此外罚函数法算法步骤Step1:给出(可是不可行点)，罚因子放大系数Step2:以为初始点求无约束问题：得Step3:若则停；否则转step4Step4:令转step2.n外罚函数法算法步骤Step1:给出(可是不可行点)，罚因子放例2：用SUMT外点法求解：取求解迭代过程见下表：n例2：用SUMT外点法求解：取求解迭代过程见下表：0.1(1.4539,0.7608)0.09350.18311(1.1687,0.7407)0.57530.390810(0.9906,0.8425)0.52030.1926100(0.9507,0.8875)1.94050.0267n0.1(1.4539,0.7608)0.09350.183收敛性分析引理1：对于由SUMT外点法产生的点列则有：设设n收敛性分析引理1：对于由SUMT外点法产生的点列则有：设收敛性分析定理1：设约束问题(3)和无约束问题(4)的整体最优解为和对正数序列且则由SUMT外点法产生的点列的任何聚点必是(3)的整体最优解证：不妨设因为和分别为(3)和(4)的整体最优解，且所以有：n收敛性分析定理1：设约束问题(3)和无约束问题(4)的整体最为单调有界序列，设其极限为亦为单调有界序列，设其极限为且连续；即为可行解为最优解；连续；即为(3)的整体最优解n为单调有界序列，设其极限为亦为单调有界序列，设其极限为且连续外罚函数法评价(1)如果有了求解无约束问题的好算法，利用外罚函数法求解约束问题很方便(2)每个近似解往往不是可行解，这是某些实际问题所无法接受的 内罚函数法可以解决(3)由收敛性定理取越大越好，而越大将造成增广目标函数的Hesse阵条件数越大，趋于病态，给无约束问题求解增加很大困难，甚至无法求解乘子法可解决这个问题n外罚函数法评价(1)如果有了求解无约束问题的好算法，利用外罚内罚函数法惩罚策略：在可行域的边界上筑起一道很高的“围墙”，当迭代点靠近边界时，目标函数值陡然增大，以示惩罚，阻止迭代点穿越边界，这样就可以把最优解“挡”在可行域内了注：惩罚策略只适合于不等式约束问题，并且要求可行域的内点集非空n内罚函数法惩罚策略：在可行域的边界上筑起一道很高的“围墙”，不等式约束问题构造：其中：或分析：为可行域的内点时，为有限正数，几乎不受惩罚；接近边界时，趋于无穷大，施以很重的惩罚；迫使极小点落在可行域内，最终逼近极小点n不等式约束问题构造：其中：或分析：为可行域的内点时，为有限正例3：用内罚函数法求解：解：令：n例3：用内罚函数法求解：解：令：所以当时，注：一般最优解很难用解析法求出，需采用序列无约束最优化方法n所以当时，注：一般最优解很难用解析法求出，需采用序列无约束最内罚函数法算法Step1:给出(要求是可行点)，罚因子缩小系数Step2:以为初始点求无约束问题：得Step3:若则停；否则转step4Step4:令转step2.n内罚函数法算法Step1:给出(要求是可行点)，罚因子缩小系例4：用SUMT内点法求解：取迭代结果见下表：n例4：用SUMT内点法求解：取迭代结果见下表：10(2.0402,3.1623)12.529012.77551(1.1473,0.3162)3.61650.99510.1(1.0488,0.1000)2.96670.30490.01(1.0157,0.0316)2.76160.09530.001(1.0016,0.0316)2.70460.0941n10(2.0402,3.1623)12.529012.77收敛性分析引理2：对于由SUMT内点法产生的点列总有：定理2：设可行域的内点集非空，在 上存在极小点对严格单减正数列且则由SUMT内点法产生的点列的任何聚点是约束问题(2)的最优解n收敛性分析引理2：对于由SUMT内点法产生的点列总有：定理2证：由于由引理2知单调减少且下有界，于是它有极限，记作即：若能证明：则可得：再由的连续性，可得：即是(2)的最优解n证：由于由引理2知单调减少且下有界，于是它有极限，记作即：若再证：由的连续性知，对于任意小的正数存在取满足的使得：由知，对于同一个存在当时又因为n再证：由的连续性知，对于任意小的正数存在取满足的使得：由知，乘子法引例：求解等式约束问题:解:最优解分析：对于任何关于 的极小点是不存在的正因为如此，才引进外罚函数法的n乘子法引例：求解等式约束问题:解:最优解分析：对于任何关于的问题：能否找到某个使恰好是的无约束极小呢？回答是否定的设想：能否在不改变最优解的前提下，以某个在最优解处梯度为零的函数来取代呢？启发：(增广Lagrange函数)通过求解增广Lagrange函数的序列无约束问题来获得原约束问题的解n问题：能否找到某个使恰好是的无约束极小呢？回答是否定的设想等式约束问题的乘子法其中和二阶连续可微设为Lagrange乘子向量，则对应Lagrange 函数为：设是的极小点，是相应的乘子向量(1)可等价为：n等式约束问题的乘子法其中和二阶连续可微设为Lagrange启发：采用外罚函数法构造：我们将证明：适当大时，是极小点但是未知的，在求的同时，采用迭代法求出这是乘子法的基本思想n启发：采用外罚函数法构造：我们将证明：适当大时，是极小点定理：设与满足为问题(1)的严格局部极小点的二阶充分条件，则存在使对所有为的严格局部极小点；反之，若且对某个是无约束问题(5)的局部极小点，则是约束问题(1)的局部极小点.n定理：设与满足为问题(1)的严格局部极小点的二阶充分条件，算法构造采用迭代法求点列使设已有和则由一阶最优性条件有：要求和且采用：或：n算法构造采用迭代法求点列使设已有和则由一阶最优性条件有：要求例5：用乘子法求解：解：增广Lagrange函数为：令：得：n例5：用乘子法求解：解：增广Lagrange函数为：令：得：所以：乘子迭代公式为：即：取：所以：设对上式取极限有：得：得：也可不取特定值，直接对上式求极限也可不取特定值，直接对上式求极限n所以：乘子迭代公式为：即：取：所以：设对上式取极限有：得：得等式约束的乘子法(PH算法)Step1:给出Step2:以为初始点求无约束问题：得Step3:若则停；否则转step4Step4:当及放大系数转step5;否则,转step5;Step5:令转step2.n等式约束的乘子法(PH算法)Step1:给出Step2:以为作业(1)用外罚函数法求解：(2)用内罚函数法求解：n作业(1)用外罚函数法求解：(2)用内罚函数法求解：