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

最优化方法及控制应用最优化方法及控制应用主讲人：董密信息科学与工程学院信息科学与工程学院参考书：1.实用最优化方法 R.Fleter著，游兆永等译 天津科技翻译出版公司2.非线性规划数值方法 袁亚湘 上海科学技术出版社 19953.非线性最优方法 席少霖 高等教育出版社 4.工程优化的算法分析 张可村 西安交大出版社 19895.最优化方法 解文新，韩立兴等 天津大学出版社 20016.最优化方法 施光燕，董加礼 高等教育出版社 2001最优化方法及控制应用最优化：在多种（有限种或无限种）决策中挑选最优化：在多种（有限种或无限种）决策中挑选 最好决策的问题。最好决策的问题。最优化方法：（也称做运筹学方法）是近几十年最优化方法：（也称做运筹学方法）是近几十年 形成的，主要运用数学方法研究各种系统形成的，主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决的优化途径及方案，为决策者提供科学决策的依据。策的依据。最优方案：是达到最优目标的方案。最优方案：是达到最优目标的方案。最优化理论：就是最优化方法的理论。最优化理论：就是最优化方法的理论。数学意义数学意义为了达到最优化目的所提出的各种求解方法。从为了达到最优化目的所提出的各种求解方法。从数学意义上说，最优化方法是一种求极值的方法，数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。和财力等资源为最少。发展简史发展简史公元前公元前 500年古希腊在讨论建筑美学中就已发现了年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为长方形长与宽的最佳比例为1.618，称为黄金分割，称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。方法解决最优化问题。最优化方法真正形成为科学方法则在最优化方法真正形成为科学方法则在17世纪以后。世纪以后。工作步骤工作步骤 提出最优化问题，收集有关数据和资料；提出最优化问题，收集有关数据和资料；建立最优化问题的数学模型建立最优化问题的数学模型,确定变量确定变量,列出目标函列出目标函数和约束条件；数和约束条件；分析模型，选择合适的最优化方法；分析模型，选择合适的最优化方法；求解，一般通过编制程序，用计算机求最优解；求解，一般通过编制程序，用计算机求最优解；最优解的检验和实施。最优解的检验和实施。模型的基本要素模型的基本要素最优化模型包括：变量、约束条件和目标函数最优化模型包括：变量、约束条件和目标函数变量：指最优化问题中待确定的某些量。变量可变量：指最优化问题中待确定的某些量。变量可用用x(x1，x2,xn)T表示。表示。约束条件约束条件:指在求最优解时对变量的某些限制指在求最优解时对变量的某些限制,包括包括技术上的约束、资源上的约束和时间上的约束等。约技术上的约束、资源上的约束和时间上的约束等。约束条件可用束条件可用 gi(x)0表示表示i1,2，m，m 表示约表示约束条件数；束条件数；目标函数：最优化有一定的评价标准。目标函数就目标函数：最优化有一定的评价标准。目标函数就是这种标准的数学描述，一般可用是这种标准的数学描述，一般可用f(x)来表示，即来表示，即f(x)=f(x1，x2,xn)。最优化方法最优化方法最优化问题的求解方法可分成解析法、直接法、数最优化问题的求解方法可分成解析法、直接法、数值计算法和其他方法。值计算法和其他方法。解析法：只适用于目标函数和约束条件有明显的解析法：只适用于目标函数和约束条件有明显的解析表达式的情况。解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。件将问题简化，因此也称间接法。直接法：当目标函数较为复杂或者不能用变量显直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。可采用直函数描述时，无法用解析法求必要条件。可采用直接搜索的方法经过若干次迭代搜索到最优点。接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索对于一维搜索(单变量极值问题单变量极值问题)，主要用消去法或，主要用消去法或多项式插值法；对于多维搜索问题多项式插值法；对于多维搜索问题(多变量极值问题多变量极值问题)主要应用爬山法。主要应用爬山法。数值计算法：也是一种直接法。它以梯度法为基数值计算法：也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。础，所以是一种解析与数值计算相结合的方法。其他方法：如网络最优化方法等其他方法：如网络最优化方法等最优解的概念最优解的概念最优化问题的解一般称为最优解。如果只考察约束集最优化问题的解一般称为最优解。如果只考察约束集合中某一局部范围内的优劣情况，则解称为局部最优合中某一局部范围内的优劣情况，则解称为局部最优解。如果是考察整个约束集合中的情况，则解称为总解。如果是考察整个约束集合中的情况，则解称为总体最优解。对于不同优化问题，最优解有不同的含意，体最优解。对于不同优化问题，最优解有不同的含意，因而还有专用的名称。因而还有专用的名称。例如，在对策论和数理经济模型中称为平衡解；在控例如，在对策论和数理经济模型中称为平衡解；在控制问题中称为最优控制或极值控制；在多目标决策问制问题中称为最优控制或极值控制；在多目标决策问题中称为非劣解（又称帕雷托最优解或有效解）。题中称为非劣解（又称帕雷托最优解或有效解）。最优化方法的应用最优化方法的应用最优化可分为最优设计、最优计划、最优管理和最最优化可分为最优设计、最优计划、最优管理和最优控制等四个方面。优控制等四个方面。最优设计：世界各国工程技术界，尤其是飞机、最优设计：世界各国工程技术界，尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法造船、机械、建筑等部门都已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计优化问题的选取等，结合有限元方法已使许多设计优化问题得到解决。得到解决。最优计划：现代国民经济或部门经济的计划，直最优计划：现代国民经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农业规至企业的发展规划和年度生产计划，尤其是农业规划、种植计划、能源规划和其他资源、环境和生态划、种植计划、能源规划和其他资源、环境和生态规划的制订，都已开始应用最优化方法。一个重要规划的制订，都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。的发展趋势是帮助领导部门进行各种优化决策。最优管理：一般在日常生产计划的制订、调度和最优管理：一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速决策支持系统的建立和使用，使最优管理得到迅速的发展。的发展。最优控制：主要用于对各种控制系统的优化。例最优控制：主要用于对各种控制系统的优化。例如，导弹系统的最优控制，能保证用最少燃料完成如，导弹系统的最优控制，能保证用最少燃料完成飞行任务，用最短时间达到目标飞行任务，用最短时间达到目标;；再如飞机、船舶、；再如飞机、船舶、电力系统等的最优控制，化工、冶金等工厂的最佳电力系统等的最优控制，化工、冶金等工厂的最佳工况的控制。工况的控制。一、组合最优化一、组合最优化TSP:（即旅行商问题）假设有（即旅行商问题）假设有n 个城市个城市，一个推销员要在这，一个推销员要在这 n个城市推销产品个城市推销产品，要求经过每个城市且仅有一次要求经过每个城市且仅有一次，如如 何选择这条路径，使路径最短？何选择这条路径，使路径最短？二、动态规划二、动态规划管道铺设：有管道铺设：有n个城市铺设管道，要求管道到达每个城市，并个城市铺设管道，要求管道到达每个城市，并且使总的费用最低。且使总的费用最低。经典极值问题经典极值问题包括：无约束极值问题约束条件下的极值问题1、无约束极值问题的数学模型 2、约束条件下极值问题的数学模型 其中，极大值问题可以转化为极小值问题来进行求解。如求：可以转化为：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=1处取得在-3,4上取得最小值f(1)=7 有约束最优化最优化方法分类（一）线性最优化：目标函数和约束条件都是线性的则称为线性最优化。非线性最优化：目标函数和约束条件如果含有非线性的，则称为非线性最优化。（二）静态最优化：如果可能的方案与时间无关，则是静态最优化问题。动态最优化：如果可能的方案与时间有关，则是动态最优化问题有约束最优化问题的数学建模 有约束最优化模型一般具有以下形式：或 其中f(x)为目标函数，省略号表示约束式子，可以是等式约束，也可以是不等式约束。根据目标函数，约束条件的特点将最优化方法包含的主要内容大致如下划分：线性规划 整数规划 非线性规划 动态规划 多目标规划 对策论最优化方法主要内容两个引例问题一：某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示 12kg40原材料B16kg04原材料A8台时21设备III该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问应如何安排计划使该工厂获利最多？解：该工厂生产产品I x1件，生产产品II x2件，我们可建立如下数学模型：s.t.问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解 设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：故目标函数为：约束条件为：运用最优化方法解决最优化问题的一般方法步骤如下：前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。针对建立的模型，选择合适的求解方法或数学软件。编写程序，利用计算机求解。对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。线 性 规 划某豆腐店用黄豆制作两种不同口感的豆腐出售。制作口感较鲜嫩的豆腐每千克需要0.3千克一级黄豆及0.5千克二级黄豆，售价10元；制作口感较厚实的豆腐每千克需要0.4千克一级黄豆及0.2千克二级黄豆，售价5元。现小店购入9千克一级黄豆和8千克二级黄豆。问：应如何安排制作计划才能获得最大收益。一、问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制作计划，使得售出各种豆腐能获得最大收益。二、模型假设1假设制作的豆腐能全部售出。2假设豆腐售价无波动。变量假设：设计划制作口感鲜嫩和厚实的豆腐各x1千克和 x2千克，可获得收益R元。目标函数：获得的总收益最大。总收益可表示为：受一级黄豆数量限制：受二级黄豆数量限制：综上分析，得到该问题的线性规划模型 s.t.用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.0000 15.0000FVAL=-175.0000用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线 性 规 划 设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品。根据机床性能和以前的生产情况，得知每单位产品所需车间的工作小时数、每个车间在一个季度工作小时的上限以及单位产品的利润，如下表所示(例如，生产一个单位的A产品，需要甲、乙、丙三个车间分别工作1小时、2小时和4小时)问：每种产品各应该每季度生产多少，才能使这个工厂每季度生产利润达到最大。生产单位生产单位产品所需产品所需车间的工车间的工作小时数作小时数 ABCDEF每个车间每个车间一个季度一个季度工作小时工作小时的上限的上限甲甲111323500乙乙255500丙丙425500丁丁138500利润利润(百元百元)4.02.45.55.04.58.5这是一个典型的最优化问题，属线性规划。假设：产品合格且能及时销售出去；工作无等待情况等 变量说明：xj：第j种产品的生产量（j=1,2,6）aij：第i车间生产单位第j种产品所需工作小时数 （i=1,2,3,4;j=1,2,6）bi：第i车间的最大工作上限 cj：第j种产品的单位利润 则：cjxj为第j种产品的利润总额；aijxj表示第i车间生产第j种产品所花时间总数；于是，我们可建立如下数学模型：s.t.计算结果：Z(百元百元)x1x2x3x4x5x6132000604010040运 输 问 题 要从甲城调出蔬菜2000吨，从乙城调出蔬菜2500吨，从丙地调出3000吨，分别供应A地2000吨，B地2300吨、C地1800吨、D地1400吨，已知每吨运费如下表：供应单位供应单位调出单位调出单位ABCD甲甲21271340乙乙45513720丙丙32352030问：如何调拨才能使运费最省？可以建立如下模型：s.t.整 数 规 划 最优化问题中的所有变量均为整数时，这类问题称为整数规划问题。如果线性规划中的所有变量均为整数时，称这类问题为线性整数规划问题。整数规划可分为线性整数规划和非线性整数规划，以及混合整数规划等。如果决策变量的取值要么为0，要么为1，则这样的规划问题称为01规划。例1 某钢厂两个炼钢炉同时各用一种方法炼钢。第一种炼法每炉用a小时，第二种用b小时（包括清炉时间）。假定这两种炼法，每炉出钢都是k公斤，而炼1公斤钢的平均燃料费第一法为m元，第二法为n元。若要求在c小时内炼钢公斤数不少于d，试列出燃料费最省的两种方法的分配方案的数学模型。设用第一种炼法炼钢x1炉，第二种炼钢x2炉 s.t.引例2.资源分配问题：某个中型的百货商场要求售货人员每周工作5天，连续休息2天，工资200元/周，已知对售货人员的需求经过统计分析如下表，问如何安排可使配备销售人员的总费用最少？星期星期一一二二三三四四五五六六日日所需售货员人数所需售货员人数18151216191412开始休息的人数 x1 x2 x3 x4 x5 x6 x7 设决策变量如上，可建立如下模型：非线性规划非线性规划问题的一般数学模型：其中，为目标函数，为约束函数，这些函数中至少有一个是非线性函数。应用实例：供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：km）及水泥日用量d(t)由下表给出目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20t假设从料场到工地之间均有直线道路相连 （1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少水泥，可使总的吨千米数最小（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20t，问应建在何处，节省的吨千米数有多大？（一）建立模型 记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；料场j向工地i的运送量为Xij当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj多目标规划引例1.投资问题 某公司在一段时间内有a(亿元)的资金可用于建厂投资。若可供选择的项目记为1,2,m。而且一旦对第i个项目投资就用去ai亿元；而这段时间内可得收益ci亿元。问如何确定最佳的投资方案？最佳投资方案：投资最少，收益最大！投资最少：约束条件为：收益最大：引例2：生产问题 某工厂生产两种产品，产品A每单位利润为10元，而产品B每单位利润为8元；产品A每单位需3小时装配时间而B为2小时，每周总装配有效时间为120小时。工厂允许加班，但加班生产出来的产品利润要减去1元。根据最近的合同，厂商每周最少的向用户提供两种产品各30单位。要求：必须遵守合同；尽可能少加班；利润最大。问应怎样安排生产？x1：每周正常时间生产得A产品的数量；x2：每周加班时间生产得A产品的数量；x3：每周正常时间生产得B产品的数量；x4：每周加班时间生产得B产品的数量；目标函数（有两个）：常用无约束最优化方法常用无约束最优化方法常用约束最优化方法常用约束最优化方法最优化问题的迭代解法（一）迭代方法 在经典极值问题中，解析法虽然具有概念简明在经典极值问题中，解析法虽然具有概念简明,计算精确等优点，但因只能适用于简单或特殊问计算精确等优点，但因只能适用于简单或特殊问题的寻优题的寻优,对于复杂的工程实际问题通常无能为力，对于复杂的工程实际问题通常无能为力，所以极少使用。所以极少使用。最优化问题的迭代算法是指：从某一选定的初最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函数、约束函数在该点的某始点出发，根据目标函数、约束函数在该点的某些信息，确定本次迭代的一个搜索方向和适当的些信息，确定本次迭代的一个搜索方向和适当的步长，从而到达一个新点，用式子表示即为步长，从而到达一个新点，用式子表示即为 式中式中,前一次已取得的迭代点，在前一次已取得的迭代点，在 开始计算时为迭代初始点开始计算时为迭代初始点 ；新的迭代点；新的迭代点；第第k k次迭代计算的搜索方向；次迭代计算的搜索方向；第第k k次迭代计算的步长因子次迭代计算的步长因子 (1.2(1.2)按照式（按照式（1.21.2）进行一系列迭代计算所根据的）进行一系列迭代计算所根据的思想是所谓的思想是所谓的“爬山法爬山法”，就是将寻求函数小点，就是将寻求函数小点（无约束或约束极小点）的过程比喻为向（无约束或约束极小点）的过程比喻为向“山山”的顶峰攀登的过程，始终保持向的顶峰攀登的过程，始终保持向“高高”的方向前的方向前进，直至达到进，直至达到“山顶山顶”。当然。当然“山顶山顶”可以理目可以理目标函数的极大值，也可以理解为极小值，前者称标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法。这两种算法都为上升算法，后者称为下降算法。这两种算法都有一个共同的特点，就是每前进一步都应该使目有一个共同的特点，就是每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息。如果是下降算法，则序列方向提供有用的信息。如果是下降算法，则序列迭代点的目标函数值必须满足下列关系迭代点的目标函数值必须满足下列关系如果是求一个约束的极小点，则每一次迭代的新如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即点都应该在约束可行域内，即 下图为迭代过程下图为迭代过程（二）收敛速度与计算终止准则（二）收敛速度与计算终止准则（二）收敛速度与计算终止准则（二）收敛速度与计算终止准则（1 1）收敛速度）收敛速度）收敛速度）收敛速度作为一个算法作为一个算法作为一个算法作为一个算法A A，能够收敛于问题的最优解当然，能够收敛于问题的最优解当然，能够收敛于问题的最优解当然，能够收敛于问题的最优解当然是必要的，但光能收敛还不够，还必须能以较快是必要的，但光能收敛还不够，还必须能以较快是必要的，但光能收敛还不够，还必须能以较快是必要的，但光能收敛还不够，还必须能以较快的速度收敛，这才是好的算法的速度收敛，这才是好的算法的速度收敛，这才是好的算法的速度收敛，这才是好的算法定义定义定义定义1.1 1.1 设由算法设由算法设由算法设由算法A A产生的迭代点列产生的迭代点列产生的迭代点列产生的迭代点列 在某种在某种在某种在某种“|”|”的意义下收敛于点的意义下收敛于点的意义下收敛于点的意义下收敛于点 ，即，即，即，即 ,若存在实数若存在实数若存在实数若存在实数 及一个与迭代次数及一个与迭代次数及一个与迭代次数及一个与迭代次数 无关的无关的无关的无关的常数常数常数常数 使得使得使得使得 则算法则算法则算法则算法A A产生的迭代点列叫做具有产生的迭代点列叫做具有产生的迭代点列叫做具有产生的迭代点列叫做具有 阶收敛速阶收敛速阶收敛速阶收敛速度，或算法度，或算法度，或算法度，或算法A A叫做是叫做是叫做是叫做是 阶收敛的，特别地：阶收敛的，特别地：阶收敛的，特别地：阶收敛的，特别地：当当当当 ，迭代点列，迭代点列，迭代点列，迭代点列 称为具有线性收敛称为具有线性收敛称为具有线性收敛称为具有线性收敛速度或算法速度或算法速度或算法速度或算法A A称为线性收敛的称为线性收敛的称为线性收敛的称为线性收敛的 当当当当 ，或，或，或，或 时，迭代点列时，迭代点列时，迭代点列时，迭代点列 叫做具有超线性收敛速度或称算法叫做具有超线性收敛速度或称算法叫做具有超线性收敛速度或称算法叫做具有超线性收敛速度或称算法A A是超线性是超线性是超线性是超线性收敛收敛收敛收敛 当当当当 时，迭代点列时，迭代点列时，迭代点列时，迭代点列 叫做具有二阶收敛速叫做具有二阶收敛速叫做具有二阶收敛速叫做具有二阶收敛速度或算法度或算法度或算法度或算法A A是二阶收敛的是二阶收敛的是二阶收敛的是二阶收敛的 一般认为，具有超线性收敛或二阶收敛的算法一般认为，具有超线性收敛或二阶收敛的算法一般认为，具有超线性收敛或二阶收敛的算法一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法是较快速的算法是较快速的算法是较快速的算法 (2)(2)计算终止准则计算终止准则计算终止准则计算终止准则 用迭代方法寻优时，其迭代过程总不能无限制地进行用迭代方法寻优时，其迭代过程总不能无限制地进行用迭代方法寻优时，其迭代过程总不能无限制地进行用迭代方法寻优时，其迭代过程总不能无限制地进行下去，那么什么时候截断这种迭代呢？这就是迭代什么下去，那么什么时候截断这种迭代呢？这就是迭代什么下去，那么什么时候截断这种迭代呢？这就是迭代什么下去，那么什么时候截断这种迭代呢？这就是迭代什么时候终止的问题。时候终止的问题。时候终止的问题。时候终止的问题。从理论上说，当然希望最终迭代点到达理论极小点，从理论上说，当然希望最终迭代点到达理论极小点，从理论上说，当然希望最终迭代点到达理论极小点，从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时才或者使最终迭代点与理论极小点之间的距离足够小时才或者使最终迭代点与理论极小点之间的距离足够小时才或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代但是这在实际上是办不到的因为对于一个终止迭代但是这在实际上是办不到的因为对于一个终止迭代但是这在实际上是办不到的因为对于一个终止迭代但是这在实际上是办不到的因为对于一个待求的优化问题，其理论极小点在哪里并不知道所知待求的优化问题，其理论极小点在哪里并不知道所知待求的优化问题，其理论极小点在哪里并不知道所知待求的优化问题，其理论极小点在哪里并不知道所知道的只是通过迭代计算获得的迭代点列，因此只能从点道的只是通过迭代计算获得的迭代点列，因此只能从点道的只是通过迭代计算获得的迭代点列，因此只能从点道的只是通过迭代计算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代。列所提供的信息来判断是否应该终止迭代。列所提供的信息来判断是否应该终止迭代。列所提供的信息来判断是否应该终止迭代。对于无约束优化问题通常采用的迭代终止准则有以下对于无约束优化问题通常采用的迭代终止准则有以下对于无约束优化问题通常采用的迭代终止准则有以下对于无约束优化问题通常采用的迭代终止准则有以下几种：几种：几种：几种：点距准则点距准则点距准则点距准则相邻两迭代点之间的距离已达到充分小，即相邻两迭代点之间的距离已达到充分小，即相邻两迭代点之间的距离已达到充分小，即相邻两迭代点之间的距离已达到充分小，即式中式中式中式中 是一个充分小正数，代表计算精度是一个充分小正数，代表计算精度是一个充分小正数，代表计算精度是一个充分小正数，代表计算精度函数下降量准则函数下降量准则函数下降量准则函数下降量准则相邻两迭代点的函数值下降量已达到充分小当相邻两迭代点的函数值下降量已达到充分小当相邻两迭代点的函数值下降量已达到充分小当相邻两迭代点的函数值下降量已达到充分小当 时，时，时，时，可用函数绝对下降量准则可用函数绝对下降量准则可用函数绝对下降量准则可用函数绝对下降量准则当当当当 时，可用函数相对下降量准则时，可用函数相对下降量准则时，可用函数相对下降量准则时，可用函数相对下降量准则梯度准则梯度准则梯度准则梯度准则目标函数在迭代点的梯度已达到充分小，即目标函数在迭代点的梯度已达到充分小，即目标函数在迭代点的梯度已达到充分小，即目标函数在迭代点的梯度已达到充分小，即这一准则对于定义域上的凸函数是完全正确的若是非凸函数，有这一准则对于定义域上的凸函数是完全正确的若是非凸函数，有这一准则对于定义域上的凸函数是完全正确的若是非凸函数，有这一准则对于定义域上的凸函数是完全正确的若是非凸函数，有可能导致误把驻点作为最优点。可能导致误把驻点作为最优点。可能导致误把驻点作为最优点。可能导致误把驻点作为最优点。对于约束优化问题，不同的优化方法有各自的终止准则对于约束优化问题，不同的优化方法有各自的终止准则对于约束优化问题，不同的优化方法有各自的终止准则对于约束优化问题，不同的优化方法有各自的终止准则综上所述，优化算法的基本迭代过程如下：综上所述，优化算法的基本迭代过程如下：综上所述，优化算法的基本迭代过程如下：综上所述，优化算法的基本迭代过程如下：选定初始点选定初始点选定初始点选定初始点 ，置，置，置，置 按照某种规则确定搜索方向按照某种规则确定搜索方向按照某种规则确定搜索方向按照某种规则确定搜索方向 按某种规则确定按某种规则确定按某种规则确定按某种规则确定 使得使得使得使得 计算计算计算计算 判定判定判定判定 是否满足终止准则若满足，则打印是否满足终止准则若满足，则打印是否满足终止准则若满足，则打印是否满足终止准则若满足，则打印 和和和和 ,停机；否则置停机；否则置停机；否则置停机；否则置 ,转转转转NYX是否满足终止准则输出X，f(X)开始结束选定X0确定P确定t，使得f(X0+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 在加步探索法中，一般建议 若能估计问题（4.3）的最优解的大体位置的话，初始点要尽量取接近于问题（4.3）的最优解.在具体运用上述加步探索法时，有时还要考虑一些细节问题例如，当探索得到新点处的目标函数值和出发点处相同时，以及初始步长应如何选取等，都需作适当处理搜索区间及其确定方法搜索区间及其确定方法 三、单谷区间与单谷函数三、单谷区间与单谷函数三、单谷区间与单谷函数三、单谷区间与单谷函数 由由于于以以后后要要介介绍绍的的一一些些维维搜搜索索方方法法，主主要要适适用用于于问问题题（4.3）在在搜搜索索区区间间中中只只有有唯唯一一的的最最优优解解的的情情况况，为为此，我们再给出下面单谷区间与单谷函数概念此，我们再给出下面单谷区间与单谷函数概念 定义定义4.2 设设 闭区间闭区间 若存在点若存在点 使使得得 在在 上上严严格格递递减减，在在 上上严严格格递递增增，则则称称 是函数是函数 的的单谷区间单谷区间，是是 上上单谷函数单谷函数 搜索区间及其确定方法搜索区间及其确定方法由由定定义义4.2易易知知，一一个个区区间间是是某某函函数数的的单单谷谷区区间间意意味味着着，在在该该区区间间中中函函数数只只有有一一个个“凹凹谷谷”（极极小小值值）例例如如，左左图图中中的的 是是 的的单单谷谷区区间间，也也即即 是是 上上的的单单谷谷函函数数右右图图中中的的 不不是是 的的单单谷谷区区间间，即即 不不是是 上的单谷函数上的单谷函数 搜索区间及其确定方法搜索区间及其确定方法 另外，从定义另外，从定义4.2还可知，某区间上的单谷函数在该区还可知，某区间上的单谷函数在该区间上不一定是连续函数，而凸函数在所给区间上必然是间上不一定是连续函数，而凸函数在所给区间上必然是单谷函数（如左图所示）由定义单谷函数（如左图所示）由定义4.1和定义和定义4.2知，函知，函数的单谷区间总是相应问题（数的单谷区间总是相应问题（4.3）的一个搜索区间）的一个搜索区间（如左图所示），但反之不然（如右图所示）（如左图所示），但反之不然（如右图所示）搜索区间及其确定方法搜索区间及其确定方法单谷区间和单谷函数有如下有用的性质：定理4.1 设 是的单谷区间，任取 并且 （1）若有 ，则 是 的单谷区间（2）若有 ，则 是 的单谷区间定理4.1说明，经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间换句话说利用这个定理可以把搜索区间无限缩小，从而求到极小点.以下介绍的几种一维搜索方法都是利用这个定理通过不断地缩短搜索区间的长度，来求得一维最优化问题的近似最优解搜索区间及其确定方法搜索区间及其确定方法一、对分法基本原理一、对分法基本原理一、对分法基本原理一、对分法基本原理求求解解一一维维最最优优化化问问题题 一一般般可可先先确确定定它它的的一一个个有有限限搜搜索索区区间间 ，把把问问题题化化为为求求解解问问题题 ，然然后后通通过不断缩短区间的长度，最后求得最优解过不断缩短区间的长度，最后求得最优解对分法对分法设设 在在已已获获得得的的搜搜索索区区间间 内内具具有有连连续续的的一一阶阶导导数数因因为为 在在 上上可可微微，故故 在在 上上连连续续，由此知由此知 在在 上有最小值上有最小值令令 ，总可求得极小点，总可求得极小点 不妨设不妨设 在在 上是单减函数；在上是单减函数；在 上是单增函数。所以上是单增函数。所以 时，时，故，故 ；当；当 时，时，亦即亦即 对分法的原理如图对分法的原理如图 对分法对分法二、对分法迭代步骤二、对分法迭代步骤二、对分法迭代步骤二、对分法迭代步骤已知已知 ，表达式，终止限表达式，终止限 (1)确定初始搜索区间确定初始搜索区间 ，要求，要求(2)计算计算 的中点的中点 (3)若若 ，则，则 ，转，转(4)(4)；若若 ，则，则 ，转，转(5)(5)；若若 ，则，则 ，转，转(4)(4)(4)若若 ，则，则 ，转，转(5)(5)；否则转；否则转(2)(2)(5)打印打印 ，停机，停机对分法对分法Y开始确定ab,要求c=(a+b)/2b=ct*=(a+b)/2输出t*结束T*=cNa=cNYNY对分法的计算流程如图所示三、对分法有关说明三、对分法有关说明三、对分法有关说明三、对分法有关说明 对分法每次迭代都取区间的中点对分法每次迭代都取区间的中点 a.若若这这点点的的导导数数值值小小于于零零，说说明明的的根根位位于于右右半半区区间间中中，因因此去掉左半区间；此去掉左半区间；b.若中点导数值大于零，则去掉右半区间；若中点导数值大于零，则去掉右半区间；c.若中点导数值正好等于零，则该点就是极小点若中点导数值正好等于零，则该点就是极小点 因因为为每每次次迭迭代代都都使使原原区区间间缩缩短短一一半半，所所以以称称为为对对分分法法或或二分法二分法对分法对分法Newton切线法一、一、一、一、NewtonNewton切线法基本原理切线法基本原理切线法基本原理切线法基本原理 设设 在在已已获获得得的的搜搜索索区区间间 内内具具有有连连续续二二阶阶导数，求导数，求 因因为为 在在 上上可可微微，故故 在在 上上有有最最小小值值，令令 下面不妨设在区间下面不妨设在区间 中经过中经过 次迭代已求得方程次迭代已求得方程 的的一一个个近近似似根根 。过过 作作曲曲线线 的的切线切线,其方程是其方程是然然后后用用这这条条切切线线与与横横轴轴交交点点的的横横坐坐标标 作作为为根根的的新新的的近近似似（如如图图）它它可可由由方方程程（4.4）在在令令 的的解解出出来来，即即 这就是这就是Newton切线法迭代公式切线法迭代公式 NewtonNewton切线法切线法二、二、二、二、NewtonNewton切线法迭代步骤切线法迭代步骤切线法迭代步骤切线法迭代步骤已知已知 ，表达式，终止限表达式，终止限 (1)确定初始搜索区间确定初始搜索区间 ，要求，要求(2)选定选定 (3)计算计算 (4)若若 ，则，则 ，转（，转（3）；否则转（）；否则转（5）(5)打印打印 ，停机，停机NewtonNewton切线法切线法Newton切线法的计算流程如图所示 三、三、三、三、NewtonNewton切线法有关说明切线法有关说明切线法有关说明切线法有关说明这这种种方方法法一一旦旦用用好好，收收敛敛速速度度是是很很高高的的如如果果初初始始点点选选得得适适当当，通通常常经经过过几几次次迭迭代代就就可可以以得得到到满满足足一一般般精精度度要要求的结果求的结果.但是它也有缺点：但是它也有缺点：第第一一，需需要要求求二二阶阶导导数数如如果果在在多多维维最最优优化化问问题题的的一一维维搜搜索索中中使使用用这这种种方方法法，就就要要涉涉及及Hesse矩矩阵阵，一一般般是是难难于求出的于求出的NewtonNewton切线法切线法第二，当曲线 在 上有较复杂的弯曲时，这种方法也往往失效如图(a)所示的迭代：结果 跳出 .迭代或者发散，或者找到的根并不是我们想要的结果第三，即使曲线比较正常，在 中或者上凹或者下凹，初始点的选取也必须适当在图（b）的情况下，曲线上凹，应选点b作为初始点；而在图（c）的情况下，曲线下凹，应选点a为初始点否则都可能失败NewtonNewton切线法切线法黄金分割法一、黄金分割法基本原理一、黄金分割法基本原理一、黄金分割法基本原理一、黄金分割法基本原理 要要介介绍绍黄黄金金分分割割法法有有必必要要回回顾顾一一下下古古老老的的黄黄金金分分割割问问题题。所所谓谓黄黄金金分分割割就就是是将将一一线线段段分分为为二二段段的的方方法法。这这样样分分后后，要要求求整整段段长长L与与较较长长段段x的的比比值值正正好等于较长段好等于较长段x与较短段与较短段 的比值的比值(如图如图)于是于是则则解得解得由由此此可可见见长长段段的的长长度度应应为为全全长长的的0.618倍