第2章经典最优化方法

1、第章第章经典最优化方法经典最优化方法内容介绍内容介绍u微分学中求极值u无约束最优化问题u常用微分公式u凸集与凸函数u等式约束最优化问题u不等式约束最优化问题u变分学中求极值微分学中求极值微分学中求极值一元函数的极值1.一元函数极值的求法与判别必要条件：设函数 在点 处具有导数，且在 处 取得极值，则该函数 在 处的导数 这里有个前提，即函数 在设计区间要连续可导。凡是满足上述的点都叫函数 的驻点。我们可知驻点并不完全是极值点，它还有拐点，当然，极值点必定是驻点。因此，还必须有判别函数极值的更充分条件。( )f x0 x( )f x0 x( )f x0 x()0fx( )f x( )f x微分学

2、中求极值微分学中求极值 ( )0,0,10( )20( )fxfxfxf xfxf x充分条件：当函数的一阶导数二阶导数并且）时，函数取极大值，有极大值点；）时，函数取极小值，有极小值点；找出函数的极值点，函数的极值自然容易计算出来。微分学中求极值微分学中求极值 *2.*2.*2.12!12!00000 xf xf xfxxfxxf xfxxfxxf xfxxfxf xfxf xfxfxxfxx 在 附近展成台劳极 = =由此可见： 当时，函数是单调上升；当时，函数函数是单调上升； 当 时，若，则 为极小点，若，则 为极大点微分学中求极值微分学中求极值二元函数的极值2*212222211222

3、222122(1)1()()2(),(),()TTTfff Xf XXXXXXfffgf XXxxffxx xfAf XXffx xxf X 二元函数的台劳展开式其中叫梯度，是一阶偏导向量。叫赫森矩阵，是二阶偏导向量，对称方阵。故台劳展开式也可写成*1()2TTf XgXX A X微分学中求极值微分学中求极值1111(2)( )( )( )ff Xf XXgxgxf Xxx梯度与方向导数梯度的定义：梯度是函数的一阶偏导数组成的向量。记为：g梯度 在 方向上的投影，即 在 方向上的分量，就是函数在 方向的偏导数，即函数在 方向的变化率。1122120( )(,)( , )( )f XXf xx

4、xxf x xf X方向导数的定义：二元函数沿任意 方向取长度为的点，该点的函数的极限 lim存在，就称极限值为函数在该点沿 方向的方向导数微分学中求极值微分学中求极值1.().( )3.0,04.f Xf xg由梯度与方向导数的概念，我们可以得到：函数在该点沿 方向的方向导数等于梯度g沿 方向的 投影。2.梯度g在自身方向上的投影最大，最大值为 g 因而，函数沿梯度方向上升最快。梯度 在与自身垂直的方向上投影为 所以函数沿与梯度垂直方向变化最慢，变化率为 ；与梯度成锐角方向，函数是上升的；与梯度成钝角方向，函数是下降的。微分学中求极值微分学中求极值(3)赫森矩阵（Hesse）222()3.0

5、0TTfAf XXAX A XX A X 定义：赫森矩阵，是二阶偏导数矩阵，且是2 2对称方阵 ，用记号A代表性质：1.A是目标函数的二阶偏导数，是梯度的一阶偏导数。 2.A是对称方阵。 为正定的条件是：各阶主子式大于零。 4.若矩阵A正定，则二次型，若矩阵A负定，则二次型2( )( ) 0( )f Xgf XAf X(4)二元函数极值的充分条件定理：二元函数存在极值点的充分条件是：梯度。且正定，则有极小点。反之，则有极大点。无约束最优化问题无约束最优化问题由上一节可知，对于无约束最优化问题，其数学模型中只有目标函数采用解析法求解，其求解过程可以归结为一下三个步骤： 1.令梯度g=0，解出各个

6、驻点。 2.计算各驻点的矩阵 A,判断矩阵A正定或负定，得到相对应的极小点 或极大点； 3.计算极值。 ()f XminXnE常用微分公式常用微分公式CC(X X)(X QX)TTTTBBB对于多元函数，在求解运算过程中，常用到以下微分公式：1.0式中 为常数； 0为n维0向量；2.0式中B为n维常向量； 0为n*n阶矩阵；3.XB式中B为n维常向量； X为n维变向量； X为标量4.2X；5.2QX；6. X=I； 凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数

7、凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数凸集与凸函数等式约束最优化问题等式约束最优化问题等式约束最优化问题的数学模型式这里介绍两种比较常用的方法：消元法和拉格朗日乘子法。(). .( )0if XS t g xminnXE1,2,.,im等式约束最优化问题等式约束最优化问题121212212111.( )( , ). ( , ) 0( , ) 0( ),( ) min ( , ( )f Xf x xStg x xg x xxh xxf Xf x h x消元法消元法就是将等式约束最优化问题转化为无约束最优化问题的一种最为简单的方法，这里以二

8、维为例，对其方法加以说明：已知问题的数学模型为min先由约束方程，解出即消去 ；然后把所得的表达式代入目标函数中，便可得到无约束的极值问题min等式约束最优化问题等式约束最优化问题2.拉格朗日乘子法消元法的特点在于改写约束条件，消除约束方程。但是，当等式约束是多维，高次或非线性时，这种方法就显得十分烦琐。拉格朗日乘子法是引进一个代定系数，构造一个新的无约束条件的目标函数，而使数学变换过程简化。这里也以二维为例 。121212121211122212,(,)(,)0000(,)0 xxLxxfxxg xxLLLxxLfgxxxLfgxxxLg xx我 们 可 以 得 到 三 元 函 数 ，的 三

9、 个 偏 导 数 都 等 于 零 的 联 立 方 程 ， 若 引 入 函 数，令 其 偏 微 分 均 等 于 ， 有于 是 可 以 得 到等式约束最优化问题等式约束最优化问题X()X()()()()Lf XLf Xg Xf Xg X由此说明，可通过求引入的函数称之为拉格朗日函数，的无约束极值，求解等式约束条件下目标函数 的极值。即称之为拉格朗日乘子法。可用如下式子表示 ： ， 其中 的几何意义表示为物理意义为：表示随着约束条件的微小变化，会使目标函数引起变化的一种比率，又称灵敏度。等式约束最优化问题等式约束最优化问题221212121212122212121212121112221()(,)1

10、 046 0. .(,)80X()()1 046 0821 00fXfxxxxx xxxS t gxxxxLfXgXxxx xxxxxLfgxxxxxLfgxxx例： 用 拉 格 朗 日 法 求 解m i n解 ： 1 . 列 出 拉 格 朗 日 函 数 ， （）2 . 求 解 偏 导 数 方 程 式211212*1*2*12*240(,)803 .534 .,5 , 3()1 7TTxxLgxxxxxxXxxfX解 以 上 联 立 方 程 式 ， 得 到 3由 于 无 约 束 的 拉 格 朗 日 函 数 的 极 值 点 就 是 原 目 标 函 数 的 极 值 点 ， 即则 原 目 标 函 数

11、 的 极 小 值 可 以 算 出 为。不等式约束最优化问题不等式约束最优化问题不等式约束的最优化问题的解析法与前面处理的基本思路相类似，也是构造一个包含原目标函数与约束函数的新目标函数。只是具体的构造方法不同，这里处理的也是二维问题 原问题的数学模型为引入一个松弛变量r,把约束条件改为等式约束，即 1212()( ,). . ( ,)0f Xf x xS t g x xmin212( ,)0g x xr2X()()Lvf Xg Xv构造一个拉格朗日函数， ，不等式约束最优化问题不等式约束最优化问题2111222212*00( ,)020,(),vLfgxxxLfgxxxLg x xvLvvXf

12、 X 由于引入的松弛变量是以 的形式出现，这就保证了引入项为非负值，能使不等式转化为等式，于是，对新构成的拉格朗日函数可列出其极值条件四个未知数四个方程，可以求解得到成为原问题的最优解，最优值。等式约束最优化问题等式约束最优化问题说明：从这个手算的约束最优化问题来看，拉格朗日乘子法使简单而易算的，但终归只是一种经典算法。当最优化问题为大型非线性问题时，要解高次联立方程组；另外，当拉格朗日函数为非凸函数时，求得得最优点可能出现鞍点，导致寻优过程失败。不过这种方法在约束非线性最优化问题的求解中仍有意义和应用。变分学中求极值变分学中求极值变分学是研究确定泛函的极值或者说驻值的学科。而泛函定义为一个函数或数个函数的函数。因此，变分学可用于求解隐函数及其动态优化问题，此外，变分学在求解某些力学，光学及最优控制中也很有用。21122A,(), (),dxduAFxudxxxuu xuu xu21xx1无约束的变分理论中的一个简单问题可叙述如下：求函数u(x)以使极小化泛函=F(x,u,u ,u )式中， 和可称为泛函， 是独立的变量，上式中的积分定义域区间或者说范围在内。设 在边界上的值已经给定为则称它们式此问题的边界条件。可用于求解此式问题的方法之一及步骤