现代设计方法-优化设计2-数学基础

现代设计方法优化设计部分黄正东，吴义忠2015年本章主要内容优化设计概述优化设计的数学基础一维探索优化方法无约束优化方法约束问题优化方法优化设计若干问题优化设计概述优化设计的数学基础一维探索优化方法无约束优化方法约束问题优化方法优化设计若干问题函数的泰勒展开目标函数无约束极值条件目标函数的凸性约束问题的极值条件（模型的性质与最优解的表征）优化设计的数学基础优化设计的本质：求极值。为便于对多变量问题进行数学分析和求解，往往需要采用线性函数和二次函数替代简化目标函数。（1）一元函数的f(X)泰勒展开：若f(x)在含有x(0)处的某个开区间内直到（n+1）阶可导，只要开区间（a,b）足够小,则该函数在（a,b）内x(0)点处的二阶泰勒展开式为（n=1)：(0)(0)(0)(0)(0)21()()'()()''()()2fxfxfxxxfxxx函数的泰勒展开（2）二元函数f(x1，x2)的泰勒展开：21xxX)0(21)0()(XXxfxfXf222122212212)0(2)(xfxxfxxfxfXf函数的泰勒展开][)(][21])[()0()0(2)0()0()0()0(XXXfXXXXXfXfXfTT12nxxXx(0)1(0)2()nXXfxfxfXfx(0)222211212222(0)2212222212()nnnnnnXXfffxxxxxffffXxxxxxfffxxxxxx（3）多元函数f(x1，x2,…xn)的泰勒展开：(0)(0)(0)(0)2(0)(0)()()()[]1[]()[]2TTfXfXfXXXXXfXXX(0)()fX2(0)()fx:目标函数f(x)在点x(0)的所有一阶偏导数组成的矩阵向量(一阶导数矩阵向量或梯度）:目标函数f(x)在点x(0)的所有二阶偏导数组成的矩阵(二阶导数矩阵或海色Hesssian矩阵，记作H(x），为n×n阶对称矩阵）f(x(2))f(x(1))函数Hessian矩阵例子优化设计的首要工作是判断极值的存在性，如不存在极值，优化设计无意义。（1）无约束目标函数极值的存在性目标函数为一元函数f(x)f(x)在点x(0)处有极值的充要条件为：(0)(0)'()0,''()0fxfx时，有极小值；时，有极大值。(0)(0)'()0,''()0fxfx目标函数无约束极值条件一元函数的极值点极小值点0xyy=f(x)x00xyy=f(x)x00yy=f(x)x0极大值点非极值点目标函数为多元函数f(x1，x2,…xn)f(X)在点X(0)处有极值的充要条件为：(0)()0XXfX（必要条件）(0)()XXHx（充分条件）正定时，有极小值；(0)()0XXfX（必要条件）(0)()XXHx（充分条件）负定？时，有极大值；二次函数与正定矩阵正定条件负定条件XXff例：试证明函数在点处具有极小值。(0)[2,4]TX1422212121()245fXxxxxxx321121112124424,22ffxxxxxxxxx解：22222121221122121242,4,2ffffxxxxxxxxx将代入得(0)[2,4]TX2121121348124240,8242xxxffHxxxH(X(0))正定，目标函数在（2,4）处具有极小值。目标函数的极值点一般是相对于它附近的局部区域中的各点而言的，目标函数在其整个可行区域中，有时可能存在许多个极值点，优化设计时应力求找到多个极值点中的最小值点，即全局最优点或整体最优点，其它非最小值的极值点称为局部最优点或相对最优点。凸性：单峰性，目标函数若为凸性，极值点只有一个，即为全局最优点。目标函数的凸性凸集：假设在n维欧式空间Rn中有一个集合D，即，若D内任意两点X(1),X(2)之间的连接直线都属于集合D,则D为n维欧式空间内的一个凸集，否则为非凸集。如果将X(1),X(2)之间的连接直线用表达，则凸集的数学表达式为：(1)(2)(1)XXXD()nDR(1)(2),XXD(1)(2)(1)XXX若则x2x1x(2)x(1)x2x1x(2)x(1)凸集非凸集凸集的几何特征：其任意两点连线上的一切点都位于这个几何内。凸函数：凸函数的数学表达式为：(1)(2)(1)(2)(1)(2)()((1))()(1)(),,fXfXXfXfXXXXDf(x)x2x1xf(x2)f(x1)21)1(xx)()1()(21xfxf))1((21xxf0≤a≤1判断函数f(x)为凸函数的充要条件：方法1：若函数f(x)在D上具有一阶的连续导数，对任意两点x(1),x(2),f(x)为凸函数的充要条件是:(2)(1)(2)(1)(1)()()()()fxfxxxfx恒成立方法2：若函数f(X)在D上具有二阶的连续导数，则f(X)为凸函数的充要条件是:H(X)处处半正定凸规划：经典局部优化的基础对于非线性规划若其中f(x)和gu(x)均为凸函数，则这样的规划问题称为凸规划。min(),x..()0,1,2,...,nufxRstgxum目标函数有约束极值还是无约束极值，主要取决于约束条件对极值和极值点的影响。同样的目标函数对于不同的约束条件，可能出现不同的最优值和最优点，其原因在于不同的约束条件限制了设计变量不同的取值范围。有约束最优问题需要解决的问题判断约束极值点存在的条件；判断找到的极值点是全局最优点还是局部最优点。约束问题的极值条件A.无约束最优点为可行域的内点，此时目标函数的最优点就是约束问题的最优点；01x2x约束最优点和无约束最优点的相互关系：B.无约束最优点在可行域外，约束问题的最优点是约束边界上的一点，该点是约束边界与目标函数一条等值线（面）的切点；1x02x对于等式约束问题等式约束的极值条件pvXhtsXfv,2,1,0)(..)(min可以建立拉格朗日函数pvvvXhXfXL1)()(),(为拉格朗日向量，，，（其中Tn)21，即可得到令0),(XL0)()(*1*XhXfpvvv这就是等式约束问题在点X*取得极值的必要条件，它的含义是：在等式约束问题的极值点上，目标函数的负梯度等于诸约束函数在该点梯度的线性组合。对于不等式约束问题不等式约束的极值条件muXgtsXfu,2,1,0)(..)(min可以通过引入m个松弛变量将不等式约束变成等式约束),2,1(0muxunmuxXgtsXfunu,2,1,0)(..)(min2muunuuxXgXfXXL12)()(),,(然后类似地建立拉格朗日函数为松弛变量组成的向量)，，，（21TmnnnxxxX020)(0)()(0),,(21unuununuumuuuxxLxXgLXgXfXLXXL，即令；0因此，必有相反）。与目标函数的梯度方向(方向指向可行域外梯度，也就是说约束函数的0为束。由于约束条件形式的起作用约为点0)(上，0)(在约束边界，这说明点0)(和0，则必有0Ⅰ）若某些***uuuuunuXXgXgXXgx1x02x0)(2Xg0)(1Xg)(*2Xg)(*1Xg)(*Xf*X020)(0)()(21unuununuumuuuxxLxXgLXgXfXL无约束最小值点在可行域外1x02x*X0)(1Xg0)(2Xg)(*1Xg)(*2Xg0)(，则必有0Ⅱ）若全部*Xfu以上两点可以统一用一个条件来表示：020)(0)()(21unuununuumuuuxxLxXgLXgXfXL无约束最小值点在角点00)()(则必有是极值点，个起作用约束，且的是点)(0)(设)()()()(iIikiikkkkikXgXfXnXIiXgK-T（Kuhn-Tucker)条件：。此时线性组合起作用约束梯度的非负的负梯度等于该点所有，要么目标函数在该点此时的极值点，要么是函数若点)0()0(0)()()()(iikkXfXfX如果有等式约束呢？满足K-T条件的点称为K-T点。对于一般非线性规划问题，K-T点一定是约束极值点，但却不一定是全域最优点。一般采用多初始点下的极值点是否都逼近同一点（可看成最优点）的近似方法来判别。但是，对于目标函数为凸函数，可行域为凸集的凸规划问题，K-T点一定是全域最优点。例:用K－T条件判断点是否是下列约束优化问题的约束极值点。0)(0)(04)(..)3()(min132222112221xXgxXgxxXgtsxxXfTX)02(*使上式成立0判断是否存在.30)()(令.2)(，)(，)(求.1****uuukuXgXfIuXgXfKKT方法一般过程：1.将X*带人全部约束方程，包括等式和不等式，判断是否满足约束，并找出起作用约束；2.求梯度；3.求起作用约束函数的梯度；4.建立方程；5.求解系数λi;6.如果系数都大于0，则X*为KT点。00)()()()(iIikiikkXgXf作业P58:2-5P59:2-7至2-9