Lecture8CAD中常用的数值分析方法.

计算机辅助设计与制造CAD中常用的数值分析方法周驰[e-mail]87110594-805优化设计方法优化设计是20世纪60年代发展起来的一门新学科，它是最优化技术和计算机技术在设计领域应用的结果。例子：怎样在保证强度的情况下，使得重量最轻模板尺寸的自动标注《数值分析》《优化设计》Matlab1000111min..(01)niiinniixastxaxaxxDin利用线性规划解决模具零件自动标注的尺寸重叠问题优化设计的基本要素与数学模型设计变量n维设计的n个设计变量，按一定顺序排列成一个n维矢量1212......TnnxxXxxxx目标函数12()(,,...)nfXfxxx使得f(X)最小的X*就是所求的最优解。多目标优化12(),(),...,()kfXfXfX1()()kiiifXwfX约束条件•不等式约束()0,1,2,...,ugXum•等式约束()0,1,2,...,vhXvpn常用的优化方法优化方法名称特点一维搜索方法黄金分割法简单、有效、成熟的一维直接搜索方法，应用广泛多项式逼近法收敛速度较黄金分割法快，初始点的选择影响收敛速度无约束线性规划算法间接法梯度法需计算一阶偏导数，对初始点的要求较低，初始迭代效果较好，在极值点附近收敛很慢，一般与其他方法配合，在迭代开始时使用牛顿法具有二次收敛性，在极值点附近收敛较快，但要用到一阶、二阶导数，计算量大，需要的存储空间大，对初始点要求很高DFP变尺寸法共轭方向法的一种，具有二次收敛性，收敛速度快，可靠性高，需计算一阶偏导，对初始点要求不太高，可求解n100的优化问题，是有效的无约束优化方法，但所需存储空间较大直接法Powell法共轭方向法的一种，具有直接法的共同优点，即不必对目标函数求导，具有二次收敛性，收敛速度快，适合于中小问题单纯形法适合于中小型问题（n20）的求解，不必对目标函数求导，方法简单、使用方便有约束非线性规划算法直接法网格法计算量大，只适合于求解小型问题（n5），对目标函数要求不高，易于求得近似局部最优解，也可用于求解离散变量问题随机方向法对目标函数的要求不高，收敛速度较快，可用于中小问题的求解，但只能求得局部最优解复合形法具有单纯形法的特点，适合于求解n20的规划问题，但不能求解有等式约束的问题间接法拉格朗日乘子法只适合于求解只有等式约束的非线性规划问题，求解时要解非线性方程组。经改进，可以求解不等式约束问题，效率也较高罚函数法将有约束问题转化为无约束问题，对大中型问题的求解均较合适，计算效果较好可变容差法可用来求解有约束的规划问题，适合问题的规模与其采用的基本算法有关优化设计的一般过程1．设计对象的分析明确设计要求、合理确定优化的范围和目标2．设计变量和设计约束条件的确定设计变量必须是对设计指标有直接影响的参数合理选择设计变量的数目各设计变量应互相独立3．目标函数的建立目标函数应针对影响设计要求最显著的指标来建立可以采用多目标优化，也可以将一些次要目标转换为约束条件优化设计的一般过程4．优化算法的选择选取的方法应适合设计对象的数学模型5．优化结果分析要对求解结果进行综合分析，并根据实际情况进行修正和调整常用优化算法分析黄金分割法f(c)f(d)在[c,b]段内f(c)f(d)在[a,d]段内f(c)=f(d)在[c,d]段内特点：适合于非光滑或者不方便计算导数的情况0.618算法（1）确定初始搜索区间[a，b]，给定精度要求ε（ε0）；（2）计算及；（3）计算及；（4）如果，则输出极小点近似值，以及，停止搜索。否则转（5）；（5）如果，则令、、，转（3）。否则转（6）；（6）令、、、、，转（4）。0.618()daba()dffd0.618()cbba()cffcdc*()/2xcd(*)fx()()fcfdbddcdcffaccdcdff0.618()daba()dffd切线法求f(x)的最小值，实际上是求'()0fx限制条件：在含有极小值在内的一个足够大的区间内二阶导数恒为正切线法的迭代公式(0)(0)(0)(1)'()tan''()fxfxxx(0)(1)(0)(0)'()''()fxxxfx(1)()(1)(1)'(),k=1,2,3...''()kkkkfxxxfx梯度法()()12()[...]kkTnffffxxxSX(1)()()()kkkkfXXX()()()()min(())()kkkkkffXXXX适用范围：适合于求解无约束多变量问题，用于要求精度不高的问题，或者为复杂函数寻找一个好的初始点牛顿法()()()2()()21()()+()()()()()2kkkkkffffXXXXXXXXX问题转化为求的极值。()X()2()()()()()()0kkkffXXXXX()()2()()()kkkffXX=XX()(1)()2()()()kkkkffXX=XX写成迭代形式：适用范围：适合于求解无约束多变量问题约束的处理罚函数法罚函数法的基本思想是根据约束的特点构造某种惩罚函数，并将惩罚函数添加到目标函数中，使约束优化问题的求解转化为无约束优化问题的求解。()min()krX,()()1()()[()]mkkuurfrGgX,XX()1lim[()]0mkukurGgX内点法罚函数()()11()()()mkkuurfrgX,XX()kr是一个递减的序列，比如1,0.1,0.01,….|()|0,1,2,...,vhXvpn等式的转化