《第四章非线性规划山大刁在筠运筹学讲义参考word》由会员分享，可在线阅读，更多相关《第四章非线性规划山大刁在筠运筹学讲义参考word（28页珍藏版）》请在金锄头文库上搜索。
1、第四章 非线性规划教学重点：凸规划及其性质，无约束最优化问题的最优性条件及最速下降法，约束最优化问题的最优性条件及简约梯度法。教学难点：约束最优化问题的最优性条件。教学课时：24学时主要教学环节的组织：在详细讲解各种算法的基础上，结合例题，给学生以具体的认识，再通过大量习题加以巩固，也可以应用软件包解决一些问题。第一节 基本概念教学重点：非线性规划问题的引入，非线性方法概述。教学难点：无。教学课时：2学时主要教学环节的组织：通过具体问题引入非线性规划模型，在具体讲述非线性规划方法的求解难题。1、非线性规划问题举例例1 曲线最优拟合问题已知某物体的温度与时间t之间有如下形式的经验函数关系： （*
2、）其中，是待定参数。现通过测试获得n组与t之间的实验数据，i=1，2，,n。试确定参数，使理论曲线(*)尽可能地与n个测试点拟合。推荐精选例 2 构件容积问题通过分析我们可以得到如下的规划模型：基本概念设，,如下的数学模型称为数学规划(Mathematical Programming, MP)：约束集或可行域 MP的可行解或可行点MP中目标函数和约束函数中至少有一个不是x的线性函数，称(MP)为非线性规划令 ，其中，那么(MP)可简记为 或者 当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。否则，称为约束非线性规划或者约束最优化问题。定义4.1.1 对于非线性规划(MP)，若，并
3、且有推荐精选则称是(MP)的整体最优解或整体极小点，称是(MP)的整体最优值或整体极小值。如果有则称是(MP)的严格整体最优解或严格整体极小点，称是(MP)的严格整体最优值或严格整体极小值。定义 4.1.2 对于非线性规划(MP)，若，并且存在的一个领域，使，则称是(MP)的局部最优解或局部极小点，称是(MP)的局部最优值或局部极小点。如果有，则称是(MP)的严格局部最优解或严格局部极小点，称是(MP)的严格局部最优值或严格局部极小点。定义 4.1.3 设，若存在，使则称向量p是函数f(x)在点处的下降方向。定义 4.1.4 设，若存在，使则称向量p是函数f(x)在点处关于X的可行方向。一般解
4、非线性规划问题的迭代方法的步骤：第一步：选取初始点；第二步：构造搜索方向；第三步：根据，确定步长；第四步：令若已满足某种终止条件，停止迭代，输出近似最优解，否则令，转回第二步。推荐精选常用规则：1、相邻两次迭代点的绝对差小于给定误差，即；2、相邻两次迭代点的相对差小于给定误差，即；3、；4、推荐精选第二节 凸函数和凸规划教学重点：凸函数的概念及性质，凸规划的概念、性质及判定。教学难点：凸规划的概念及性质。教学课时：4学时主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划的性质。凸函数的定义及性质：定义 4.2.1 设是非空凸集，如果对任意的有，则称f是S上的凸函数，或f在S上是凸
5、的。如果对于任意的有，则称f是S上的严格凸函数，或f在S上是严格凸的。若-f是S上的（严格）凸函数，则称f是S上的（严格）凹函数，或f在S上是（严格）凹的。(a) 凸函数 (b)凹函数凸函数的性质：定理 4.2.1 设是非空凸集。（1）若是S上的凸函数，则 是S上的凸函数；（2）若都是S上的凸函数，则是S上的凸函数。定理 4.2.2 设是非空凸集，是凸函数，则集合是凸集。注：一般来说上述定理的逆是不成立的。推荐精选定理 4.2.3 设是非空开凸集，可微，则（1） f是S上的凸函数的充要条件是， 其中是函数f在点处的一阶导数或梯度。（2） f是S上的严格凸函数的充要条件是， 证明 （1）. 必要
6、性.设是上的凸函数，对有：故（4.2.3）由多元函数Taylor展开式可知：将其带入（4.2.3）并令便便可得到充分性.设对取，由凸知，对分别有：（4.2.4）和（4.2.5）将（4.2.4）乘以，（4.2.5）乘以，两式相加得到推荐精选（2）. 证明和（1）类似.定理 4.2.4 设是非空开凸集，二阶连续可导，则f是S上的凸函数的充要条件是f的Hesse矩阵在S上是半正定的。当在S上是正定矩阵时，f是S上的严格凸函数。（注意：该逆命题不成立。）凸规划及其性质 约束集如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。凸规划的性质定理 4.2.5
7、 对于非线性规划(MP)，若皆为上的凸函数，皆为线性函数，并且f是X上的凸函数，则(MP)是凸规划。定理 4.2.6 凸规划的任一局部最优解都是它的整体最优解。证明：设是凸规划（MP）的一个局部解，存在则的临域使得若不是（MP）的整数最优解，则存在，使又因为是凸函数，有推荐精选显然，当充分小时，有出现矛盾。例 4.2.3 验证下列（MP）是凸规划解答：将二次目标函数改写为：由例4.2.2知的 Hesse矩阵为： 的一、二、三阶顺序主子式分别为：正定，为凸函数。而半正定，是凸函数。其他约束条件均为线性。故改（MP）为凸规划。推荐精选第三节 一维搜索教学重点：0.618法，牛顿法，非精确一维搜索方
8、法。教学难点：0.618法和牛顿法。教学课时：4学时主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划的性质。目标函数为单变量的非线性规划问题称为一维搜索问题(或线性搜索问题)，其数学模型为，其中。1、0.618法函数称为在a,b上是单谷的，如果存在一个，使得在上严格递减，且在上严格递增。区间a,b称为的单谷区间。第一步： 插入等长度，令第二步： 使区间缩小同样的比例，不妨设新区间为 设插入，则 若令，则有；若令，则有以后类似迭代算法的具体步骤：第1步 确定单谷区间a,b，给定最后区间精度;第2步 计算最初两个探索点并计算，；第3步 若，转第4步。否则转第5步；第4步 若，停止迭
9、代，输出。否则令，推荐精选，计算，转第3步；第5步 若，停止迭代，输出。否则令，计算，转第3步。 例4.3.1 用0.618法求解的单谷区间为0,3，迭代步骤可以由下表给出：012340000.4380.70831.8541.1461.1461.1461.1460.7080.4380.7081.8541.1460.7080.8760.2131 3.6648-0.0611 0.21310.2082 -0.0611-0.0611 -0.0798 换 换在0.618法中每次迭代搜索区间按常比例缩小，所以要使给定的单谷区间减少到所要求的区间精度，需要的迭代次数是可以预估的。另外若每次每次迭代按不同比例
10、缩小搜索区间，但仍要求每次迭代只计算一个函数值，且希望在搜索点个数相同的情况下使最终的搜索区间的长度最小，按此要求设计的方法是Fibonacci法2、牛顿法考虑一维搜索问题，其中是二次可微的，且。Newton法的基本思想是：用在探索点处的二阶泰勒展开式来替代，然后用的最小点作为新的探索点.据此，可得：开始时给定一个初始点，然后按照上式进行迭代计算，当时，终止迭代，为的最小点的近似。Newton法步骤第1步 给定初始点，；推荐精选第2步 如果，停止迭代，输出.否则，当时，停止，解题失败；当时，转下一步；第3步 计算，如果，停止迭代，输出，否则，转至第2步；例 用牛顿法求下题。解：首先求出，取，计
11、算结果列于下表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法思想预先指定两个数满足，用一下两个式子限定 （4.3.10） （4
12、.3.11）推荐精选（4.3.10）式所限定的是使位于直线之下的点，用以控制不太大；（4.3.11）用于限定使位于直线之上的点，用以控制不太小.第1步 给定满足的正数，增大探索点系数；初始探索点（或）。令（或），第2步 计算若，进行第3步；否则，令转第4步；第3步 若，停止迭代，输出。否则，令若，进行第4步；否则，令，转第2步；第4步 取，令，转第2步。例 用 法 求解下题 解答：取并且因为，令由于，选取新探索点并计算，因为有和推荐精选停止迭代，得到非精确解4.Armijo法取定，用以下两个式子限定不太大也不太小：(0.0.1)(0.0.2)推荐精选第四节 无约束最优化问题教学重点：无约束最优
13、化问题的最优性条件，最速下降法。教学难点：最速下降法。教学课时：6学时主要教学环节的组织：首先给出无约束最优化条件，然后介绍无约束最优化问题的两种算法，最速下降法、共轭方向法。1 无约束问题的最优性条件定理4.4.1 设在点处可微。若存在，使则向量p是f在点处的下降方向。证：因为在点处可微，有泰勒展开， （4.4.1）由于，因而，则存在，对有 由（4.4.1）由定义知是在点的处下降方向定理 4.4.2 设在点处可微。若是(UMP)的局部最优解，则 定理4.4.3 设在点处的Hesse矩阵存在。若，并且正定则是(UMP)的局部最优解。 定理4.4.4 设，f是上得可微凸函数。若有则是(UMP)的整体最优解。推荐精选证：因为是上的可微凸函数，由定理4.2.3知由于，因而推知由此是（UMP）问题的整数最优解2 最速
