最优化方法及控制应用.pptx

《最优化方法及控制应用.pptx》由会员分享，可在线阅读，更多相关《最优化方法及控制应用.pptx（108页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、参考书：参考书：1.实用最优化方法 R.Fleter著，游兆永等译 天津科技翻译出版公司2.非线性规划数值方法 袁亚湘 上海科学技术出版社 19953.非线性最优方法 席少霖 高等教育出版社 4.工程优化的算法分析 张可村 西安交大出版社 19895.最优化方法 解文新，韩立兴等 天津大学出版社 20016.最优化方法 施光燕，董加礼 高等教育出版社 2001第1页/共109页最优化方法及控制应用最优化：在多种（有限种或无限种）决策中挑选 最好决策的问题。最优化方法：（也称做运筹学方法）是近几十年 形成的，主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优方案：是达

2、到最优目标的方案。最优化理论：就是最优化方法的理论。第2页/共109页数学意义为了达到最优化目的所提出的各种求解方法。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。第3页/共109页发展简史公元前 500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618，称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开

3、始研究用数学方法解决最优化问题。最优化方法真正形成为科学方法则在17世纪以后。第4页/共109页工作步骤 提出最优化问题，收集有关数据和资料；建立最优化问题的数学模型,确定变量,列出目标函数和约束条件；分析模型，选择合适的最优化方法；求解，一般通过编制程序，用计算机求最优解；最优解的检验和实施。第5页/共109页模型的基本要素最优化模型包括：变量、约束条件和目标函数变量：指最优化问题中待确定的某些量。变量可用x(x1，x2,xn)T表示。约束条件:指在求最优解时对变量的某些限制,包括技术上的约束、资源上的约束和时间上的约束等。约束条件可用 gi(x)0表示i1,2，m，m 表示约束条件数；目标

4、函数：最优化有一定的评价标准。目标函数就是这种标准的数学描述，一般可用f(x)来表示，即f(x)=f(x1，x2,xn)。第6页/共109页最优化方法最优化问题的求解方法可分成解析法、直接法、数值计算法和其他方法。解析法：只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。第7页/共109页直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验

5、或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。第8页/共109页数值计算法：也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。其他方法：如网络最优化方法等第9页/共109页最优解的概念最优化问题的解一般称为最优解。如果只考察约束集合中某一局部范围内的优劣情况，则解称为局部最优解。如果是考察整个约束集合中的情况，则解称为总体最优解。对于不同优化问题，最优解有不同的含意，因而还有专用的名称。例如，在对策论和数理经济模型中称为平衡解；在控制问题中称为最优控制或极值控制；在多目标决策问题中称为

6、非劣解（又称帕雷托最优解或有效解）。第10页/共109页最优化方法的应用最优化可分为最优设计、最优计划、最优管理和最优控制等四个方面。最优设计：世界各国工程技术界，尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计优化问题得到解决。第11页/共109页最优计划：现代国民经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农业规划、种植计划、能源规划和其他资源、环境和生态规划的制订，都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。第12页/共109页最优管理：一般在日常生产计

7、划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。最优控制：主要用于对各种控制系统的优化。例如，导弹系统的最优控制，能保证用最少燃料完成飞行任务，用最短时间达到目标;；再如飞机、船舶、电力系统等的最优控制，化工、冶金等工厂的最佳工况的控制。第13页/共109页一、组合最优化TSP:（即旅行商问题）假设有n 个城市，一个推销员要在这 n个城市推销产品，要求经过每个城市且仅有一次，如 何选择这条路径，使路径最短？二、动态规划管道铺设：有n个城市铺设管道，要求管道到达每个城市，并且使总的费用最低。第14页/共109页经典极值问题包括：无约

8、束极值问题约束条件下的极值问题第15页/共109页1、无约束极值问题的数学模型 2、约束条件下极值问题的数学模型 其中，极大值问题可以转化为极小值问题来进行求解。如求：可以转化为：第16页/共109页1、无约束极值问题的求解 例1：求函数y=2x3+3x2-12x+14在区间-3,4上的最大值与最小值。解：令f(x)=y=2x3+3x2-12x+14 f(x)=6x2+6x-12=6(x+2)(x-1)解方程f(x)=0，得到x1=-2，x2=1，又由于f(-3)=23，f(-2)=34，f(1)=7，f(4)=142，综上得，函数f(x)在x=4取得在-3,4上得最大值f(4)=142，在x

9、=1处取得在-3,4上取得最小值f(1)=7 第17页/共109页有约束最优化最优化方法分类（一）线性最优化：目标函数和约束条件都是线性的则称为线性最优化。非线性最优化：目标函数和约束条件如果含有非线性的，则称为非线性最优化。（二）静态最优化：如果可能的方案与时间无关，则是静态最优化问题。动态最优化：如果可能的方案与时间有关，则是动态最优化问题第18页/共109页有约束最优化问题的数学建模 有约束最优化模型一般具有以下形式：或 其中f(x)为目标函数，省略号表示约束式子，可以是等式约束，也可以是不等式约束。第19页/共109页 根据目标函数，约束条件的特点将最优化方法包含的主要内容大致如下划分

10、：线性规划 整数规划 非线性规划 动态规划 多目标规划 对策论最优化方法主要内容第20页/共109页两个引例问题一：某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示 12kg40原材料B16kg04原材料A8台时21设备III该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问应如何安排计划使该工厂获利最多？第21页/共109页解：该工厂生产产品I x1件，生产产品II x2件，我们可建立如下数学模型：s.t.第22页/共109页问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验

11、员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解 设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：第23页/共109页故目标函数为：约束条件为：第24页/共109页运用最优化方法解决最优化问题的一般方法步骤如下：前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。针对建立的模型，选择

12、合适的求解方法或数学软件。编写程序，利用计算机求解。对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。第25页/共109页线 性 规 划某豆腐店用黄豆制作两种不同口感的豆腐出售。制作口感较鲜嫩的豆腐每千克需要0.3千克一级黄豆及0.5千克二级黄豆，售价10元；制作口感较厚实的豆腐每千克需要0.4千克一级黄豆及0.2千克二级黄豆，售价5元。现小店购入9千克一级黄豆和8千克二级黄豆。问：应如何安排制作计划才能获得最大收益。第26页/共109页一、问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制作计划，使得售出各种豆腐能

13、获得最大收益。二、模型假设1假设制作的豆腐能全部售出。2假设豆腐售价无波动。第27页/共109页变量假设：设计划制作口感鲜嫩和厚实的豆腐各x1千克和 x2千克，可获得收益R元。目标函数：获得的总收益最大。总收益可表示为：受一级黄豆数量限制：受二级黄豆数量限制：第28页/共109页综上分析，得到该问题的线性规划模型 s.t.第29页/共109页用Matlab编程求解程序如下：X,FVAL,EXITFLAG,OUTPUT=LINPROG(f,A,b)f=-10 5;A=0.3 0.4;0.5 0.2;B=9;8;X,FVAL,EXITFLAG,OUTPUT=LINPROG(f,A,b)X=10.0

14、000 15.0000FVAL=-175.0000第30页/共109页用YALMIP编程求解程序如下：x=sdpvar(1,2);C=10 5;a=0.3 0.4;0.5 0.2;b=9 8;f=C*x;F=set(0=x=inf);F=F+set(a*x=b);solvesdp(F,-f)double(f)double(x)ans=175ans=10 15第31页/共109页线 性 规 划 设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品。根据机床性能和以前的生产情况，得知每单位产品所需车间的工作小时数、每个车间在一个季度工作小时的上限以及单位产品的利润，如下表所示(例如

15、，生产一个单位的A产品，需要甲、乙、丙三个车间分别工作1小时、2小时和4小时)问：每种产品各应该每季度生产多少，才能使这个工厂每季度生产利润达到最大。第32页/共109页生产单位生产单位产品所需产品所需车间的工车间的工作小时数作小时数 ABCDEF每个车间每个车间一个季度一个季度工作小时工作小时的上限的上限甲甲111323500乙乙255500丙丙425500丁丁138500利润利润(百元百元)4.02.45.55.04.58.5第33页/共109页这是一个典型的最优化问题，属线性规划。假设：产品合格且能及时销售出去；工作无等待情况等 变量说明：xj：第j种产品的生产量（j=1,2,6）aij

16、：第i车间生产单位第j种产品所需工作小时数 （i=1,2,3,4;j=1,2,6）bi：第i车间的最大工作上限 cj：第j种产品的单位利润 则：cjxj为第j种产品的利润总额；aijxj表示第i车间生产第j种产品所花时间总数；第34页/共109页于是，我们可建立如下数学模型：s.t.计算结果：Z(百元百元)x1x2x3x4x5x6132000604010040第35页/共109页运 输 问 题 要从甲城调出蔬菜2000吨，从乙城调出蔬菜2500吨，从丙地调出3000吨，分别供应A地2000吨，B地2300吨、C地1800吨、D地1400吨，已知每吨运费如下表：供应单位供应单位调出单位调出单位A

17、BCD甲甲21271340乙乙45513720丙丙32352030问：如何调拨才能使运费最省？第36页/共109页可以建立如下模型：s.t.第37页/共109页整 数 规 划 最优化问题中的所有变量均为整数时，这类问题称为整数规划问题。如果线性规划中的所有变量均为整数时，称这类问题为线性整数规划问题。整数规划可分为线性整数规划和非线性整数规划，以及混合整数规划等。如果决策变量的取值要么为0，要么为1，则这样的规划问题称为01规划。第38页/共109页例1 某钢厂两个炼钢炉同时各用一种方法炼钢。第一种炼法每炉用a小时，第二种用b小时（包括清炉时间）。假定这两种炼法，每炉出钢都是k公斤，而炼1公斤

18、钢的平均燃料费第一法为m元，第二法为n元。若要求在c小时内炼钢公斤数不少于d，试列出燃料费最省的两种方法的分配方案的数学模型。第39页/共109页设用第一种炼法炼钢x1炉，第二种炼钢x2炉 s.t.第40页/共109页引例2.资源分配问题：某个中型的百货商场要求售货人员每周工作5天，连续休息2天，工资200元/周，已知对售货人员的需求经过统计分析如下表，问如何安排可使配备销售人员的总费用最少？星期星期一一二二三三四四五五六六日日所需售货员人数所需售货员人数18151216191412开始休息的人数 x1 x2 x3 x4 x5 x6 x7 设决策变量如上，可建立如下模型：第41页/共109页第

19、42页/共109页非线性规划非线性规划问题的一般数学模型：其中，为目标函数，为约束函数，这些函数中至少有一个是非线性函数。第43页/共109页应用实例：供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：km）及水泥日用量d(t)由下表给出目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20t假设从料场到工地之间均有直线道路相连 （1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少水泥，可使总的吨千米数最小（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20t，问应建在何处，节省的吨千米数有多大？第44页

20、/共109页（一）建立模型 记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；料场j向工地i的运送量为Xij当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj第45页/共109页多目标规划引例1.投资问题 某公司在一段时间内有a(亿元)的资金可用于建厂投资。若可供选择的项目记为1,2,m。而且一旦对第i个项目投资就用去ai亿元；而这段时间内可得收益ci亿元。问如何确定最佳的投资方案？最佳投资方案：投资最少，收益最大！第46页/共109页投资最少：约束条件为：收益最大：第47页/共109页引例2：生产问题

21、 某工厂生产两种产品，产品A每单位利润为10元，而产品B每单位利润为8元；产品A每单位需3小时装配时间而B为2小时，每周总装配有效时间为120小时。工厂允许加班，但加班生产出来的产品利润要减去1元。根据最近的合同，厂商每周最少的向用户提供两种产品各30单位。要求：必须遵守合同；尽可能少加班；利润最大。问应怎样安排生产？x1：每周正常时间生产得A产品的数量；x2：每周加班时间生产得A产品的数量；x3：每周正常时间生产得B产品的数量；x4：每周加班时间生产得B产品的数量；第48页/共109页目标函数（有两个）：第49页/共109页常用无约束最优化方法常用无约束最优化方法常用约束最优化方法常用约束最

22、优化方法第50页/共109页最优化问题的迭代解法最优化问题的迭代解法（一）迭代方法 在经典极值问题中，解析法虽然具有概念简明在经典极值问题中，解析法虽然具有概念简明,计算精确等优点，但因只能计算精确等优点，但因只能适用于简单或特殊问题的寻优适用于简单或特殊问题的寻优,对于复杂的工程实际问题通常无能为力，所以对于复杂的工程实际问题通常无能为力，所以极少使用。极少使用。最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函数、最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函数、约束函数在该点的某些信息，确定本次迭代的一个搜索方向和适当的步长，从约束函数在该点的某些信息，确定本次迭

23、代的一个搜索方向和适当的步长，从而到达一个新点，用式子表示即为而到达一个新点，用式子表示即为第51页/共109页 式中式中,前一次已取得的迭代点，在前一次已取得的迭代点，在 开始计算时为迭代初始点开始计算时为迭代初始点 ；新的迭代点；新的迭代点；第第k k次迭代计算的搜索方向；次迭代计算的搜索方向；第第k k次迭代计算的步长因子次迭代计算的步长因子 (1.2)(1.2)第52页/共109页 按照式（按照式（1.21.2）进行一系列迭代计算所根据的思想是所谓的）进行一系列迭代计算所根据的思想是所谓的“爬山法爬山法”，就是将寻求函数小点（无约束或约束极小点）的过程比喻为向，就是将寻求函数小点（无约

24、束或约束极小点）的过程比喻为向“山山”的顶的顶峰攀登的过程，始终保持向峰攀登的过程，始终保持向“高高”的方向前进，直至达到的方向前进，直至达到“山顶山顶”。当然。当然“山顶山顶”可以理目标函数的极大值，也可以理解为极小值，前者称为上升算法，可以理目标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法。这两种算法都有一个共同的特点，就是每前进一步都应后者称为下降算法。这两种算法都有一个共同的特点，就是每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息。该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息。如果是下降算法，则序列迭代点的

25、目标函数值必须满足下列关系如果是下降算法，则序列迭代点的目标函数值必须满足下列关系第53页/共109页如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即即 下图为迭代过程下图为迭代过程第54页/共109页（二）收敛速度与计算终止准则（二）收敛速度与计算终止准则（1 1）收敛速度）收敛速度作为一个算法作为一个算法A A，能够收敛于问题的最优解当然，能够收敛于问题的最优解当然是必要的，但光能收敛还不够，还必须能以较快是必要的，但光能收敛还不够，还必须能以较快的速度收敛，这才是好的算法的速度收敛，这才是好的算法定义定

26、义1.1 1.1 设由算法设由算法A A产生的迭代点列产生的迭代点列 在某种在某种“|”|”的意义下收敛于点的意义下收敛于点 ，即，即 ,若存在实数若存在实数 及一个与迭代次数及一个与迭代次数 无关的常数无关的常数 使得使得 则算法则算法A A产生的迭代点列叫做具有产生的迭代点列叫做具有 阶收敛速度，或算法阶收敛速度，或算法A A叫做是叫做是 阶收阶收敛的，特别地：敛的，特别地：第55页/共109页 当当 ，迭代点列，迭代点列 称为具有线性收敛速度或算法称为具有线性收敛速度或算法A A称为线性收敛称为线性收敛的的 当当 ，或，或 时，迭代点列时，迭代点列 叫做具有超线性收敛速度或叫做具有超线性

27、收敛速度或称算法称算法A A是超线性收敛是超线性收敛 当当 时，迭代点列时，迭代点列 叫做具有二阶收敛速度或算法叫做具有二阶收敛速度或算法A A是二阶收敛的是二阶收敛的 一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法 第56页/共109页 (2)(2)计算终止准则计算终止准则 用迭代方法寻优时，其迭代过程总不能无限制地进行用迭代方法寻优时，其迭代过程总不能无限制地进行下去，那么什么时候截断这种迭代呢？这就是迭代什么下去，那么什么时候截断这种迭代呢？这就是迭代什么时候终止的问题。时候终止的问题。从理论上说，当然希望最终迭代点到达理论极

28、小点，从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时才或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代但是这在实际上是办不到的因为对于一个终止迭代但是这在实际上是办不到的因为对于一个待求的优化问题，其理论极小点在哪里并不知道所知待求的优化问题，其理论极小点在哪里并不知道所知道的只是通过迭代计算获得的迭代点列，因此只能从点道的只是通过迭代计算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代。列所提供的信息来判断是否应该终止迭代。对于无约束优化问题通常采用的迭代终止准则有以下对于无约束优化问题通常采用的迭代终止准则有以下几种：几

29、种：第57页/共109页点距准则点距准则相邻两迭代点之间的距离已达到充分小，即相邻两迭代点之间的距离已达到充分小，即式中式中 是一个充分小正数，代表计算精度是一个充分小正数，代表计算精度函数下降量准则函数下降量准则相邻两迭代点的函数值下降量已达到充分小当相邻两迭代点的函数值下降量已达到充分小当 时，时，可用函数绝对下降量准则可用函数绝对下降量准则当当 时，可用函数相对下降量准则时，可用函数相对下降量准则梯度准则梯度准则目标函数在迭代点的梯度已达到充分小，即目标函数在迭代点的梯度已达到充分小，即这一准则对于定义域上的凸函数是完全正确的若是非凸函数，有这一准则对于定义域上的凸函数是完全正确的若是非

30、凸函数，有可能导致误把驻点作为最优点。可能导致误把驻点作为最优点。对于约束优化问题，不同的优化方法有各自的终止准则对于约束优化问题，不同的优化方法有各自的终止准则第58页/共109页综上所述，优化算法的基本迭代过程如下：综上所述，优化算法的基本迭代过程如下：选定初始点选定初始点 ，置，置 按照某种规则确定搜索方向按照某种规则确定搜索方向 按某种规则确定按某种规则确定 使得使得 计算计算 判定判定 是否满足终止准则若满足，则打印是否满足终止准则若满足，则打印 和和 ,停机；否则置停机；否则置 ,转转第59页/共109页NYX是否满足终止准则输出X，f(X)开始结束选定X0确定P确定t，使得f(X

31、0+tP)0，加步系数1，令k=00=(t0)，比较目标函数值tk+1=tk+hk,k+1=(tk+1)a=mint，tk+1b=maxt，tk+1结束NYNY k+1khk+1=hk,t=tk,tk=tk+1,k=k+1,k=k+1k=0hk=hk,k=k+1第70页/共109页 在加步探索法中，一般建议 若能估计问题（4.3）的最优解的大体位置的话，初始点要尽量取接近于问题（4.3）的最优解.在具体运用上述加步探索法时，有时还要考虑一些细节问题例如，当探索得到新点处的目标函数值和出发点处相同时，以及初始步长应如何选取等，都需作适当处理搜索区间及其确定方法搜索区间及其确定方法第71页/共10

32、9页 三、单谷区间与单谷函数三、单谷区间与单谷函数 由于以后要介绍的一些维搜索方法，主要适用于问题（4.3）在搜索区间中只有唯一的最优解的情况，为此，我们再给出下面单谷区间与单谷函数概念 定义4.2 设 闭区间 若存在点 使得 在 上严格递减，在 上严格递增，则称 是函数 的单谷区间，是 上单谷函数 搜索区间及其确定方法搜索区间及其确定方法第72页/共109页由定义4.2易知，一个区间是某函数的单谷区间意味着，在该区间中函数只有一个“凹谷”（极小值）例如，左图中的 是 的单谷区间，也即 是 上的单谷函数右图中的 不是 的单谷区间，即 不是 上的单谷函数 搜索区间及其确定方法搜索区间及其确定方法

33、第73页/共109页 另外，从定义4.2还可知，某区间上的单谷函数在该区间上不一定是连续函数，而凸函数在所给区间上必然是单谷函数（如左图所示）由定义4.1和定义4.2知，函数的单谷区间总是相应问题（4.3）的一个搜索区间（如左图所示），但反之不然（如右图所示）搜索区间及其确定方法搜索区间及其确定方法第74页/共109页单谷区间和单谷函数有如下有用的性质：定理4.1 设 是的单谷区间，任取 并且 （1）若有 ，则 是 的单谷区间（2）若有 ，则 是 的单谷区间定理4.1说明，经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间换句话说利用这个定理可以把搜索区间无限缩小，从而求到极小点.以下介绍

34、的几种一维搜索方法都是利用这个定理通过不断地缩短搜索区间的长度，来求得一维最优化问题的近似最优解搜索区间及其确定方法搜索区间及其确定方法第75页/共109页 一、对分法基本原理一、对分法基本原理求解一维最优化问题 一般可先确定它的一个有限搜索区间 ，把问题化为求解问题 ，然后通过不断缩短区间的长度，最后求得最优解对分法对分法第76页/共109页设 在已获得的搜索区间 内具有连续的一阶导数因为 在 上可微，故 在 上连续，由此知 在 上有最小值令 ，总可求得极小点 不妨设 在 上是单减函数；在 上是单增函数。所以 时，故 ；当 时，亦即 对分法的原理如图 对分法对分法第77页/共109页二、对分

35、法迭代步骤二、对分法迭代步骤已知 ，表达式，终止限 (1)确定初始搜索区间 ，要求(2)计算 的中点 (3)若 ，则 ，转(4)；若 ，则 ，转(5)；若 ，则 ，转(4)(4)若 ，则 ，转(5)；否则转(2)(5)打印 ，停机对分法对分法第78页/共109页Y开始确定ab,要求c=(a+b)/2b=ct*=(a+b)/2输出t*结束T*=cNa=cNYNY对分法的计算流程如图所示第79页/共109页三、对分法有关说明三、对分法有关说明 对分法每次迭代都取区间的中点 a.若这点的导数值小于零，说明的根位于右半区间中，因此去掉左半区间；b.若中点导数值大于零，则去掉右半区间；c.若中点导数值正

36、好等于零，则该点就是极小点 因为每次迭代都使原区间缩短一半，所以称为对分法或二分法对分法对分法第80页/共109页NewtonNewton切线法切线法 一、一、NewtonNewton切线法基本原理切线法基本原理 设 在已获得的搜索区间 内具有连续二阶导数，求 因为 在 上可微，故 在 上有最小值，令 第81页/共109页下面不妨设在区间 中经过 次迭代已求得方程 的一个近似根 。过 作曲线 的切线,其方程是然后用这条切线与横轴交点的横坐标 作为根的新的近似（如图）它可由方程（4.4）在令 的解出来，即 这就是Newton切线法迭代公式 NewtonNewton切线法切线法第82页/共109页

37、 二、二、NewtonNewton切线法迭代步骤切线法迭代步骤已知 ，表达式，终止限 (1)确定初始搜索区间 ，要求(2)选定 (3)计算 (4)若 ，则 ，转（3）；否则转（5）(5)打印 ，停机NewtonNewton切线法切线法第83页/共109页Newton切线法的计算流程如图所示第84页/共109页 三、三、NewtonNewton切线法有关说明切线法有关说明这种方法一旦用好，收敛速度是很高的如果初始点选得适当，通常经过几次迭代就可以得到满足一般精度要求的结果.但是它也有缺点：第一，需要求二阶导数如果在多维最优化问题的一维搜索中使用这种方法，就要涉及Hesse矩阵，一般是难于求出的N

38、ewtonNewton切线法切线法第85页/共109页第二，当曲线 在 上有较复杂的弯曲时，这种方法也往往失效如图(a)所示的迭代：结果 跳出 .迭代或者发散，或者找到的根并不是我们想要的结果第三，即使曲线比较正常，在 中或者上凹或者下凹，初始点的选取也必须适当在图（b）的情况下，曲线上凹，应选点b作为初始点；而在图（c）的情况下，曲线下凹，应选点a为初始点否则都可能失败NewtonNewton切线法切线法第86页/共109页黄金分割法黄金分割法 一、黄金分割法基本原理一、黄金分割法基本原理 要介绍黄金分割法有必要回顾一下古老的黄金分割问题。所谓黄金分割就是将一线段分为二段的方法。这样分后，要

39、求整段长L与较长段x的比值正好等于较长段x与较短段 的比值(如图)第87页/共109页于是则解得由此可见长段的长度应为全长的0.618倍，而短段的长度应为全长的0.382倍因为古代的人们认为按0.618的比率来分割线段是最协调，胜似黄金，故称之为黄金分割黄金分割法黄金分割法第88页/共109页 用黄金分割法进行一维搜索，其基本思想是在单谷区间内适当插入两点，由此把区间分为三段，然后再通过比较这两点函数值大小，就可以确定是删去最左段还是最右段，或者同时删去左右两段保留中间段如此继续下去可将单谷区间无限缩小黄金分割法黄金分割法第89页/共109页二、黄金分割法迭代步骤二、黄金分割法迭代步骤 现在提

40、出一个问题，就在 上如何选取二点使得迭代次数最小而区间缩短最快？要解决这个问题，人们想到对区间 选二点 等价于将区间长度 进行黄金分割，也就是将第一个搜索点 取在 的0.618处，第二个搜索点 取成 的对称点即 的0.382处（如图所示）黄金分割法黄金分割法第90页/共109页即要求接着计算 与 的值，并根据 与 的值的大小关系分情况讨论：（1）若 ,说明 是好点，于是把区间 划掉，保留 ，则 内有一保留点 ，置新的区间 ；（2）若 ，说明 是好点，于是应将 划掉，保留 ,则 内有保留点 ,置新的区间 .黄金分割法黄金分割法第91页/共109页(3)若 则应具体分析,看极小点可能在哪一边再决定

41、取舍，在一般情况下，可同时划掉 和 仅保留中间的 重置新的区间 接下来是在留下的区间 内找好点重复上面的步骤，直到搜索区间 小于给定的允许误差 为止。这样就得到黄金分割法迭代算法：黄金分割法黄金分割法第92页/共109页已知 ，常数 0.382，终止限 (1)确定 的初始搜索区间 (2)计算 (3)计算 (4)若 ,则打印 ，停机；否则，转(5)(5)判别是否满足 ：若满足，则置 ，然后转(3)；否则，置 然后转(4)黄金分割法黄金分割法第93页/共109页黄金分割法算法流程如图所示第94页/共109页 三、黄金分割法有关说明三、黄金分割法有关说明 黄金分割法是通过所选试点的函数值而逐步缩短单

42、谷区间来搜索最优点该方法适用于单谷区间上的任何函数，甚至可以是不连续函数，因此这种算法属于直接法，适用相当广泛 黄金分割法黄金分割法第95页/共109页 抛物线插值法抛物线插值法 一、抛物线插值法基本原理一、抛物线插值法基本原理 考虑一维搜索问题 假设其中 是定义在区间 上的单峰函数首先用试探法在 上找一点 ，使之满足 第96页/共109页 通过目标函数曲线上的三个点 作它的二次拟合曲线（如图所示）图4.14 抛物线插值法抛物线插值法第97页/共109页 由于上述三个点既是目标函数曲线 上的点，又是二次拟合曲线 上的点，故有方程组 将方程组（4.5）中的 消去，得 抛物线插值法抛物线插值法第9

43、8页/共109页 从方程组（4.6）可解出待定系数 对于二次拟合函数 ，我们很容易求得它的极小值点令 即 ，从中解出 即为二次拟合函数 的极小值点 抛物线插值法抛物线插值法第99页/共109页将式（4.7）与式（4.8）代入式（4.9）得用区间 上二次拟合函数 的这个极小值点 作为目标函数 在该区间极小值点的一个估计值若 和 已充分接近，即对给定的允许误差 使 成立时，就可被看作是 在区间 内近似最优解；否则应缩短区间，按照 值保持两头大、中间小的原则构成新的三点，继续上述过程，直至不等式（4.11）成立为止 抛物线插值法抛物线插值法第100页/共109页 二、抛物线插值法迭代步骤二、抛物线插

44、值法迭代步骤下面具体介绍缩短区间,构成新三点的方法 由式（4.10）得到的点 ,在区间 内既可能在点 的左侧(即 ),又可能在 的右侧(即 )。分别对应这两种情形比较 和 的大小，又有 等三种情形，故共有如下六种情况（如图所示）：抛物线插值法抛物线插值法第101页/共109页 抛物线插值法抛物线插值法第102页/共109页（1）对于图(a)的情况:因 ,所以相对 为说 是好点，故划掉区间 ,保留 为新区间，故置 保持不变；（2）对于图(b)的情况：因 ,所以相对 来说 是好点，故划掉 保留为 新区间，故置 与 保持不变；（3）对于图(c)的情况：因 所以相对 来说 是好点，故划掉 ,保留 为新

45、区间，故置 保持不变；抛物线插值法抛物线插值法第103页/共109页（4）对于图(d)的情况:因 所以相对 来说 是好点，故划掉 保留 故置 ，与 保持不变（5）对于图(e)的情况：一般同时划掉 及 仅留中间的 ，故置（6）对于图(f)的情况：一般同时划掉 及 ，仅留中间的 ，故置 抛物线插值法抛物线插值法第104页/共109页通过上述讨论,我们可直接给抛物线插值法的迭代流程图.第105页/共109页 三、抛物线插值法有关说明三、抛物线插值法有关说明 抛物线插值法是多项式逼近法的一种所谓多项式逼近，是利用目标函数在若干点的函数值或导数值等信息，构成一个与目标函数相接近的低次插值多项式，用该多项式的最优解作为目标函数的近似最优解。抛物线插值法抛物线插值法第106页/共109页第107页/共109页第108页/共109页