最优化理论与方法

最优化理论与方法课件制作：北方民族大学高岳林任子晖目录第一章概论第二章线性规划第三章无约束非线性规划第四章约束非线性规划第五章多目标规划第六章整数规划第七章动态规划第一章概论

模型举例最优化问题的模型与分类第二章线性规划

凸集与凸函数线性规划的几何特征线性规划的标准型线性规划的基本定理单纯型法大M法第三章无约束非线性规划

最优性条件一维搜索最速下降法与共轭梯度法牛顿法与拟牛顿法第四章约束优化方法

最优性条件二次规划可行方向法惩罚函数法复型法第五章多目标规划

模型举例向量集的优化问题有效解和弱有效解评价函数法第六章整数规划

整数规划问题的基本概念线性整数规划问题的分枝定界法

0—1的隐枚举法第七节动态规划

动态规划的基本概念动态规划的最优性与基本方程第一章概论

随着生产、经济、技术的发展，工程技术、管理人员在实际工作中，肯定会面临这样的一类问题:工程设计中怎样选择参数，使得设计既满足要求，又能降低成本；资源分配中，怎样的分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产计划安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例才能提高质量、降低成本；城建规划中，怎样安排工厂、机关、学校、商店、医院、住宅和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排农作物的合理布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争的全局；在人类活动的各个领域，诸如此类问题，不胜枚举。这一类问题的共同特点，就是要在所有可能的方案中，选出最合理的，达到事先规定的最优目标的方案，这个方案可称为最优方案，寻求最优方案的方法称为最优化方法，它是一门应用广泛、实用性强的学科。定义1:寻找最优方案的方法称为最优化方法。所谓的最优方案就是要在所有可能的方案中，选出最合理的，达到事先规定的最优目标的方案，最优化结合管理，经济等一些领域，而最根本的要以我们的数学知识为基础，现已被广泛地应用于工程，国防，管理和经济等许多重要的领域。1.1模型举例

当我们要量化一个问题时,首先需要将此问题转化为一个数学问题,即建立数学模型。抓住其主要因素,理清其相互的联系,然后综合地运用有关学科的知识和数学知识才能完成。下面举几个例子。例1:配棉问题所谓的配棉问题就是要根据棉纱的质量指标，采用各种价格不同的棉花，按一定的比例配制成纱，使其即达到质量指标又使总成本最低。棉纱的质量指标一般有棉结和品质指标来决定，这两项指标都可以用数量形式来表示，一般来说，棉结粒越少越好，品质指标越大越好。个年纺能力为15000锭的小厂在采用最优化方法配棉时，某一产品32D纯棉纱的棉花配比质量指标及单价如下:原料品名单价（元/t）混合比（%）

棉结

（粒）

品质指标

混棉单价

（元/t）国棉131

8400

25

60

3800

2100国棉229

7500

35

65

3500

2625国棉327

6700

40

80

2500

2680平均合计

100

70

3175

7405有关部门对32D纯棉纱规定的质量指标为棉结不多于70粒，品质指标不小于2900。下面我们建立数学模型:首先:根据问题需要设置变量:设分别为国棉131,229,327的棉花配比，然后用所设置的变量把所追求的目标及所受的约束，用数学语言表达出来，即得到该问题的数学模型。本例的目标是混棉单价最小，用即可表示为:

本例关于32D纯棉纱的质量指标作为约束条件表出，即有:

又因为的实际意义，它们应为百分数且和为100%，故又有:

故32D纯棉纱配棉问题的数学模型为:

例2:资金使用问题设有400万元资金，要求4年内使用完，若在一年内使用资金万元，则可得到效益万元，（效率不能再次使用），当年使用的资金可存入银行，年利率为10%，试制定出资金的使用计划，以使4年资金效益之和最大。很明显，不同的使用方案，所取得的效益之和是不同的，如第一年就把400万元全部用完，则效益总和为20万元，若前三年均不使用而存入银行，则第四年把本息和400=532.4万元全部用完，则效益总和为万元，比第一种方案效益大3万多元。第一年

第二年

第三年

第四年现有资金

400

345.2

265.1

152.8

使用资金

86.2

104.2126.2

152.8效益总和为万元，使第一种效益总和的两倍多。注:此例反映出进行定量的优化计算作用，故一些工业人士称最优化方法是不需要增加投入而增加产出的手段。为了将上述的问题转化为最优化问题，先建立数学模型，设变量分别表示第年所使用的资金数，于是所追求的目标----4年的效益总和最大，即可表示为:

所受的约束为每年的使用金额既不能为负数又不能超过当年资金拥有数，即:第一年:第二年:第三年:第四年:故资金使用问题的数学模型为:例3:汽轮机排序问题环形排序问题:由于考虑其共振的因素，一百多个叶片的质量及几何形状各不相同。转动时产生的惯性离心力也就存在差异，如何确定它们的安转位置（排列顺序），使诸离心力的合力最小。设有个叶片，第个叶片在转动时产生的惯性离心的数值（模）为，转子的一周被分为等份，安装位置用辐角表示，如将第个叶片安装在位置上，它产生的离心力（向量）可用复数表示:设叶片的排序方案用排列来表示，即叶片排在第位，那么合力就是:问题就是求排列使为最小。于是，设变量为，其意义为:这样合力可表示为:而

于是问题的目标可以表示为:，而约束条件为每片叶子只能安装在一个位置上，即:而且每个位置上只能安装一片叶子，即:故汽轮机叶片排序问题的数学模型为:例4:投资的收益与风险市场上有种资产(如股票，债券等)共投资者选择，某公司有一笔数额为的资产作为一个时期的投资，公司财务人员对几种资产进行了评估，估算出在这一时期内购买的平均收益率为，并预测购买的风险损失率为,考虑到投资越分散，总的风险越小，公司决定，当用这笔资金购买若干种资产时，总体风险可用所投资的中最大的一个风险来度量。购买要付交易费，费率为，并且当购买不超过给定值时，交易费按购买计算（不买无需付费），另外，假定同期存款利率且既无交易费又无风险。已知时的相关数据如下:

（%）

（%）

（%）(元)

28

2.5

1

103

21

1.5

2

198

23

5.5

4.5

52

25

2.6

6.5

40试给该公司设计一种投资组合方案,即用给定的资金,有选择地购买若干种资产或银行生息,使净收益尽可能的大,总风险尽可能的小。设变量分别表示存入银行和购买的金额，表示不购买，表示购买，目标有两个:第一个目标:第二个目标:约束是总资金为，以及之间的关系。故投资的收益和风险的数学模型为:1.2最优化问题的模型与分类数学规划定义:在一些等式或不等式约束条件下，求一个目标函数的极大或极小的优化模型称为数学规划。数学规划分为:约束数学规划和无约束数学规划。约束数学规划一般形式为:(P)其中称为优化向量或决策变量；称为目标函数；约束函数分别称为不等式约束和等式约束，等式约束和不等式约束统称为约束条件。令:,我们称D为（P）的约束集合（约束区域）或可行域。若，则称为可行点或可行解，设若对任意的，都有，则称为优化问题（P）的全局最优解（极小点或极大点）若存在的一个的领域:当时，有，称为优化问题（P）的局部最优解，如时，有，称为优化问题（P）的严格局部最优解。问题的分类1.无约束优化问题当时，问题(P)称为无约束优化问题，无约束优化问题是指在空间上寻求使目标函数达到极小或最小的点（解）。2.约束优化问题若指标集I与E中至少有一个非空，则称(P)为约束优化问题，约束优化问题是在约束集D上寻求使目标函数达到极小或最小的点（解）。若,即问题(P)只含有等式约束,此时称问题(P)为等式约束优化问题；若,即问题(P)只含不等式约束,此时称问题(P)问不等式约束优化问题；否则称问题(P)为混合优化问题。如果目标函数目标函数和约束函数都是线性,则称问题为线性规划,线性规划常记为LP；如果目标函数和约束函数中至少有一个是非线性函数,则称问题为非线性规划,常记为NP；在非线性规划中,若约束函数均是线性函数,则称问题为线性约束非线性规划问题,常记为NLP；目标函数为二次函数的线性约束问题称为二次规划问题,常记为QP。若变量限制取整数,则称为整数规划；若变量限制取0或1,则称为0—1规划；若变量既可取整数,又可取小数,则成为混合整数规划。若所研究的问题只含一个目标,则称为单目标规划；若所研究的问题需要同时考虑多个目标,则成为多目标规划。组合优化组合优化为一个又有有限个元素组成的集合和定义在E的某些子集组成的集合上的实值函数。若E只有有限个元素,E的所有子集也只有有限个,故组合优化问题的解必然存在,而且一定可以用原始的方法----逐个列举法得到。图论，网络流定义：所谓的图是由一组点和一组点与点之间的连线（边）组成的总体组成的，图论所研究的问题主要分为两类：在给定的图中具有某种性质的点和边是否存在，若存在，有多少？或至多（少）有多少？如何构造具有某些给定性质的图或子图？网络：各边赋有权值的图：分为有向网络和无向网络。网络流：路，流动态规划定义:动态规划方法将一个最优化问题视为符合最优性原理，无后效性的多阶段决策过程，并进行求解的方法。注:最优决策的任何截断仍是最优的。特点:将一个复杂的问题转化为若干个较为简单的问题。第二章线性规划2.1凸集与凸函数1.凸集及基本性质Def:设集合,若,有，则称集合为凸集。由定义可直接验证:设为凸集，，则

①是凸集。②是凸集。③是凸集。④是凸集。

[0,1],利用数学归纳法可证:设D是凸集，则任意和数，都有[0,1],其中,2.凸函数的定义及其基本性质①Def:设f:,且D为非空凸集,若都有:(*)若

则称f(x)是定义在凸集D上的凸函数。在式(*)中,若严格不等式成立时,则称f(x)是凸集D上的严格凸函数。我们就不强调凸集D,而称f(x)是凸函数或严格凸函数。凸函数的几何意义:以n＝1来说明，当f(x)是凸函数时，其图形f(x)上任意两点之间的弧必在连接这两点的弦的下方。

注:由定义1.5，我们不难用归纳法证明:若f(x)是凸集D上的凸函数，则任意和数，，有

定义:设D为凸集，,若D中不存在两个相异的点y，z及某一实数使得,则称x为D的极点。注:线性函数既是凸函数也是凹函数。证明:设

②凸函数的性质:i)设f(x)是凸集上的凸函数，实数，则kf(x)也是D上的凸函数。

ii)设是凸集上的凸函数，实数则也是D上的凸函数。iii）设f(x)是凸集上的凸函数,为实数,则水平集是凸集。iv)f(x)是凸集上的凹函数的充分必要条件是(-f(x))是凸集上的凸函数。证明:iii)设,于是且因为D是凸集，所以又因为f(x)是D上的凸函数,所以有

即因此，是凸集。3．凸函数的判别条件

定理:设f(x)定义在凸集上，令则:i)f(x)是凸集D上的凸函数的充分必要条件为对任意单元函数在[0,1]上为凸函数。ii)设，若在[0,1]上为严格凸函数，则f(x)在D上为严格凸函数。证明:i)必要性:设f(x)在凸集D上为凸函数，

于是

故为[0,1]上的凸函数。充分性:设为[0,1]上的凸函数，对任意的则有

故f(x)是D上的凸函数。定理:(一阶条件)设在凸集上可微，则f(x)在D上为凸函数的充分必要条件是对任意的，都有

证明:必要性:设f(x)是D上的凸函数，任取及有

即由Taylor公式有

代入上式得

上式两端取极限，令有充分性:设，则令,有

用分别乘上面两式再相加得

即

故f(x)在D上为凸函数。定理:设在凸集上f(x)可微，则f(x)为D上严格凸函数的充要条件为对,有定理:（二阶条件）设在开凸集内f(x)二阶可微，则i)f(x)是D内凸函数的充分必要条件为在D内任一点x处，f(x)的海色(Hesse)矩阵G(x)半正定，其中

ii)若在D内G(x)正定，则f(x)在D内为严格凸函数。2.2线性规划解的几何特征例:下面考察仅含两个决策变量的线性规划:

我们在的坐标平面上画出其可行域:为此，我们只需画出K的边界:

观察目标函数，对于任一给定的实数z，方程表示一直线(称为f的等值线)，变动z即得一族互相平行的直线，把f的等值线向z减小的方向移动，其和凸多边形K的最后一个交点即为(2.1)的最优解。而为K的一个顶点。结论:若两个变量的线性规划有最优解，则必能在可行域凸多边形的顶点中找到。由此:具有三个变量及一般具有几个变量的情形，线性规划的可行域K则是以一个平面(或超平面)为边界的凸的多面体，而且目标函数等于常数的几何图形亦为平面(或超平面)即f的等值面，让等值面往函数减小方向平行移动，其和凸多面体的最后一个交点之一比为凸多面体的顶点。线性规划关于解的情形:①可行域是空集②有唯一最优解（紧集上的连续函数）

③有无穷多最优解（当f(x)分段且周期）④目标函数无界而无最优解2.3线性规划的标准型线性规划的标准型:对目标函数求极小，决策变量一律为非负变量，约束条件除变量的非负条件外，一律为等式约束。各种形式的线性规划模型一律为等式约束。①若目标函数为则可令f=-z,此问题转化为求②若约束条件含则引进有

称为松弛变量③若约束条件含,则引进新变量,有

称为剩余变量。④若约束条件含则引进,于是

⑤若变量的符号不受限制,则可引进两个新变量,并以代入目标函数及约束中消去,

而在约束条件中增加例2.1把线性规划化为标准型.分析:①令，将maxz改为求minf②用代替，其中③对不等式约束分别引进松弛变量和剩余变量

于是，原问题化为标准型:

2.4线性规划的基本定理

观察线性规划(2.1)及其相应的标准型(2.1)的可行域K共有四个顶点，这四个顶点在标准型的形式下所对应的变量值分别

可以发现这四个顶点的共同点为所对应的变量值中均有两个坐标为0。作为平面上凸多边形的顶点必然为两条边界直线之交点。若边界直线为坐标轴，则相应的一个坐标为0。若非坐标轴，则化标准型时所引进的松弛变量或剩余变量就应为0。故在仅有两个决策变量的线性规划标准型的形式下，顶点所对应的变量(包括决策变量，松弛变量，剩余变量)值为0的个数不少于两个。线性规划的标准型用矩阵表示为:其中不妨设矩阵A的秩r(A)=m.这样，线性规划(2.3)的可行解等价于线性方程组Ax＝B的非负解。因线性方程组Ax＝B有n个变量和r(A)=m，故当Ax＝B的一个解中非零分量所对应A中的列为线性无关时，则非零分量的个数就不会超过r(A)(=m).也即零分量的个数不少于n-m.称A中对应于非零分量的列是线性无关的Ax=B的解为线性规划(2.3)的基本解，称非负的基本解为基本可行解。线性规划的基本定理:定理:对于线性规划(2.3)①若有可行解，则一定有基本可行解。②若有最优解，则一定有最优基本可行解。

2.5单纯形法由基本定理，求解线性规划可采用如下步骤:①求得一个基本可行解②检查该基本可行解是否为最优解③若不是，设法再求一个没有检查过的基本可行解。

如此继续，直至检查出的基本可行解为最优解为止。按照上面的思路，线性规划的求解只需解决:①如何求出第一个基本可行解②如何判断基本可行解为最优解③如何由一个基本可行解过渡到另一个尚未检查过的基本可行解。Ax=B中，A为m行n列矩阵，即Ax=B为有n个未知数，m个方程的线性方程组，又设A的秩为m，故由它可解出m个变量(称为基本变量)，剩余的n－m个变量为自由取值的变量(称为自由变量)。而所谓基本解即解中取零的变量个数不少于n－m个。于是，我们可令自由变量取值为零相应得到的解即为基本解。例:

把约束方程写成表格形式：20－416(2.5)-11305从上述表格可以看出由第二、四列构成一个单位子块，因此将和解出，即和作为基本变量，余下的，作为自由变量，即令自由变量，则，即得一基本解,由此例可看出基本变量的取值即为(2.5)中右列的相应值。因此所得到的基本解是否为基本可行解，只需看当左边有单位子快时，右列的元素是否均为非负？若是(即非负)，则所得到的基本解即为基本可行解。从n个变量中解出不同基本变量的组数不会超过组合数

因此线性规划(2.3)的基本可行解(必为基本解)总数不会超过个。如何判断所得到的基本可行解是否为最优解呢？以(2.4)为例，我们把和(2.4)的约束方程等价的关系式(2.6)带入目标函数以消去基本变量，而只剩下自由变量，即其实，这个过程也可以在表格上进行，即在表格(2.5)的基础上加一底行，把目标函数的系数相应的写在底行中，即20-416-113051-3240右下角的0为目标函数的变号值，因表格中的竖线可理解为一个等号，于是将目标函数中的常数项移至等号的另一边而变号。为要在目标函数中消去变量，即把底行的系数变为零，可采取把底线以上的行倍加至底行的办法，如第一行乘(-4)，第二行乘3均加至底行即得:20-416-11305(2.8)-100270-9目前的底行即为式(2.7)，无非是把常数项9移至等号另一边变成(-9)，9即为相应基本可行解所对应的目标函数值。这样，我们把线性规划(2.4)化成与之等价的线性规划:

由于(2.9)的目标函数中仅含，而要求非负，所以也只需判断时是否在非负的范围内使目标函数取最小值，而这等价于(2.9)的目标函数中，的系数均为非负，如本例在表格(2.8)的形式下，由于底行中存在负系数(-10)，所以对应的基本可行解就不是最优解，也即若取正值，可使目标函数值减小。总结:当把线性规划(2.3)写成表格形式AB0表格的四个部分分别称为:中心部位右列底线底行右下端

求解线性规划(2.3)，既可以用如下的计算:①底线以上的部分进行行交换②底线以上的某一行乘以非零常数③底线以上的行进行倍加运算④把地线以上行乘常数后加至底行(包括右下端)上当表格具有如下特点:①中心部位具有单位子块②右列元素非负③底行相应于单位子块的位置的元素为0④底行其它元素非负则从表格中立即可以读出线性规划(2.3)的最优解和最优值。读法为:单位子块中1所对应的变量去相应右列的值，不在单位子块位置的变量取值为0，而右下端元素变号即为最优值。

例：10-21/230111/28007521从形式上看，当表已经具备了①②③三个特点，而第④个特点尚不具备时如何进行？单纯形法的步骤：前提：设当前的表格已具备第①②③三个特点。设一般为：

具体的如表(2.8)20-416-11305(2.8)-100270-9①从底行负元素中任意选一个，设为(实质上即为选该列所对应的变量取正值，因它取正值能使目标函数值下降，而变量要取正值必须作为基本变量，即必须将该列调至单位子块中)，这一步称为选择进基变量。②从所选元素对应列(列)底线以上的正元素中按下列规则选定一元素:

=(2.11)我们即要使作为基本变量，则必须在原来的基本变量中选定一个退出改作自由变量，至于从正元素中选，以及若不止一个正元素时，采用(2.11)式所示的原则选，这一步称为离基变量。10-21/230111/28007521③利用初等行变换及倍加至底行的运算把变为1，该列的其它元素(包括底行的相应元素)变为0，这一步称为旋转运算。④若底行元素均非负，则终止，否则回①。注:当最优解存在和基变量的值都大于零时，经有限步后一定能得到最优解。定理2.2:在已知一个基本可行解的前提下，使用单纯行法求解线性规划时，若每次迭代得出的基本可行解的基变量均大于零(称为非退化的)，则算法必有限步终止。例2.2:用单纯形法求解:

解:先化为标准型:

列成表格:-11100212010103100115-2-30000可见此表已具备①②③三个特点，可采用单纯形法。min{2/1,10/2,15/1}=2,选第一行第二列元素1，迭代依次得:-1110023^0-210640-10113-5*03006

-1/31100210-21064/30-101135/303006011/31/30410-2/31/302005/3^-4/31500-1/3*5/3016

0103/5-1/53100-1/52/54001-4/53/530007/51/517这时第④特点已具备，故终止。从表中读出最优解:

例:

解:20-416-11*3051-3*2402*0-416-11305-2*01141510-21/23-11305-2011415

10-21/230111/28007521

2.6大M法当初始基本可行解不知道时,即①②两个特点不能兼得时,先利用容许的运算使右列为非负,然后在中心部位人工地添加一个单位子块。

例:列成表格:32-36-12-1-4-3120

32-361-214-3120

32-31061-21014-3120上述第三张表格人工地增加了两个变量(称人工变量)，即把原约束条件修改为:2.13)和(2.12)的约束方程组并不同解，但(2.12)的解和(2.13)中的解是相对应的。因此只要找到以(2.13)为约束条件，且人工变量和均为自由变量的取值为零。现介绍的这个方法就是通过修改(2.12)的目标函数来实现这个目的。具体修改为:

其中，M为足够大的正数，然后以(2.13)为约束条件，求(2.14)的最小值，这样，只要不为0，则一定为正数，于是目标就会增加它们和的M倍，由于M足够大，所以只要原问题有基本可行解，就不会让，取正值而达到最小，于是本例的单纯形表应改为:3*2-31061-21014-3*12MM0再通过运算使第③个特点具备，然后再严格地按照单纯形法步骤执行:3*2-31061-21014-3-4M*12+2M0010M

由于M为足够大正数，所以-3-4M应视为负数，故选它，于是有12/3-11/3020-8/32-1/31203+8M/3-1-2M*1+4M/306-2M这时人工变量已经成为自由变量，所以可立即将其略去，即可将第四列删去:1-2/301/230-4/311/2105/301/2+M7这时表已具有四个特点且人工变量亦成为自由变量，故

如果表中已具备四个特点，而人工变量并没有全都成为自由变量，则此题无最优解。

第三章无约束非线性规划本章讨论如下的优化模型:

（3.1）其中是的实值连续函数,通常假定具有二阶连续偏导数.3.1最优性条件由于可以等价地化为,所以下面仅讨论极小化问题.无约束极小的最优性条件现有多元函数,若点存在一邻域,使得对于均有:则称为的局部极小点.

若为的局部极小点,显然可以得出以下结论:为一元函数的局部极小点.由一元函数极值的必要条件有:(3.2)

因此有以下定理成立:

定理3.1(局部极小点的一阶必要条件)设函数在点处可微,且为局部极小点,则必有梯度.

在一元函数的讨论中,一已知满足一阶必要条件的(称为驻点)未必是局部极小点,有可能是极大点或者鞍点.

利用局部极小点的一阶必要条件求函数极值的问题往往化成求解

即求,使满足:

(3.3)

的问题,这是含有个未知量,个方程的方程组,并且一般是非线性的.对于一些特殊的情形,如当目标函数是二次函数,因而此时方程组(3.3)是线性方程组时,有时可以解出,一般来说,非线性方程组的求解与无约束极值一样也是一个困难的问题,甚至前者比后者更困难,一般是很难用解析方法求解的.这时必须用数值计算方法逐步求出非线性方程组的解.但是,与其用数值计算方法求解(3.3),倒不如用数值计算方法直接求极值.

迭代法数值解法中最为常见的是用迭代法,其基本思想是:

在给出的极小点位置的一个初始估计(称为初始点)后,计算出一系列的迭代点,希望点列的极限就是的一个极小点.怎样产生这样的点列呢?也就是说,当有了迭代点后,怎样求得新的迭代点呢?我们知道和之差是一个向量,而一个向量总是有其方向和长度所能确定.即总可以写成

或

其中为一个向量,为一个实数(称为常数).当和确定之后，由就可以唯一地确定，于是依次下去，从给定的便可以求出，由确定等等，从而也就确定了一个点列，如果这个点列逼近我们要求的极小点，我们便称序列为极小化序列.所以对于每个迭代点，如果能设法给出和，则算法也就确定了.各种迭代法的区别就在于得出方向与步长的方式不同.特别是方向（我们称为搜索方向）的产生在方法中起着关键的作用.我们要求:一.所构造出来的极小化序列对应的函数值序列应该是逐次减小的,即

这种性质的算法称为下降算法.二.算法应该具有收敛性,即所产生的极小化序列具有这样的性质:或者序列中的某一点,它本身就是极小点;或者序列有一个极限点,它是函数的极小点.但是这个要求却是不容易做到的,例如:考虑函数,显然就是的极小点,即,我们按照下述的方式构造极小化序列:已知后,令容易证明,这个算法是一个下降算法,即

若取初始点,则所有,因此序列不可能收敛到极小点(事实上,收敛到1),但若取初始点,则极小化序列收敛到极小点0.

注:当目标函数具有不止一个极小点时,则求得的往往是一个局部极小点,这时可以改变初始点的取值,更新计算,如果求得的仍然是同一个极小点,我们就可以认为它是总体极小点了.

综上所述,最优化算法中的迭代方法大致由下述步骤组成:1选择初始点,要求越接近最优解越好,2寻找可行下降方向,3选取步长,4迭代:,5终止条件:

须方能推出

(*)

我们称为在处的下降方向.

设可行域为,若:

且满足()式,则称为在处的可行下降方向.

由出发沿方向求步长的过程叫一维搜索或线性搜索.

判断算法好坏:一看是否收敛,二看收敛速度增:

定义:设序列收敛于,而且

若,则称为线性收敛的,为收敛比;若,则称为超线性收敛.

定义:设序列收敛于,若对于某个实数有

,

则称序列为阶收敛的.

3.2一维搜索上节提到,在大多数无约束极值的算法中,为了确定最优解,一般用解析的方法是很难得到的,即精确解通常是计算不出来的,故我们常采用的是数值的方法来得到其近似解,上节我们提到,数值解法最常用的一种方法是迭代法.

为了确定极小化点列,要沿逐次确定的系列射线求极小点,即所谓的一维搜索.

一维搜索可归结为单变量函数求极小的问题,设目标函数为,过点沿方向的直线可用点集表示为:

求在直线L上的极小点转化为求一元函数

的极小点.如果的极小点为,通常称为沿方向的步长因子或简称步长.函数在直线上的极小点就是

一维搜索的方法一般有以下几类:1.数学分析中所讲的方法，即解方程，此方法称为精确线性搜索.2.试探法:按照某种方式试探点,通过一系列试探点的比较确定极小点.3.函数逼近法:用比较简单的曲线近似代替原来的曲线,用近似曲线的极小点来估计原来的极小点.下面我们将分别具体介绍几种方法:一.平分法根据以前我们所学习的知识,我们知道,在的极小点处有,并且当时,函数是递减的,即;,而当时,函数递增,即.注:因为为极小点,若:

此时为极大点.

我们找到了一个区间,具有性质则在间必然有的极小点,且.为了找到,我们取.1.若,则在中有极小点,

2.若,则在中有极小点.y=f(x)00xy若情形1满足时,此时以作为新的区间;若情形2满足时,此时以作为新的区间.继续上述过程,逐步将区间换小,当区间充分小时,或者当充分小时,即可将区间中点取做极小点的近似,此时有:0xy0xy注:也可以用以下的收敛准则:1.成立,

2.成立.但是我们如何来确定初始区间呢?一般可以采取下述的方式:1.首先取一初始点,若,则在的右方取一点.其中为事先给定的一个步长;否则,在其左方取.2.若,则令.3.若,则在其右方取(或者将扩大一倍,再取4.若,则令.5.若转步2.

如此继续下去,对于的情况,做类似的情况讨论.这一技巧不仅对平分法有用,对后面的方法也有用,例如,我们可以用类似的方法,找出,满足,并且,便可一得到含极小点的区间

此时需要用数值的比较而不需要计算.

二.0.618法(黄金分割法)

该方法的使用范围:单峰函数,即在所讨论的区间上函数只有一个极小点在极小点右边,函数单调上升,如:对于单峰函数,只需要选择两个试探点且.就可将极小点的区间缩短,事实上必有:(1)若,则

(2)若,则.0xy0xy0xy0xy0xy根据单峰函数的此性质,即可以不断地缩小包含极小点的区间(可称为搜索区间).若进行次迭代k以后,又有,此时取两个试探点,,并规定<,计算函数值.1.若,即满足(1)的情况,则令;2.若,即满足(2)的情况,则令.如此继续下去.但是我们怎么合理地选取,呢?1.因通过比较后,有可能去掉搜索中部分,也有可能去掉部分.因此,,取在中对称的位置是合理的.2.将缩短为后,,必有一个仍然属于.根据以上两点有:

(3.4)(3.5)由前:1.若,有

上两式推出此时有

2.若,有

上两式推出(3.6)

注:

i)设在第k次迭代中得出:

于是有=,则由(3.7)有:

令,则为留在中已经算出过函数值的试探点(令).

故有,算出

.

设在第k次迭代中得出:

于是有=,则有:

令,则根据前系数相等有:

所以有,

0.618法取试探点的规则为

计算步骤:1.给定一初始区间及精度要求,计算试探点:极其函数值,令;2.若,停止.中的任意点均可以作为所求极小点的近似,否则当时,转步3,当时,转步4;

3.置,,计算

及,转步5;4.置,,计算及,转步5;5.令,转步2.参见46页例3.1.注:在使用0.618法之前,务必确定目标函数为单峰函数.三.牛顿法(函数逼近):基本思想:在迭代点附近用二阶泰勒展开式近似目标,进而求极小点的估计值.

优化模型:

（3.12）首先我们令

再令得到（3.13）用迭代公式（3.13）可得到一个点列,在一定条件下,这个

点列收敛于（3.12）的最优解,且具有二阶收敛速度.xy

3.3最速下降法与共轭梯度法在本章开始介绍了关于无约束极小问题普遍使用下降迭代算法,每一类算法中包含两个关键步骤,得到一个迭代点后,如何选择搜索方向以及在确定搜索方向上用什么方法进行一维搜索?而有关一维搜索的方法在上节已经作了详细的介绍,本章与下一章就介绍几种常用的确定搜索方向的方法.一最速下降法考虑到函数在点处沿方向的方向导数,其意义为:函数在点处沿方向的变化率.求解问题:

其中最速下降法的计算步骤

1选定初始点和给定精度,令

2若,则停止,;

否则令=－▽.3在点处沿方向作线性搜索,得到