工程优化方法第1章PPT演示课件

1、1,最优化方法,2,主要内容,第一章 最优化简介 第二章 基本概念和理论基础 第三章 线性规划 第四章 最优化搜索算法结构与一维搜索 第五章 无约束最优化方法 第六章 约束最优化方法,3,第一章,最优化简介,4,最优化寻求最优方案的方法称为最优化方法。 最优方案：从所有可能的方案中选择最合理的一 种以达到最优目标。 最优目标：与工程设计密切相关。如：产值最大、 耗能最小、 速度最快等等。 处理方法：对实际问题建立一个数学模型。 发展过程运筹学、线性规划、非线性规划、动态规划、组合优化等。 促进最优化发展的主要因素 近代科技与生产发展的需要 计算机技术的飞速发展,5,参考书目 最优化理论与方法袁

2、亚湘等编，科学出版社 数学规划讲义马仲蓄等编，人大出版社 实用线性规划D.M希梅尔布劳著 无约束最优化计算方法邓乃杨等编 基础：高等数学，线性代数,6,1 最优化问题的数学模型及分类,共同特点： 求x1 ,x2 ,xn 使函数f（ x1 ,x2 ,xn） （被称为目标函数或评价函数） 达到极小min； 若求极大max，相当于一个min（-f,7,优化模型的一般形式,min. f ( xi, yj, k ) s.t. gh ( xi, yj, k ) , 0 h = 1,2, ,m 其中： xi 为决策变量（可控制） yj 为已知参数 k 为随机因素 f , gh 为（一般或广义）函数 建模举例

3、（略） 自看,8,一）根据问题的不同特点分类 无约束最优化问题 约束最优化问题 等式约束优化问题 不等式约束优化问题,9,一般的约束优化问题 以上为标准形式，某些问题可标准化： 1） 2,10,二）根据函数类型分类 线性规划：目标函数、约束条件都是线性的 二次规划：目标函数为二次函数，约束条件 中的函数为线性的。 非线性规划：目标函数不是一次or二次的， 或约束条件中的函数不全是线 性的。 （三）根据函数性质分类 动态与静态 随机与确定 单目标与多目标,11,四）解法的分类 解析方法:利用函数的分析性质去构造迭代 公式，使之收敛到极值点。 直接方法：按一定的数学原理，用尽量少的 计算量，直接比

4、较函数值的大小,12,2 最优化方法解决问题的工作步骤,1 ）提出问题：目标、约束、决策变量、参数 2 ）建立模型：变量、参数、目标之间的关系 表示 3 ）模型求解：数学方法及其他方法 4 ）解的检验：制定检验准则、讨论与现实的 一致性 5 ）灵敏性分析：参数扰动对解的影响情况 6 ）解的实施：回到实践中 7 ）后评估：考察问题是否得到完满解决,13,1、最优解与极值点 容许解集： Def1:若 使得 ，恒有 称 为问题（p）的最优解or全局极小 值点。记 g.opt.( global optimum),简 记 opt,3 基本概念,14,Def2:若 ，使得 ， 恒有 ， 称 为问题（p）的

5、严格全局极小值点。 Def3:若 ， 使得 ，恒有 称 为问题（p）的局部极小值点。 记 l .opt.(local optimum) Def4:若 ， 恒有 ， 称 为问题（p）的严格局部极小值点,15,严格l .opt,严格g .opt,l .opt,16,由以上定义，可得到两个简单定理： Th1：问题（p）的任意全局极小值点必为局部 极小值点。 Th2：若目标f(x)和g(x)都为定义域上的连续 函数，则： （1）问题（p）的容许解集R为闭集。 （2）问题（p）的最优解集R为闭集,17,2、向量和子空间投影定理 (1) n维欧氏空间：Rn 点（向量）：x Rn, x = (x1 ,x2

6、,xn)T 分量 xi R (实数集) 方向（自由向量）：d Rn, d 0 d =(d1 ,d2 ,dn)T 表示从0指向d 的方向 实用中，常用 x + d 表示从x 点出发沿d 方向移动d 长度得到的点,d,0,x,x+(1/2)d,18,2) 向量运算：x , y Rn x , y 的内积：xTy = xiyi = x1y1+ x2y2+ + xnyn i =1 x , y 的距离： x-y = (x-y)T(x-y)(1/2) x 的长度： x= xTx (1/2) 三角不等式： x + y xy 点列的收敛：设点列x(k) Rn , x Rn 点列x(k)收敛到 x ，记 lim

7、x(k) = x limx(k)- x = 0 lim xi(k) = xi ,i k k k,x+y,y,x,19,3) 子空间：设 d (1) , d (2) , , d (m) Rn, d (k) 0 m 记 L( d (1) , d (2) , , d (m) )= x = j d (j) jR j =1 为由向量d (1) , d (2) , , d (m) 生成的子空间，简记 为L。 正交子空间：设 L 为Rn的子空间，其正交子空间为 L x Rn xTy=0 , y L 子空间投影定理：设 L 为Rn的子空间。那么 z Rn， 唯一 x L , y L, 使 z=x+y , 且

8、x 为问题 min z - u s.t. u L 的唯一解，最优值为y。 特别， L Rn 时，正交子空间 L 0 （零空间,20,规定：x , y Rn，x y xi yi ，i 类似规定 x y，x = y，x y . 一个有用的定理: 设 xRn，R，L为Rn 的线性子空间， (1)若 xTy , yRn 且 y 0， 则 x 0， 0 . (2)若 xTy , y L Rn ， 则 x L， 0 .(特别, LRn时,x =0) 定理的其他形式： “若 xTy , yRn 且 y 0，则 x 0， 0 .” “若 xTy , yRn 且 y 0，则 x 0， 0 .” “若 xTy ,

9、 yRn 且 y 0，则 x 0， 0 .” “若 xTy , y L Rn ， 则 x L， 0 .,21,3、多元函数及其导数 (1) n元函数：f (x): Rn R 线性函数：f (x) = cTx + b = ci xi + b 二次函数：f (x) = (1/2) xTQx + cTx + b = (1/2)i j aij xi xj + ci xi + b 向量值线性函数：F(x) = Ax + d Rm 其中 A为 mn矩阵，d为m维向量 F(x)=( f1(x), f2(x), , fm(x) )T 记 aiT为A的第i行向量，fi(x) = aiTx+di,22,2) 梯度

10、（一阶偏导数向量）： f (x) Rn . 线性函数：f (x) = cTx + b , f (x) = c 二次函数：f (x) = (1/2) xTQx + cTx + b f (x) = Qx + c 注：Q为对称阵 向量值线性函数：F(x) = Ax + d Rm F / x = AT,23,3) Hesse 阵（二阶偏导数矩阵）： 线性函数：f (x) = cTx + b , 2f (x) = 0 二次函数：f (x) = (1/2) xTQx + cTx + b, 2f(x)=Q 注：Q为对称阵,24,4)n元函数的Taylor展开式及中值公式： 设 f (x): Rn R ，二阶

11、可导。在x* 的邻域内 一阶Taylor展开式： f (x) = f (x*)+ f T(x*)(x-x*) + ox-x* 二阶Taylor展开式： f (x) = f (x*)+ f T(x*)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + ox-x*2 一阶中值公式：对x, , 使 f (x) = f (x*)+ f (x*+(x-x*)T(x-x*) Lagrange余项：对x, , 记xx*+ (x-x*) f (x) = f (x*)+ f T(x*)(x-x*) + (1/2)(x-x*)T H (x )(x-x*,25,5)多元函数的极值 二元函数

12、Th1(必要条件)（可微的极值点为驻点）： 设f(x,y): D ( ) (D定义域) (1) 为D的一个内点; (2) f(x,y)在 可微; (3) 为f(x,y)的极值点; 则: 在 处,26,Th2(充分条件) ： 设f(x,y): D ( ) (D定义域) (1) 为D的一个内点; (2) f(x,y)在 处二次可微; (3) ; (即: ) 则:. 若 , (矩阵正定) 则 为f(x,y)的严格极小点,27,则:. 若 , (矩阵负定) 则 为f(x,y)的严格极大点. .若 , 则 不是f(x,y)的极值点.,此时称 为f(x,y)的鞍点,28,一般多元函数的极值判别条件 Th3(必要条件)（可微的极值点为驻点）： 设 f: D ( ) (D定义域) (1) 为D的一个内点; (2) f(x)在 可微; (3) 为f(x)的极值点; 则,29,Th3(充分条件) ： 设 f