最优化方法复习.doc

第1章 最优化问题的基本概念
§1.1最优化的概念
最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率求得工程问题最优解决方案的过程。
§1.2最优化问题的数学模型
1.最优化问题的一般形式

2.最优化问题的向量表达式

式中：

3.优化模型的三要素
设计变量、约束条件、目标函数称为优化设计的三要素！
设计空间：由设计变量所确定的空间。设计空间中的每一个点都代表一个设计方案。
§1.3优化问题的分类
按照优化模型中三要素的不同表现形式，优化问题有多种分类方法：
1按照模型中是否存在约束条件，分为约束优化和无约束优化问题
2按照目标函数和约束条件的性质分为线性优化和非线性优化问题
3按照目标函数个数分为单目标优化和多目标优化问题
4按照设计变量的性质不同分为连续变量优化和离散变量优化问题

第2章 最优化问题的数学基础

§2.1 元函数的可微性与梯度
一、可微与梯度的定义
1.可微的定义
设是定义在维空间的子集上的元实值函数，且。若存在维向量，对于任意维向量，都有

则称在处可微。
2.梯度
设有函数，，在其定义域内连续可导。我们把在定义域内某点处的所有一阶偏导数构成的列向量，定义为在点处的梯度。记为：

梯度有3个性质：
⑴函数在某点的梯度方向为函数过该点的等值线的法线方向；
⑵函数值沿梯度方向增加最快，沿负梯度方向下降最快；
⑶梯度描述的只是函数某点邻域内的局部信息。
§2.2极小点及其判别条件
一、相关概念
1.极小点与最优解
设是定义在维空间的子集上的元实值函数，若存在及实数，使得都有，则称为的局部极小点；若，则称为的严格局部极小点。
若，都有，则称为的全局极小点，若，则称为的全局严格极小点。
对最优化问题而言
满足所有约束条件的向量称为上述最优化问题的一个可行解，全体可行解组成的集合称为可行解集。在可行解集中，满足：
的解称为优化问题的最优解。
2.凸集和凸函数
凸集：设，若对所有的，及，都有，则称为凸集。
凸函数：设，是凸集，如果对于所有的，及，都有，则称为上的凸函数。
二、局部极小点的判别条件
驻点：设是定义在维空间的子集上的元实值函数，是的内点，若，则称为的驻点。
局部极小点的判别：设是定义在维空间的子集上的元实值函数，具有连续的二阶偏导数。若是的驻点，且是正定矩阵，则是的严格局部极小点。
三、全局极小点的判别
1.凸规划
对于优化问题：
若、都是凸函数，则称该优化问题为凸规划。
2.全局极小点的判别
若优化问题为凸规划，则该优化问题的可行集为凸集，其任何局部最优解都是全局最优解。（能否证明）

第3章 无约束优化方法
§3.1下降迭代算法及终止准则
一、数值优化方法的基本思想
基本思想就是在设计空间内选定一个初始点，从该点出发，按照某一方向（该方向的确定原则是使函数值下降）前进一定的步长，得到一个使目标函数值有所下降的新设计点，然后以该点为新的初始点，重复上面过程，直至得到满足精度要求的最优点。
该思想可用下式表示：
二、迭代计算的终止准则
工程中常用的迭代终止准则有3种：
⑴点距准则
相邻两次迭代点之间的距离充分小时，迭代终止。
数学表达为：
⑵函数下降量准则（值差准则）
相邻两次迭代点的函数值之差充分小，迭代终止。
数学表达为：
⑶梯度准则
目标函数在迭代点处的梯度模充分小时，迭代终止。
数学表达为：
三、算法的收敛速度
对于某一确定的下降算法，其优劣如何评价？人们通常采用收敛速度来评价。
下面给出度量收敛速度的几个概念。
1.阶收敛
设序列收敛于解，若存在常数及、，使当时下式：

成立，则称为阶收敛。
2.线性收敛
设序列收敛于解，若存在常数、及，使当时下式：

成立，则称为线性收敛。
3.超线性收敛
设序列收敛于解，若任给都存在，使当时下式：

成立，则称为超线性收敛。
§3.2一维最优化方法
一、确定初始区间的进退法
任选一个初始点和初始步长，由此可确定两点和，通过比较这两点函数值、的大小，来决定第三点的位置。比较这三点函数值是否呈“高——低——高”排列特征，若是则找到了单峰区间，否则向前或后退继续寻求下一点。
进退法依据的基本公式：

具体步骤为：
⑴任意选取初始点和恰当的初始步长；
⑵令，取，计算、；
⑶若，说明极小点在右侧，应加大步长向前搜索。转⑷；
若，说明极小点在左侧，应以点为基准反向小步搜索。转⑹；
⑷大步向前搜索：令，取，计算；
⑸若，则、、呈“高——低——高”排列，说明即为所求的单峰区间；
若，说明极小点在右侧，应加大步长向前搜索。此时要注意做变换：舍弃原点，以原点为新的点，原点为新的点。转⑷，直至出现“高——低——高”排列，则单峰区间可得；
⑹反向小步搜索（要注意做变换）：为了保证点计算公式的一致性，做变换：将原点记为新点，原点记为新点，令，取，转⑸
例：用进退法确定函数的单峰区间[a，b]，设初始点，。
解：①
②
③
说明极小点在点右侧，应加大步长向前搜索
④令，取 则
⑤
说明极小点在点右侧，应加大步长向前搜索
舍弃原的点，令，则
令，取 则
、、呈“高——低——高”排列
为单峰区间，即区间[1，7]即为所求
二、黄金分割法
黄金分割法是基于区间消去思想的一维搜索方法，其搜索过程必须遵循以下的原则：
⑴对称取点的原则：即所插入的两点在区间内位置对称；
⑵插入点继承的原则：即插入的两点中有一个是上次缩减区间时的插入点；
⑶等比收缩的原则：即每一次区间消去后，单峰区间的收缩率保持不变。
设初始区间为[a，b]，则插入点的计算公式为：

黄金分割法的计算步骤如下：
①给定初始区间[a，b]和收敛精度；
②给出中间插值点并计算其函数值：

；
③比较、，确定保留区间得到新的单峰区间[a，b]；
④收敛性判别：计算区间[a，b]长度并与比较，若，输出
否则转⑤；
⑤在保留区间内继承一点、插入一点，转②。
例：使用黄金分割法求解优化问题：。
解：①
②
③∵ ∴舍弃（1.944，5]，保留[-3，1.944] ；
④继承原点，即
插入
∵ ∴舍弃（0.056，1.944]，保留[-3，0.056] ；
继承原点，即
插入
∵ ∴保留[-1.832，0.056] ；
继承原点，即
插入
∵ ∴保留[-1.832，-0.665]
如此迭代，到第8次，保留区为[-1.111,-0.940]
∴

§3.3梯度法
一、基本思想
对于迭代式，当取搜索方向时构成的寻优算法，称为求解无约束优化问题的梯度法。
二、迭代步骤
⑴给定出发点和收敛精度；
⑵计算点的梯度，并构造搜索方向；
⑶令，通过一维搜索确定步长，即：

求得新点
⑷收敛判断：若成立，输出、，寻优结束；否则令转⑵继续迭代，直到满足收敛精度要求。
三、梯度法的特点
梯度法寻优效率受目标函数性态影响较大。若目标函数等值线为圆，则一轮搜索就可找到极致点；若当目标函数等值线为扁椭圆时，收敛速度则显著下降。
梯度法中相邻两轮搜索方向相互垂直。（是否会证明）
§3.4牛顿法
牛顿法分为基本牛顿法和阻尼牛顿法两种。
对于迭代式，当取且搜索方向时构成的寻优算法，称为求解无约束优化问题的基本牛顿法；
对于迭代式，取搜索方向，为从出发、沿牛顿方向做一维搜索获得的最优步长，所构成的寻优算法，称为求解无约束优化问题的阻尼牛顿法。
搜索方向称为牛顿方向。
这里需要注意的是会求海塞阵的逆矩阵。
§3.5变尺度法
我们把具有迭代模式的寻优算法称为变尺度法。
其搜索方向表达式为：，称为拟牛顿方向，其中称为变尺度矩阵。
在迭代开始的时候，；随着迭代过程的继续，。
因此，变尺度法从梯度法出发，随着迭代过程的继续最终趋向于牛顿法。
§3.6共轭梯度法
一、共轭方向的概念
设为对称正定矩阵，若有两个维向量和，满足，则称向量与关于矩阵共轭，共轭向量的方向称为共轭方向。
若有一组非零向量，，…，满足，则称这组向量关于矩阵共轭。
对于元正定二次函数，依次沿着一组共轭方向进行一维搜索，最多次即可得到极值点。
二、共轭方向的形成
对于函数
沿任意方向在设计空间上任意做两条平行线，分别与目标函数等值线切于点、，令，则、关于矩阵共轭。（能否给出证明）
三、共轭梯度法
对于迭代式，取搜索方向
其中：，
共轭梯度法相邻两轮搜索方向是一对共轭方向。
§3.7鲍威尔法
基本迭代公式仍旧是：
基本鲍威尔法每轮搜索分为两步：一环的搜索+在该环搜索完毕后生成的新方向上的一维搜索。
对于基本鲍威尔法，相邻两轮搜索生成的搜索方向是共轭的。
修正鲍威尔法与基本鲍威尔法类似，所不同的是每环搜索后生成的新方向要利用鲍威尔条件判别其可用性。
注意掌握鲍威尔条件的表达式和应用！
每环搜索方向组的生成：
1．第一环的搜索方向组就是各坐标轴方向
2．下一环的搜索方向组由本环搜索方向组和本环生成的新方向共同确定，方法是：若本环的搜索结果满足鲍威尔条件，则将本环搜索方向组中使目标函数下降量最大的方向去掉，并将本环生成的新方向递补进去，就形成下一环的搜索方向组；若本环的搜索结果不满足鲍威尔条件，则下一环的搜索方向组仍旧沿用本环搜索方向组不变。
下一环搜索起点的确定：
下一环搜索起点由本环搜索结果确定，方法是：若本环的搜索结果满足鲍威尔条件，则以本环搜索终点为起点，沿新生成的方向作一维搜索，得到的新点作为本轮的搜索终点，也是下一轮的搜索起点；若本环的搜索结果不满足鲍威尔条件，则取本环搜索终点和反射点中目标函数值小的点作为本轮的搜索终点，也是下一轮的搜索起点。
这里需要注意的是反射点的计算：
式中：是本环起点相对于本环终点沿新生成方向的反射点。
例：对于无约束目标函数，利用修正Powell法从出发求最优解。
解：令

令 得： 则：

令 得： 则：
该环生成的新搜索方向为：
对进行有效性判别：
反射点

，
故最大下降量
故：和均成立
方向可用
以为起点，沿方向作一维搜索：

由得
故，本轮寻优的终点为：
做收敛性判别：
，应继续搜索
下一轮寻优过程的起点为：
下一轮寻优过程的搜索方向组为：
继续依样搜索直至满足收敛精度

第4章 约束优化方法

约束优化方法要求大家重点掌握惩罚函数法，包括内点法、外点法、混合法。
一、外点法
构造惩罚函数：

外点法既可以处理不等式约束优化问题，又可以处理等式约束优化问题。
需要注意的是：惩罚因子随迭代次数的增加是递增的，当时得到的解就是原问题的最优解。
例：用外点法求解

解：构造惩罚函数

令

为内点时无约束最优解
故得：
二、内点法
构造惩罚函数：
或：
内点法只能处理不等式约束优化问题，不能处理等式约束优化问题。
需要注意的是：惩罚因子随迭代次数的增加是递减的，当时得到的解就是原问题的最优解。
例：用内点法求解约束优化问题

解：构造惩罚函数
令

得，
当时，得
三、混合法
构造惩罚函数：

或：
混合法的特点是：对于不等式约束按照内点法构造惩罚项，对于等式约束按照外点法构造惩罚项。混合法既可以处理不等式约束优化问题，也可以处理等式约束优化问题。
例：用混合惩罚函数法求解约束优化问题

解：构造惩罚函数
令
得：，
当时，得

第5章 遗传算法与多目标优化

本章要求重点掌握遗传算法的5个要素、遗传算法的寻优机制、多目标优化特点及其Pareto解。
一、遗传算法的5个要素
1.编码
将优化问题的解编码，用以模拟生物个体的基因组成；
2.初始种群生成
将优化问题多个随机可行解汇成集合，用以模拟进化的生物种群；
3.个体适应度评估
将优化问题目标函数加以变换，生成适应度函数来评价种群个体的适应度，用以模拟生物个体对环境的适应能力；
4.遗传操作
包含选择、交叉、变异
选择：一种使适应度函数值大的个体有更大的存活机会的机制，用以模拟环境对生物个体的自然选择；
遗传操作
否
是
编 码
初始群体的生成
群体中个体适应度函数的评估
选 择
交 叉
变 异
收敛？
结 束
基本遗传算法流程图
交叉：不同个体间相互交换信息，用以模拟高级生物有性繁殖过程中的基因重组过程；
变异：模拟生物在遗传过程中基因复制差错而产生新个体的现象。
5.控制参数的设定
种群规模：； 交叉概率：
变异概率： 最大进化代数：
二、遗传算法的寻优机制
寻优机制见右侧的基本遗传算法流程图。
仔细看看遗传算法人工模拟进化的例题。
三、多目标优化问题
1.特点
任意两个目标彼此冲突，不存在使所有目标同时最优的绝对最优解，只有彼此无法比较的Pareto解集。
2.Pareto解、Pareto解集和Pareto前沿面
对于目标向量，是其可行域。，如果都有，并且使得，，则称比优越（也称支配）。如果不存在这样一个可行解，则称为非劣解或非支配解、Pareto解，而把称作目标空间中的非劣解。
通常将设计空间上所有非劣解称为多目标优化问题的Pareto解集，而将所有目标空间中的非劣解称为多目标优化问题的Pareto最优前沿面（图6.1b中的曲线）。
作业练习：

1.用薄钢板制造一个体积等于的货箱，各边长度不小于。要求确定货箱的长、宽、高尺寸，以使钢板的用量最省（忽略钢板厚度）。试写出该问题的数学模型。
2.将函数在点处简化为近似的二次函数。
答案：
3.确定下列函数的初始区间。
⑴ 取， 答案：[0.8，2]
⑵ 取， 答案：[0.8，2.6]
4.用黄金分割法求解，取、初始搜索区间[0.8，2]。
答案：
5.对于函数，用梯度法对其寻优，其迭代公式可表示为：

试证明之。
6.用梯度法求解，（做两轮迭代）
答案：
7.用阻尼牛顿法求解，
答案：
8.用共轭梯度法求解，
答案：
9.用Powell法求解，（迭代2轮，计算过程中小数点后面保留3位）
答案：
10.用外点法求解：
答案：，
11.用混合罚函数法求解：
答案：