最优化方法课件2011级课件.ppt

最优化方法 南京邮电大学理学院 目录 第一章 最优化问题概述 第二章 线性规划 第三章 无约束最优化方法 第四章 约束最优化方法 第一章最优化问题概述 §1.1 最优化问题的数学模型与基本概念 例 1.1.1 运输问题 设有m个水泥厂A1,A2, …, Am,年产量各为a1, a2, …,am吨.有k个城市B1,B2…, Bk用这些水泥厂生产的水泥,年需求量b1,b2, …,bk吨.再设由Ai到Bj每吨水泥的运价为cij元.假设产销是平衡的,即: 由题意可画出如下的运输费用图: 例1.1.2 生产计划问题 设某工厂有m种资源B1,B2, …,Bm,数量分别为: b1,b2, …, bm,用这些资源产n种产品A1,A2, …, An.每生产一个单位的Aj产品需要消耗资源Bi的量为aij,根据合同规定,产品Aj的量不少于dj.再设Aj的单价为cj. 问如何安排生产计划,才能既完成合同,又使该厂总收入最多? 数学模型 例 1.1.3 指派问题 设有四项任务B1,B2,B3,B4派四个人A1,A2, A3,A4去完成.每个人都可以承担四项任务中的任何一项,但所消耗的资金不同.设Ai完成Bj所需资金为cij. 如何分配任务,使总支出最少? 设变量 则总支出可表示为: 例 1.1.4 数据拟合问题 在实验数据处理或统计资料分析中常遇到如下问题.设两个变量x和y,已知存在函数关系,但其解析表达式或者是未知的或者虽然为已知的但过于复杂. 设已取得一组数据: (xi,yi) i=1,2,…,m. 根据这一组数据导出函数y=f(x)的一个简单而近似的解析表式. 最小二乘法 解这种问题常用的方法是最小二乘法,以一个简单的函数序列 j1(x), j2(x),···, jn(x) 为基本函数. 一般选取1,x,x2,···,xn为基本函数,即以 最小二乘法 系数的选取要使得下面得平方和最小: 最优化问题 最优化问题的一般形式为: 相关定义 定义1.1.1 (可行解) 满足约束条件(1.2)和(1.3)的x称为可行解,也称为可行点或容许点. 相关定义 定义1.1.3 (整体最优解) 若x*∈D,对于一切x∈D恒有f(x*)≤f(x),则称x*为最优化问题(P)的整体最优解. 若x*∈D,x≠x*, 恒有f(x*) f(x),则称x*为最优化问题(P)的严格整体最优解. 相关定义 定义1.1.4 (局部最优解) 若x*∈D,存在x*的某邻域Ne(x*),使得对于一切x∈D∩Ne(x*),恒有f(x*)≤f(x),则称为最优化问题(P)的局部最优解,其中Ne(x*)={x| ||x-x*||e,e0}. 当x≠x*时,若上面的不等式为严格不等式则称x*为问题(P)的严格局部最优解. 显然,整体最优解一定是局部最优解,而局部最优解不一定是整体最优解. x*对应的目标函数值f(x*)称为最优值，记为f *. 相关定义 求解最优化问题(P),就是求目标函数f(x)在约束条件(1.2),(1.3)下的极小点,实际上是求可行域D上的整体最优解.但是,在一般情况下,整体最优解是很难求出的,往往只能求出局部最优解. 在求解时需要范数的概念，以下给出定义。 向量范数 定义1.1.5 如果向量x∈Rn 的某个实值函数||x||,满足条件 (1)||x||≥0(||x||=0当且仅当x=0)(正定性); (2)||ax||=|a|·||x||(对于任意a∈R); (3) ||x+y||≤||x||+||y||(三角不等式); 则称||x||为Rn 上的一个向量范数. 常用的向量范数 1-范数 常用的向量范数 对向量x=(1,-2,3)T,有 最优化问题的分类 根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题. 根据目标函数和约束函数的函数类型分类:线性最优化问题,非线性最优化问题,二次规划,多目标规划,动态规划,整数规划,0-1规划. §1.2 最优化问题的一般算法 迭代算法 迭代算法 选取一个初始可行点x0∈D,由这个初始可行点出发,依次产生一个可行点列: x1,x2,···,xk,···, 记为{xk},使得某个xk恰好是问题的一个最优解,或者该点列收敛到问题的一个最优解x*. 下降算法 在迭代算法中一般要求 f(xk+1)≤f(xk). 可行点列的产生 在xk处求得一个方向pk(下降方向),在射线xk+apk(a 0)上求一点: xk+1=xk+akpk 使得f(xk+1)≤f(xk).其中ak称为步长. 定义1.2.1(下降方向) 在点xk处,对于方向pk≠0, 若存在实数b 0,使得任意的a∈(0,b ),有: f(xk+apk)f(xk), 则称pk