最优化第一部分

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

1、非线性优化与动态规划,第一部分 绪论,最优化方法的定义、研究对象及研究方法 2. 最优化问题的基本概念 3. 梯度与Hesse矩阵 4. 凸函数与凸规划,非线性优化与动态规划 第一部分 绪论,内容简介： 最优化方法 近几十年形成的. 它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。 最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。,实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的

2、重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、国防等各个领域，发挥着越来越重要的作用。 本门课程将介绍非线性最优化方法的研究对象、特点。主要是无约束优化计算、约束优化计算以及动态规划的模型、求解。,非线性优化与动态规划 第一部分 绪论,一、最优化方法的定义、研究对象及研究方法 英国运筹学会给最优化方法下的定义是，最优化方法是一 系列科学方法的应用。在工业、商业、政府及国防部门中，用 这些方法处理大量的人员、机器、材料和资金等复杂问题。这 种方法的特点是科学地建立系统模型，包括度量各种因素，例 如分析机会和风险，以此预测和比较各种决策、策略或控制的 结果，使管理机构科学地确

3、定它的政策及行动。 美国运筹学会下了一个比较简短的、与上述相类似的定义： 最优化方法的研究内容是，在需要对有限的资源进行分配的情 况下，作出人机系统最优设计的操作的科学决策。,非线性优化与动态规划 第一部分 绪论,以上几种定义中虽然每个定义所强调的侧重点略有不同， 但总的含义是一致的。一般说来，最优化方法的研究对象是各 种有组织的系统（主要是经济组织系统）的经营管理问题，最 优化方法所研究的系统是在一定时空条件下存在，为人所能控 制和操纵，有两个以上行动方案可供选择而需要人们作决策的 系统。最优化方法研究的问题是能用数量表示与系统各项活动 有关而带有运用、策划、使用、安排、控制和规划等方面的问

4、 题。最优化方法的任务就是在现有条件下，根据问题的要求， 对有关活动中的错综复杂的数量进行分析研究，并归纳为一定 的模型，然后运用有关原理和方法求得解决问题的最优途径和 方案，以求实现预期目标。,非线性优化与动态规划 第一部分 绪论,最优化问题的数学模型 数学模型是对实际问题的数学描述和概括 , 是进行最优 化设计的基础 . 根据设计问题的具体要求和条件建立完备的 数学模型是最优化设计成败的关键 . 这是因为最优化问题的 计算求解完全是针对数学模型进行的 . 也就是说，最优化计 算所得最优解实际上只是数学模型的解，至于是否是实际问 题的解，则完全取决于数学模型与实际问题符合的程度. 工程设计问

5、题通常是相当复杂的，欲建立便于求解的数 学模型，必须对实际问题加以适当的抽象和简化 . 不同的简 化方法得到不同的数学模型和计算结果，而且一个完善的数 学模型，往往需要在计算求解过程中进行反复地修改和补充 才能最后得到.,非线性优化与动态规划 第一部分 绪论,通过几个简单的最优化设计简例，说明数学模型的一般 形式、结构及其有关的基本概念. 例1. 用一块边长3m 的正方形薄板，在四角各裁去一个大 小相同的方块，做成一个无盖的箱子，试确定如何裁剪可以 使做成的箱子具有最大的容积. 解: 设裁去的4个小方块的边长为x，则做成的箱子的容 积为:,于是，上述问题可描述为: 求变量 x , 使函数,极大

6、化 .,这样就把该设计问题转化成为一个求函数f(x)最大值的数学问 题. 其中, x 是待定的求解参数, 称为决策变量; 函数f(x)代表设 计目标, 称为目标函数. 由于目标函数是设计变量的三次函数, 并且不存在任何限制条件, 故称此类问题为非线性无约束最优 化问题 .,非线性优化与动态规划 第一部分 绪论,例2 . 某工厂生产甲、乙两种产品，生产每种产品所需的材料、 工时、用电量和可以获得的利润，以及每天能够提供的材料、 工时、用电量见表11，试确定该厂两种产品每天的生产计 划，以使得每天获得的利润最大.,表1-1 生产条件基本数据,解: 这是一个简单的生产计划问题, 可归结为在满足各项生

7、产 条件的基础上, 合理安排两种产品每天的生产量, 以使利润最 大化的最优化设计问题.,非线性优化与动态规划 第一部分 绪论,设每天生产甲产品x1件, 乙产品x2 件, 每天获得的利润用函数 f (x1, x2)表示, 即:,每天实际消耗的材料、工时和电力分别用函数,表示，即,于是，该问题可归结为以下数学模型：求变量 x1 , x2 ,使函数,极大化,并满足条件:,称此类问题为 线性约束最优 化问题 .,非线性优化与动态规划 第一部分 绪论,二、最优化问题的基本概念,1. 最优化问题的向量表示 研究最优化问题，一般都采用向量表示，例如决策变量,可以看作是n维向量空间Rn中的一个向量x的n个,分

8、量，即,或,例如，例1、例2中的目标函数都可以写成,设x是n维向量变量，则如下函数,称为向量值函数, 如果它的定义域为D, 则简记为,MTAP-D-18-02390,非线性优化与动态规划 第一部分 绪论,2.向量的范数,约定：取向量为列向量，即 n 维Euclid 空间Rn中的一个 向量 x 可表示为：,或,矩阵相等：设,如果对一切,都有,则称向量x与y相等，记作,类似可定义两向量小于等于或小于关系。,非线性优化与动态规划 第一部分 绪论,矩阵的正定性质及对称矩阵的判定：,设A为n 阶对称矩阵，x 为任意非零n 维向量 (1) 若 xTAx0 , 则称A为正定矩阵，记作 A0 ; (2) 若

9、xTAx 0 , 则称A为半正定矩阵，记作 A0 ; (3) 若 xTAx0 , 则称A为负定矩阵，记作 A0 ; (4)若 xTAx 0 , 则称A为半负定矩阵，记作 A 0 . 除此之外，称 A为不定矩阵 .,非线性优化与动态规划 第一部分 绪论,判定方法：设A 为 n 阶对称矩阵,非线性优化与动态规划 第一部分 绪论,两向量内积：,设,称,为向量 x 和 y 的内积 .,向量 x 的 Euclid 范数 (向量 x 的长度),称,为向量 x 的 Euclid 范数 (向量 x 的长度).,关于Euclid范数及内积的两个重要不等式,(1) 三角不等式,(2) Cauchy不等式,非线性优

10、化与动态规划 第一部分 绪论,3. 最优化问题的一般形式,非线性优化与动态规划 第一部分 绪论,概括地说，后面大部分章节要讨论的问题是如下的最优化问题:,其中f , si , hj 都是 x 的实值连续函数，通常假定它们都具有二 阶连续偏导数. 上面的模型也可以用向量来表示. 常用术语: f(x) 称为目标函数, 或求它的极小 , 或求它的极大;,被称为不等式约束，,称为等式约束.,称为集约束. 在（1.1）中, 集约束一般为,（1.1）,非线性优化与动态规划 第一部分 绪论,不然的话, 可以用不等式约束出来, 因此，后面一般不考虑 集约束. 满足所有约束的向量x 称为可行解或容许解 , 可行

11、解的集 合称为可行域（容许域）. 全局极小点与局部极小点：若存在,则称x*为f(x)在D上的全局极小点. 这里的“”改为“”，则称x*为f(x)在D上的全局严格极小点. x*组成的集合称为最优解集.,若存在,则称x*为问题（1.1） f(x) 的局部极小点（最优解）.,非线性优化与动态规划 第一部分 绪论,从以上定义可以看出，x*是局部极小点，是指在以 x* 为 中心的一个小邻域中f(x)在点x*处取得极小值；而 x*是全局极 小点，是指在定义域中，f(x)在点x*处取得极小值. 全局最小 点必定是局部极小点. 实际问题通常是求全局极小点，但直到目前为止，最优 化中绝大多数方法都是求局部极小点

12、的. 解决这类问题的方法 是，先求出所有的局部极小点，然后再求全局极小点. 在模型(1.1)中, 设,向量,均在D 的内部，则称h为x 的一个可行方向.,结论: 设在 (1.1)中,对于x*的任意可行方向,h , 均有,则x*为(1.1)的严格局部,最优解.,非线性优化与动态规划 第一部分 绪论,4. 最优化问题分类,最优化问题可做如下分类：,最优化问题,静态问题,动态问题,无约束非线性规划问题,约束问题,一维问题,n 维问题,线性规划,非线性规划,没有约束的问题：,称为无约束问题. 如决策变量只有,一个，称为一维问题.求解一维问题的方法称为一维搜索或线 性搜索，在最优化中起着十分重要的作用.

13、,非线性优化与动态规划 第一部分 绪论,一维问题,n 维问题,三、多元函数的梯度、Hesse矩阵及Taylor公式,可微函数 f(x) 的梯度，记为 f(x) ，它是以 f(x)对 xi (i=1 , 2 , , n）的偏导数为元素的n 维向量(本书规定为列向量)，即,也可以把梯度称为函数关于向量x 的一阶导数 . 函数在某 一点x(1)的梯度可表示为：,1. 梯度,非线性优化与动态规划 第一部分 绪论,定义1: 设 f : RnR，xRn， 如果存在n 维向量 p ，对任 意的非零向量x，使得,则称 f(x)在点x 处可微分，记作,定理1：设 f : RnR，xRn，如果f(x) 在x 点可

14、微，则 f(x) 在x 点的梯度 存在，且,称为f(x)在x 点的微分.,非线性优化与动态规划 第一部分 绪论,定义2: 设 f : RnR，x Rn， d 是给定的n维非零向量，,则称该极限为f(x)在点x 处沿d 的方向导数，记作,定理：设 f : RnR，xRn，如果f(x) 在x 点可微，则 在x 处沿任何非零向量d 的方向导数存在，且,如果下面的极限存在,非线性优化与动态规划 第一部分 绪论,定义3 设 f (x)是 Rn上的连续函数，x 0Rn， d 是给定的 n维非零向量，如果存在0，使得,则称d 为f(x) 在x0点的下降方向，若,定理3 设 f : RnR，x Rn，且f(x

15、) 在x 点可微，如果 存在非零向量d Rn，使得f(x)Td 0，则d 是上升方向。,则称d为f(x) 在x0点的上升方向。,非线性优化与动态规划 第一部分 绪论,此定理说明，与f在x0处的梯度方向交成锐角的任何方向都是f 在x0处的上升方向；相反，与f在x0处的梯度梯度方向交成钝 角的任何方向都是f在x0处的下降方向。 可以证明：梯度方向是函数值上升最快的方向，梯度负方向 是函数值下降最快的方向。因此我们把负梯度方向叫做最速 下降方向. 还可以证明： f(x)在x0处的梯度与f(x)过x0处等值面上任一曲线 l在该点的切线垂直，即与过该点的切平面垂直。或者可以说 f(x0)是曲面f(x)=

16、f(x0)在点x0处的一个法线向量。 注：过x0的等值面方程为： f(x)=f(x0)=c.,非线性优化与动态规划 第一部分 绪论,2 . 海赛（Hesse）矩阵,假设函数 f(x) 二阶可微，则以其二阶偏导数为元素构成的下 述nn矩阵称为f(x)的海赛矩阵，记为,即,当f(x)在x处的所有二阶偏导数连续时，有,这时的Hesse矩阵为对称矩阵.,非线性优化与动态规划 第一部分 绪论,向量函数的导数 定义4 设,如果,对于自变量,的各分量的偏导数,都存在，则称向量,函数h 在 处是一阶可导的，并且称矩阵,为h(x)在 处的,一阶导数或Jacobi 矩阵，简记为,非线性优化与动态规划 第一部分 绪论,n元函数,的梯度是向量函数,由上面定义知，f(x)的一阶导数或Jacobi矩阵为：,非线性优化与动