机械优化设计讲义.doc

《机械优化设计》讲义
第一讲
第一课时：机械优化设计概论
课程的研究对象：根据最优化原理和方法，利用计算机为计算工具，寻求最优设计参数的一种现代设计方法。
目标：本课程目标体系可以分为三大块：理论基础、算法的分析、理解和掌握，算法的设计、实现（编程）能力的培养。将主要是对算法的学习为主，并兼顾培养一定的解决实际问题能力、上机编程调试能力。
首先，几个概念：优化（或最优化原理、方法）、优化设计、机械（工程）优化设计。
现代的优化方法，研究某些数学上定义的问题的，利用计算机为计算工具的最优解。
优化理论本身是一种应用性很强的学科，而工程优化设计（特别是机械优化设计）由于采用计算机作为工具解决工程中的优化问题，可以归入计算机辅助设计(CAD)的研究范畴。
再，优化方法的发展：源头是数学的极值问题，但不是简单的极值问题，计算机算法和运算的引入是关键。
从理论与实践的关系方面，符合实践-理论-实践的过程。优化原理和方法的理论基础归根结底还是来源于实际生产生活当中，特别是工程、管理领域对最优方案的寻找，一旦发展为一种相对独立系统、成熟的理论基础，反过来可以指导工程、管理领域最优方案的寻找（理论本身也在实践应用中不断进步、完善）。

解决优化设计问题的一般步骤：
机械设计问题
建立数学模型
选择或设计算法
编码调试
计算结果的分析整理

相关知识：数学方面：微积分、线性代数；计算机方面：编程语言、计算方法；专业领域方面：机械原理、力学等知识
内容：数学基础、一维到多维、无约束到有约束
1.1 数学模型
三个基本概念：设计变量、目标函数、约束条件
设计变量：
相对于设计常量（如材料的机械性能）
在设计域中变量是否连续：连续变量、离散变量（齿轮的齿数，）。
设计问题的维数，表征了设计的自由度。每个设计问题的方案（设计点）为设计空间中的一个对应的点。
设计空间：二维（设计平面）、三维（设计空间）、更高维（超设计空间）。
目标函数：
设计变量的函数。
单目标、多目标函数。
等值面的概念：设计目标为常量时形成的曲面（等值线、等值面、超等值面）。几何意义：等值线（等值线的公共中心既是无约束极小点）、等值面。
约束条件：
等式约束（约数个数小于设计问题的维数）
不等式约束
满足约束条件的设计点的集合构成可行域D：可行点、非可行点、边界设计点
几何意义（二维）：对于设计空间不满足不等式约束的部分，用阴影表示。
数学模型的一般形式：
寻找一个满足约束条件的设计点，使得目标函数值最小。
标准形式：

1.2 优化问题的几何描述

第二章 数学基础和数值迭代法
2.1 函数的方向导数和梯度
一、 函数的方向导数

二、函数的梯度

令为函数在X点的梯度，包含函数的一阶导数信息。

即梯度方向是函数变化率最大的方向。

2.2 函数的泰勒展开与黑塞矩阵
一、泰勒展开式

其中黑塞（hessian）矩阵:
包含函数的二阶导数信息。

2.3 凸集、凸函数、凸规划
一、凸集
有，则D为凸集.
凸集的性质：1. 若D为凸集，λ为实数，则λD仍为凸集。（凸集的实数积为凸集）
2．若D、φ均为凸集，则二者的并集（和）为凸集。（凸集的和为凸集）
3．若D、φ均为凸集，则二者的交集（积）为凸集。（凸集的积为凸集）

二、凸函数
En的子集D为凸集，f为D上的函数，恒有，则f为D上的凸函数。反之为凹函数。
凸函数的性质：
1. 设f为D上的凸函数，λ为实数，则λf为D上的凸函数。
2. 设f1，f2为D上的凸函数,则f= f1+f2为D上的凸函数。
3. 若f在En一阶可微，则对，f为凸函数的充要条件：
4. 若f在En二阶可微，则对，f为凸函数的充要条件：黑塞矩阵半正定（若正定，严格凸函数）。
三、凸规划
其中目标函数、不等式约束均为凸函数，则称该问题为凸规划。
凸规划的性质：
1． 集合为凸集。
2． 可行域为凸集。
3． 任何局部最优解即为全域最优解。
4． 若目标函数可微，则最优解的充要条件：

2.4 无约束优化的极值条件
1．一阶导数（梯度）为零。
2．二阶导数（黑塞矩阵）正定（极小点），或负定（极大点）。

2.5 有约束优化的极值条件(Kuhn-Tucker条件)
对优化问题库恩-塔克条件描述为
，即约束极小点存在的必要条件是：目标函数在该点的梯度可表示为诸约束面梯度的线性组合的负值。从几何意义上来说，即约束极小点目标函数梯度向量的反方向必须落在诸约束面所构成的锥角范围之内。
对于凸规划问题，K-T条件是充要条件。
只能作为验证条件，但到底是局部最优点还是全域最优点尚不能确定。

2.6 优化问题的数值迭代法
1．迭代过程 (k=0,1,2,…)
迭代的基本思想：搜索、迭代、逼近。
2．迭代终止条件：
点距准则：
函数值下降准则：
梯度准则：

第三章 一维搜索的优化方法
一维优化是多维优化的基础。包含两个步骤
1．确定搜索区间（进退法）
2．寻优（黄金分割法、二次差值法）

3.1 进退法——一维搜索区间的确定
基本思想：对单峰函数（凸函数）f(x)，只要找到可行域内三个点a<b<c，满足函数值先减小再增大的趋势，即f(a)>f(b)且f(b)<f(c)，则可以确定区间[a,c]内必存在最优点。
算法流程：

3.2 一维优化方法——黄金分割法

一维搜索的基本思想：在确定了搜索区间的前提下，不断缩小搜索区间，直到区间的宽度小于预定的精度。

黄金分割法的基本思想：
黄金分割点的计算：
算法流程：

3.3一维优化方法——二次插值法

首先，10分钟回顾上次课的内容，并讲解作业：进退法、黄金分割法概要、
103页作业（程序演示）
30分钟：
基本思路：类似于二次曲线拟合。以搜索区间三个点构造一个二次曲线（抛物线），并以该二次曲线的极值点替代目标函数的最优点，若不满足迭代中止条件，缩短搜索区间，反复迭代，直到相近两次二次曲线极值满足精度要求（点距准则）。
3.3.1 基本原理
搜索区间[a1，a3]及其中间某一点（a2）这三个点构造一个二次曲线。这三个点构成一个三元线性方程组,可求得该二次曲线极值点a*p作为a4。
其中a*p = 0.5(a1+a3-C1/C2)
C1 = (f3-f1)/(a3-a1)
C2 = [(f2-f1)/(a2-a1)-C1]/(a2-a1)
若a2 与a4之间趋于重合，则迭代结束；否则比较这四点的函数值，并在其中选择三点，满足函数值“先递增再递减”的趋势，构成新的a1、a2、a3。开始新一轮迭代。
3.3.2 迭代过程和算法流程
例题本周五，p24,p29

第四章　（多维）无约束优化方法
概述：工程优化问题通常都是多维有约束优化问题，但需从一维无约束问题到多维无约束优化问题再到多维约束优化问题的由简单到复杂的循序渐进的学习研究过程。
无约束优化问题数学模型：
分类，从是否利用目标函数的导数信息，分直接法和间接法
直接法：坐标轮换法、共轭方向法、鲍威尔法
间接法：梯度法、牛顿法、变尺度法

4.1 坐标轮换法

4.1.1 坐标轮换法基本原理
将多维无约束优化问题分解、转化为一系列一维优化问题，轮换沿各个坐标轴一维搜索，直到求得最优点。
在每次迭代内部，要依次沿各坐标轴进行N次（N为优化问题的维数）一维搜索。这种一维搜索是固定其它N-1维变量，视为常量，然后进行一维搜索，，对于第k轮迭代，须重复N次该式的一维搜索，搜索的参数为ajk（即要优化的参数是ajk），为相对第j维变量的搜索步长，搜索方向为第j维空间坐标的方向。当k轮迭代结束后，本轮搜索的重点作为下一轮的起点，即，然后投入下一轮迭代。
4.1.2 该方法特点
不考虑目标函数本身的变化情况（函数特点），简单、效率低、收敛速度慢。

4.2 共轭方向法
4.2.1 共轭方向
对于N维正定二次函数 (当N=2，为同心椭圆族)，[H]为函数f的黑塞矩阵(正定对称阵)。若存在两个方向向量，，满足，则称与为共轭方向。
如何构造共轭方向（二维）？对于某两点，沿方向（不平行）一维搜索得到两个最优点，构成方向，则可以证明与为共轭方向，即
（对于二维问题，可以简单证明）
当然，这个结论可以从2维推广到N维。同样，说明对于N维函数，有N个共轭方向。对于二次函数，只要经过N个一维搜索即可到达最优点（即N维空间内完成一轮迭代）。对于大于二次的函数，则可能需要将上一轮迭代的终点作为新一轮迭代的起点。在构造迭代方程式时，可以用二次泰勒展开式来近似目标函数的等值面。
第二课时：
4.2.2 共轭方向法基本原理
第一轮迭代与坐标轮换法相同。将起点和N次一维搜索的末点组成一个新的方向，沿这个方向一维搜索，得到本轮迭代的终点。
从第二轮起，舍去前一轮的第一个一维搜索方向，将前一轮的后N个一维搜索方向作为本轮迭代的前N个方向，这N个方向的一维搜索终点与本轮搜索的起点构成第N+1个一维搜索方向，沿这个方向做一维搜索，得到本轮搜索的终点。
若不满足精度要求，则重复迭代。
4.2.3 共轭方向法的特点
收敛速度比坐标轮换法有明显的提高，但前提是每次迭代所产生的新的方向与原来的N-1个方向之间要保持线性无关，若这些方向之间线性相关，则降低了搜索空间的维数，导致不能完全穷尽对设计空间每个方向的搜索，从而不能收敛于真正的最优解。

上机调试内容：
4.3 鲍威尔法
4.3.1 鲍威尔法基本原理
共轭方向法的前提是每一轮迭代中新生成的第N+1个方向（共轭方向）与其它方向线性无关，如果出现线性相关，则导致算法不能正确收敛。鲍威尔为了解决该问题，加入了对共轭方向的判断，如果线性无关则采用该方向，但并不是机械的替换上一轮第一个方向，而是替换函数值下降最多的方向；如果相关，则还是用上一轮迭代的方向。
对于共轭方向法的判别准则。
（4-2）
其中： f1 ——本轮迭代起点函数值
f2 ——本轮迭代终点函数值
f3 ——映射点函数值
Δkm——函数值下降最大的一步一维搜索
若满足公式（4-2）则去掉第m个方向，下一轮的m到N方向采用本轮次第m+1到N+1个方向；若不满足，则本轮迭代结束，以本轮终点为下一轮起点，仍采用本轮的N个方向进行迭代。
4.3.2 迭代步骤
（1）给定初始点和计算精度。
（2）置k=1，取N个坐标轴的单位向量为搜索方向（i=0,1,…,N-1），,
（3）从出发，沿一维搜索，得到N个极小点（i=1,2,…,N）,找到函数值下降最快的一次一维搜索的函数下降值和方向，记作Δkm，
（4）计算反射点，计算f1，f2，f3。
（5）若满足（4-2）式，构造本轮迭代第N+1个方向，由N次一维搜索的终点沿一维搜索得到本轮迭代终点，作为下一轮迭代（k+1轮）起点；去掉方向，将作为下一轮迭代的第N个方向。
否则，保留前N个搜索方向到下一轮迭代，取min(f2，f3)对应的点作为下一轮起点。
（6）若满足迭代终止条件，终止迭代，输出优化结果，否则kßk+1,返回（3）。
4.3.3 算法流程
（见下页）
共轭方向法习题课：
用共轭方向法和鲍威尔法求解优化问题，初始点[0,0]T,精度ε=0.01。
解：共轭方向法：
鲍威尔法：

4.4 梯度法（最速下降法）
4.4.1 梯度法基本原理
无约束优化的直接法（坐标轮换法和共轭方向法、鲍威尔法）没有考虑无约束优化最优解存在的必要条件（梯度为零），使用这一条件，可以设计出更为高效的算法，所谓间接法（梯度法、牛顿法、变尺度法）。
梯度方向是函数值变化最快的方向，那么负梯度方向便是函数值下降最快的方向。从这一点受启发，可以使迭代方向沿梯度方向进行一维搜索来再多维空间寻优。即搜索方向为梯度方向：，或，则迭代公式为。
4.4.2 梯度法的特点
前提是梯度存在。
优点是算法简单。
相邻两次迭代的搜索方向垂直。即
证明：，即k轮迭代经过一次一维搜索由k点到达k+1点，那么，对于一维优化有，所以
可见，相邻两轮迭代的搜索方向并不一致，为相互垂直的锯齿形过程。剃度法对于迭代出发点目标函数等值面偏心率为零时很有效，但对于有偏心的其效率就低了，随偏心率的增加，迭代终止的难度也在增加。可见这种搜索在接近目标时的收敛是比较慢（缺点）的，效率也就不会高了。剃度法一般并不作为工程中实际应用的方法，常用于其他方法的初始迭代（类似于坐标轮换法）。

4.5 牛顿法
4.5.1 牛顿法基本原理
类似二次插值法，将目标函数在某一点附近二阶泰勒展开，用这个二次函数的最优点近似目标函数的最优点；若不满足精度要求，在上一轮得到的最优点最为本轮起点，再次用上述方法求最优点；直到满足精度要求。
4.5.2 牛顿法迭代公式
目标函数在的二次展开，求近似目标函数的最优解，即，有即
，所以牛顿法迭代公式为。
从牛顿法的原理分析，如果目标函数为二次函数，有，即牛顿法一轮迭代的终点就是最优解，而且是精确解。因此，牛顿法解决了二次函数非球面时的搜索方向问题，找到了一个可以消除偏心存在对采用梯度方向为搜索方向时的影响，直接给出了搜索二次函数最优点的方向。或者说，牛顿法对偏心率进行了变化，消除了二次曲面的偏心率，对于更高次曲面，也可以减小这种偏心。从而在一定程度上解决了梯度发收敛慢的缺点。
4.5.3 牛顿法的特点
（1）由于采用了目标函数二阶导数信息，收敛速度比梯度法快。
（2）牛顿法迭代公式与一般迭代公式的区别在于，没有步长系数。这使得在接近最优点时由于步长不能调节，可能会错过最优点，造成算法的稳定性欠佳，甚至造成不能收敛而导致计算失败。为了克服这一点提出阻尼牛顿法，添加阻尼因子，迭代公式为。
（3）需要计算黑塞矩阵及其逆矩阵，内存占用、计算量大；此外二阶导数不存在，或者逆矩阵不存在的情况不能应用。

4.6 变尺度法
4.6.1 变尺度法基本原理
牛顿法的缺点集中在黑塞矩阵及其逆的计算上，解决的方法是保留牛顿迭代法的迭代公式的形式，但不计算黑塞矩阵的逆，而是用一个矩阵去近似和逼近[H]-1,以减少计算量。
4.6.2 变尺度法迭代公式

[Ak]——称为变尺度矩阵
对第一轮迭代，[A0]ß[I], 即，也就是梯度法
当迭代过程逼近最优点，[Ak]à[H]-1,迭代公式变成，也就是阻尼牛顿法。
所以，可以把变尺度法看作梯度法和牛顿法的改进算法。或者梯度法和牛顿法是变尺度法的特例。
至于变尺度矩阵[Ak]如何构造，才能达到预期的效果，方法很多，主要介绍DFP法和BFGS法。思路为：为了使变尺度矩阵随着迭代过程逐渐逼近黑塞矩阵的逆，构造，其中为k次迭代的修正矩阵。
4.6.2 DFP变尺度法
变尺度矩阵的修正是变尺度法区别于牛顿法之处：
修正矩阵
其中 ，相邻两迭代点之间的变化量
，相邻两迭代点之间梯度的变化量
4.6.3 BFGS变尺度法
修正矩阵
4.6.4变尺度法迭代步骤和算法流程
迭代步骤
（1）给定初始点，精度，维数N；
（2）置kß0，[Ak]ß[I],计算初始点梯度；
（3）计算搜索方向；
（4）从k点开始一维搜索，得到k+1点；
（5）迭代终止条件，若满足，输出最优点和最优解；否则下一步；
（6）检验迭代次数，若为N,置k+1点为初始点，转（2）重新构造变尺度矩阵；否则下一步；
（7）计算、，修正矩阵、变尺度矩阵，置kßk+1,转（3）。
算法流程图：

第五章 约束优化方法
前言：实际工程优化问题大多数为设计空间多维且带有约束条件的非线性优化问题。其数学模型为

根据对约束条件处理方法的不同：
直接法（约束坐标轮换法、随机方向法、复合形法、可行方向法）
间接法（简约梯度法、惩罚函数法等）。
直接法可以直接从可行域中找到最优解；将问题分解为一系列比较简单的子问题，用子问题的解逼近原问题的解。
直接法简单直观、对目标函数要求不高；计算量大、收敛慢，因此效率低。

5.1 约束随机方向搜索法（随机方向法）
5.1.1 基本原理
从可行域内某一点出发，沿某一给定步长，并随机产生搜索方向，直到该方向同时满足可行性和下降性要求，沿着这个方向以该步长继续搜索，直到不满足可行性及下降性条件为止。把上述满足要求的终点作为新的起点，重新产生随机方向，如果能够找到一个合适的方向，同时满足条件，则沿该方向以原步长继续搜索；如若找不到适合的方向，则将步长减半，仍以该点为起点随机搜索，如果能找到新的方向，则沿该方向继续，如果不能，步长再减半。直到找不到新的搜索方向，且步长满足精度要求，则以该起点为最优点。
一个需要说明的问题：从某一点出发，如何判断沿某一给定步长找不到可行的方向呢？如果不靠目标函数和约束条件中隐含的指引信息，那么只有对搜索空间进行机械的排查，对随机方向搜索法而言，就是在产生并搜索了足够多方向之后，认为可以近似的得出这个结论。那么，到底随机搜索了多少个方向才能得出结论呢？一般取50~500个方向，当然，如果不考虑计算的速度和效率，这个最大的方向数大一些更好，而且设计空间维数越大，这个数也应越大。
5.1.2 初始点的选取

其中ri为随机数，对C语言，有函数rand()产生一个0到RAND_MAX的伪随机整数，则
5.1.3随机搜索方向的产生
。通过该变换，使搜索方向的每个分量为-1到1之间的随机值，从而确保对每个坐标方向的正负两方向的搜索。之后可以进行标准化处理
5.1.4 算法流程
（下一页）

5.1.5 随机法的特点
算法简单，对目标函数要求不高；由于随机搜索带有盲目性，效率低，速度慢，可能不收敛。

5.2 复合形法
5.2.1 基本原理
（1） 在设计空间找到K个可行点构成多面体（复合形），一般N+1≤K≤2N。
（2） 不断使复合形向着约束内最优点移动和收缩。更具体一些，根据目标函数值的大小找出这K个点中的最坏点（函数值最大），除最坏点之外的其它K-1个点的形心为映射中点，找到最坏点的映射点（对称点），最坏点之外其余K-1个点以及这个映射点构成新的复合形。
（3） 检验复合形中各个点与最好点是否满足重合,或这些点收敛于某个精度构成的最好点的临域之内。若满足，则算法成功结束；否则，重复(2)。
5.2.2 几个关键问题
（一）初始复合形的产生
1． 确定第一个可行点作为复合形的第一个顶点。如果不满足可行性，反复进行随机搜索，直到找到可行点。公式
2． 再随机产生其余K-1个顶点。
3． 对2.中产生的K-1个点逐一检验可行性，并将不满足的点调入可行域。
具体的方法：
1） 从第一个点起，找到满足可行性的q个点，第q+1个点不满足。求前q个点的形心。
2） 将q+1点向这个形心按两点长度的一半移动，如此反复，直到将该点移入可行域。
3） 之后其它不可行的点按1）、2）的步骤重复，直到K个点均满足可行性。
（二） 映射点不满足可行性和下降性的处理
1） 如果映射点不满足可行性和下降性，将映射系数减半，产生新的映射点，如此反复，直到满足；否则2）
2） 以次坏点取代最坏点，求新的形心和形心的映射点。
（三） 可行域为非凸集的处理
如果除最坏点外其它K-1个点的形心不在可行域内，则可行域可能是非凸集。
这时在以最好点和该形心构成的超立方体中重新构造复合形。如果，
则
（四）迭代终止条件：各顶点与最好点目标函数值之差的均方根小于设计精度
5.2.3 算法流程

5.2.4 复合形法的特点
搜索具有方向性，收敛速度较快
例

5.3 惩罚函数法
罚函数法基本思想：约束条件构造罚函数项，并入目标函数，化为无约束优化问题。所谓“惩罚”，既是给不满足约束条件的惩罚项以很大的值，使目标函数的总值增大（就是惩罚），那么无约束优化方法就会使搜索向着总值减小的方向前进，从而使不满足的约束的点（或远离约束边界的点）向满足约束的方向靠拢。
5.3.1 外罚函数法
（一）基本原理
1． 不等式约束的处理
2． 等式约束的处理
3． 带有惩罚项的目标函数的构造
4． 约束条件的收缩
（二）算法流程
（三）算法的特点
远离约束边界时
5.3.2 内罚函数法
5.3.3 混合罚函数法