现代设计方法-优化设计的理论与数学基础

13.优化设计的理论与数学基础2020/2/181现代设计方法——优化设计2020/2/1821）多元函数的Taylor展开式2）二次齐次函数3）关于优化方法中搜索方向的理论基础4）凸集与凸函数5）最优化问题的极值存在条件现代设计方法——优化设计2020/2/183函数的Taylor展开式nnkknkkkkkRxxxfnxxxfxxxfxfxf))((!1...))((21))(()()()()()(2)()(//)()(/)()(2)(//)(/)(,)(21)()()(kkkkxxxxxfxxfxfxf式中*在实际计算中,常取前三项(二次函数)来近似原函数:1)()1())(()!1(1nknnxxfnR)()(之间与在点xxk式中,一.一元函数的Taylor展开式现代设计方法——优化设计二.多元函数的Taylor展开式2020/2/184TnkkkkxXFxXFxXFXF])(...)()([)()(2)(1)()(TnkxxxXXX...21)(令Tknnkkxxxxxx...2211jinininjjikiikkxxxxXFxxXFXFXF111)(2)()()(21)()()((1)2)(22)(21)(22)(222)(212)(21)(221)(221)(2)(2)()(...)()(.......)(...)()()(...)()()()(nknknknkkknkkkKKxXFxxXFxxXFxxXFxXFxxXFxxXFxxXFxXFXFXH(2)(3)XXHXXXFXFXFkTTkk)(][21)]([)()()()()(梯度海赛(Hessian)矩阵对称矩阵现代设计方法——优化设计二次齐次函数2020/2/185njijiijxxaXF1,)(nnnnnnnnxxxaaaaaaaaaxxx...............]...[2121222211121121AXXT2221212)(cxxbxaxXF2121][xxcbbaxx例：22212121cxxbxxbxax系数矩阵;,0)(,0)1为正定矩阵则恒有对于根据线性代数AXFX.)(,)2称为正定二次型则为正定若XFA现代设计方法——优化设计*矩阵A为正定的充要条件--A的各阶主子式均大于零。2020/2/1860003332312322211312112221121111aaaaaaaaaaaaaa333231232221131211aaaaaaaaaA如为正定，则必有：现代设计方法——优化设计2020/2/187关于优化方法中搜索方向的理论基础1.方向导数一.函数的最速下降方向2.最速下降方向二.共轭方向1.正定二次函数2.共轭方向的基本概念3.构成共轭方向的方法现代设计方法——优化设计2020/2/188XXXFXFSXFkkk)()()()()(lim)()(kXXSX)(kXS1.定义--函数沿指定方向的平均变化率的极限。一)方向导数一.函数的最速下降方向现代设计方法——优化设计2.方向余弦2020/2/189niXXxkii,...,2,1,cos)(121x2xoX)(kX1x2x1coscos:122122)(222)(212)(2221即XXxXXxXXxxkkk现代设计方法——优化设计3.方向导数的计算2020/2/1810nnkkkkxxXFxxXFxxXFXFXFF)(...)()()()()(22)(11)()(()()()1212()()()coscos...coskkknnFXFXFXxxxXXXFXFSXFkkk)()()()()(lim)()(kXX现代设计方法——优化设计2020/2/1811二）最速下降方向TnKKKKxXFxXFxXFXF])(...)()([)()(2)(1)()(因为SXFSXFTkk)]([)()()(于是单位矢量TnS]cos...coscos[21令),cos()()(SFSXFk),cos(SFF现代设计方法——优化设计从上式可得出如下结论：2020/2/1812FSF最优点*最速下降只是局部性质.4）在与梯度垂直的方向（等值线的切线方向）上，函数的变化率为零。2）梯度的模就是沿梯度方向的方向导数，1）方向导数是梯度在指定方向上的投影；3）最速下降方向为等值线（面）的法线方向；负梯度方向是函数的最速下降方向；SXFk)()(),cos(SFF也是最大的方向导数,现代设计方法——优化设计2020/2/1813二.共轭方向CXBAXXXFTT21)(常数阶正定对称矩阵CxxxXbbbBnATnTn......2121*当n=2时，fexdxcxxbxaxXF21222121)(fxxedxxcbbaxx21212122][2112112222()22axbxdxabdFXAXBbxcxexbceC1）矩阵表示一）正定二次函数也适于多元函数AcbbaXF22)(2TB现代设计方法——优化设计2020/2/18142)正定二元二次函数的特点fcxaxF2221.0,,,,caca且必同号故因是椭圆方程且有极小ⅱ)F=f时有极小.此时椭圆缩为一点,即椭圆中心.ⅰ)F的值只影响椭圆的大小,不影响其中心位置---同心;②椭圆方程经坐标轴平移和转动后可去掉一次项和交叉项,故写成下述形式不失一般性:.04,02acba①因函数为正定，故A为正定，即：由于判别式0，无论F(X)取何值,所得方程均为椭圆方程.证：（1）正定二元二次函数的等值线是一族同心椭圆，其中心坐标就是该函数的极小点。AcbbaXF22)(21)()(222221cfFxafFx现代设计方法——优化设计（2）过同心椭圆族的中心作任意直线与椭圆族中任意两椭圆相交，再过两交点所作相应椭圆的切线必相互平行。fcxaxF222121121221022cxaxdxdxdxdxcxaxckacxaxdxdx2112为常量,说明该直线上各椭圆的斜率均相等.)2()1(,XX)2()1(,XX逆命题:设两平行线与同心椭圆族中两椭圆分别相切于点,则过的直线必通过椭圆族的中心.12kxx设过中心的直线为,代入上式得:1x就上式对求导:证:)1(X)1(X)2(X现代设计方法——优化设计二）共轭方向的基本概念2020/2/18160324632422214*几何意义:经过线性变换A后成了与正交的向量.1S2S例：021ASST21,SS21SS和设A为n×n阶正定对称矩阵，是两个n维向量，若存在则称对A共轭。1)定义现代设计方法——优化设计2)共轭方向的性质2020/2/1817*这种性质称为有限步收敛性（亦称二次收敛性）（2）从任意选定的初始点出发，只要依次沿n个共轭方向进行一维搜索，一轮后便可达到n元正定二次函数的极小点。(证明见席少霖:《最优化方法》，P97）nSSS,...,,21（1）若矢量系彼此对正定对称矩阵A共轭，则它们组成线性无关的矢量系；现代设计方法——优化设计三）构成共轭方向的方法2020/2/181821,ll1S)2()1(,XX)1()2(2XXS1S设为平行于的两条直线，则过这两直线上正定n元二次目标函数的极小点的向量和对Hession矩阵A共轭。1S)1(X)2(X2S1l2l现代设计方法——优化设计2020/2/1819证明：CXBAXXXFTT21)(二次函数BAXXF)(其梯度为0)(0)()2(1)1(1XFSXFSTT因分别为两直线上的极小点，故有)2()1(,XX0)]()([)1()2(1XFXFST将上述两式相减0)()1()2(1XXAST0][)1()2(1BAXBAXST021ASST1S)(XF现代设计方法——优化设计2020/2/1820例：对于目标函数，给定，试求出与共轭的方向，并求出目标函数的极小点。2122212)(xxxxXFTS]10[11S2S现代设计方法——优化设计凸集与凸函数XX2X1llllXXXX122凸集非凸集凹集*若X是X1和X2连线上的点，则有一.凸集---若任意两点，对于，恒有，则D为凸集。DXXX21)1(DXX21,:10整理后即得21X)1(XX现代设计方法——优化设计2020/2/1822y)(xfx2xx1xof1f2flxxlxx212,二.凸函数10:)()1()(])1([2121XfXfXXf设f(X)为定义在Rn内一个凸集D上的函数，若对于及D上的任意两点X1,X2,恒有则f(X)为定义在D上的一个凸函数。1.定义llffyf12221)1(ffy现代设计方法——优化设计2020/2/18232.凸函数的基本性质)]()[1()]([])1([2121XFXFXXF)()1()(])1([2121XFXFXXF两边乘上证:由定义（1）设为定义在凸集D上的凸函数，为任意正实数,则也是定义在D上的凸函数。)(XF)(XF现代设计方法——优化设计2020/2/1824)()1()(])1([2111211XFXFXXF)()1()(])1([2212212XFXFXXF证:由定义（2）设、均为定义在凸集D上的凸函数，则+也是定义在D上的凸函数。)(1XF)(2XF)(1XF)(2XF（3）设、均为定义在凸集D上的凸函数，为任意正实数，则也是定义在D上的凸函数。)(2XF)(1XF)()(2211XFXF21,两式相加,整理后可得证.现代设计方法——优化设计2020/2/18253.凸函数的判定}{)(min,...,2,1,0)(piXgiXDXFnRDX若D为凸集，F(x)为定义在D上的凸函数，则此规划为凸规划。对于数学规划问题：4.凸规划凸规划的最优点是唯一的.DX为凸函数的充要条件是对于任意的)X(F.0)(2XF(D为凸集),现代设计方法——优化设计2020/2/18262122212141060)(判断函数xxxxxxXF.是否为凸函数现代设计方法——优化设计最优化问题的极值存在条件2020/2/18270)(0)(///xfxf0)(0)(2XFXFxxfo梯度为零向量海赛矩阵正定2.多元函数具有极小值的充要条件1.一元函数具有极小值的充要条件一.无约束问题的极值存在条件现代设计方法——优化设计2020/2/1828充分条件的简易证明：XXHXXXFXFXFTT)(][21)]([)()(由线性代数可知0)(XH0)(XF因0)(][21)()(XXHXXFXFT故AXXT二次型正定现代设计方法——优化设计2020/2/1829例：求的极小点。4445)(1222121xxxxxXF现代设计方法——优化