第2章经典最优化方法

第２章经典最优化方法内容介绍微分学中求极值无约束最优化问题常用微分公式凸集与凸函数等式约束最优化问题不等式约束最优化问题变分学中求极值微分学中求极值•一元函数的极值1.一元函数极值的求法与判别必要条件：设函数在点处具有导数，且在处取得极值，则该函数在处的导数这里有个前提，即函数在设计区间要连续可导。凡是满足上述的点都叫函数的驻点。我们可知驻点并不完全是极值点，它还有拐点，当然，极值点必定是驻点。因此，还必须有判别函数极值的更充分条件。()fx0x()fx0x()fx0x'()0fx()fx()fx微分学中求极值''''''()0,0,10()20()fxfxfxfxfxfx'充分条件：当函数的一阶导数二阶导数并且）时，函数取极大值，有极大值点；）时，函数取极小值，有极小值点；找出函数的极值点，函数的极值自然容易计算出来。微分学中求极值**'*''*2.*'*''*2.*'*'*'*'*''**''**2.12!12!00000xfxfxfxxfxxfxfxxfxxfxfxxfxfxfxfxfxfxxfxx在附近展成台劳极==由此可见：当时，函数是单调上升；当时，函数函数是单调上升；当＝时，若，则为极小点，若，则为极大点微分学中求极值•二元函数的极值2***212222211222222122(1)1()()2(),,(),()TTTfffXfXXXXXXfffgfXXxxffxxxfAfXXffxxxfX二元函数的台劳展开式其中叫梯度，是一阶偏导向量。叫赫森矩阵，是二阶偏导向量，对称方阵。故台劳展开式也可写成*1()2TTfXgXXAX微分学中求极值1111(2)()()()ffXfXXgxgxfXxx梯度与方向导数梯度的定义：梯度是函数的一阶偏导数组成的向量。记为：g梯度在方向上的投影，即在方向上的分量，就是函数在方向的偏导数，即函数在方向的变化率。1122120()(,)(,)()fXXfxxxxfxxfX方向导数的定义：二元函数沿任意方向取长度为的点，该点的函数的极限lim存在，就称极限值为函数在该点沿方向的方向导数微分学中求极值1.().()3.0,04.fXfxg由梯度与方向导数的概念，我们可以得到：函数在该点沿方向的方向导数等于梯度g沿方向的投影。2.梯度g在自身方向上的投影最大，最大值为g因而，函数沿梯度方向上升最快。梯度在与自身垂直的方向上投影为所以函数沿与梯度垂直方向变化最慢，变化率为；与梯度成锐角方向，函数是上升的；与梯度成钝角方向，函数是下降的。微分学中求极值(3)赫森矩阵（Hesse）222×()3.00TTfAfXXAXAXXAX定义：赫森矩阵，是二阶偏导数矩阵，且是22对称方阵，用记号A代表性质：1.A是目标函数的二阶偏导数，是梯度的一阶偏导数。2.A是对称方阵。为正定的条件是：各阶主子式大于零。4.若矩阵A正定，则二次型，若矩阵A负定，则二次型2()()0()fXgfXAfX(4)二元函数极值的充分条件定理：二元函数存在极值点的充分条件是：梯度＝。且正定，则有极小点。反之，则有极大点。无约束最优化问题•由上一节可知，对于无约束最优化问题，其数学模型中只有目标函数采用解析法求解，其求解过程可以归结为一下三个步骤：1.令梯度g=0，解出各个驻点。2.计算各驻点的矩阵A,判断矩阵A正定或负定，得到相对应的极小点或极大点；3.计算极值。()fXminXnE常用微分公式CC(XX)(XQX)TTTTBBB对于多元函数，在求解运算过程中，常用到以下微分公式：1.＝0式中为常数；0为n维0向量；2.＝0式中B为n维常向量；0为n*n阶矩阵；3.X＝B式中B为n维常向量；X为n维变向量；X为标量4.＝2X；5.＝2QX；6.X=I；凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数等式约束最优化问题等式约束最优化问题的数学模型式这里介绍两种比较常用的方法：消元法和拉格朗日乘子法。()..()0ifXStgxminnXE1,2,...,im等式约束最优化问题121212212111.()(,)..(,)0(,)0(),()min(,())fXfxxStgxxgxxxhxxfXfxhx消元法消元法就是将等式约束最优化问题转化为无约束最优化问题的一种最为简单的方法，这里以二维为例，对其方法加以说明：已知问题的数学模型为min＝先由约束方程＝，解出即消去；然后把所得的表达式代入目标函数中，便可得到无约束的极值问题min等式约束最优化问题2.拉格朗日乘子法消元法的特点在于改写约束条件，消除约束方程。但是，当等式约束是多维，高次或非线性时，这种方法就显得十分烦琐。拉格朗日乘子法是引进一个代定系数，构造一个新的无约束条件的目标函数，而使数学变换过程简化。这里也以二维为例。121212121211122212,,(,)(,)0000(,)0xxLxxfxxgxxLLLxxLfgxxxLfgxxxLgxx我们可以得到三元函数，的三个偏导数都等于零的联立方程，若引入函数，令其偏微分均等于，有于是可以得到＝＝等式约束最优化问题X()X()()()()LfXLfXgXfXgX由此说明，可通过求引入的函数称之为拉格朗日函数，的无约束极值，求解等式约束条件下目标函数的极值。即称之为拉格朗日乘子法。可用如下式子表示：，＝－其中的几何意义表示为＝物理意义为：表示随着约束条件的微小变化，会使目标函数引起变化的一种比率，又称灵敏度。等式约束最优化问题221212121212122212121212121112221()(,)10460..(,)80X()()1046082100fXfxxxxxxxxStgxxxxLfXgXxxxxxxxxLfgxxxxxLfgxxx例：用拉格朗日法求解min＝解：1.列出拉格朗日函数，＝－＝－（）2.求解偏导数方程式＝－－＝＝211212*1*2***12*240(,)803.534.,5,3()17TTxxLgxxxxxxXxxfX－－－＝＝解以上联立方程式，得到＝＝3由于无约束的拉格朗日函数的极值点就是原目标函数的极值点，即则原目标函数的极小值可以算出为＝。不等式约束最优化问题不等式约束的最优化问题的解析法与前面处理的基本思路相类似，也是构造一个包含原目标函数与约束函数的新目标函数。只是具体的构造方法不同，这里处理的也是二维问题原问题的数学模型为引入一个松弛变量r,把约束条件改为等式约束，即1212()(,)..(,)0fXfxxStgxxmin＝212(,)0gxxr2X()()LvfXgXv构造一个拉格朗日函数，，不等式约束最优化问题2111222212**00(,)020,(),vLfgxxxLfgxxxLgxxvLvvXfX由于引入的松弛变量是以的形式出现，这就保证了引入项为非负值，能使不等式转化为等式，于是，对新构成的拉格朗日函数可列出其极值条件＝＝＋四个未知数四个方程，可以求解得到成为原问题的最优解，最优值。等式约束最优化问题说明：从这个手算的约束最优化问题来看，拉格朗日乘子法使简单而易算的，但终归只是一种经典算法。当最优化问题为大型非线性问题时，要解高次联立方程组；另外，当拉格朗日函数为非凸函数时，求得得最优点可能出现鞍点，导致寻优过程失败。不过这种方法在约束非线性最优化问题的求解中仍有意义和应用。变分学中求极值变分学是研究确定泛函的极值或者说驻值的学科。而泛函定义为一个函数或数个函数的函数。因此，变分学可用于求解隐函数及其动态优化问题，此外，变分学在求解某些力学，光学及最优控制中也很有用。'21122A,,(),(),dxduAFxudxxxuuxuuxu21x'''x1无约束的变分理论中的一个简单问题可叙述如下：求函数u(x)以使极小化泛函=F(x,u,u,u)式中，和可称为泛函，是独立的变量，上式中的积分定义域区间或者说范围在内。设在边界上的值已经给定为则称它们式此问题的边界条件。可用于求解此式问题的方法之一及步骤是：1.选择一系列试验解u(x),并对每一试验解求泛函A值。2.比较不同试验对应的A值。3.此问题的正确解是使泛函A为极值或驻值的那一特定的试验解。如此由一系列试验解中选择正确解的数学步骤称变分学变分学中求极值21212''2'''''''''()()0()00xxxxdFdFdxudxuFdFuudxuFuu我们可以得到Fu上面第一个为给定问题的基本方程，也称欧拉－拉格朗日方程，另外两个为边界条件。谢谢！