最优化第一部分课件

《最优化第一部分课件》由会员分享，可在线阅读，更多相关《最优化第一部分课件（58页珍藏版）》请在金锄头文库上搜索。

1、非线性优化与动态规划非线性优化与动态规划第一部分第一部分 绪论绪论1.最优化方法的定义、最优化方法的定义、研究对象及研究方法研究对象及研究方法2. 最优化问题的基本概念最优化问题的基本概念 3. 梯度与梯度与Hesse矩阵矩阵4. 凸函数与凸规划凸函数与凸规划 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论内容简介：内容简介：最优化方法最优化方法 近几十年形成的近几十年形成的. 它主要运用数学方法它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科研究各种系统的优化途径及方案，为决策者提供科学决策的依据。学决策的依据。 最优化方法的主要研究对象是各种有组织系统最

2、优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到理论基础和不可缺少

3、的方法，被人们广泛地应用到公共管理、经济管理、国防等各个领域，发挥着越公共管理、经济管理、国防等各个领域，发挥着越来越重要的作用。来越重要的作用。本门课程将介绍本门课程将介绍非线性最优化方法的研究对象、特非线性最优化方法的研究对象、特点。主要是无约束优化计算、约束优化计算以及动点。主要是无约束优化计算、约束优化计算以及动态规划的模型、求解。态规划的模型、求解。非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论一、最优化方法的定义、研究对象及研究方法一、最优化方法的定义、研究对象及研究方法 英国运筹学会给英国运筹学会给最优化方法最优化方法下的定义是，下的定义是，最优化方法是一最

4、优化方法是一系列科学方法的应用系列科学方法的应用。在工业、商业、政府及国防部门中，用。在工业、商业、政府及国防部门中，用这些方法处理大量的人员、机器、材料和资金等复杂问题。这这些方法处理大量的人员、机器、材料和资金等复杂问题。这种方法的特点是科学地建立系统模型，包括度量各种因素，例种方法的特点是科学地建立系统模型，包括度量各种因素，例如分析机会和风险，以此预测和比较各种决策、策略或控制的如分析机会和风险，以此预测和比较各种决策、策略或控制的结果，使管理机构科学地确定它的政策及行动。结果，使管理机构科学地确定它的政策及行动。 美国运筹学会下了一个比较简短的、与上述相类似的定义：美国运筹学会下了一

5、个比较简短的、与上述相类似的定义：最优化方法的研究内容是，在需要对有限的资源进行分配的情最优化方法的研究内容是，在需要对有限的资源进行分配的情况下，作出人机系统最优设计的操作的科学决策。况下，作出人机系统最优设计的操作的科学决策。 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论 以上几种定义中虽然每个定义所强调的侧重点略有不同，以上几种定义中虽然每个定义所强调的侧重点略有不同，但总的含义是一致的。一般说来，最优化方法的研究对象是各但总的含义是一致的。一般说来，最优化方法的研究对象是各种有组织的系统（主要是经济组织系统）的经营管理问题，种有组织的系统（主要是经济组织系统）的

6、经营管理问题，最最优化方法所研究的系统是在一定时空条件下存在，为人所能控优化方法所研究的系统是在一定时空条件下存在，为人所能控制和操纵，有两个以上行动方案可供选择而需要人们作决策的制和操纵，有两个以上行动方案可供选择而需要人们作决策的系统。系统。最优化方法研究的问题是能用数量表示与系统各项活动最优化方法研究的问题是能用数量表示与系统各项活动有关而带有运用、策划、使用、安排、控制和规划等方面的问有关而带有运用、策划、使用、安排、控制和规划等方面的问题。最优化方法的任务就是在现有条件下，根据问题的要求，题。最优化方法的任务就是在现有条件下，根据问题的要求，对有关活动中的错综复杂的数量进行分析研究，

7、并归纳为一定对有关活动中的错综复杂的数量进行分析研究，并归纳为一定的模型，然后运用有关原理和方法求得解决问题的最优途径和的模型，然后运用有关原理和方法求得解决问题的最优途径和方案，以求实现预期目标。方案，以求实现预期目标。 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论最优化问题的数学模型最优化问题的数学模型 数学模型是对实际问题的数学描述和概括数学模型是对实际问题的数学描述和概括 , 是进行最优是进行最优化设计的基础化设计的基础 . 根据设计问题的具体要求和条件建立完备的根据设计问题的具体要求和条件建立完备的数学模型是最优化设计成败的关键数学模型是最优化设计成败的关键

8、. 这是因为最优化问题的这是因为最优化问题的计算求解完全是针对数学模型进行的计算求解完全是针对数学模型进行的 . 也就是说，也就是说，最优化计最优化计算所得最优解实际上只是数学模型的解，至于是否是实际问算所得最优解实际上只是数学模型的解，至于是否是实际问题的解，则完全取决于数学模型与实际问题符合的程度题的解，则完全取决于数学模型与实际问题符合的程度. 工程设计问题通常是相当复杂的，欲建立便于求解的数工程设计问题通常是相当复杂的，欲建立便于求解的数学模型，必须对实际问题加以适当的抽象和简化学模型，必须对实际问题加以适当的抽象和简化 . 不同的简不同的简化方法得到不同的数学模型和计算结果，而且一个

9、完善的数化方法得到不同的数学模型和计算结果，而且一个完善的数学模型，往往需要在计算求解过程中进行反复地修改和补充学模型，往往需要在计算求解过程中进行反复地修改和补充才能最后得到才能最后得到. 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论 通过几个简单的最优化设计简例，说明数学模型的一般通过几个简单的最优化设计简例，说明数学模型的一般形式、结构及其有关的基本概念形式、结构及其有关的基本概念. 例例1. 用一块边长用一块边长3m 的正方形薄板，在四角各裁去一个大的正方形薄板，在四角各裁去一个大小相同的方块，做成一个无盖的箱子，试确定如何裁剪可以小相同的方块，做成一个无盖的箱

10、子，试确定如何裁剪可以使做成的箱子具有最大的容积使做成的箱子具有最大的容积. 解解: 设裁去的设裁去的4个小方块的边长为个小方块的边长为x，则做成的箱子的容，则做成的箱子的容积为积为: 于是，上述问题可描述为于是，上述问题可描述为: 求变量求变量 x , 使函数使函数极大化极大化 .这样就把该设计问题转化成为一个求函数这样就把该设计问题转化成为一个求函数f(x)最大值的数学问最大值的数学问题题. 其中其中, x 是待定的求解参数是待定的求解参数, 称为决策变量称为决策变量; 函数函数f(x)代表代表设设计目标计目标, 称为目标函数称为目标函数. 由于目标函数是设计变量的三次函数由于目标函数是设

11、计变量的三次函数,并且不存在任何限制条件并且不存在任何限制条件, 故称此类问题为非线性无约束最优故称此类问题为非线性无约束最优化问题化问题 .非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论例例2 . 某工厂生产甲、乙两种产品，生产每种产品所需的材料、某工厂生产甲、乙两种产品，生产每种产品所需的材料、工时、用电量和可以获得的利润，以及每天能够提供的材料、工时、用电量和可以获得的利润，以及每天能够提供的材料、工时、用电量见表工时、用电量见表11，试确定该厂两种产品每天的生产计，试确定该厂两种产品每天的生产计划，以使得每天获得的利润最大划，以使得每天获得的利润最大.表表1-1

12、生产条件基本数据生产条件基本数据产品产品材料材料/kg工时工时/h用电能量用电能量/kw h利润利润/元元甲甲乙乙供应量供应量943603103004520060120解解: 这是一个简单的生产计划问题这是一个简单的生产计划问题, 可归结为在满足各项生产可归结为在满足各项生产条件的基础上条件的基础上, 合理安排两种产品每天的生产量合理安排两种产品每天的生产量, 以使利润最以使利润最大化的最优化设计问题大化的最优化设计问题.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论设每天生产甲产品设每天生产甲产品x1件件, 乙产品乙产品x2 件件, 每天获得的利润用函数每天获得的利润用

13、函数f (x1, x2)表示表示, 即即: 每天实际消耗的材料、工时和电力分别用函数每天实际消耗的材料、工时和电力分别用函数表示，即表示，即于是，该问题可归结为以下数学模型：求变量于是，该问题可归结为以下数学模型：求变量 x1 , x2 ,使函数使函数极大化极大化并满足条件并满足条件:称此类问题为称此类问题为线性约束最优线性约束最优化问题化问题 .非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论二、二、最优化问题的基本概念最优化问题的基本概念 1. 最优化问题的向量表示最优化问题的向量表示 研究最优化问题，一般都采用向量表示，例如决策变量研究最优化问题，一般都采用向量表示，

14、例如决策变量可以看作是可以看作是n维向量空间维向量空间Rn中的一个向量中的一个向量x的的n个个分量，即分量，即或或例如，例例如，例1、例、例2中的目标函数都可以写成中的目标函数都可以写成设设x是是n维向量变量，则如下函数维向量变量，则如下函数称为向量值函数称为向量值函数, 如果它的定义域为如果它的定义域为D, 则简记为则简记为MTAP-D-18-02390 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论2. .向量的范数向量的范数约定：约定：取向量为列向量，即取向量为列向量，即 n 维维Euclid 空间空间Rn中的一个中的一个向量向量 x 可表示为：可表示为：或或矩阵相

15、等：矩阵相等：设设如果对一切如果对一切都有都有则称向量则称向量x与与y相等，记作相等，记作类似可定义两向量小于等于或小于关系。类似可定义两向量小于等于或小于关系。非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论矩阵的正定性质及对称矩阵的判定：矩阵的正定性质及对称矩阵的判定：设设A为为n 阶对称矩阵，阶对称矩阵，x 为任意非零为任意非零n 维向量维向量(1) 若若 xTAx0 , 则称则称A为正定矩阵，记作为正定矩阵，记作 A0 ; (2) 若若 xTAx 0 , 则称则称A为半正定矩阵，记作为半正定矩阵，记作 A 0 ; (3) 若若 xTAx0 , 则称则称A为负定矩阵，

16、记作为负定矩阵，记作 A 0 A的特征值都大于的特征值都大于0 A的各阶顺序主子式都大于的各阶顺序主子式都大于0 A 0A的特征值都大于的特征值都大于等于等于0 A的各阶顺序主子式都大于等于的各阶顺序主子式都大于等于0 A 0，使得，使得则称则称d 为为f(x) 在在x0点的点的下降方向下降方向，若，若 定理定理3 设设 f : RnR，x Rn，且，且f(x) 在在x 点可微，如果点可微，如果存在非零向量存在非零向量d Rn，使得，使得 f(x)Td 0，则，则d 是上升方向是上升方向。则称则称d为为f(x) 在在x0点的点的上升方向上升方向。非线性优化与动态规划非线性优化与动态规划 第一部

17、分第一部分 绪论绪论此定理说明，与此定理说明，与f在在x0处的梯度方向交成锐角的任何方向都是处的梯度方向交成锐角的任何方向都是f在在x0处的上升方向；相反，与处的上升方向；相反，与f在在x0处的梯度梯度方向交成钝处的梯度梯度方向交成钝角的任何方向都是角的任何方向都是f在在x0处的下降方向。处的下降方向。可以证明：可以证明：梯度方向是函数值上升最快的方向，梯度负方向梯度方向是函数值上升最快的方向，梯度负方向是函数值下降最快的方向是函数值下降最快的方向。因此我们把负梯度方向叫。因此我们把负梯度方向叫做最速做最速下降方向下降方向.还可以证明：还可以证明： f(x)在在x0处的梯度与处的梯度与f(x)

18、过过x0处等值面上任一曲线处等值面上任一曲线l在该点的切线垂直，即与过该点的切平面垂直。或者可以说在该点的切线垂直，即与过该点的切平面垂直。或者可以说 f(x0)是曲面是曲面f(x)=f(x0)在点在点x0处的一个法线向量。处的一个法线向量。注：过注：过x0的等值面方程为：的等值面方程为： f(x)=f(x0)=c.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论 2 . 海赛（海赛（Hesse）矩阵）矩阵 假设函数假设函数 f(x) 二阶可微，则以其二阶偏导数为元素构成的下二阶可微，则以其二阶偏导数为元素构成的下述述nn矩阵称为矩阵称为f(x)的海赛矩阵，记为的海赛矩阵，

19、记为即即当当f(x)在在x处的所有二阶偏导数连续时，有处的所有二阶偏导数连续时，有这时的这时的Hesse矩阵为对称矩阵矩阵为对称矩阵.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论向量函数的导数向量函数的导数定义定义4 设设如果如果对于自变量对于自变量的各分量的偏导数的各分量的偏导数都存在，则称向量都存在，则称向量函数函数h 在在 处是一阶可导的，并且称矩阵处是一阶可导的，并且称矩阵为为h(x)在在 处的处的一阶导数或一阶导数或Jacobi矩阵，简记为矩阵，简记为非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论n元函数元函数的梯度是向量函数的梯度是向量

20、函数由上面定义知，由上面定义知， f(x)的一阶导数或的一阶导数或Jacobi矩阵为：矩阵为：非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论即即函数梯度的函数梯度的Jacobi矩阵即为该函数的矩阵即为该函数的Hesse矩阵矩阵.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论 例例例例1 1 求函数求函数 在任意点的梯在任意点的梯度度和海赛矩阵。和海赛矩阵。 解解: 先求先求f(x)的各阶偏导数，有的各阶偏导数，有 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论例例2 求二次齐次函数的求二次齐次函数的Hesse矩阵矩阵 解：解：非

21、线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论3. Taylor展式展式 设设n元实函数元实函数 f(x) 在某点在某点 x(0) 的某一邻域内有连续二阶偏导的某一邻域内有连续二阶偏导数，则可写出它在数，则可写出它在 x(0 )处的处的泰勒泰勒（Taylor）展开）展开式如下：式如下：若在上式中略去高阶无穷小项，则有相应的近似关系式：若在上式中略去高阶无穷小项，则有相应的近似关系式：非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论四、凸函数与凸规划四、凸函数与凸规划 求解非线性规划问题的

22、算法很多，但一般情况下求出的求解非线性规划问题的算法很多，但一般情况下求出的都是局部最优解。而我们的目的是求问题的全局最优解。为都是局部最优解。而我们的目的是求问题的全局最优解。为了达到这个目的，我们一般可以从两个方面着手考虑，一是了达到这个目的，我们一般可以从两个方面着手考虑，一是寻求求全局极值的计算方法，二是从理论上说明在何种情况寻求求全局极值的计算方法，二是从理论上说明在何种情况下，求出的局部极值一定是问题的全局极值。实际上，研究下，求出的局部极值一定是问题的全局极值。实际上，研究结果表明，对于结果表明，对于凸规划来说，局部最优解一定是全局最优解凸规划来说，局部最优解一定是全局最优解（对

23、极值问题而言）。（对极值问题而言）。 本部分首先介绍凸函数的概念和性质，再介绍凸规划的本部分首先介绍凸函数的概念和性质，再介绍凸规划的概念与性质。概念与性质。非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论凸集凸集的线段都全部包含在该集合内，就称该点集为凸集，的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。否则为非凸集。一个点集（或区域），如果连接其中任意两点一个点集（或区域），如果连接其中任意两点非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论1. 凸函数及其性质凸函数及其性质定义定义5 若对任意的若对任意的 及及D 中任意两点中任意两点

24、和和 有有（1.2） 成立，成立， 则称则称f（X）为）为D上的凸函数，上的凸函数， 或称或称f（X）在）在 D上是凸的上是凸的. 设设f (X)为定义在非空凸集为定义在非空凸集 上的函数。上的函数。 （1.3） 成立成立, 则称则称f(X)为为D上的严格凸函数，上的严格凸函数， 或称或称f(X)在在D上是严格凸的上是严格凸的.若对任意的若对任意的 及任意两点及任意两点有有非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论注注1： 若若f 是是D 上的（严格）凸函数，上的（严格）凸函数， 则称则称-f 是是D 上的上的(严格严格)凹函数，凹函数， 或称或称-f 在在D 上是（

25、严格）凹的。上是（严格）凹的。 实际上，我们也可以仿照定义实际上，我们也可以仿照定义2来定义凹函数，只要令式来定义凹函数，只要令式（1.2）和（）和（1.3）不等号反向）不等号反向.当当n=1时，如图时，如图1.1所示凸所示凸（凹）（凹）函数的函数曲线上任意两点间的连线总在函数曲线的上函数的函数曲线上任意两点间的连线总在函数曲线的上(下下)图图1.1（a） 凸函数凸函数非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论图图1.1（b） 凹函数凹函数注注2： 由凸（凹）函数的定义，可知线性函数既是由凸（凹）函数的定义，可知线性函数既是凸函数也是凹函数。凸函数也是凹函数。非线性优

26、化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论根据凸函数的定义，易证凸函数有如下的基本性质根据凸函数的定义，易证凸函数有如下的基本性质.性质性质 1.1 设设f（X）是凸集）是凸集D上的凸函数，上的凸函数， 为实数，为实数， 则则 也是也是D上的凸函数。上的凸函数。性质性质 1.2 设设 和和 均为凸集均为凸集D上的凸函数，上的凸函数，则则 也是也是D上的凸函数上的凸函数.性质性质 1.3 也是也是D上的凸函数上的凸函数.设设 均为凸集均为凸集D上的凸函数，上的凸函数，且且则线性组合则线性组合 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论性质性质 1.4

27、集合集合设设 f (X)是凸集是凸集D上的凸函数，对任一实数上的凸函数，对任一实数 ,也是凸集也是凸集. .证明：证明： 任取任取则则且且任取任取因为因为D为凸集，为凸集，所以所以又因为又因为f（X）为）为D上的凸函数，上的凸函数， 所以所以由集合由集合 的定义知，的定义知， 证毕证毕.根据凸集的定义知根据凸集的定义知 为凸集为凸集. 我们称集合我们称集合 为为f（X）在）在 集合集合D上关于数上关于数 的水平集的水平集.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论2. 凸函数的判定凸函数的判定我们可以根据凸函数的定义来判定一个函数是否为凸函数我们可以根据凸函数的定义来

28、判定一个函数是否为凸函数, 但但如果该函数是可微函数，那么可按下述法则判别如果该函数是可微函数，那么可按下述法则判别.定理定理4 （函数凸性的一阶条件）（函数凸性的一阶条件） 设设D是是En的非空开凸集的非空开凸集, 函数函数 具有一阶连续的偏具有一阶连续的偏导数，导数， 则函数则函数f 为凸函数的充要条件是为凸函数的充要条件是,恒有恒有（1.4） 其中其中 为函数为函数 f 在在 处的梯度向量处的梯度向量.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论证明：证明： 必要性。必要性。因为因为D是是 的非空开的非空开凸集，凸集， 所以所以 因为函数因为函数f 为凸函数，为凸

29、函数， 所以所以 从而有从而有由于由于上式不等式两边同除以上式不等式两边同除以 得得非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论由于由于f 具有一阶连续的偏导数，具有一阶连续的偏导数， 故有故有所以所以 于是得到于是得到非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论充分性。充分性。因为因为D是是的非的非空开凸集，空开凸集， 则则由充分性条件式（由充分性条件式（1.4）得）得以以和和分别乘以上述两个不等式的两边，分别乘以上述两个不等式的两边， 并相加整理得并相加整理得由定义知函数为凸函数由定义知函数为凸函数. 证毕证毕.非线性优化与动态规划非线性优化

30、与动态规划 第一部分第一部分 绪论绪论定理定理5 （函数凸性的二阶条件）（函数凸性的二阶条件） 设设D是是 的非空开凸集，函数的非空开凸集，函数 的偏导数，则的偏导数，则函数函数f 为凸函数的充要条件是函数为凸函数的充要条件是函数 f 的的Hesse矩矩阵阵 H(X)在在D 上为半正定矩阵上为半正定矩阵. 函数函数f 为严格凸函数的充要条件是函数为严格凸函数的充要条件是函数 f 的的Hesse矩矩矩矩阵阵 H(X)在在D 上为正定矩阵上为正定矩阵.具有二阶连续具有二阶连续证明：证明： 必要性。必要性。因为因为D是是的非空开凸集，的非空开凸集， 所以所以有有f 为严格凸函数，为严格凸函数，因为因

31、为D是是Rn的非空开凸集的非空开凸集所以存在所以存在 当当时，时，由定理由定理4得得 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论因为函数因为函数f 具有二阶连续的偏导数，具有二阶连续的偏导数， 由由Taylor展式得展式得 所以由上两式得所以由上两式得上式两边同除以上式两边同除以 注意到注意到则有则有即即Hesse矩阵矩阵H(X)在在D上为半正定矩阵。上为半正定矩阵。充分性。充分性。由由Taylor展式得，展式得， 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论其中其中因为因为D 是凸集，是凸集， 所以所以由充分性的条件知由充分性的条件知Hess

32、e矩阵矩阵H（X）在）在D 上为半正定上为半正定矩阵，矩阵， 从而从而为半正定矩阵，为半正定矩阵， 即有即有 所以所以由定理由定理4 知函数为的凸函数知函数为的凸函数. 第二个结论的证明只要把上述的不等号换成严第二个结论的证明只要把上述的不等号换成严格的不等号即知成立格的不等号即知成立.证毕证毕.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论例例3 判断判断 是否为凸函数是否为凸函数.解：解： 用二阶条件用二阶条件. 从而有从而有因为顺序主子式因为顺序主子式所以所以H(X) 正定，正定， 故故f(X)为严格凸函数为严格凸函数. 非线性优化与动态规划非线性优化与动态规划 第

33、一部分第一部分 绪论绪论定理定理6 若若f(X) 是凸集是凸集D Rn上的凸函数上的凸函数 ,则它的任一局则它的任一局证明：证明： 设设 是任一局部极小点，是任一局部极小点， 为其充分小的邻域为其充分小的邻域 ,则则 有有 充分小，充分小，则有则有 所以所以 部极小点就是它在部极小点就是它在D 上的全局极小点，而且它的极小点全体上的全局极小点，而且它的极小点全体形成一个凸集形成一个凸集 .因为因为f(X)是凸集是凸集 D Rn上的凸函数上的凸函数 ,所以所以 将上两式相加并除以将上两式相加并除以 , 即得即得 所以结论成立所以结论成立. 证毕证毕. 非线性优化与动态规划非线性优化与动态规划 第

34、一部分第一部分 绪论绪论定理定理 7设设 f（X）在凸集）在凸集D Rn 上可微且为凸函上可微且为凸函 数，数， 若存在点若存在点 都有都有 （1.5） 则则 是是f（X）在）在D上的全局极小点；上的全局极小点； 若若f（X）为可微的严格）为可微的严格凸函数，凸函数， 则则 即即 是是f（X）的唯一全局极小点）的唯一全局极小点.证明：证明： 由定理由定理4 知知 由条件由条件 知知 所以所以 若若f（X）为可微的严格凸函数，）为可微的严格凸函数， 则则(1.5) 成立严格不等号成立严格不等号, 即即 是是f（X）在）在D上的全局极小点上的全局极小点.由由X 的任意性知的任意性知 由定理由定理知

35、结论成立知结论成立 .证毕证毕.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论定理定理7 的含义可参考图的含义可参考图1.2图图1.2非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论3. 凸规划及其性质凸规划及其性质 考虑非线性规划问题考虑非线性规划问题这里这里 约束约束D 可表示为可表示为 若若f（X）为凸函数，）为凸函数， 为为凹函数（或说凹函数（或说 为凸函数），为凸函数），则称以上非线性规划为凸规划则称以上非线性规划为凸规划.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论凸规划是一类比较简单，而且具有一些良好性质的非凸规划

36、是一类比较简单，而且具有一些良好性质的非线性规划。前面已经指出，凸规划的可行域为凸集，线性规划。前面已经指出，凸规划的可行域为凸集，其局部极小点就是全局极小点，而且局部极小点的全其局部极小点就是全局极小点，而且局部极小点的全体构成一个凸集。当凸规划的目标函数为严格凸函数体构成一个凸集。当凸规划的目标函数为严格凸函数时，其全局极小点唯一时，其全局极小点唯一.注注1：注注2：线性规划是一种特殊的凸规划线性规划是一种特殊的凸规划.目标函数为凸函数目标函数为凸函数约束条件为凹函数约束条件为凹函数凸规划凸规划凸规划特点凸规划特点1. 可行域为凸集可行域为凸集; 2.局部最优解为全局最优解局部最优解为全局

37、最优解;3.最优解最优解集为凸集集为凸集; 4.目标函数为严格凸函数，则最优解必定唯一目标函数为严格凸函数，则最优解必定唯一非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论例例4验证下述非线性规划为凸规划。验证下述非线性规划为凸规划。 解：解： 目标函数可写成目标函数可写成 f(X) 的海赛矩阵为的海赛矩阵为 非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论它的顺序主子式分别为它的顺序主子式分别为故故为正定矩阵，为正定矩阵， 即即f（X）为严格凸函数）为严格凸函数. 同理可以验证同理可以验证 为严格凸函数，为严格凸函数， 是线性函数是线性函数,因此上述非

38、线性规划为凸规划因此上述非线性规划为凸规划.所以此规划的可行域为凸集，所以此规划的可行域为凸集， 若非线性规划的目标函数为的二次函数或二次型，约束若非线性规划的目标函数为的二次函数或二次型，约束条件又全是线性函数，则称之为二次规划条件又全是线性函数，则称之为二次规划 .二次规划的数学二次规划的数学模模型可表示为型可表示为:非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论这里这里 若目标函数第二项的二次型为正定（或半正定）则目标函数若目标函数第二项的二次型为正定（或半正定）则目标函数必为严格凸函数必为严格凸函数(或凸函数或凸函数) . 二次规划的可行域为凸集，故二次规划的可行

39、域为凸集，故此时为凸规划，它是非线性规划中比较简单的一类，较容易此时为凸规划，它是非线性规划中比较简单的一类，较容易求解求解.许多实际问题，均可归结为二次规划模型许多实际问题，均可归结为二次规划模型.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论例例5 判定下述非线性规划是否为凸规划判定下述非线性规划是否为凸规划非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论解：解： (1)因为因为为线性函数，故为凸函数；为线性函数，故为凸函数；设设g1(x)的海赛矩阵的海赛矩阵 负定，故负定，故g1(x)为凹函数为凹函数.g2(x)为线性函数，可以看成是凸函数，也可以看成凹函数，为线性函数，可以看成是凸函数，也可以看成凹函数，这里看成凹函数，因此，此规划为凸规划这里看成凹函数，因此，此规划为凸规划.的海赛矩阵为的海赛矩阵为:为正定的，所以为正定的，所以f(x)为凸函数为凸函数.g2(x)的海赛矩阵的海赛矩阵 负定，所以负定，所以g2(x)为凹函数为凹函数.非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论又设又设则则 g1(x) , g3(x) , g4(x) 都是线性函数，所以为凹函数，都是线性函数，所以为凹函数，因因此，所给规划为凸规划此，所给规划为凸规划 .非线性优化与动态规划非线性优化与动态规划 第一部分第一部分 绪论绪论