最优化方法及控制应用1课件

最优化方法及控制应用主讲人：董密信息科学与工程学院参考书：1.实用最优化方法R.Fleter著，游兆永等译天津科技翻译出版公司2.非线性规划数值方法袁亚湘上海科学技术出版社19953.非线性最优方法席少霖高等教育出版社4.工程优化的算法分析张可村西安交大出版社19895.最优化方法解文新，韩立兴等天津大学出版社20016.最优化方法施光燕，董加礼高等教育出版社2001最优化方法及控制应用最优化：在多种（有限种或无限种）决策中挑选最好决策的问题。最优化方法：（也称做运筹学方法）是近几十年形成的，主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优方案：是达到最优目标的方案。最优化理论：就是最优化方法的理论。发展简史公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618，称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。最优化方法真正形成为科学方法则在17世纪以后。工作步骤①提出最优化问题，收集有关数据和资料；②建立最优化问题的数学模型,确定变量,列出目标函数和约束条件；③分析模型，选择合适的最优化方法；④求解，一般通过编制程序，用计算机求最优解；⑤最优解的检验和实施。模型的基本要素最优化模型包括：变量、约束条件和目标函数①变量：指最优化问题中待确定的某些量。变量可用x＝(x1，x2,…,xn)T表示。②约束条件:指在求最优解时对变量的某些限制,包括技术上的约束、资源上的约束和时间上的约束等。约束条件可用gi(x)≤0表示i＝1,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)为目标函数，省略号表示约束式子，可以是等式约束，也可以是不等式约束。

根据目标函数，约束条件的特点将最优化方法包含的主要内容大致如下划分：线性规划整数规划非线性规划动态规划多目标规划对策论最优化方法主要内容解：该工厂生产产品Ix1件，生产产品IIx2件，我们可建立如下数学模型：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．假设豆腐售价无波动。综上分析，得到该问题的线性规划模型s.t.用Matlab编程求解程序如下：[X,FVAL,EXITFLAG,OUTPUT]=LINPROG(f,A,b)f=-[105];A=[0.30.4;0.50.2];B=[9;8];[X,FVAL,EXITFLAG,OUTPUT]=LINPROG(f,A,b)X=10.000015.0000FVAL=-175.0000用YALMIP编程求解程序如下：x=sdpvar(1,2);C=[105];a=[0.30.4;0.50.2];b=[98];f=C*x';F=set(0<=x<=inf);F=F+set(a*x'<=b');solvesdp(F,-f)double(f)double(x)

ans=175ans=1015线性规划

设某工厂有甲、乙、丙、丁四个车间，生产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，则这样的规划问题称为0－1规划。例1某钢厂两个炼钢炉同时各用一种方法炼钢。第一种炼法每炉用a小时，第二种用b小时（包括清炉时间）。假定这两种炼法，每炉出钢都是k公斤，而炼1公斤钢的平均燃料费第一法为m元，第二法为n元。若要求在c小时内炼钢公斤数不少于d，试列出燃料费最省的两种方法的分配方案的数学模型。设用第一种炼法炼钢x1炉，第二种炼钢x2炉s.t.引例2.资源分配问题：某个中型的百货商场要求售货人员每周工作5天，连续休息2天，工资200元/周，已知对售货人员的需求经过统计分析如下表，问如何安排可使配备销售人员的总费用最少？星期一二三四五六日所需售货员人数18151216191412开始休息的人数x1x2x3x4x5x6x7

设决策变量如上，可建立如下模型：非线性规划非线性规划问题的一般数学模型：其中，，为目标函数，为约束函数，这些函数中至少有一个是非线性函数。应用实例：供应与选址

某公司有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次迭代计算的步长因子．(1.2)

按照式（1.2）进行一系列迭代计算所根据的思想是所谓的“爬山法”，就是将寻求函数小点（无约束或约束极小点）的过程比喻为向“山”的顶峰攀登的过程，始终保持向“高”的方向前进，直至达到“山顶”。当然“山顶”可以理目标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法。这两种算法都有一个共同的特点，就是每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息。如果是下降算法，则序列迭代点的目标函数值必须满足下列关系如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即下图为迭代过程（二）收敛速度与计算终止准则（1）收敛速度作为一个算法A，能够收敛于问题的最优解当然是必要的，但光能收敛还不够，还必须能以较快的速度收敛，这才是好的算法．定义1.1设由算法A产生的迭代点列在某种“||·||”的意义下收敛于点，即,若存在实数及一个与迭代次数无关的常数使得则算法A产生的迭代点列叫做具有阶收敛速度，或算法A叫做是阶收敛的，特别地：①当，迭代点列称为具有线性收敛速度或算法A称为线性收敛的．②当，或时，迭代点列叫做具有超线性收敛速度或称算法A是超线性收敛．③当时，迭代点列叫做具有二阶收敛速度或算法A是二阶收敛的．一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法．(2)计算终止准则用迭代方法寻优时，其迭代过程总不能无限制地进行下去，那么什么时候截断这种迭代呢？这就是迭代什么时候终止的问题。从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代．但是这在实际上是办不到的．因为对于一个待求的优化问题，其理论极小点在哪里并不知道．所知道的只是通过迭代计算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代。对于无约束优化问题通常采用的迭代终止准则有以下几种：①点距准则相邻两迭代点之间的距离已达到充分小，即式中是一个充分小正数，代表计算精度．②函数下降量准则相邻两迭代点的函数值下降量已达到充分小．当时，可用函数绝对下降量准则当时，可用函数相对下降量准则③梯度准则目标函数在迭代点的梯度已达到充分小，即这一准则对于定义域上的凸函数是完全正确的．若是非凸函数，有可能导致误把驻点作为最优点。对于约束优化问题，不同的优化方法有各自的终止准则．综上所述，优化算法的基本迭代过程如下：①选定初始点，置．②按照某种规则确定搜索方向．③按某种规则确定使得④计算⑤判定是否满足终止准则．若满足，则打印和,停机；否则置,转②．NYX是否满足终止准则输出X，f(X)开始结束选定X0确定P确定t，使得f(X0+tP)<f(X0)X=X0+tPX0=X上述算法框图如右图一维搜索法§搜索区间及其确定方法§

对分法§Newton切线法§

黄金分割法§抛物线插值法

由前面关于求解最优化问题概述中我们知道，从已知迭代点出发按照基本迭代格式来求解最优化问题，其关键在于如何构造一个搜索方向和确定一个步长使下一迭代点处的目标函数值下降，即。现在我们来讨论，当搜索方向已经确定的情况下，如何来确定步长？步长因子的选取有多种方法，如取步长为常数，但这样选取的步长并不最好，如何选取最好步长呢？实际计算通常采用一维搜索来确定最优步长。一维搜索法

对无约束最优化问题当已知迭代点和下降方向时，要确定适当的步长使

比有所下降，即相当于对于参量的函数要在区间上选取使即．由于这种从已知点出发，沿某一下降的探索方向来确定步长的问题，实质上是单变量函数关于变量的一维搜索选取问题，故通常叫做一维搜索．

一维搜索法按这种方法确定的步长又称为最优步长，这种方法的优点是：它使目标函数值在搜索方向上下降得最多．今后为了简便起见，我们用记号

表示从点

出发沿方向对目标函数作直线搜索所得到的极小点是

其中l和s分别是Linearsearch(直线搜索)两词的词首,在目标函数已确定的条件下(4.1)等价于如下两式：一维搜索法下面进一步解释迭代点的空间位置。容易证明，若从出发，沿方向进步一维搜索得极小点

则该点处的梯度方向与搜索方向之间应满足事实上，设对求导有令即所以一维搜索法式（4.2）的几何意义是明显的:从某一点出发沿方向对目

标函数作直线搜索,所得到

的极小点为式（4.2）指出，

梯度必与搜索方向正交.又因为与目标函数过点的等值面正交，所以进一步看到，搜索方向与这个等值面在点处相切（如图所示）．

一维搜索法搜索区间及其确定方法

一、搜索区间

设一维最优化问题为为了求解问题(4.3),我们引入如下的搜索区间概念．定义4.1若存在闭区间使则称是问题(4.3)的搜索区间．简言之，一个一维最优化问题的搜索区间，就是包含该问题最优解的一个闭区间．通常，在进行一维搜索时，一般要先确定出问题的一个搜索区间，然后再此区间中进行搜索求解．

二、加步探索法下面，介绍一个确定问题(4.3)的搜索区间的简单方法．这个方法的思想是：先选定一个初始点或和初始步长然后，沿着轴的正方向探索前进一个步长，得到新点若目标函数在新点处的值是下降了，即

则下一步就从新点出发加大步长，再向前探索。若目标函数在新点处的值上升，即则下一步仍以为出发点以原步长开始向轴的负方向同样探索。当达到目标函数上升的点时，就停止探索，这时便得到问题（4.3）的一个搜索区间．这种以加大步长进行探索来寻找探索区间的方法叫加步探索法。

搜索区间及其确定方法

加步探索法算法的计算步骤：(1)

选取初始数据．选取初始点计算给出初始步长加步系数令(2)

比较目标函数值．令计算，

若转(3)。否则转(4)。(3)加大探索步长,令同时令转(2)．(4)反向探索,若转换探索方向,令转(2);否则,停止迭代,令输出搜索区间及其确定方法

加步探索法算法的流程图如图所示

开始选取初始点t0，初始步长h0>0，加步系数α>1，令k=0φ0=φ(t0)，比较目标函数值tk+1=tk+hk,φk+1=φ(tk+1)a=min{t，tk+1}b=max{t，tk+1}结束NYNYφk+1<φkhk+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说明，经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间．换句话说利用这个定理可以把搜索区间无限缩小，从而求到极小点.以下介绍的几种一维搜索方法都是利用这个定理通过不断地缩短搜索区间的长度，来求得一维最优化问题的近似最优解．搜索区间及其确定方法一、对分法基本原理求解一维最优化问题一般可先确定它的一个有限搜索区间，把问题化为求解问题，然后通过不断缩短区间的长度，最后求得最优解．对分法设在已获得的搜索区间内具有连续的一阶导数．因为在上可微，故在上连续，由此知在上有最小值．令，总可求得极小点．不妨设在上是单减函数；在上是单增函数。所以时，，故；当时，亦即．对分法的原理如图．

对分法二、对分法迭代步骤已知，表达式，终止限．确定初始搜索区间，要求(2)计算的中点．(3)若，则，转(4)；

若，则，转(5)；

若，则，转(4)．(4)若，则，转(5)；否则转(2)．(5)打印，停机．对分法Y开始确定[ab],要求c=(a+b)/2b=ct*=(a+b)/2输出t*结束T*=cNa=cNYNY对分法的计算流程如图所示三、对分法有关说明对分法每次迭代都取区间的中点a.若这点的导数值小于零，说明的根位于右半区间中，因此去掉左半区间；b.若中点导数值大于零，则去掉右半区间；c.若中点导数值正好等于零，则该点就是极小点．因为每次迭代都使原区间缩短一半，所以称为对分法或二分法．对分法Newton切线法一、Newton切线法基本原理设在已获得的搜索区间内具有连续二阶导数，求．因为在上可微，故在上有最小值，令．下面不妨设在区间中经过次迭代已求得方程

的一个近似根。过作曲线的切线,其方程是

然后用这条切线与横轴交点的横坐标作为根的新的近似（如图）．它可由方程（4.4）在令的解出来，即这就是Newton切线法迭代公式．

Newton切线法二、Newton切线法迭代步骤已知，表达式，终止限．确定初始搜索区间，要求

选定．计算．若，则，转（3）；否则转（5）．打印，停机．Newton切线法Newton切线法的计算流程如图所示

三、Newton切线法有关说明这种方法一旦用好，收敛速度是很高的．如果初始点选得适当，通常经过几次迭代就可以得到满足一般精度要求的结果.但是它也有缺点：第一，需要求二阶导数．如果在多维最优化问题的一维搜索中使用这种方法，就要涉及Hesse矩阵，一般是难于求出的．Newton切线法第二，当曲线在上有较复杂的弯曲时，这种方法也往往失效．如图(a)所示的迭代：结果跳出.迭代或者发散，或者找到的根并不是我们想要的结果．第三，即使曲线比较正常，在中或者上凹或者下凹，初始点的选取也必须适当．在图（b）的情况下，曲线上凹，应选点b作为初始点；而在图（c）的情况下，曲线下凹，应选点a为初始点．否则都可能失败．Newton切线法黄金分割法一、黄金分割法基本原理要介绍黄金分割法有必要回顾一下古老的黄金分割问题。所谓黄金分割就是将一线段分为二段的方法。这样分后，要求整段长L与较长段x的比值正好等于较长段x与较短段的比值(如图)于是则解得由此可见长段的长度应为全长的0.618倍，而短段的长度应为全长的0.382倍．因为古代的人们认为按0.618的比率来分割线段是最协调，胜似黄金，故称之为黄金分割．黄金分割法用黄金分割法进行一维搜索，其基本思想是在单谷区间内适当插入两点，由此把区间分为三段，然后再通过比较这两点函数值大小，就可以确定是删去最左段还是最右段，或者同时删去左右两段保留中间段．如此继续下去可将单谷区间无限缩小．黄金分割法二、黄金分割法迭代步骤现在提出一个问题，就在上如何选取二点使得迭代次数最小而区间缩短最快？要解决这个问题，人们想到对区间选二点等价于将区间长度进行黄金分割，也就是将第一个搜索点取在的0.618处，第二个搜索点取成的对称点即的0.382处（如图所示）

黄金分割法即要求接着计算与的值，并根据与的值的大小关系分情况讨论：（1）若,说明是好点，于是把区间划掉，保留，则内有一保留点，置新的区间；（2）若，说明是好点，于是应将划掉，保留,则内有保留点,置新的区间．.黄金分割法(3)若则应具体分析,看极小点可能在哪一边再决定取舍，在一般情况下，可同时划掉和

仅保留中间的重置新的区间．接下来是在留下的区间内找好点．重复上面的步骤，直到搜索区间小于给定的允许误差为止。这样就得到黄金分割法迭代算法：黄金分割法已知，常数0.382，终止限．(1)确定的初始搜索区间．(2)计算．(3)计算．(4)

若,则打印，停机；否则，转(5)．(5)

判别是否满足：若满足，则置，然后转(3)；否则，置

然后转(4)．

黄金分割法黄金分割法算法流程如图所示．

三、黄金分割法有关说明黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点．该方法适用于单谷区间上的任何函数，甚至可以是不连续函数，因此这种算法属于直接法，适用相当广泛．

黄金分割法

抛物线插值法一、抛物线插值法基本原理考虑一维搜索问题假设其中是定义在区间上的单峰函数．首先用试探法在上找一点，使之满足．

通过目标函数曲线上的三个点