优化方法数学基础.ppt

2 优化方法数学基础,优化设计极值 多变量、多约束非线性优化,高等数学极值理论是求解基础，但是不能直接求出最优解。对多变量约束优化问题的求解方法所涉及的数学概念及有关理论进行补充和扩展。介绍二次函数、多元函数的梯度、函数的近似表示以及极值条件和数值迭代解法等基本概念。,一、正定二次型,二次函数,XTHX二次型，H二次型矩阵 正定和负定矩阵。对于所有非零向量 XTHX 0，矩阵正定 XTHX=0，矩阵半正定 XTHX 0，矩阵负定 XTHX=0，矩阵半负定 XTHX=0，矩阵不定,写成向量形式,一、正定二次型,线性代数可知，矩阵H的正定性除用定义判断外，还可以用矩阵的各阶主子式进行判别 主子式包含第一个元素在内的左上角各阶子矩阵所对应的行列式。,一、正定二次型,二次型矩阵H正定正定二次函数。正定二次函数性质：正定二次函数的等值线或等值面是一族同心椭圆(或同心椭球)。椭圆族或椭球族的中心是极小点。函数椭圆族等值线与一组平行线切点的连线通过椭圆中心；反之，过椭圆中心的直线与各椭圆的交点所作椭圆的切线是一组平行线。,非正定二次函数在极小点附近的等值线或等值面近似于椭圆或椭球。求极值时，近似按二次函数处理，即用二次函数的极小点近似函数的极小点，反复进行，逐渐逼近函数的极小点。,一、正定二次型,二、方向导数和梯度,1方向导数 导数是描述函数变化率的数学量。微分理论知，一元函数在点xk的一阶导数表示函数在该点的变化率。,二元函数在某点沿坐标方向xi的变化率用函数对该坐标变量的一阶偏导数表示。,二、方向导数和梯度,函数沿任一方向的变化率，用方向导数描述。二元函数在X（k）处沿与坐标轴夹角为i的 S方向的变化率，即方向导数,二、方向导数和梯度,二、方向导数和梯度,多元函数在X（k）处方向导数,梯度；方向S上的单位向量；S的方向角；S的方向余弦,2梯度,函数在点X（k）的梯度是由函数在该点的一阶偏导数组成的向量。,根据矢量代数,2梯度,函数在某点沿方向S的方向导数等于 该点的梯度在方向S上的投影。,函数梯度性质,(1)梯度方向是函数等值线(或等值面)的法线方向 当S方向与该点的梯度相垂直时，函数在该点沿S的方向导数等于零。,说明方向位于该点等值线的切线上(或等值面的切平面内)函数在该点的梯度方向必定是该点等值线或等值面的法线方向。,函数梯度性质,(2)(负)梯度方向是函数值(下降)增长最快的方向 当S方向与梯度夹角为零时，方向导数达到最大值,函数在一点的梯度方向是该点方向导数最大的方向(函数值增长最快的方向)；与梯度相反的方向称为负梯度方向。函数在一点的负梯度方向是该点函数值下降最快的方向。与梯度成锐角的方向是函数值上升的方向，与梯度成钝角的方向是函数值下降的方向。,函数梯度性质,(3)各点函数梯度不同。梯度大小就是梯度的模长。(4)梯度是函数在一点邻域内局部性态的描述。(5)极值点处梯度为零 梯度为零不一定是极值点。,函数梯度,例 求函数f(X)=(x1-2)2+(x2-1)2在点X(1)=3,2T和X(2)=2,2T处的梯度并作图表示。,解 梯度,三、多元函数的近似表示,一元函数在点xk的邻域内n阶可导，可在该点的邻域内泰勒展开,多元函数若在点X（k）作泰勒展开，展开式一般取三项，形式与一元函数展开式的前三项相似，即,三、多元函数的近似表示,二阶导数矩阵海赛(Hessian)矩阵，n阶对称矩阵,取泰勒展开式的前两项，得到泰勒线性近似式,例 用泰勒展开函数f(X)=x13-x23+3x12+3x22-9x1，在点X(1)=1,1T简化成线性函数和二次函数。,三、多元函数的近似表示,解 函数在点X(1)的函数值、梯度和二阶导数矩阵,三、多元函数的近似表示,简化线性函数,简化二次函数,将X(1)代入简化所得的线性函数和二次函数中，其函数值等于-3，与原函数在点X(1)的值相等，说明简化正确。,四、函数的极值,无约束优化问题的极值只取决于目标函数本身性态，约束优化问题的极值不仅与目标函数的性态有关，且与约束函数的构成相关。,(一)无约束问题极值条件 高等数学知，一元函数在点xk 取得极值：必要条件是函数在该点的一阶导数等于零，充分条件是二阶导数不等于零。,四、函数的极值,多元函数在点X(k)取得极值的必要条件：函数在该点的所有方向导数等于零函数在该点的梯度等于零。,多元函数在点X(k)取得极小值条件：函数在该点的梯度为零，二阶导数矩阵为正定,展开成泰勒二次近似式,四、函数的极值,例 求函数f(X)=x12+x1x2+x22-6x1-3x2的极值。解,(二)约束问题极值条件(后述),五、数值迭代算法,最优化方法基本思想 消去法和爬山法 消去法处理单变量函数极值问题时有效 对于多维函数，消去的不是线段，而是平面(两变量函数)、立体(三变量函数)或多维空间的一部分，使求解问题变得复杂 爬山法上山或下山 极大值上升算法；极小值下将算法 每前进一步，函数值有所改善，同时为下一步移动方向提供有用信息数值迭代算法基本思想。,五、数值迭代算法,按照某一迭代格式，从一个初始点X(0)出发逐步产生一个点列 X(0)，X(1)，X(k)，X(k+1)，点列所对应的目标函数值呈下降趋势，构成此点列的方法就是下降迭代算法。,点列的极限就是目标函数的极小点,1下降迭代算法基本格式,迭代点列递推方法,为使每一次迭代都能让目标函数获得最大的下降量，新的迭代点X(k+1)通常取作方向S(k)上的一维极小点，对应的步长记作k，称最优步长因子。,下降迭代算法基本格式：给定初始点X(k)和收敛精度；选取搜索方向S(k)；确定步长因子k，得到迭代点X(k+1)；收敛判断：若满足收敛精度，以X(k+1)作为最优点，终止计算；否则，以X(k+1)作为新起点，转进行下一轮迭代。,1下降迭代算法基本格式,下降迭代算法的构成需要解决基本问题：选择搜索方向 不同的搜索方向，构成不同的下降迭代算法；确定步长因子 一般通过一维搜索法取得最优步长因子；给定收敛准则 用以判断迭代点是否能够作为近似的最优点。,2收敛准则,判断迭代点与精确解近似程度的方法收敛准则。(1)点距准则(坐标准则)一般来说，迭代点向极小点的逼近速度是逐近变慢的，越接近极小点，相邻迭代点间的距离越短。当相邻两迭代点间的距离充分小，即有,(2)函数值准则 迭代点接近极小点，迭代点距离接近，函数值也越接近。将相邻的函数值之差作为判断极小点的准则函数值准则。,2收敛准则,(2)函数值准则,2收敛准则,(3)梯度准则 梯度等于零的点是极小点，梯度近似于零的点则必定是近似极小点。当,准则选用：优化方法、函数性态。,3算法的收敛性,点列向极小点逼近的速度算法的收敛速度算法的收敛性和收敛速度定义,p点列 的收敛阶，正实数；q 收敛比 对于与迭代次数k无关的常数 q(0,1)，如果存在一个大于零的数p使公式成立，则 p=1，线性收敛性(线性收敛速度)；p=2，二次收敛性；1p 2，超线性收敛性。,3算法的收敛性,算法的收敛性也可以根据算法对二次函数的求解能力加以判断。对于正定二次函数，如果算法能在有限次迭代中得到极小点，称此算法具有二阶收敛性。,解题所需迭代计算过程的长短，主要取决于：问题的性态；所用的优化方法；终止准则和收敛精度。从工程实际出发，采用适当终止准则和收敛精度,