第四章非线性规划山大刁在筠 运筹学讲义(21页).doc

-第四章 非线性规划 山大刁在筠 运筹学讲义-第 21 页第四章 非线性规划教学重点：凸规划及其性质，无约束最优化问题的最优性条件及最速下降法，约束最优化问题的最优性条件及简约梯度法。教学难点：约束最优化问题的最优性条件。教学课时：24学时主要教学环节的组织：在详细讲解各种算法的基础上，结合例题，给学生以具体的认识，再通过大量习题加以巩固，也可以应用软件包解决一些问题。第一节 基本概念教学重点：非线性规划问题的引入，非线性方法概述。教学难点：无。教学课时：2学时主要教学环节的组织：通过具体问题引入非线性规划模型，在具体讲述非线性规划方法的求解难题。1、非线性规划问题举例例1 曲线最优拟合问题已知某物体的温度与时间t之间有如下形式的经验函数关系： （*）其中，是待定参数。现通过测试获得n组与t之间的实验数据，i=1，2，,n。试确定参数，使理论曲线(*)尽可能地与n个测试点拟合。例 2 构件容积问题通过分析我们可以得到如下的规划模型：基本概念设，,如下的数学模型称为数学规划(Mathematical Programming, MP)：约束集或可行域 MP的可行解或可行点MP中目标函数和约束函数中至少有一个不是x的线性函数，称(MP)为非线性规划令 其中，那么(MP)可简记为 或者 当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。否则，称为约束非线性规划或者约束最优化问题。定义 对于非线性规划(MP)，若，并且有则称是(MP)的整体最优解或整体极小点，称是(MP)的整体最优值或整体极小值。如果有则称是(MP)的严格整体最优解或严格整体极小点，称是(MP)的严格整体最优值或严格整体极小值。定义 对于非线性规划(MP)，若，并且存在的一个领域，使则称是(MP)的局部最优解或局部极小点，称是(MP)的局部最优值或局部极小点。如果有则称是(MP)的严格局部最优解或严格局部极小点，称是(MP)的严格局部最优值或严格局部极小点。定义 设，若存在，使则称向量p是函数f(x)在点处的下降方向。定义 设，若存在，使则称向量p是函数f(x)在点处关于X的可行方向。一般解非线性规划问题的迭代方法的步骤：第一步：选取初始点；第二步：构造搜索方向；第三步：根据，确定步长；第四步：令若已满足某种终止条件，停止迭代，输出近似最优解，否则令，转回第二步。常用规则：1、相邻两次迭代点的绝对差小于给定误差，即；2、相邻两次迭代点的相对差小于给定误差，即；3、；4、第二节 凸函数和凸规划教学重点：凸函数的概念及性质，凸规划的概念、性质及判定。教学难点：凸规划的概念及性质。教学课时：4学时主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划的性质。凸函数的定义及性质：定义 设是非空凸集，如果对任意的有则称f是S上的凸函数，或f在S上是凸的。如果对于任意的有则称f是S上的严格凸函数，或f在S上是严格凸的。若-f是S上的（严格）凸函数，则称f是S上的（严格）凹函数，或f在S上是（严格）凹的。(a) 凸函数 (b)凹函数凸函数的性质：定理 设是非空凸集。（1）若是S上的凸函数，则 是S上的凸函数；（2）若都是S上的凸函数，则是S上的凸函数。定理 设是非空凸集，是凸函数，则集合是凸集。注：一般来说上述定理的逆是不成立的。定理 设是非空开凸集，可微，则（1） f是S上的凸函数的充要条件是其中是函数f在点处的一阶导数或梯度。（2） f是S上的严格凸函数的充要条件是证明 （1）. 必要性.设是上的凸函数，对有：故由多元函数Taylor展开式可知：将其带入（）并令便便可得到充分性.设对取，由凸知，对分别有：和将（）乘以，两式相加得到（2）. 证明和（1）类似.定理 设是非空开凸集，二阶连续可导，则f是S上的凸函数的充要条件是f的Hesse矩阵在S上是半正定的。当在S上是正定矩阵时，f是S上的严格凸函数。（注意：该逆命题不成立。）凸规划及其性质 约束集如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。凸规划的性质定理 对于非线性规划(MP)，若皆为上的凸函数，皆为线性函数，并且f是X上的凸函数，则(MP)是凸规划。定理 凸规划的任一局部最优解都是它的整体最优解。证明：设是凸规划（MP）的一个局部解，存在则的临域使得若不是（MP）的整数最优解，则存在，使又因为是凸函数，有显然，当充分小时，有出现矛盾。例 验证下列（MP）是凸规划解答：将二次目标函数改写为：由例知的 Hesse矩阵为：的一、二、三阶顺序主子式分别为：正定，为凸函数。而半正定，是凸函数。其他约束条件均为线性。故改（MP）为凸规划。第三节 一维搜索教学重点：0.618法，牛顿法，非精确一维搜索方法。教学难点：0.618法和牛顿法。教学课时：4学时主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划的性质。目标函数为单变量的非线性规划问题称为一维搜索问题(或线性搜索问题)，其数学模型为其中。1、0.618法函数称为在a,b上是单谷的，如果存在一个，使得在上严格递减，且在上严格递增。区间a,b称为的单谷区间。第一步： 插入等长度，令第二步： 使区间缩小同样的比例，不妨设新区间为 设插入，则 若令，则有；若令，则有以后类似迭代算法的具体步骤：第1步 确定单谷区间a,b，给定最后区间精度;第2步 计算最初两个探索点并计算，；第3步 若，转第4步。否则转第5步；第4步 若，停止迭代，输出。否则令，计算，转第3步；第5步 若，停止迭代，输出。否则令，计算，转第3步。 例 用0.618法求解的单谷区间为0,3，迭代步骤可以由下表给出： 01234 0000.4380.708 31.8541.1461.1461.146 1.1460.7080.4380.708  1.8541.1460.7080.876 0.2131 3.6648-0.0611 0.21310.2082 -0.0611-0.0611 -0.0798  换 换üüüü 在0.618法中每次迭代搜索区间按常比例缩小，所以要使给定的单谷区间减少到所要求的区间精度，需要的迭代次数是可以预估的。另外若每次每次迭代按不同比例缩小搜索区间，但仍要求每次迭代只计算一个函数值，且希望在搜索点个数相同的情况下使最终的搜索区间的长度最小，按此要求设计的方法是Fibonacci法2、牛顿法考虑一维搜索问题，其中是二次可微的，且。Newton法的基本思想是：用在探索点处的二阶泰勒展开式来替代，然后用的最小点作为新的探索点.据此，可得：开始时给定一个初始点，然后按照上式进行迭代计算，当时，终止迭代，为的最小点的近似。Newton法步骤第1步 给定初始点，；第2步 如果，停止迭代，输出.否则，当时，停止，解题失败；当时，转下一步；第3步 计算，如果，停止迭代，输出，否则，转至第2步；例 用牛顿法求下题。解：首先求出取，计算结果列于下表110.785422-0.5708-0.51781.325830.11690.11631.01374-0.001061用数学分析方法知，的精确最优解是，用Newton法迭代三此后就已经十分接近该最优解。但是取，则有：121.107152-3.5357-1.295213.50313.95点列不收敛于从任意初始点开始的Newton法产生的点列，一般来说不一定收敛，即使收敛，其极限点也不一定是 的极小点，只能保证它是 的驻点。但当初始点充分接近 时，可以证明Newton法是收敛的。非精确一维搜索：3、Goldstein法思想预先指定两个数满足，用一下两个式子限定（）式所限定的是使位于直线之下的点，用以控制不太大；（）用于限定使位于直线之上的点，用以控制不太小.第1步 给定满足的正数，增大探索点系数；初始探索点（或）。令（或），第2步 计算若，进行第3步；否则，令转第4步；第3步 若，停止迭代，输出。否则，令若，进行第4步；否则，令，转第2步；第4步 取，令，转第2步。例 用 法 求解下题 解答：取并且因为，令由于，选取新探索点并计算，因为有和停止迭代，得到非精确解4.Armijo法取定，用以下两个式子限定不太大也不太小：(0.0.1)(0.0.2)第四节 无约束最优化问题教学重点：无约束最优化问题的最优性条件，最速下降法。教学难点：最速下降法。教学课时：6学时主要教学环节的组织：首先给出无约束最优化条件，然后介绍无约束最优化问题的两种算法，最速下降法、共轭方向法。1 无约束问题的最优性条件定理 设在点处可微。若存在，使则向量p是f在点处的下降方向。证：因为在点处可微，有泰勒展开，由于，因而，则存在，对有由（）由定义知是在点的处下降方向定理 设在点处可微。若是(UMP)的局部最优解，则定理 设在点处的Hesse矩阵存在。若，并且正定则是(UMP)的局部最优解。 定理 设，f是上得可微凸函数。若有则是(UMP)的整体最优解。证：因为是上的可微凸函数，由定理知由于，因而推知由此是（UMP）问题的整数最优解2 最速下降法设（NMP）问题中的目标函数一阶连续可微最速下降法基本思想：从当前点出发，取函数在点处下降最快的方向作为我们的搜索方向，由的Taylor展开式知忽略的高阶无穷小项，可见取时，函数值下降的最多。最速下降法的计算步骤：第1步 选取初始点，给定终止误差，令；第2步 计算，若，停止迭代，输出。否则进行第3步；第3步 取第4步 进行一维搜索，求，使得令，转第2步。例 用最速下降法求解如下（UMP）问题 取初始点终止误差显然，该问题的整体最优解为下面用最速下降法求解.由构造负梯度方向则令，解得：，所以重复上述过程，经十轮迭代可得满足误差要求的解。最速下降法算法分析：1）随着迭代次数的增加，收敛速度越来越慢；2）最速下降法的相邻两个搜索方向是彼此正交的；3）具有全局收敛性。3 共轭方向法定义 设A为n阶实对称，对于非零向量，若有则称p和q是相互A共轭的。对于非零向量组，若有则称是A共轭方向组，也称它们为一组A共轭方向。定理 设A是n阶实对称正定矩阵，是非零向量。若是一组A共轭方向，则它们一定是线性无关的。考虑二次严格凸函数的无约束最优化问题： （AP）其中A是n阶实对称正定矩阵，定理 对于问题(AP)，若为任意一组A共轭方向，则由任意初始点出发，依次沿进行精确一维搜索，则最多经n次迭代可达(AP)的整体最优解。共轭方向法-步骤第1步 选取初始点，给定终止误差；第2步 计算，若，停止迭代，输出；否则，进行第3步；第3步 取，令；第4步 进行一维搜索求使得，令；第5步 计算，若，停止迭代，输出；否则，进行第6步；第6步 若k+1=n，令，转第3步；否则进行第7步；第7步 用F-R公式取，其中。令k:=k+1，转第4步。例 用F-R法求解如下（UMP）问题 取初始点终止误差解： F-R方法的第一轮迭代与最速下降法相同，由例知下面利用F-R公式（）构造新的共轭方向，其中：所以令，有，因而得到下一个迭代点,由于，停止迭代，输出整体最优解共轭方向法-算法分析：1）F-R法具有二次终止性。对一般可微函数的无约束优化问题，当函数满足一定的条件时，可以证明F-R方法具有全局收敛性其收敛速度比最速下降法快；2）F-R法强烈依赖于一位搜索的精确性。第五节 约束最优化方法教学重点：约束最优化问题的最优性条件，简约梯度法和惩罚函数法。教学难点：约束最优化问题的最优性条件。教学课时：8学时主要教学环节的组织：首先给出约束最优化问题的最优性条件即K_T条件，然后介绍两种约束最优化方法：简约梯度法和惩罚函数法。1、约束最优化问题的最优性条件给定约束最优化问题： 其中 积极约束：称使的约束为点的一个积极约束。我们记积极约束的下标集为：K-T条件：定理 设和在点处可微，在点处连续，在点处连续可微，并且各线性无关。若是(MP)的局部最优解，则存在两组实数和，使得：“向量组线性无关”这个条件称为约束规范条件其几何意义可以用下图来说明。图4.5.1若定理中进一步要求在点处均可微，则K-T条件可简便写为其中为互补松紧条件例用K-T条件求解下列问题解：问题（）的Lagrange函数为：得到K-T条件如下作为K-T点，还应满足可行性条件：从互补松紧条件入手进行讨论（1） 设此时可求解出，不满足可行性条件中的不等式约束。舍弃。（2） 设解出为K-T点由定理知为整体最优解定理 对于(MP)问题，若，在点处连续可微，可行点满足(MP)的K-T条件，且是凸函数，是线性函数，则是(MP)的整体最优解。2. 简约梯度法其中，简约梯度法-基本思想首先，分析等式约束得，带入目标函数令，即为在处对应的简约梯度.其次，再由构造定理 ，并且有分解，。若由下式确定，则：（1） 当时，是f在点处关于的可行下降方向；（2） 的充要条件是是问题()的K-T点。简约梯度法-Wolfe法步骤第1步 选取初始可行点，给定终止误差，令k:=0;第2步 设是的m个最大分量的下标集，对矩阵A进行相应分解第3步 计算，然后，计算简约梯度记的第个分量为；第4步 按(*)式构造可行下降方向。若，停止迭代，输出；否则进行第5步；第5步 进行有效一维搜索，求解，得到最优解，其中令，k:=k+1，转第2步例 用Wolfe法求解约束极小化问题解：首先将问题化为：第一轮迭代： ，相应分解为由公式（）有，由此可得可行下降方向为根据（）式有，求解可得最优解，于是得到下一个迭代点然后依次进行第二轮第三轮迭代，最后得到整体最优解3. 惩罚函数法思想：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数，把(MP)问题的求解转换为求解一系列无约束非线性规划问题。设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束极小化问题的最优解。可取罚函数：相应的构造增广目标函数：当充分大时，总可使（MP）问题转换为无约束的极小化问题实际应用中，选取一个递增且趋于无穷的正罚函数参数列：其中， 罚函数法计算步骤第1步 选取初始点，罚参数列，给出检验终止条件的误差，令k:=1；第2步 按(*)构造函数，再按(*)构造(MP)的增广目标函数，即第3步 选用某种无约束最优化方法，以为初始点，求解，设得到最优解。若已满足某种终止条件，停止迭代，输出。否则令k:=k+1，转第2步；例 用罚函数法求解解：罚函数为相应的增广目标函数为：原问题转换为求解一系列无约束最优化问题用解析方法求解：令，求得可以看到，当无限增大时是从问题（）可行域外部趋于它的最优解的。图见障碍函数法在可行区域的边界上筑起一道“墙”，当迭代点靠近边界时，所构造的增广目标函数值陡然增大，于是最优点就被“挡”在可行区域内部了。令，可行域X的内部记为构造障碍函数当时，或其中，为罚参数或罚因子障碍函数法步骤第1步 选取初始点，罚参数列，给出检验终止条件，令k:=1；第2步 做障碍函数，构造增广目标函数第3步 选用某种无约束最优化方法，以为初始点求解得到最优解。若已满足某种终止条件，停止迭代，输出。否则，令k:=k+1，转第2步。例 采用对数形式的障碍函数解: 取相应的增广目标函数为：用解析方法求得的最优解为由上式可见，当无限增大，即无限减小时，从问题（）的可行域内部趋于最优解两类方法的优缺点比较：优点：罚函数法：结构简单初始点选取比较自由障碍函数法：结构简单但初始点必须是可行内点，由此产生的迭代点均为可行内点缺点：1、收敛速度慢2、工作量大，每次迭代都要求解一个无约束优化问题3、方法本身造成数值困难性