运筹学ch非线性规划.pptx

1第七章 非线性规划第七章 非线性规划第一节 引言 定义：具有以下特征的问题称为非线性规划问题：难点：第1页/共78页2第一节 引言第七章 非线性规划第一节 引言例7-2 一、引例 第2页/共78页3第七章 非线性规划第一节 引言二、非线性规划的数学模型 第3页/共78页4第七章 非线性规划第一节 引言二、非线性规划的图示二、非线性规划的数学模型 第4页/共78页5第七章 非线性规划第一节 引言立体图解 二、非线性规划的图示 分析:(1)立体图解（图7-1）第5页/共78页6第七章 非线性规划第一节 引言平面投影图解 BAO3x23x1x23D椭圆抛物面最优点图7-1 例7-3立体图解第6页/共78页7第七章 非线性规划第一节 引言讨论(2)平面投影图解（图7-2）O33x1x2BAD图7-2 例7-3平面投影图解C22（1）求可行域：（2）求目标函数等值线：（3）利用目标函数等值线求最优点 该问题可行域的平面投影为第一象限内满足约束条件的一段直线。（注意：直线，而不是封闭区域）该问题目标函数等值线平面投影为圆（4）最优点、最优解、最优值第7页/共78页8第七章 非线性规划第一节 引言第二节 基本概念讨论：O33x1x2BAD图7-2 例7-3平面投影图解C22考虑约束条件改为：最优点可位于可行域内部，即非线性规划的可能在可行域的任意一点得到，这与线性规划不同。非线性规划最优点的特点：最优解有何变化?第8页/共78页9第七章 非线性规划第二节 基本概念 一局部极值与全局极值 第二节 基本概念 极值问题（回顾）极值存在的条件凸函数凸函数性质及定理主要内容：第9页/共78页10第七章 非线性规划第二节 基本概念 1.局部极小点及局部极小值，严格局部极小点及严格局部极小值 一局部极值与全局极值 线性规划的最优解是整个可行域的全局最优解，这是由于：线性规划的目标函数为线性函数，且可行域为凸集。线性规划的最优解与全局最优解的关系：非线性规划的极值点与全局最优点的关系：非线性规划的极值点（局部极值点）：不一定是 整个可行域的最优极值点（图7-3）。图7-3 局部极小点与全局极小点Obxax*x1全局极小点局部极小点第10页/共78页11第七章 非线性规划第二节 基本概念（图7-4）1.局部极小点及局部极小值，严格局部极小点及严格局部极小值 定义:解释:第11页/共78页12第七章 非线性规划第二节 基本概念 2.全局极小点及全局全局极小值，严格全局极小点及严格全局全局极小值 图7-4 局部极小点与严格局部极小点Oxx*局部极小点Oxx*严格局部极小点第12页/共78页13第七章 非线性规划第二节 基本概念 二极值存在的条件 2.全局极小点及全局极小值，严格全局极小点及严格全局极小值 定义:第13页/共78页14第七章 非线性规划第二节 基本概念 极值存在的条件第二节 基本概念 极值问题（回顾）极值存在的条件凸函数凸函数性质及定理主要内容：第14页/共78页15第七章 非线性规划第二节 基本概念 2.驻点 二极值存在的条件 1.极值存在的必要条件 定理1:第15页/共78页16第七章 非线性规划第二节 基本概念 3.极值存在的充分条件 2.驻点 满足式（7-1）的点称为驻点，极值点必为驻点，但驻点不一定是极值点。第16页/共78页17第七章 非线性规划第二节 基本概念 注：充分条件非必要条件 3.极值存在的充分条件 定理2:第17页/共78页18第七章 非线性规划第二节 基本概念 补充知识：二次型及正定二次型 注1:注2:第18页/共78页19第七章 非线性规划第二节 基本概念（2）二次型展开式及其矩阵表示 补充知识：二次型及正定二次型（1）二次型的定义：第19页/共78页20第七章 非线性规划第二节 基本概念（3）正定二次型及正定矩阵（2）二次型展开式及其矩阵表示 第20页/共78页21第七章 非线性规划第二节 基本概念（5）负定二次型及负定矩阵（3）正定二次型及正定矩阵（4）半正定二次型及半正定矩阵 第21页/共78页22第七章 非线性规划第二节 基本概念（7）不定二次型及不定矩阵（5）负定二次型及负定矩阵（6）半负定二次型及半负定矩阵 第22页/共78页23第七章 非线性规划第二节 基本概念（8）二次型为正定的充要条件（或正定矩阵的充要条件）（7）不定二次型及不定矩阵 第23页/共78页24第七章 非线性规划第二节 基本概念（11）矩阵的阶顺序主子式（8）二次型为正定的充要条件（或正定矩阵的充要条件）（9）二次型为负定的充要条件（或负定矩阵的充要条件）（10）矩阵的k阶主子式第24页/共78页25第七章 非线性规划第二节 基本概念 例7-3（必要条件非充分条件举例）（11）矩阵的k阶顺序主子式 第25页/共78页26第七章 非线性规划第二节 基本概念 鞍点（图7-5）第26页/共78页27第七章 非线性规划第二节 基本概念 例7-4求极小点及极小值 鞍点：图7-5 驻点、极值点、鞍点第27页/共78页28第七章 非线性规划第二节 基本概念 三凸函数 1阶顺序主子式：2阶顺序主子式：因此，为正定矩阵 根据定理2（极值存在的充分条件），所给函数的极小点为 极小值为 第28页/共78页29第七章 非线性规划第二节 基本概念 凸函数第二节 基本概念 极值问题（回顾）极值存在的条件凸函数凸函数性质及定理主要内容：第29页/共78页30第七章 非线性规划第二节 基本概念 三、凸函数1.凸函数的定义 三凸函数 主要内容：凸集（见线性规划）凸函数凸函数的性质函数凸性的判定凸函数的极值上述内容为研究非线性规划不可缺少的内容。第30页/共78页31第七章 非线性规划第二节 基本概念 三、凸函数 推导g(x3)1.凸函数的定义（1）一元凸函数（i）一元凸函数的几何特性（参考图7-6）图7-6 一元凸函数Oxx3x1x2第31页/共78页32第七章 非线性规划第二节 基本概念 三、凸函数 凸函数定义 图7-6 一元凸函数Oxx3x1x2第32页/共78页33第七章 非线性规划第二节 基本概念 三、凸函数（ii）一元凸函数的定义 图7-6 一元凸函数Oxx3x1x2因此，对于凸函数，应有：而：因此，凸函数应满足的条件为：如果则函数f(x)称为凹函数。第33页/共78页34第七章 非线性规划第二节 基本概念 三、凸函数（2）多元凸函数（ii）一元凸函数的定义 第34页/共78页35第七章 非线性规划第二节 基本概念 三、凸函数 2.凸函数的性质（2）多元凸函数第35页/共78页36第七章 非线性规划第二节 基本概念 三、凸函数2.凸函数的性质三凸函数 主要内容：凸集（见线性规划）凸函数凸函数的性质函数凸性的判定凸函数的极值上述内容为研究非线性规划不可缺少的内容。第36页/共78页37第七章 非线性规划第二节 基本概念 三、凸函数 3.函数凸性的判断2.凸函数的性质性质1:性质2:第37页/共78页38第七章 非线性规划第二节 基本概念 三、凸函数3.函数凸性的判断三凸函数 主要内容：凸集（见线性规划）凸函数凸函数的性质函数凸性的判定凸函数的极值上述内容为研究非线性规划不可缺少的内容。第38页/共78页39第七章 非线性规划第二节 基本概念 三、凸函数 定理43.函数凸性的判断直接方法:定理3:利用凸函数定义判断，难度较大。第39页/共78页40第七章 非线性规划第二节 基本概念 三、凸函数 例7-5 函数凸性的判断定理4:证略。第40页/共78页41第七章 非线性规划第二节 基本概念 三、凸函数 例7-5 函数凸性的判断第41页/共78页42第七章 非线性规划第二节 基本概念 三、凸函数4.凸函数的极值三凸函数 主要内容：凸集（见线性规划）凸函数凸函数的性质函数凸性的判定凸函数的极值上述内容为研究非线性规划不可缺少的内容。第42页/共78页43第七章 非线性规划第二节 基本概念 三、凸函数 定理44.凸函数的极值局部极小点虽然易于求得但函数的局部极小点不一定等于其全局极小点（最小点）实际优化问题的目标为求函数的全局极小点（或全局极大点）常用方法为将全部极小值进行比较（有时需考虑边界值）但对于凸函数，局部极小点就是全局极小点。第43页/共78页44第七章 非线性规划第二节 基本概念 三、凸函数 第三节 凸规划定理5:证略。定理6:第44页/共78页45目录第三节 凸规划第七章 非线性规划第一节 引言 第二节 基本概念第三节 凸规划 第四节 一维搜索 第45页/共78页46第七章 非线性规划第三节 凸规划二凸规划的解一凸规划的定义第三节 凸规划定义:第46页/共78页47第七章 非线性规划第三节 凸规划例7-6 讨论凸规划问题二凸规划的解凸规划的局部最优解为全局最优解。当凸规划的目标函数为严格凸函数时，最优解唯一（如最优解存在）。线性规划与凸规划：由于线性函数既为凸函数，又为凹函数，所以线性规划也属于凸规划。凸规划是非线性规划中既简单又具有重要理论意义的一类规划。但是，用解析方法求解依然不实际。第47页/共78页48第七章 非线性规划第三节 凸规划约束函数凸性判断1阶顺序主子式:2阶顺序主子式:第48页/共78页49第七章 非线性规划第三节 凸规划图7-71阶顺序主子式:2阶顺序主子式:综上，该规划为凸规划，其目标函数等值线投影及可行域如图7-7所示。第49页/共78页50第七章 非线性规划第三节 凸规划第四节 一维搜索方法 图7-7 例7-6图示Ox1x2目标函数等值线可行域最优点C第50页/共78页51目录第四节 一维搜索方法第七章 非线性规划第一节 引言 第二节 基本概念第三节 凸规划 第四节 一维搜索方法 第51页/共78页52第七章 非线性规划第四节 一维搜索方法一维搜索概要一、概述第四节 一维搜索方法 1.非线性规划解析方法的局限性 第52页/共78页53第七章 非线性规划第四节 一维搜索方法多维搜索与一维搜索的关系2.求解无约束非线性规划的一维搜索方法概要第53页/共78页54第七章 非线性规划第四节 一维搜索方法多维搜索与一维搜索的关系（续）3.多维搜索与一维搜索之间的关系图7-8 一维搜索第54页/共78页55第七章 非线性规划第四节 一维搜索方法3.一维搜索的两大步骤3.多维搜索与一维搜索之间的关系图7-8 一维搜索第55页/共78页56第七章 非线性规划第四节 一维搜索方法二、斐波那契（Fionacci）法3.一维搜索的两大步骤（1）确定初始搜索区间，该区间必须为单峰区间。（2）确定最优步长。单峰区间:下单峰函数:4.搜索方法优劣的衡量标准 第56页/共78页57第七章 非线性规划第四节 一维搜索方法斐波那契法概述（续）二、斐波那契（Fionacci）法1.斐波那契法概述Oxx*图7-9 下单峰函数极小点所在区间第57页/共78页58第七章 非线性规划第四节 一维搜索方法斐波那契法须解决的问题图7-9 下单峰函数极小点所在区间Oxx*启发:第58页/共78页59第七章 非线性规划第四节 一维搜索方法f2=?斐波那契法须解决的问题:问题:现考虑计算两次函数值的情形。即：今后将需计算函数值的点成为试算点或试点。计算两次函数值，能将多大的区间缩短为单位区间，即f2=?第59页/共78页60第七章 非线性规划第四节 一维搜索方法如果区间长度等于2？图7-10 搜索区间的缩短baa1b1baa1b1201第60页/共78页61第七章 非线性规划第四节 一维搜索方法递推公式图7-10 搜索区间的缩短baa1b1baa1b1201第61页/共78页62第七章 非线性规划第四节 一维搜索方法给定区间长度及缩短精度，函数值计算次数？(7-2)斐波那契数:表7-1 斐波那契数表第62页/共78页63第七章 非线性规划第四节 一维搜索方法斐波那契法的步骤2.给定区间长度及缩短精度，函数值计算次数？或 计算函数值多少次，才能将给定长度的区间缩短为满足精度的区间？第63页/共78页64第七章 非线性规划第四节 一维搜索方法确定试算点个数3.斐波那契法的步骤（1）确定试算点个数（4）重复步骤（3）第64页/共78页65第七章 非线性规划第四节 一维搜索方法（1）确定试算点个数 图7-11 试算点互为对称点L0 x1将区间缩短至那个区间？或保留那个试算点更好？最好的方案是使两种可能性相等。如何实现？据此选择试算点确定试算点第65页/共78页66第七章 非线性规划第四节 一维搜索方法计算另一试算点(i)考虑原区间长度为fn的情况（图7-12）：图7-12 确定试算点1x1x第1次缩短：(ii)考虑原区间长度为b0-a0的情况，显然：第66页/共78页67第七章 非线性规划第四节 一维搜索方法（3）计算并比较函数值，确定保留区间及保留区间内新的试算点图7-12 确定试算点1x1x由于两个试算点互为对称，因此：第2次缩短时，只要将新区间端点的下标改为1，即可直接利用以上公式。第3次缩短时，只要将新区间端点的下标改为2。类似地：第4次缩短时，只要将新区间端点的下标改为3。第(n-1)次缩短时，只要将新区间端点的下标改为(n-2)。第67页/共78页68第七章 非线性规划第四节 一维搜索方法（3）计算并比较函数值，确定保留区间3.斐波那契法的步骤（1）确定试算点个数（4）重复步骤（3）第68页/共78页69第七章 非线性规划第四节 一维搜索方法重复步骤（3）1x1x1x保留点作为一个试算点 第69页/共78页70第七章 非线性规划第四节 一维搜索方法重复步骤（3）3.斐波那契法的步骤（1）确定试算点个数（4）重复步骤（3）第70页/共78页71第七章 非线性规划第四节 一维搜索方法特殊情况：k=n-11x1x1x保留点作为一个试算点 第71页/共78页72第七章 非线性规划第四节 一维搜索方法0.618法（黄金分割法）根据试算点一般公式：k=n-1时：即：两个试算点位置相同，因此无法通过比较函数值确定最终区间。为此，xn-1取计算值，而 人为取值为：斐波那契法采用对称搜索的方法，逐步缩短搜索区间，该方法能以尽量少的函数值计算次数，达到预定的某一缩短率。第72页/共78页73第七章 非线性规划第四节 一维搜索方法黄金分割法的缩短率三、黄金分割法（0.618法）：所谓黄金分割，指的是把长为L的线段分为两部分，使其中一部分对于全部之比，等于另一部分对于该部分之比。其比值为一无理数，取其前三位数字的近似值是0.618，所以也称为0.618法。黄金分割法与斐波那契法的相同点：1.搜索原理相同。2.比较函数值，确定保留区间的方法相同。黄金分割法每次缩短区间的缩短率相同。黄金分割法与斐波那契法的区别：第73页/共78页74第七章 非线性规划第四节 一维搜索方法1.0.618法的缩短率(续)1.黄金分割法的缩短率（参考图7-13）图7-13 0.618法的试算点L0 x1第74页/共78页75第七章 非线性规划第四节 一维搜索方法总缩短率图7-13 0.618法的试算点L0 x1第75页/共78页76第七章 非线性规划第四节 一维搜索方法（3）判断区间总缩短率是否满足预定精度 总缩短率：2.黄金分割法的计算步骤 第76页/共78页77第七章 非线性规划第四节 一维搜索方法本章结束（3）判断区间总缩短率是否满足预定精度 如满足，则迭代结束，比较函数值，得近似极小点及近似极小值。否则重复第（2）步（在保留区间内确定新的试算点，比较函数值，确定新的保留区间，判断区间总缩短率是否满足预定精度）。无约束非线性规划的其他求解方法：最速下降法、DFP法等。有约束非线性规划求解方法：（1）直接处理约束法（在可行域内迭代，直到获得最优解）：约束坐标轮换法、约束随机法、复合形法、正多面体法等；（2）间接处理约束法（转换为无约束问题，然后利用无约束方法求解）：拉格朗日乘子法、罚函数法等。第77页/共78页78感谢您的观看！第78页/共78页