非线性优化问题ppt课件(PPT 163页)

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

2、组约束条件下 的极值问题。在目标函数或约束条件中，至少有一个是变量的非线性函数。.第4页，共163页。非线性规划问题一般形式：向量形式：.第5页，共163页。非线性优化问题的寻优相关概念及理论一维最优化方法多维无约束最优化方法多维有约束最优化方法.第6页，共163页。非线性规划的相关概念及理论一阶导数、二阶导数和n元函数的Taylor公式.第7页，共163页。.第8页，共163页。.第9页，共163页。定义4设函数定义在凸集上，若对任意的及任意的都有：则称函数为凸集上的凸函数定义5严格凸函数注：将上述定义中的不等式反向，可以得到凹函数的定义凸函数.第10页，共163页。例1：设试证明在上是严格

3、凸函数证明:设且都有：因此在上是严格凸函数.第11页，共163页。例2：试证线性函数是证明:设上的凸函数则所以是凸函数类似可以证明是凹函数.第12页，共163页。凸函数的几何性质对一元函数在几何上表示连接的线段表示在点处的函数值所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.第13页，共163页。.第14页，共163页。凸函数的性质（）设（）设函数，是凸集上的凸函数，实数则也是上的凸函数是凸集上的凸实数则也是上的凸函数（）设是凸集上的凸函数，是实数，则水平集是凸集.第15页，共163页。下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集.第16页，共163页。凸函数

4、的判定定理1设上，令则:(1)是定义在凸集是凸集上的凸函数的充要条件是对任意的一元函数为上的凸函数.(2)设若在上为严格凸函数，则在上为严格凸函数.第17页，共163页。该定理的几何意义是：凸函数上任意两点之间的部分是一段向下凸的弧.第18页，共163页。一阶条件定理2.1设在凸集上可微，则：在上为凸函数的充要条件是对任意的都有：定理2.2严格凸函数(充要条件).第19页，共163页。二阶条件定理3设在开凸集内二阶可微，则(1)是内的凸函数的充要条件为，在内任一点处，的海色矩阵半正定,其中：.第20页，共163页。二阶条件定理3设在开凸集内(2)若在内正定,则在内二阶可微，则是严格凸函数注:反

5、之不成立例：显然是严格凸的，但在点处不是正定的.第21页，共163页。凸规划定义6设为凸集，为上的凸函数，则称规划问题为凸规划问题定理4(1)凸规划问题的任一局部极小点是整体极小点，全体极小点组成凸集(2)若是凸集上的严格凸函数，且凸规划问题整体极小点存在，则整体极小点是唯一的.第22页，共163页。非线性规划的最优性条件 最优性条件：是指非线性规划模型的最优解所要满足的必要和充分条件。无约束最优性条件 约束最优性条件 .第23页，共163页。无约束最优性条件.第24页，共163页。一（单）元函数的最优性条件（）若（）为的局部极小点，则若则为的严格局部极小点；若（）为的局部极小点，则：.第25

6、页，共163页。多元函数的一阶必要条件（P106-107)定理1:若为的局部极小点，且在内一阶连续可导，则注:(1)仅仅是必要条件，而非充分条件(2)满足的点称为驻点驻点分为：极小点，极大点，鞍点.第26页，共163页。多元函数的二阶充分条件定理2:若在 内 二阶连续可导， 且 正定, 则 为严格局部 极小点 注:如果 负定, 则 为严格局部极大点 .第27页，共163页。二阶必要条件和充要条件定理3:若为的局部极小点，且在内二阶连续可导，则半正定定理4:设在上是凸函数且有一阶连续偏导数，则为的整体极小点的充要条件是.第28页，共163页。例1：利用极值条件解下列问题：解：令即：得到驻点：.第

7、29页，共163页。函数的海色阵：由此，在点处的海色阵依次为：.第30页，共163页。由于矩阵不定，则不是极小点负定，则不是极小点，实际上它是极大点正定，则是局部极小点.第31页，共163页。约束最优性条件(p133-p136).第32页，共163页。定义1:有效约束：若(*)中的一个可行点使得某个不等式约束变成等式，即则称为关于的有效(积极）约束非有效约束：若对则称为关于的非有效(无效）约束有效集：定义2:锥：的子集，如果它关于正的数乘运算是封闭的如果锥也是凸集，则称为凸锥凸锥关于加法和正的数乘运算是封闭的.第33页，共163页。一阶必要条件定理3.5:(Kuhn-Tucker一阶必要条件)

8、(1951)设在（K-T条件）.第34页，共163页。一阶必要条件定理1:(Kuhn-Tucker一阶必要条件)（互补松弛条件）.第35页，共163页。.第36页，共163页。例2：验证 是否满足Kuhn-Tucker条件：试验证最优点为KT点.第37页，共163页。解：令所以即：所以：是KT点.第38页，共163页。Lagrange函数及K-T条件.第39页，共163页。在一定凸性下的最优性的充分条件.第40页，共163页。一维最优化方法（线性搜索方法）已知并且求出了处的可行下降方向从出发，沿方向求目标函数的最优解，或者选取使得：问题描述即.第41页，共163页。设其最优解为（叫精确步长因子

9、），所以线性搜索是求解一元函数的最优化问题（也叫一维最优化问题）。我们来求解：于是得到一个新点：.第42页，共163页。一般地，线性搜索算法分成两个阶段：第一阶段确定包含理想的步长因子（或问题最优解）的搜索区间；第二阶段采用某种分割技术或插值方法缩小这个区间。搜索区间：.第43页，共163页。搜索区间求取方法 进退法：一种简单的确定初始搜索区间方法.基本思想：是从一点出发，按一定步长，试图确定出函数值呈现“高-低-高”的三点，即 这里 。 具体地说，就是给出初始点 ，初始步长 ，若 ，则下一步从新点 出发，加大步长，再向前搜索，直到目标函数上升为止。 .第44页，共163页。 若 ，则下一步仍

10、以 为出发点，沿反方向同样搜索，直到目标函数上升就停止。这样便得到一个搜索区间。这种方法叫进退法。 计算步骤：见P96计算框图:见P97.第45页，共163页。.第46页，共163页。黄金分割法（0.618法）基本思想： 它通过对试探点的函数值进行比较，使得包含极小点的区间不断缩短，当区间长度小到精度范围之内时，可以粗略地认为区间上各点的函数值均接近于极小值。.第47页，共163页。设在上为下单峰函数，即有唯一的极小点在左边严格下降，在右边严格上升。在内任取若则若则单峰函数：黄金分割法.第48页，共163页。黄金分割法若第一次选取的试点为则下一步保留的区间为或两者的机会是均等的因此我们选取试点

11、时希望设则另外，我们希望如果缩小的区间包含原来的试点，则该试点在下一步被利用若保留的区.第49页，共163页。我们希望原来的间为前一次的试点在这个区间内在缩小的区间内成为新的我们根据这条件 来计算计算的公式为：因此我们希望：即：.第50页，共163页。化简得：若保留区间为我们得到的结果是一致的该方法称为黄金分割法，实际计算取：所以黄金分割法又称为0.618法黄金分割法每次缩小区间的比例是一致的，每次将区间长度缩小到原来的0.618倍.第51页，共163页。 黄金分割法的算法步骤Step1给定以及令Step2Step3转Step.令转Step.若则停；否则转Step.Step4若则转Step3.

12、第52页，共163页。黄金分割法的算法步骤Step5若则转Step3.若则转Step3.第53页，共163页。例1（黄金分割法）用黄金分割法求函数在区间上的极小点。要求最终区间长度不大于原始区间长度的0.08倍解：函数在区间上为下单峰函数，.第54页，共163页。第一次迭代：缩短后区间为第二次迭代：缩短后区间为.第55页，共163页。迭代次数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

13、.5280.5801.7511.757是.第56页，共163页。Fibonacci法为了尽快得到结果，希望区间缩小的尽量小。 如果在区间只有一个试点，我们无法将区间缩小。如果知道两个试点根据的大小关系，可以得到缩小的区间或者 它与0.618法的主要区别之一在于：搜索区间长度的缩短率不是采用0.618，而是采用Fibonacci数。 .第57页，共163页。下面我们考虑任给一个另外一种思维方式为，的单峰区间如果给定试点的个数如何使最后确定最优值的区间尽量的小。按什么方式取点，求次函数值之后，可最多将多长的原始区间长度缩小为设为试点个数为最终区间长度为时、原始区间的最大可能长度。的包含.第58页，

14、共163页。设最初两个试点为和若极小点在内，至多还有个试点，则若极小点在内，包括在内可以有个试点，则因此，如果我们采取合适的技巧，可以使得：另外，显然，.第59页，共163页。从而满足差分方程：此为Fibonacci数列，一般写为：.第60页，共163页。若原始区间为要求最终区间长度则由此可确定区间缩短之后与之前的比依次为：确定之后，最初两个试点分别为：关于对称由于 .第61页，共163页。上述过程完成了依次迭代，新区间仍记为若已经进行了次迭代，第次迭代时，还有个试点（包括已经计算过的函数值的一个）注意：（）若在一定的误差范围内，则认为在内。（）最后的两个试点的选取方式：.第62页，共163页

15、。例3.1（Fibonacci法）用Fibonacci法求函数在区间上的极小点。要求最终区间长度不大于原始区间长度的0.08倍解：函数在区间上为下单峰函数，由可知应取Fibonacci算法与0.618法几乎完全相同 。.第63页，共163页。第一次迭代：缩短后区间为.第64页，共163页。第二次迭代：缩短后区间为.第65页，共163页。第三次迭代：缩短后区间为第四次迭代：缩短后区间为.第66页，共163页。第五次迭代：取最优解.第67页，共163页。Fibonacci方法评价Fibonacci法的优点（）如果缩小的区间包含原来的试点，则该试点在下一步被利用；（）效率最高，有限个试点的情况下，可

16、将最优点所在的区间缩小到最小.第68页，共163页。Fibonacci法的缺点（）搜索前先要计算搜索的步数；（）每次搜索试点计算的公式不一致1、黄金分割法（0.618法）与Fibonacci法的区别与联系是什么？2、请读者自己写出算法和程序 .第69页，共163页。二分法若的导数存在且容易计算，则线性搜索的速度可以得到提高下面的二分法每次将区间缩小至原来的二分之一设为下单峰函数，若在内具有连续的一阶导数，且.第70页，共163页。取若则为极小点；若则以代替若则以代替 二分法每次迭代都将区间缩短一半，故二分法的收敛速度也是线性的，收敛比为1/2。 计算步骤：见P105 计算框图:见P106.第7

17、1页，共163页。多维无约束最优化方法最速下降法(阻尼)牛顿法共轭梯度法.第72页，共163页。最速下降法.第73页，共163页。问题提出问题：在点处，沿什么方向下降最快?分析：考查：显然当时，取极小值因此：结论：负梯度方向使下降最快，亦即最速下降方向.第74页，共163页。最速下降法算法Step1:给出Step2:计算如果停Step3:计算下降方向Step4:计算步长因子Step5:令转步.第75页，共163页。问题：设是正定二次函数,由精确的线搜索确定的特别当：.第76页，共163页。例1：用最速下降法求解：解：.第77页，共163页。分析：(1)因此：最速下降法是整体收敛的，且是线性收敛

18、的(2)两个相邻的搜索方向是正交的.第78页，共163页。.第79页，共163页。收敛性分析定理1:设在上存在且一致连续，则最速下降法产生的序列满足或者对某个有或者证明：对于最速下降法，由以上定理立得.第80页，共163页。收敛性分析定理2:设二次连续可微，且其中是个正常数，对任何给定的初始点最速下降算法或有限终止，或者或者证明：用以上的结论：.第81页，共163页。最速下降法优点(1)程序设计简单，计算量小，存储量小，对初始点没有特别要求(2)有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛.第82页，共163页。最速下降法缺点最速下降法是线性收敛的，并且有时是很慢的线性收敛原因：仅

19、反映在处的局部性质相继两次迭代中搜索方向是正交的.第83页，共163页。小结最速下降法是基本算法之一，而非有效的实用算法最速下降法的本质是用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近.第84页，共163页。牛顿法.第85页，共163页。基本思想利用目标函数在点处的二阶Taylor展开式去近似目标函数，用二次函数的极小点去逼近目标函数的极小点.第86页，共163页。算法构造问题：设二阶连续可微，海色阵正定如何从因为正定，则有唯一极小点，用这个极小点作为.第87页，共163页。所以要求：即：因此：这就是牛顿法迭代公式注：这里.第88页，共163页。牛顿法算法Step1:

20、给出Step2:计算如果停Step3:否则计算Step4:令转步.并且求解方程得出.第89页，共163页。例1：用牛顿法求解：解：.第90页，共163页。牛顿法收敛定理定理1:设二次连续可微，是的局部极小点，正定假定的海色阵满足Lipschitz条件，即存在使得对于所有有：其中是海色阵的元素则当充分靠近时，对于一切牛顿迭代有意义，迭代序列收敛到并且具有二阶收敛速度.第91页，共163页。牛顿法优点(1)(2)对正定二次函数，迭代一次就可以得到极小点如果正定且初始点选取合适，算法二阶收敛.第92页，共163页。牛顿法缺点(1)(2)对多数问题算法不是整体收敛的每次都需要计算计算量大(3)每次都需

21、要解方程组有时奇异或病态的，无法确定或不是下降方向(4)收敛到鞍点或极大点的可能性并不小.第93页，共163页。阻尼牛顿法算法Step1:给出Step2:计算如果停Step3:否则计算Step4:沿并且求解方程得出进行线搜索，得出Step5:令转Step2.第94页，共163页。阻尼牛顿法收敛定理定理2:设二阶连续可微，又设对任意的存在常数使得在上满足：则在精确线搜索条件下，阻尼牛顿法产生的点列满足：(1)当是有限点列时，其最后一个点为的唯一极小点(2)当是无限点列时，收敛到的唯一极小点.第95页，共163页。阻尼牛顿法收敛定理定理3:设二阶连续可微，又设对任意的存在常数使得在上满足：则在Wo

22、lfe不精确线搜索条件下，阻尼牛顿法产生的点列满足：且收敛到的唯一极小点.第96页，共163页。例2：用阻尼牛顿法求解：解：显然不是正定的，但：于是，沿方向进行线搜索，得其极小点从而迭代不能继续下去.第97页，共163页。带保护的牛顿法算法给出Step1:若为奇异的，转Step8，否则，Step2:令Step3:若为奇异的，转Step8，否则，则转Step8，否则，Step4:若则转Step9，否则，Step5:沿方向进行线搜索，求出并令.第98页，共163页。Step6:若停；Step7:令转Step1；Step8:令转Step5；Step9:令转Step5.第99页，共163页。例3：用带

23、保护的牛顿法求解：解：显然不是正定的，但：于是，因为，故令，沿进行线搜索得：.第100页，共163页。第二次迭代：而：使故令沿进行线搜索，得出于是:此时:.第101页，共163页。共轭梯度法.第102页，共163页。问题1:如何建立有效的算法？从二次模型到一般模型问题2:什么样的算法有效呢？二次终止性(经过有限次迭代必达到极小点的性质）.第103页，共163页。算法特点（）建立在二次模型上，具有二次终止性（）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点（）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法.第104页，共163页。共轭方向及其

24、性质定义1:设是中任一组非零向量，如果：则称是关于共轭的注：若则是正交的，因此共轭是正交的推广.第105页，共163页。定理1:设为阶正定阵，非零向量组关于共轭，则必线性无关推论1:设为阶正定阵，非零向量组关于共轭，则向量构成的一组基推论2:设为阶正定阵，非零向量组关于共轭，若向量与关于共轭，则.第106页，共163页。求 的极小点的方法共轭方向法算法Step1:给出计算和初始下降方向Step2:如果停止迭代Step3:计算使得Step4:采用某种共轭方向法计算使得：Step5:令转Step2.第107页，共163页。共轭方向法基本定理定义2:设维向量组线性无关，向量集合为与生成的维超平面.第

25、108页，共163页。引理1:设是连续可微的严格凸函数，维向量组线性无关，则：是在上唯一极小点的充要条件是：.第109页，共163页。定理2:设为阶正定阵，向量组关于共轭，对正定二次函数由任意开始，依次进行次精确线搜索：则：（）（）是在上的极小点推论:当时，为正定二次函数在上的极小点.第110页，共163页。共轭梯度法记：左乘并使得：（Hestenes-Stiefel公式）取：是一种特殊的共轭方向法.第111页，共163页。共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的共轭梯度法在步后终止，且对成立下列关系式：（共轭性）（正交性）（下降条件）.第112页，共163页。系数的其他形

26、式（）FR公式（1964）（2）PRP公式（1969）.第113页，共163页。FR共轭梯度法算法Step1:给出Step2:如果停Step5:转Step2.计算Step4:Step3:由精确线搜索求计算.第114页，共163页。例4：用FR共轭梯度法求解：解：化成形式(1).第115页，共163页。(2).第116页，共163页。.第117页，共163页。例5：用FR共轭梯度法求解：解：化成形式(1).第118页，共163页。(2).第119页，共163页。注意：FR方法中初始搜索方向必须取最速下降方向，才满足二次终止性。.第120页，共163页。FR共轭梯度法收敛定理定理4:假定在有界水平

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

28、无约束极小化方法 (Sequential Unconstrained Minimization Technique) 乘子法外点法（二次罚函数方法） 内点法（内点障碍罚函数法） .第125页，共163页。罚函数法.第126页，共163页。基本思想设法将约束问题求解转化为无约束问题求解具体说：根据约束的特点，构造某种惩罚函数，然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解惩罚策略：企图违反约束的迭代点给予很大的目标函数值迫使一系列无约束问题的极小点或者无限地靠近可行域，或者一直保持在可行域内移动，直到收敛到极小点.第127页，共163页。外罚函数法（外点法）引例：求解等式约

29、束问题:解:图解法求出最优解构造：但是性态极坏，无法用有效的无约束优化算法求解.第128页，共163页。设想构造：其中是很大的正数求解此无约束问题得：当时，有：.第129页，共163页。等式约束问题构造：其中为参数，称为罚因子分析：当不是可行解时，越大，惩罚越重因此当充分大时，应充分小即的极小点应充分逼近可行域，进而逼近(1)的最优解.第130页，共163页。不等式约束问题构造：分析：当不是可行解时，越大，惩罚越重因此当充分大时，应充分小即的极小点应充分逼近可行域，进而逼近(2)的最优解.第131页，共163页。一般约束问题构造：其中：.第132页，共163页。例1：用外罚函数法求解：解：即：

30、因此：.第133页，共163页。令：得：最优值：当时：.第134页，共163页。注：(1)往往不满足约束条件，都是从可行域外部趋向于的因此叫外罚函数法(2)通过求解一系列无约束最优化问题来求解约束最优化问题的方法，又称为序列无约束极小化技术SUMT.外罚函数法,又称SUMT外点法.第135页，共163页。外罚函数法算法步骤Step1:给出(可是不可行点)，罚因子放大系数Step2:以为初始点求无约束问题：得Step3:若则停；否则转step4Step4:令转step2.第136页，共163页。例2：用SUMT外点法求解：取求解迭代过程见下表：.第137页，共163页。0.1(1.4539,0.

31、7608)0.09350.18311(1.1687,0.7407)0.57530.390810(0.9906,0.8425)0.52030.1926100(0.9507,0.8875)1.94050.0267.第138页，共163页。收敛性分析引理1：对于由SUMT外点法产生的点列则有：设.第139页，共163页。收敛性分析定理1：设约束问题(3)和无约束问题(4)的整体最优解为和对正数序列且则由SUMT外点法产生的点列的任何聚点必是(3)的整体最优解证：不妨设因为和分别为(3)和(4)的整体最优解，且所以有：.第140页，共163页。为单调有界序列，设其极限为亦为单调有界序列，设其极限为且连

32、续；即为可行解为最优解；连续；即为(3)的整体最优解.第141页，共163页。外罚函数法评价(1)如果有了求解无约束问题的好算法，利用外罚函数法求解约束问题很方便(2)每个近似解往往不是可行解，这是某些实际问题所无法接受的内罚函数法可以解决(3)由收敛性定理取越大越好，而越大将造成增广目标函数的Hesse阵条件数越大，趋于病态，给无约束问题求解增加很大困难，甚至无法求解乘子法可解决这个问题.第142页，共163页。内罚函数法惩罚策略：在可行域的边界上筑起一道很高的“围墙”，当迭代点靠近边界时，目标函数值陡然增大，以示惩罚，阻止迭代点穿越边界，这样就可以把最优解“挡”在可行域内了注：惩罚策略只适

33、合于不等式约束问题，并且要求可行域的内点集非空.第143页，共163页。不等式约束问题构造：其中：或分析：为可行域的内点时，为有限正数，几乎不受惩罚；接近边界时，趋于无穷大，施以很重的惩罚；迫使极小点落在可行域内，最终逼近极小点.第144页，共163页。例3：用内罚函数法求解：解：令：.第145页，共163页。所以当时，注：一般最优解很难用解析法求出，需采用序列无约束最优化方法.第146页，共163页。内罚函数法算法Step1:给出(要求是可行点)，罚因子缩小系数Step2:以为初始点求无约束问题：得Step3:若则停；否则转step4Step4:令转step2.第147页，共163页。例4：用SUMT内点法求解：取迭代结果见下表：.第148页，共163页。10(2.0402,3.1623)12.529012.77551(1.1473,0.3162)3.61650.99510.1(1.0488,0.1000)2.96670.3049