第一次基础知识

1、 基基 础础 知知 识识一一. .引言引言二二. .最优化问题实例最优化问题实例三三. .极值最优化问题的经典方法极值最优化问题的经典方法四四. .最优化问题及基本概念最优化问题及基本概念五五. .梯度与梯度与HesseHesse阵阵六六. .TaylorTaylor展开式展开式七七. .凸集与凸函数凸集与凸函数八八. .极小点的判定条件极小点的判定条件九九. .算法及相关概念算法及相关概念十十. .中止条件中止条件十一十一. .收敛速度收敛速度一一. 引引 言言1. 最优化定义最优化定义最优化最优化是从所有可能方案中选择最合理方案以达到最优目是从所有可能方案中选择最合理方案以达到最优目标的一

2、门学科。标的一门学科。（1 1） 达到最优目标的方案：达到最优目标的方案：最优方案最优方案（最优解）（最优解）（2 2） 搜寻最优方案的方法：搜寻最优方案的方法：最优化方法最优化方法最优化问题：最优化问题：寻求某些变量的取值使其符合某些限制条件，寻求某些变量的取值使其符合某些限制条件，并使某个目标函数达到最大值或最小值的问题。并使某个目标函数达到最大值或最小值的问题。 一般的数学形式为：一般的数学形式为：Dxtsxf .)(min其中其中 D 为为可行域可行域。例例. 0.min22 yxtsyxz0| ),(),(.min22 yxyxDyxtsyxzxyO0 yxD2.2.包含内容：包含内

3、容：最优化又称最优化又称数学规划数学规划： LPLP、NLPNLP、DPDP、IPIP 多多目目标标动动态态问问题题非非线线性性规规划划线线性性规规划划有有约约束束问问题题无无约约束束问问题题静静态态问问题题单单目目标标最最优优化化问问题题多参数曲线拟合问题多参数曲线拟合问题例例 1组数值。组数值。的的和和，得到，得到是待定参数。通过试验是待定参数。通过试验和和，其中其中。的函数关系为的函数关系为依赖于温度依赖于温度已知热电阻已知热电阻15 )exp( 321321RtxxxxtxxRtR i it ti iR Ri i1 1505034780347802 2555528610286103 3

4、60602365023650。151512012033073307二二. . 最优化问题实例最优化问题实例试确定函数关系。试确定函数关系。利用利用最小二乘思想最小二乘思想，可将其化为无约束最优化问题：，可将其化为无约束最优化问题： 1512321321)exp(),(miniiixtxxRxxxf总利润最大？总利润最大？生产计划才能使生产计划才能使。问：工厂应如何安排。问：工厂应如何安排种产品的利润为种产品的利润为单位第单位第。种资源的量为种资源的量为种产品需要的第种产品需要的第生产单位第生产单位第。，产品产品种种这些资源可用来生产这些资源可用来生产。，种资源，数量为种资源，数量为某厂有某厂有

5、生产计划问题生产计划问题例例 1 2ij21jmcjaijnnbbbm建立模型：建立模型：。总总利利润润为为种种产产品品的的产产量量为为设设第第 Cxjj njxmibxatsxcCjinjjijnjjj,.,2,10,.,2,1.max11模模型型： m 2 1 n 2 1产量产量 销量销量 销销 地地产产地地运费运费11a12ana121a22ana21ma2mamna1b2bmb1c2cnc？方案才能使总运费最小方案才能使总运费最小。问：应如何安排运输。问：应如何安排运输为为的单位运价的单位运价到到从从。，销量分别为，销量分别为个销地个销地有有分别为分别为，可供应某种商品的量，可供应某种

6、商品的量个生产点个生产点已知有已知有运输问题运输问题例例 ), 1( ), 1( 3ijjijjiiaCBnjcCnmibBm 在产销平衡条件下，要求总运费最小的调运方案，可得如在产销平衡条件下，要求总运费最小的调运方案，可得如下模型。下模型。 .,.,1,.,10,.,2,1,.,2,1.min1111njmixnjcxmibxtsxazijjmiijinjijminjijij；则有则有个销地的运量。个销地的运量。个产地向第个产地向第表示从第表示从第设设 jixij三三. . 极值最优化问题的经典方法极值最优化问题的经典方法1.1.无约束极值问题无约束极值问题 000)()(1minnRxx

7、fxfxfxfn多元函数：多元函数：)(minxfRx 一元函数：一元函数：必要条件：必要条件：0)( xf 0),(0),(.),(min2121121nlnnxxxhxxxhtsxxxf2.2. 约束极值问题约束极值问题 0)(0)()()(),(min1xhLxhxfxLxhxfxLliiiRRxln （四四. . 最优化问题及基本概念最优化问题及基本概念1.1.模型模型 pjxhmixgtsxfji，, 10)(, 10)(.)(min 0)(0)(.)(minxhxgtsxfDxtsxf .)(min 0)(,0)(| 称为可行域。称为可行域。其中其中 xhxgxDTpTmxhxhx

8、hxgxgxg) )(, )()() )(, )()(11 Tnxxx),(1 3.3.解法分类：解法分类： 解析方法解析方法：利用函数的解析性质去构造迭代公式使之收敛到：利用函数的解析性质去构造迭代公式使之收敛到最优解（如牛顿法）。最优解（如牛顿法）。 直接方法直接方法：它对函数的分析性质如可微性没有要求，而是根：它对函数的分析性质如可微性没有要求，而是根据一定的数学原理来确定（如据一定的数学原理来确定（如0.6180.618法）。法）。2.2.基本概念：全局最优解与局部最优解基本概念：全局最优解与局部最优解DxxfxfxDxNxxfxfxxxxxNxfxxfxT ),()(:)*,(),(

9、)(:|),()(,();(;*00*全全局局最最优优解解局局部部最最优优解解邻邻域域最最优优解解：最最优优值值：最最优优点点： 五五. 梯度与梯度与Hesse阵阵1. 梯度梯度TnxfxfxfXf),.,()(21 性质性质1：函数在某点的梯度若不为函数在某点的梯度若不为0， 则必与过该点的等值线则必与过该点的等值线（面）垂直。（面）垂直。x0Lf(X)=f(X0)f(X0)X0L性质性质2：梯度方向是函数具有最大变化率的方向，即函数值上梯度方向是函数具有最大变化率的方向，即函数值上升最快的方向。升最快的方向。2. 方向导数和下降（上升）方向方向导数和下降（上升）方向（1）方向导数方向导数：

10、|)()(lim)(0000ptxfptxfpxft 的方向导数。的方向导数。处沿着方向处沿着方向在点在点函数函数 )( 0pxxf（2）给定函数给定函数 和方向和方向p，如果存在实数如果存在实数 ，使得对，使得对于任意的于任意的 ，都有，都有 ，则称，则称p为为 在在点点 处的处的下降方向下降方向。)(xf0 t),0(t )()(0 xfpxfo )(xf0 x（3） 性质性质 (a) . |)()(00ppxfpxfT (b) p是下降方向是下降方向; 0)(0pxf 0)(0pxf(c) p是下降方向。是下降方向。 0)(0pxfTp 是上升方向。是上升方向。（4） 常用梯度公式常用梯

11、度公式,0 c,)(bxbT ,2)(xxxT .2)(AxAxxT 3. Hesse矩阵矩阵（1）雅可比矩阵：设雅可比矩阵：设,)()()(1 xgxgxgmnmijnmnmxgxxgxxgxxgxxgxg )()()()()(1111（2）海赛（海赛（Hesse） 矩阵矩阵：nnjinnnnxxfxfxxfxxfxxfxxfxfxfxf 2221222122122122)()(（3）其它）其它Ix 11TAAx )(则则，设设)()(0tpxft ,)()(0ptpxftT 。ptpxfptTT)()(02 01 ncc例例 已知已知 ，求，求3313212232132),(xxxxxxx

12、xxf （1） ， 。)1 ,2, 1(321| ),(xxxf )1 ,2, 1(3212| ),(xxxf （2）判断向量）判断向量 是否为函数是否为函数 在点在点),(321xxxf 的下降方向？的下降方向？)1 , 2 , 1(解解： （1）,32321xxxf ,22122xxxf .332313xxxf )1 ,2, 1(321| ),(xxxf )1 ,2, 1(2311232|)33 ,22 ,32(Txxxxxx T)0 , 2 , 1( Td)1 , 0 , 2( )1 ,2, 1(3212| ),(xxxf)1 ,2, 1(3603022320 x 603022320 0

13、21)1 , 0 , 2(（2） )1 ,2, 1(321| ),(xxxfdT02 所以向量所以向量 是函数是函数 在点在点 的的),(321xxxf下降方向。下降方向。)1 , 2 , 1(Td)1 , 0 , 2( 六六. Taylor展开式展开式例例 函数函数 在点在点 的泰勒展开式为的泰勒展开式为xexf )(0 x)()0(!1)0(! 21)0(! 1112nnxxoxnxxe )(!12112nnxoxnxx )10(,)(21)()()()(21)()()(1222 pxxpxfppxfxfpopxfppxfxfpxfTTTT： )()(21)()()()(20020000

14、xxxfxxxxxfxfxfTT：七七. 凸集与凸函数凸集与凸函数1.凸集凸集（1）凸组合：凸组合：（2）凸集：）凸集：为凸集。为凸集。则称则称如果如果及及任取任取，已知已知XXxxXxxRXn,)1( , 10 , )2(1)2()1( )1(x)2(x)1(x)2(x的的凸凸组组合合。为为，则则称称使使得得，如如果果存存在在常常数数，个个点点任任取取，已已知知 ),1( 1 ),1( 0 )(1)(1)(kixxxxaakiaXxkRXikiiikiiiin 2.凸函数凸函数设设RRXfn :，任取任取 Xxx )2()1(,，如果如果,1,0,2121 iiaaa有有)()()()2(2

15、)1(1)2(2)1(1xfaxfaxaxaf ，则称则称 f 为为X上的上的(严格严格)凸函数。凸函数。例子：例子： 2)(xxf 凸凸集集的的交交仍仍为为凸凸集集。性性质质 )2(2)1(1xaxax )()1(xf)()2(xf x水平集水平集： fXxxfxD,)(| 是凸函数是凸函数。性质性质：水平集一定是凸集。：水平集一定是凸集。3. 凸函数的性质凸函数的性质定理定理. 凸函数的局部极小点就是全局极小点。凸函数的局部极小点就是全局极小点。4. 凸函数的判断条件凸函数的判断条件定理定理1. )(xf是凸集是凸集X上的凸函数的充要条件是上的凸函数的充要条件是Xxx )2()1(,，有，

16、有)()()()()1()2()1()1()2(xxxfxfxfT .定理定理2.设设)(xf在凸集在凸集X上有二阶连续偏导数，则上有二阶连续偏导数，则)(xf是凸是凸函数的充要条件是函数的充要条件是Xx ，有，有)(2xf 半正定。半正定。例：正定二次函数例：正定二次函数cxbAxxxfTT 21)(，其中，其中A是正定矩阵。是正定矩阵。)(xf是凸函数。是凸函数。的凸性。的凸性。判断判断例例 26293)( 313221232221xxxxxxxxxxf 解：解： 1233123212618626222xxxxxxxxxf,022 ,086222 02 f )(是

17、凸函数。是凸函数。xf5. 凸规划凸规划（1）Dxtsxf .)(min其中其中)(xf是凸函数，是凸函数，D是凸集。是凸集。（2）)(minxf 0)(0)(0)(0)(.11xhxhxgxgtskl其中其中),2,1()(, )(lixgxfi 是线性函数。是线性函数。),2,1( )(kjxhj 是凸函数是凸函数,八八. 极小点的判定条件极小点的判定条件（1）必要条件：）必要条件：0)()(min)( xfxfxf（2）充分条件：）充分条件：0)(0)(2 xfxf)(min)(xfxf 22)()(21)()()()(xxoxxxfxxxxxfxfxfTT（3） 两个结论两个结论 02

18、)x(f 函数在极小点附近的等值线为近似的同心椭圆。函数在极小点附近的等值线为近似的同心椭圆。有唯一的极值点：有唯一的极值点：正定二次函数正定二次函数bQxcxbQxxxfTT1*21)( 九九. 算法及相关概念算法及相关概念1、迭代算法、迭代算法集合集合 D上的迭代算法上的迭代算法A： （1）初始点）初始点 ；)0(x（2）按照某种规则）按照某种规则A产生下一个迭代点产生下一个迭代点)()()1(kkxAx 。（i）如果点列如果点列)(kx收敛于最优解收敛于最优解*x，则称算法，则称算法 A 收敛收敛。（ii）如果如果 )()()()()1()0(kxfxfxf，则称算法，则称算法A为为下降迭代算法。下降迭代算法。.)0(x.)1(x.)2(xD.)3(x迭代格式：迭代格式：已知当前迭代点已知当前迭代点 ，如何确定下一个迭代点，如何确定下一个迭代点 ？)(kx)1( kx)(kx)1( kx)(kdk )()()1(kkkkdxx :)(kd 搜索方向搜索方向； 搜索步长搜索步长。:k 2.下降迭代算法步骤下降迭代