建模仿真与优化设计2010.

1、一优化模型的一般意义二非线性规划建模无纟三 非线性规划建模有约束非线性规戈四连续结构体建模与优化设计目的1. 掌握优化问题的数学描述方法;2. 熟练掌握常用优化算法。一优化模型的一般意义（一）优化模型的数学描述将一个优化问题用数学式子来描述，即求函数U = f(x)在约束条件 人（X）= 0, / = 12昇72.和&O） <0（&（兀）二0）丿=12，P下的最大值或最小值，其中X 一设计变量（决策变量） fM目标函数xeQ 可行域min(f?r max)“ = f(x) x e Qs. t. /2z(x) = 0.i = 1,2., m.g,(x) SO(gO) AO)

2、, = 1,2,“ P-st. subject to “受约束于”之意(二) 优化模型的分类1 根据是否存在约束条件有约束问题和无约束问题。2 根据设计变量的性质静态问题和动态问题。3根据目标函数和约束条件表达式的性质线性规划，非线性规划，二次规划，多目标规划等。(1)非线性规划目标函数和约束条件中，至少有一个非线性函数。min u = f(x) x c Q5. t.人(x) = OJ =匕2,昇72.z(x) <0(.(x)>0XZ = 1,2,.,5 /（2）线性规划（LP）目标函数和所有的约束条件都是设计变量的线性函数。min u = cixi/=122aikxk = bi

3、= 1,2,., n. s.t< k=xx； >0.i = 1,2,. n.V （3）二次规划问题目标函数为二次函数，约束条件为线性约束min u = /(x)=工ZNbjjXjXj i=l厶 J=152 aijxJ -bi = 1，2,.，n.s.t< 丿=ixi > O.i = 1,2,., n4.根据设计变量的允许值整数规划（01规划）和实数规划。5.根据变量具有确定值还是随机值确定规划和随机规划。（三）建立优化模型的一般步骤1确定设计变量和目标变量;2.确定目标函数的表达式；3 寻找约束条件o二、优化求解的数学基础函数的梯度泰勒展开二阶导数矩阵矢量的概念.运算牙

4、矩阵的运算和逆矩阵芮h和亦别是函薮几x, x22)Ex0点处沿坐标孤湎£方向的变化率(-)方向导数Iim /go 十 5心。）/（皿七） Axj-X）AX.|-m /*（旳0，*20 十 42）-/（“IO, *20）I g ->0Ar2I .1菁二、优化求解的数学基础故函数f(Xlf X2 沁o(X“,七/点处沿某一方向銅变化率为:（&*>Hm /Ow 屮"1 *20 + 心2）一 /（X1D，勺.）AS-K）AS称为该函数沿此方向的方向导数 偏导数可以看作是函数沿坐标轴 方向的方向导数，并有旦 dx血 COSO?dfx COSf/j +1 dx2X

5、"A d rIZ1 X2X XII xio(二)梯度二元函数在点X。的梯度是由函数在该点的各一阶偏导数组 成的向量。即:W(斗)三dx2二、优化求解的数学基础设S方向单位向量cosq COSoy = V/Xxo )rS= |V/(x()|cos(Vf, S) d Xo函数的梯度具有以下性质：(1) 函数在一点的梯度是一个向量。梯度的方向是该点函数 值上升最快的方向，与梯度相反的方向是该点函数值下降 的最快的方向，梯度的大小就是它的模长。(2) 一点的梯度方向是与过该点的等值线或等值面的切线或 切平面相垂直的方向，或者说是该点等值线或等值面的法 线方向。(3) 梯度是函数在一点邻域内局

6、部形态的描述。在一点上升得快的方向，离开该领域后就不一定上升得快，甚至毋能 下降。V二、优化求解的数学基础(三) 泰勒展开为了便于数学问题的分析和求解，往往需要将一 复杂的非线性函数简化成线性函数或二次函数。简化郎 方法可以采用泰勒展开式。由高等数学可知，一元函数若在点X。的邻域 内n阶可导，则函数可在该点邻域内作泰勒展开：f(x) = /(x0) + f (xJAr + -/7x0)Ar2 + nAx” + Rn (x)其中 X 三.二元函数3在点xo(xio, x2Oy可以作泰勒展开，展 式一般取前三项，即：1 A 喲 + 2 諾二、优化求解的数学基础将上式写为矩阵形式OfAr】dx2/（

7、"）= /*（兀。）+ | 警+ 7 g 心2=/(x0) +Vf(x0)rAx + izrrG(x0)Ar + 其中，GQfo冲为函数f（xlfx2）点血处的 二阶导数矩阵或海赛矩阵。二、优化求解的数学基础在优化计算中，当某点附近的函数值采用泰勒展 开式作近似表达时，研究该点邻域的极值问题需要另 析二次型函数是否正定。当对任何非零向量X使f (jc) = xrGx > O则二次型函数正定，G为正定矩阵二.优化求解的数学基础（四）二次函数当将函数的泰勒展开式取到二次项时得到二 次函数形式。优化计算经常把目标函数表示为二次 函数以使问题分析得以简化。在线性代数中将二次 齐次函数称

8、作二次型，其矩阵形式f（x） = xT Gx在优化计算中，当某点附近的函数值采用泰 勒展开式作近似表达时，研究该点邻域的极值问题 需要分析二次型函数是否正定。当对任何非零向量 X使丁y（x）= xtGx > o则二次型函数正定，G为正定矩阵二、优化求解的数学基础对于一般二次函数/X") = + FGx +十 C |则称矩阵是正定的； 则称矩阵是半正定的;则称矩阵是负定的； 则称矩阵是半负定的;则称矩阵是不定的(1)(2)(3)(4)(5)矩阵有正定和负定之分。对于所有非零向量: 若有xTGx > Q 若有 x1 Gx > 0, 若有 xrGx v 0, 若有 x7G

9、x < 0> 若有 xrGx = 09二、优化求解的数学基础可以证明，正定二次函数具有以下性质：(1) 正定二次函数的等值线或等值面是一簇同心圆 或同心椭球。椭圆簇或椭球簇的中心就是该二次函 数的极小点。(2) 非正定二次函数在极小点附近的等值线或等值二、优化求解的数学基础(五) 无约束优化问题的极值条件充分条件为：该点处海赛矩阵正定，即二次函数f(xl, x2Ex0取得极值的必要条件 为d2fd2f正定：各阶主二dx dxdx2 d2fd2f>0均大于零。0xX2OX2*0二.优化求解的数学基础（六）下降迭代算法及其收敛性无约束最优化问题求优过程的 求解方法大致分为两类。(

10、1)解析法VF(X) = OHessian矩阵正定Hessian 矩阵负定=极小值点极大值点二.优化求解的数学基础用迭代汁算逐步逼近是优点搜索过程血三、优化设计的4（一）优化问题的求P优化问题的本F优化问题的本2、优化问题的求解e.数值计算法可以较好地解决这类问题理论上解析法即应用极值理论求傑数值计算法（二）数值计算法的迭代方法1、2、数值计算法的迭代方法三.优化设计的迭代计算三.优化设计的迭代计算（三）迭代计算的迭代过程由选定的初始点X）某种优化方法序 :定的搜索方向SX=乂（0）-使满足F(x(,)门J2).-J1）由于各设计点的函数值僧 次下降，可见迭代点不衣 向理论最优点逼近，最尼 可

11、得到一定精度下的近雄 最优皆，记作兀"。兀(Sl)=*«)+C(AOs")三.优化设计的迭代计算三.优化设计的迭代计算!1!)迭代计算的终止准则由于数值迭代是逐步逼近最优点而获得近似解的， 所以要考虑优化问题解的收敛性及迭代过程的终止条件。1、迭代的收敛性指某种迭代印住立斗侶住和山=0,1,2,)收敛亍 恤乂*+1相邻两个李计点宀的距离已达到充两迭代点的坐标2、通常采用怎分小分量之差(1)点距准“llxk+1-Xkll<E 或_、倔化zrr相邻迭代点的函数值下降(2)函数下降量准则畐扶创呑并小F(x"i)_F(+相邻迭代点的函数值的相 对it狂到充

12、另小尸(严)一尸(來)F(J)(3)梯度准则心)后5非线性规划建模无约束最优化丄、了解无约束最优化基本算法。2、掌握用数学软件包求解无约束最优化问题。1无约束优化基本思想及基本算法。2. MATLAB优化工具箱简介 3.用NIAIIAB求解无约束优化问题七）=西 +蓼2 一?:!". 參/ «纟： <算一Jimin /(%! x2) = 1 (X)(x2 -x)2 + (1 xx)2兀2f114.00-0.790.583.390.530.232.600.180.001.500.09-0.030.980.37010.470.590.330.200.800.630.050

13、.950.90().0030.990.991E-40.9990.998IE-50.99970.9998IE-8搜索过程最优点(11)初始点(-1 1)潴'心严坐标轮换法-坐标轮换法的迭代过程 如图，以二次函数为例。坐标轮换法任取一初始点X。作为第一轮的始点xj,先沿第 一坐标轴的方向6作一维搜索，用一维优化方法确 定最优步长aF，得第一轮的第一个迭代点 X11=xo1+ a11e1,然后以xj为新起点，沿第二坐 标轴的方向6作一维搜索，礎定步长a，得第一 轮的第二个迭代点x/zzx/4- aFd第二轮迭代，需要xi1<-xo1xx2<-x02+x22=xx2+ a22 e2

14、依次类推，不断迭代，目标函数值不断下降, 最后逼近该目标函数的最优点。寻坐标轮换法二.终止准则可以采用点距准则或者其它准则O注意：若釆用点距准则或函数值准则，其中釆用的点应该是一轮迭代的始点和终点，而不是某搜索方 向的前后迭代点。鲍威尔方法一方向加速法坐标轮换法三、坐标轮换法的流程图K=1i鲍威尔方法一方向加速法i鲍威尔方法一方向加速法坐标轮换法U!例题i鲍威尔方法一方向加速法五.小结坐标轮换法程序简单，易于掌握。但是计算效率比牧低，尤其是当优化问题的维数较高时更为严重。一般把此 种方法应用于维数小于10的低维优化问题。对于目标函数存在“脊线”的情况，在脊线 的尖点处没有一个坐标方 向可以使函

15、数值下降，只 有在锐角所包含的范围搜 索才可以达到函数值下降 的目的，故坐标轮换法对 此类函数会失效。鲍威尔方法是直接利用函数值来构造共轨方向 的一种共轨方向法。这种方法是在研究具有正定矩阵 G的二次函数1 ,f(x) = xtGx + BT x + C的极小化问题时形成的。其基本思想是在不用导数的 前提下，在迭代中逐次构造砒共轨方向。一、共轨方向的概念设G为一正定对称矩阵，若有一组非零向量勻， W，$满足STGSj=O (i工j),则称这组向量 关于矩阵强钝。共轨方向对于构造一种有效的算法是很重要的。 以正定二元二次函数为例，我们进行探讨。.普鲍威尔方法正定的二元二次函数的等值线为一组椭圆，

16、任 选初始点W沿某个下降方向夕作一维搜索，得疋X】+a。此时，点疋的梯度必然与方向夕唾直，即有d s1NS7VfCxpSP歹与某一等值线相切于疋点O 下一次的迭代，若选择负梯 度方向为搜索方向，将产生 锯齿现象。为避免锯齿的产 生，我们取迭代方向歹直指 极小点X*,如图所示。i鲍威尔方法若选定这样的方向，则对于二元二次函数只需 进行夕和歹两次搜索就可以求得极小点X*,即x=xx+a AS3由于 Vf(x1)=Gx1+b9 当x1a 09 由于x讨 (x)的极小点，应满足极值必要条件，故 Vf(x*)=Gx*+b=O,即Vf(x*)=G (x+a+b= Vf(x1)+ a S1=0等式两端同乘以

17、(刃7；得(歹)TG9=0,故两个向 量歹、歹是G的共轨向量。因此，若要使第二个迭代点成为正定二元二次 函数的极小点，只要使两次一维搜索的方向歹、歹关 于函数的二阶导数矩阵G共轨就可以了。宀鲍威尔方法一、扌上掠方向的牛成一、潑#、卅宀为从不同点出发，沿同一方向9进行 一维搜索得到的两个极小点，如图所示。根据梯度和 等值面的性质，和卅 哂点处的梯度严 之间存在如下关系(9叶=0 (9)丁严=0 又因为卅卅宀两点处的梯度 可表示为gk=Gxk+b 严 uGZ+b 两式相减，得 g+1 &=6(疋+丄屮)因此有(Sf(Si)T彳卅乜49=0若取方向少"+",则网列妙轨。这

18、说 明只要沿方向9分别对函数作两次一维搜索，得到两 个极小点，则这两点的连线方向就是与。共钝的方 向。鲍威尔方法三、鲍威尔基本算法如图所示，以三维二次目标函数的无约束优化问题为例。鲍威尔基本算法的步骤: 第一环基本方向组取单位坐标矢量系8丄e2e3 en,沿这些方向依次作一维搜索，然治将始末两点相连作为新生方向，再沿新生方向作一维搜索，完成第一环的迭代。以后每环的基本方向组是将 上环的第一个方向淘汰，上环的新生方向补入本环的 最后而构成。n维目标函数完成n环的迭代过程称为 一轮。从这一轮的终点出发沿新生方向搜索所得到的 极小点，作为下一轮迭代的始点。这样就形成了算法 的循环。鲍威尔方法鲍威尔基本算法的缺陷，可能在某一环迭代中出现基本方向组为线性 相关的矢量系的情况。如第k环中，产生新的方向:S=x#xJ(=aS+ +a$S卜式中，S' S$、3/为第k环基本 方向组矢量，a/、af、a/为个方向的 最优步长。若在第k环的优化搜索过程中出现af =0.则 方向5*表示为冷、S$、5；啲殘性组合, 以后的各次搜索将在降维的空间进行，无法得到n 维空间的函数极小值，计算将失败。鲍威尔方法如图所示为一个三维优化问题的示例，设第一环中al =O9则新生方向与e2、e戏面，随后的各 环方向组中，各矢量必在 该平面内，使搜索局限于 二维空间，不能得到最优