优化设计复习

优化设计复习优化设计数学模型统一形式：求设计变量极小化函数满足约束：§1概述

一个完整的规格化的优化数学模型包含有三部分:设计变量X；目标函数；约束条件和。它们又被称为：优化数学模型的三要素。

当涉及问题要求极大化f(X)目标函数时，只要将式中目标函数改写为－f(X)即可。同样，当不等式约束为：“≥０”时，只要将不等式两端同乘以“－1”，即可得到“≤”的一般形式。§1概述由于每一条曲线上的各点都具有相等的目标函数值，所以这些曲线称为目标函数的等值线。目标函数的等值线(面):就是当目标函数f(X)的值依次等于一系列常数ci

(i=1,2,…)时，设计变量X取得一系列值的集合。§1概述x1x20F(X)=εx1x2等值线的形状：同心圆族、椭圆族，近似椭圆族、直线等等值线的疏密：沿等值线密的方向，函数值变化快；沿等值线疏的方向，函数值变化慢。等值线的疏密定性反应函数值变化率。§1概述（１）点距足够小准则式中，——给定的计算精度，一般可取。（２）函数下降量足够小准则

（３）函数梯度充分小准则迭代计算的终止准则§1概述n维函数f(X)在x0点沿d方向的方向导数:§2数学基础表示沿d方向在x0处的f(X)变化率梯度方向是函数值变化最大的方向。x1x2x3x2(0)x1(0)x3(0)0X(0)θ2θ1dθ3二元函数极值必要条件:即:二元函数极值充分条件:海塞矩阵各阶主子式均大于零。§2数学基础一、适用范围

适用于[a,b]区间上的任何单谷函数求极小值问题。对函数除要求“单峰”外不作其他要求，甚至可以不连续。适应面相当广。基本原理为区间消去法§3.3黄金分割法黄金分割法插入两点：f(a2)af(a1)

a1

a2bf(a2)af(a1)

a1b

a2即依此类推可得牛顿迭代公式：即依此类推可得牛顿迭代公式：二、牛顿法§3.4插值方法x2x1x0x*f(x)

f(x)

φ0(x)

φ1(x)

优点：1）收敛速度快。

缺点：1）要计算函数的一阶和二阶导数，增加每次迭代的工作量。

2）数值微分计算函数二阶导数，舍入误差将严重影响牛顿法的收敛速度，f

’(x)的值越小问题越严重。

3）牛顿法要求初始点离极小点不太远，否则可能使极小化序列发散或收敛到非极小点。二、二次插值法（抛物线法）a1af(a)2a3a1ff23fa*

在给定的单峰区间中，利用目标函数上的三个点来构造一个二次插值函数，以近似地表达原目标函数，并求这个插值函数的极小点近似作为原目标函数的极小点。

ap§3.4插值方法y0aap1a1a2apa3ay0a*y1y2ypy3a1a2apa*y1y2ypyp1apap1a1a2apa3ay0a*y1y2ypy3a2a3ay0a*y2ypy3yp1构造的二次插值函数曲线通过原函数上的三个点:

解得系数可求得二、二次插值法（抛物线法）§3.4插值方法（1）二次插值法只要求f(x)连续，不要求其一阶可微；（2）收敛速度比黄金分割法快，但可靠性不如黄金分割

法好，程序也较长。特点：§3.4插值方法二、二次插值法（抛物线法）无约束优化方法分类间接法:利用目标函数的一阶或二阶导数直接法:利用目标函数值最速下降法、牛顿法、共轭梯度法、变尺度法坐标轮换法、鲍威尔方法、单形替换法等

把初始点x0

、搜索方向d

k、迭代步长ak

称为优化方法算法的三要素。其中搜索方向d

k从根本上决定若一个算法的成败、收敛速率的快慢等。无约束优化方法主要不同点在于构造搜索方向上的差别。§4无约束优化方法搜索方向d取该点负梯度方向-▽f(X)

(最速下降方向)，使函数值在该点附近的范围内下降最快。§4.1最速下降法x1x20最速下降法程序框图开始计算，YN给定初始点，误差,令k=0计算，计算，结束§4.1最速下降法最速下降法评价：迭代过程简单，对初始点选择要求不高。梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。§4.1最速下降法X(k)S(k)S(k+1)X(k+1)X(k+2)X(k+3)X*f(X)=Ckf(X)=Ck+1f(X)=Ck+31、牛顿法

在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。求的极小点

§4.2牛顿型方法牛顿法迭代公式:

§4.2牛顿型方法牛顿型方法评价：（1）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；

（2）

不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的f(X)也不适用。§4.2牛顿型方法例4－2用牛顿法求下列目标函数的极小点。初始点为x0=[2,2]T解初始点梯度：海赛矩阵:带入到牛顿迭代公式：海赛矩阵逆阵：§4.2牛顿型方法共轭方向的性质1）非零向量系d0,d1,d2,…,dn-1是对G共轭，则这n个向量线性无关。2）在n维空间中互相共轭的非零向量个数不超过n。

3）从任意初始点出发，顺次沿n个G的共轭方向d0,d1,d2,…,进行一维搜索，最多经过

n次迭代就可以找到二次函数f(x)极小点。§4.3共轭梯度法共轭梯度法递推公式：其中:§4.3共轭梯度方法例，已知初始点[1,1]T解：1）第一次沿负梯度方向搜寻为一维搜索最佳步长，应满足迭代精度。§4.3共轭梯度方法得:2）第二次迭代：代入目标函数得因,收敛。由从而有：§4.5坐标轮换法一.坐标轮换法：1.基本思想：每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。x1x20X11X12X21X*X00X22计算步骤:⑴任选初始点,确定搜索方向第一轮的起点，置n个坐标轴方向矢量为单位坐标矢量§4.5坐标轮换法⑵迭代计算k为迭代轮数的序号，取k=1，2，……；i为该轮中一维搜索的序号，取i=1，2，……n步长α一般通过一维优化方法求出其最优步长。⑶判断是否中止迭代如满足，迭代中止，并输出最优解最优解否则，令k←k+1返回步骤（2）§4.5坐标轮换法

应该是一轮迭代的始点和终点，不是某搜索方向的前后迭代点。例:用坐标轮换法求下列目标函数的无约束最优解。

给定初始点，精度要求ε=0.1解：做第一轮迭代计算沿e1方向进行一维搜索式中，为第一轮的起始点，取按最优步长原则确定最优步长α1，即极小化此问题可由某种一维优化方法求出α1:

以为新起点，沿e2方向一维搜索以最优步长原则确定α2，即为极小化对于第一轮按终止条件检验计算5轮后，有故近似优化解为§4.5

坐标轮换法

3.方法评价：

方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。

受目标函数的性态影响很大。如图a)所示，二次就收敛到极值点；如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊（或称陡谷），若搜索到A点，再沿两个坐标轴以±t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。x1x2最优点X*X(0)①x1x2最优点X*X(0)①③②x2x1最优点X*终点A脊线X(0)一、共轭方向的生成§4.6

鲍威尔方法

Xk,

Xk+1为两个极小点根据梯度与等值面之间关系可知▽f(Xk)▽f(Xk+1)djdjXkXk+1二、鲍威尔基本算法

鲍威尔基本算法的搜索过程（二维）x1x2X10X20X11d2d1X*X0X01X21二、鲍威尔基本算法

鲍威尔基本算法的搜索过程（三维）x1x2x30X0(1)e1e3S1S1e2e2e3X2(3)X(3)S2S3S1X(2)S2e3第一轮：{e1,e2,e3}第二轮：{e2,e3,S1}第三轮：{e3,S1,S2}

X(1)X3(1)X2(1)X1(1)X1(2)X2(2)X3(2)X1(3)X3(3)为了构造第k+1轮基本方向组，采用如下判别式：

按照以下两种情况处理：

1)

上式中至少一个不等式成立，则第k+1轮的基本方向仍用老方向组d1k、d2k、

•••、

dnk。k+1轮的初始点取

x0k+1=xnkF2<F3

x0k+1=xn+1kF2F3

鲍威尔修正算法2）两式均不成立，则淘汰函数值下降最大的方向，并用第k轮的新生方向补入k+1轮基本方向组的最后，即k+1轮的方向组为d1k、d2k

、•••、dm-1k、dm+1k、•••、dnk、

dk

。(F3)(F2)(F1)反射点始点终点函数最大下降量△mk+1轮的初始点取:

x0k+1=xk

xk是第k轮沿dk方向搜索的极小点。

(F3)(F2)(F1)反射点函数下降量△始点终点dk方向极小点线性规划标准形式：§5.1

概述求使且满足说明：1）m=n,唯一解2）m>n,无解3）m<n,无穷解§5-3单纯形方法1）最速变化规则决定进基的非基本变量两个重要结论：2）规则决定了出基的基本变量3）若对基本可行解X，所有检验数rk≥0，则X为最优解。二.计算实例1.初始基本可行解取x5,

x6为基本变量,则有:[000045]T2.第一次变换(1)选取进基变量计算检验数的值:r3最小,

x3应为进基变量(2)确定离基变量规则∴x6

应为离基变量∵以a23为转轴元素进行转轴运算：进基3.第二次变换1)确定进基变量2)确定离基变量∴x5

应为离基变量∵以a14为转轴元素进行转轴运算：4.第三次变换1)确定进基变量

故X(2)为最优点,F

(2)为最优值:421235基变量x1x2x3x4x5x63x5112410425x612310155/3x0000045F037-4-11-20-15s.t.离基判别数进基判别数例1用单纯形表求解线性规划42123基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35x1005/302/30F111/38/37/3-25/3421235基变量x1x2x3x4x5x63x5112410425x612310155/3x0000045F037-4-11-20-1542123基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35x1005/302/30F111/38/37/3-25/34212基变量x1x2x3x4x5x62x41/10-1/10011/51x33/107/10108/5x2001.60.200F223.51.5已获得最优解§6.1

概述

直接解法：随机方向搜索法、复合形法、可行方向法

间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法一.有约束问题解法分类：二.直接解法的基本思想：

合理选择初始点，确定搜索方向，在可行域中寻优，经过若干次迭代，收敛至最优点。

xk+1=xk+αkdkdk::

可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下降,且不会超出可行域直接解法通常适用于仅含不等式约束的问题§6.1概述特点：①由于求解过程在可行域内进行；无论迭代计算何时终止,都可以获得一个比初始点好的设计点;②若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。凸可行域x1x20X(0)X(0)X(0)X(0)非凸可行域x1x20X1*X2*§6.1

概述原理：将有约束优化问题转化为无约束优化问题来解决。方法：以原目标函数和加权的约束函数共同构成一个新的

目标函数Φ(x,r1,r2)，成为无约束优化问题。通

过不断调整加权因子，产生一系列Φ函数的极小点

序列x(k)*(r1(k),r2(k))k=0,1,2…，逐渐收敛到原目标

函数的约束最优解。

其中：新目标函数：三.间接解法的基本思想：

惩罚因子：r1,r2§6.2随机方向法一.基本思想：随机产生初始点，随机产生若干个搜索方向dk，并从中选择一个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。确保：①新迭代点在可行域中②目标函数值的下降性。X(0)X(L)X(1)X*x1x20§6.3复合形法一.单纯形法：基本思想：以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，不断地迭代，逐渐逼近最优点。

二维空间中映射法比较单纯形X(1)X(2)X(3)的顶点，f(X(1))>f(X(2))>f(X(3)),X(1)为最坏点，称为X(H)，通过映射得到新点X(R)，X(R)＝X(S)＋a(X(S)-X(H))以X(R)来代替X(H)，组成新的单纯形X(R)X(2)X(3)。其中f(X(R))<f(X(H));

a>1；称为映射因子；X(1)=X(H)X(2)X(3)X(S)X(R)=X(4)X(5)X(6)定义：在n维空间中，由n+1个点组成的图形称单纯形。X*除X(H)外，其它顶点的几何中心二.复合形法：定义：

在n维空间中，由n+1≤k≤2n个点组成的多面体称为复合形。基本思想：

以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。说明：

单纯形是无约束优化方法，复合形用于约束优化的方法。因为顶点数较多，所以比单纯形更灵活易变。复合形只能解决不等式约束问题。因为迭代过程始终在可行域内进行，运行结果可靠。三.迭代方法：1.映射法：

例：二维空间中，k=4，复合形是四面体X(1)X(2)X(3)X(4)，计算得：f(X(1))<f(X(2))<f(X(3))<f(X(4)),确定最坏点X(H)=X(4)，次坏点X(G)=X(3)，最好点X(L)=X(1)。X(S)为除X(H)以外，各点的几何中心。映射迭代公式：X(R)=X(S)+α(X(S)-X(H))搜索方向：沿X(H)→X(S)的方向。步长因子（映射系数）α：α>1，建议先取1.3。若求得的X(R)在可行域内，且f(X(R))<f(X(H))，则以X(R)代替X(H)组成新复合形，再进行下轮迭代。●

X(S)X(R)

X(H)X(1)X(4)X(3)X(2)变形法一

——扩张：若f(X(R))<f(X(L))，则可沿此方向扩张取若f(X(E))<f(X(L))，则扩张成功，以X(E)代替X(H)组成新复合形若f(X(E))>f(X(L))，则扩张失败，以X(R)代替X(H)组成新复合形●

X(S)X(R)

X(H)X(E)X(1)X(4)X(3)X(2)变形法二

——收缩：

若在映射法中f(X(R))>f(X(H)),则以a＝0.5a重复采用映射法若直至a<10-5仍不成功，考虑采用收缩法

取

若f(X(K))<f(X(H)),则成功，以X(K)代替X(H)组成新复合形。●

X(S)X(R)

X(H)X(K)X(1)X(4)X(3)X(2)4.变形法三

——压缩：

如采用上述方法均无效，还可以将复合形各顶点向最好点

X(L)靠拢，即采用压缩的方法改变复合形的形状。

取

X(L)X(1)X(4)X(3)X(2)§6.4可行方向法一.基本思想：在可行域内选择一个初始点X(0)，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：

X(k+1)=X(k)+ad通过不断的调整可行方向，使迭代点逐步逼近约束最优点。该方法是求解大行约束优化问题的主要方法之一。§6.4可行方向法二.搜索策略：

根据目标函数和约束函数的不同性态，选择不同的搜索策略。

1)

边界反弹法：第一次搜索为负梯度方向，终止于边

界。以后各次搜索方向均为适用可行方向，以最大

步长从一个边界反弹到另一个边界，直至满足收敛

条件。f(X)X(0)X(1)X(2)X*X(3)§6.4可行方向法

2)最优步长法：第一次搜索为负梯度方向，终止于边

界。第二次搜索沿适用可行方向作一维搜索以最优

步长因子求得最优点。反复以上两步，直至得到最

优点X*。X(1)X(0)X(2)X(3)X*f(X)§6.4可行方向法

3)贴边搜索法：

第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。X(1)X(0)X(2)X*§6.4可行方向法

若约束面是非线性时，从X(k)点沿切线（面）方向d(k)

搜索，会进入非可行域。容差带δ：

建立约束面的容差带+δ，从X(k)

出发，沿d(k)方向搜索到d(k)方向与g(X)+δ=0的交点X'后，再沿适时约束的负梯度方向返回约束面的X(k+1)点。

X(k)g(X)g(X)+

δX'-▽g(X)d(k)X(k+1)§6.4

可行方向法二.搜索策略：

根据目标函数和约束函数的不同性态，选择不同的搜索策略。

1)

边界反弹法：第一次搜索为负梯度方向，终止于边

界。以后各次搜索方向均为适用可行方向，以最大

步长从一个边界反弹到另一个边界，直至满足收敛

条件。x(1)x(2)x(3)x*x(0)将有约束的优化问题转化为无约束优化问题来求解。保证：转化后的无约束优化问题与原约束问题具有同一最优解。

构成一个新的目标函数：§6.5惩罚函数法惩罚项惩罚因子惩罚函数内点法特点：

（1）初始点必须为严格的可行点

（2）不适于具有等式约束的数学模型

（3）迭代过程中各个点均为可行设计方案

（4）一般收敛较慢

（5）初始惩罚因子要选择得当

（6）惩罚因子为递减，递减率c有0<c<1

外点法特点：

（1）初始点可以任选

（2）对等式约束和不等式约束均可适用

（3）仅最优解为可行设计方案

（4）一般收敛较快

（5）初始罚因子要选择得当

（6）惩罚因子为递增，递增率c有c>1（1）基本思想：给每一个分目标函数值一个评价，以功效系数ci

表示:

功效函数:ci=Fi（fi）

0≤ci

≤1

功效系数法(几何平均法)

当fi取值很满意时，ci=1；当fi取值不能接受时，ci=0

整体评价函数:c值要求越大越好，即c=1为最满意；c=0表示此方案不能被接受。§7

多目标优化（2）功效函数的类型（按照对目标函数的不同要求）①目标函数越大越好