第四章非线性规划

第四章非线性规划第一页，共三十八页，编辑于2023年，星期五第4章非线性规划非线性规划问题一维搜索方法寻求一元函数在某区间上的最优解的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。第二页，共三十八页，编辑于2023年，星期五§4.1非线性规划问题引例——建立整数线性规划模型非线性规划的数学模型第三页，共三十八页，编辑于2023年，星期五1引例——建立非线性规划模型例某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过80米。为使建筑面积最大，应如何选择长宽尺寸？解：第四页，共三十八页，编辑于2023年，星期五1引例——建立非线性规划模型例设某物理过程具有如下规律用试验法求得现要确定参数使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足第五页，共三十八页，编辑于2023年，星期五2非线性规划的数学模型数学规划模型简称：MP问题（Mathematicalprogramming）如果目标函数或约束条件中存在非线性函数，则称为非线性规划。非线性规划问题一般分为约束非线性规划和无约束非线性规划问题。约束集/可行域第六页，共三十八页，编辑于2023年，星期五2非线性规划的数学模型定义1.对于非线性规划问题(MP)，如果并且有：则称x*是(MP)的整体最优解或整体极小点，f(x*)是(MP)的整体最优值或整体极小值。第七页，共三十八页，编辑于2023年，星期五2非线性规划的数学模型定义2.对于非线性规划问题(MP)，如果并且存在x*的一个邻域，使：则称x*是(MP)的局部最优解或局部极小点，f(x*)是(MP)的局部最优值或局部极小值。第八页，共三十八页，编辑于2023年，星期五3非线性规划问题的求解例求解如下非线性规划问题o2266第九页，共三十八页，编辑于2023年，星期五§4.3一维搜索（线搜索）方法0.618方法（近似黄金分割法）Newton法一维最优化方法是优化设计中最简单、最基本的方法，一维问题是多维问题的基础，在数值方法迭代计算过程中，都要进行一维搜索，也可以把多维问题化为一些一维问题来处理。一维问题算法的好坏，直接影响到最优化问题的求解速度。第十页，共三十八页，编辑于2023年，星期五第十一页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）0.618法适用于确定区间上的任何单谷函数求极小值的问题。对函数除要求单谷之外没有任何其它要求。高——低——高第十二页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）定义：函数称为区间[a,b]上的单谷函数，如果存在一个t*∈

[a,b],使得函数在[a,t*]上严格减少，且在[t*,b]上严格递增。区间[a,b]称为的单谷区间。高——低——高第十三页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）算法原理：区间消去原理为简化计算，第三种情况可以合并入前两种情况之一。第十四页，共三十八页，编辑于2023年，星期五区间消去法原理：搜索区间确定之后，采用区间消去法，选取计算点计算函数值并比较它们的大小，消去不可能包含极小点的区间，逐步缩短搜索区间，从而找到极小点的数值近似解。1近似黄金分割法（0.618方法）关键：如何不断消去部分区间而不丢掉极小点？任何保证区间缩小率？第十五页，共三十八页，编辑于2023年，星期五1b要求插入点a1、b1的位置相对于区间[a,b]两端点具有对称性。除对称要求外，黄金分割法还要求在保留下来的区间再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。1近似黄金分割法（0.618方法）第十六页，共三十八页，编辑于2023年，星期五1b1近似黄金分割法（0.618方法）所谓的“黄金分割”是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段的比值，即第十七页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）第十八页，共三十八页，编辑于2023年，星期五迭代a

b

a1

b1

f(a1)f(b1)1近似黄金分割法（0.618方法）例：对函数f(x)=x3-2x+1,当给定搜索区间[0,3]时，试用黄金分割法求极小点。其中精度0031.1461.8540.21313.6648101.8540.7081.146-0.06110.2131201.1460.4380.7080.2082-0.061130.4381.1460.7080.876-0.0611-0.079840.7081.146近似最优解为x=0.792。第十九页，共三十八页，编辑于2023年，星期五迭代a

b

a1

b1

f(a1)f(b1)0031.1461.8540.21313.6648101.8540.7081.146-0.06110.2131201.1460.4380.7080.2082-0.061130.4381.1460.7080.876-0.0611-0.079840.7081.1461近似黄金分割法（0.618方法）第二十页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）关于黄金分割比例的起源大多认为来自毕达哥拉斯，据说在古希腊，有一天毕达哥拉斯走在街上，在经过铁匠铺前他听到铁匠打铁的声音非常好听，于是驻足倾听。他发现铁匠打铁节奏很有规律，这个声音的比例被毕达哥拉斯用数理的方式表达出来，被应用在很多领域。后来很多人专门研究过，开普勒称其为“神圣分割”也有人称其为“金法”。在金字塔建成1000年后才出现毕达哥拉斯定律，可见这很早就存在。只是不知这个谜底。第二十一页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）古希腊帕特农神庙第二十二页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）埃及金字塔第二十三页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）故宫第二十四页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）第二十五页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）第二十六页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）第二十七页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）第二十八页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）第二十九页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）第三十页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）第三十一页，共三十八页，编辑于2023年，星期五1近似黄金分割法（0.618方法）第三十二页，共三十八页，编辑于2023年，星期五2Newton法考虑如下问题：其中二次可微，且牛顿法基本思想：用二阶泰勒展开式对函数作近似；用g(t)的最小点作为新的探索点；当时（满足计算终止误差），计算结束，tk为最小点近似。第三十