最优化方法课件01.1.ppt
- 文档编号:14668712
- 上传时间:2023-06-26
- 格式:PPT
- 页数:41
- 大小:724.50KB
最优化方法课件01.1.ppt
《最优化方法课件01.1.ppt》由会员分享,可在线阅读,更多相关《最优化方法课件01.1.ppt(41页珍藏版)》请在冰点文库上搜索。
最优化原理与方最优化原理与方法法辽宁科技大学理学院辽宁科技大学理学院任课教师:
陶玉敏任课教师:
陶玉敏2前言前言一、什么是最优化一、什么是最优化最优化是一门应用性相当广泛的学科,它讨论最优化是一门应用性相当广泛的学科,它讨论决策问题的最佳选择之特性,寻找最佳的计算方法,决策问题的最佳选择之特性,寻找最佳的计算方法,研究这些计算方法的理论性质及其实际计算表现。
研究这些计算方法的理论性质及其实际计算表现。
应用范围:
信息工程及设计、经济规划、生产管理、应用范围:
信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。
交通运输、国防工业以及科学研究等诸多领域。
3二、包含的内容二、包含的内容按照优化思想分为经典方法与现代方法。
按照优化思想分为经典方法与现代方法。
经典方法主要包括:
线性规划、非线性规划、整数规经典方法主要包括:
线性规划、非线性规划、整数规划、动态规划等划、动态规划等现代方法主要包括:
随机规划、模糊规划、模拟退火现代方法主要包括:
随机规划、模糊规划、模拟退火算法、遗传算法、禁忌搜索和人工神经网络等。
算法、遗传算法、禁忌搜索和人工神经网络等。
我们学习的内容主要是经典的最优化方法。
我们学习的内容主要是经典的最优化方法。
内容包括线性规划及其对偶规划,无约束最优化方法内容包括线性规划及其对偶规划,无约束最优化方法、约束最优化方法等主要内容。
、约束最优化方法等主要内容。
4三、学习方法三、学习方法1、认真听讲,课后及时复习巩固,并主动完成课、认真听讲,课后及时复习巩固,并主动完成课后习题。
后习题。
2、多看参考书,通过不同学者的讲述,全方位理、多看参考书,通过不同学者的讲述,全方位理解最优化方法的思想方法和应用,特别是计算方法解最优化方法的思想方法和应用,特别是计算方法。
3、学以致用,通过最优化方法的学习,培养研究、学以致用,通过最优化方法的学习,培养研究生数学建模的能力和解决实际问题的能力。
大家可生数学建模的能力和解决实际问题的能力。
大家可以尝试对于一些实际问题,先建立数学模型,转化以尝试对于一些实际问题,先建立数学模型,转化为数学问题,通过一些算法解决。
为数学问题,通过一些算法解决。
5四四、主要参考书、主要参考书1、薛嘉庆最优化原理与方法冶金工业出版社、薛嘉庆最优化原理与方法冶金工业出版社2、陈宝林最优化理论与算法清华大学出版社、陈宝林最优化理论与算法清华大学出版社3、席少霖非线性最优化方法高等教育出版社、席少霖非线性最优化方法高等教育出版社4、邓乃扬诸梅芳最优化方法辽宁教育出版社、邓乃扬诸梅芳最优化方法辽宁教育出版社5、袁亚湘最优化理论与方法科学出版社、袁亚湘最优化理论与方法科学出版社6、薛毅最优化原理与方法、薛毅最优化原理与方法7、曹卫华最优化技术方法及、曹卫华最优化技术方法及MATLAB的实现化的实现化学工业出版社学工业出版社第一章第一章第一章第一章最优化问题与数学预备最优化问题与数学预备最优化问题与数学预备最优化问题与数学预备知识知识知识知识71.11.1最优化问题实例最优化问题实例最优化问题实例最优化问题实例8例例例例1.1.11.1.1运输问题运输问题运输问题运输问题设有设有设有设有mm个水泥厂个水泥厂个水泥厂个水泥厂AA11,A,A22,A,Amm,年产量各为年产量各为年产量各为年产量各为aa11,a,a22,a,amm吨吨吨吨.有有有有kk个城市个城市个城市个城市BB11,B,B22,B,Bkk用这些用这些用这些用这些水泥厂生产的水泥水泥厂生产的水泥水泥厂生产的水泥水泥厂生产的水泥,年需求量年需求量年需求量年需求量bb11,b,b22,b,bkk吨吨吨吨.再设由再设由再设由再设由AAii到到到到BBjj每吨水泥的运价为每吨水泥的运价为每吨水泥的运价为每吨水泥的运价为ccijij元元元元.假假假假设产销是平衡的设产销是平衡的设产销是平衡的设产销是平衡的,即即即即:
11mkijijab=邋邋试设计一个调运方案试设计一个调运方案试设计一个调运方案试设计一个调运方案,在满足需要的同时使总在满足需要的同时使总在满足需要的同时使总在满足需要的同时使总运费最省运费最省运费最省运费最省.9A1由题意可画出如下的运输费用图由题意可画出如下的运输费用图由题意可画出如下的运输费用图由题意可画出如下的运输费用图:
B2AmB1A2Bk11kmijijjiScx=产量产量产量产量需求量需求量需求量需求量设设设设AAiiBBjj的水泥量为的水泥量为的水泥量为的水泥量为xxijij,已知已知已知已知AAiiBBjj单价为单价为单价为单价为ccijij,单位为元单位为元单位为元单位为元,则总运费为则总运费为则总运费为则总运费为:
1a2ama1b2bkb1011mkijijab=邋邋1111121201212min.(,)(,)(,)kmijijjikijijmijjiijcxstxaimxbjkximjk=LLLL数学模型数学模型数学模型数学模型:
注注注注:
平衡条件平衡条件平衡条件平衡条件作为已知条件并不出现在约束条件中作为已知条件并不出现在约束条件中作为已知条件并不出现在约束条件中作为已知条件并不出现在约束条件中.11例例例例1.1.21.1.2生产计划问题生产计划问题设某工厂有设某工厂有设某工厂有设某工厂有mm种资源种资源种资源种资源BB11,B,B22,B,Bmm,数量分别数量分别数量分别数量分别为为为为:
b:
b11,b,b22,b,bmm,用这些资源产用这些资源产用这些资源产用这些资源产nn种产品种产品种产品种产品AA11,A,A22,A,Ann.每生产一个单位的每生产一个单位的每生产一个单位的每生产一个单位的AAjj产品需要消耗产品需要消耗产品需要消耗产品需要消耗资源资源资源资源BBii的量为的量为的量为的量为aaijij,根据合同规定根据合同规定根据合同规定根据合同规定,产品产品产品产品AAjj的的的的量不少于量不少于量不少于量不少于ddjj.再设再设再设再设AAjj的单价为的单价为的单价为的单价为ccjj.问如何安排生产计划问如何安排生产计划问如何安排生产计划问如何安排生产计划,才能既完成合同才能既完成合同才能既完成合同才能既完成合同,又使又使又使又使该厂总收入最多该厂总收入最多该厂总收入最多该厂总收入最多?
12假设产品假设产品假设产品假设产品AAjj的计划产量为的计划产量为的计划产量为的计划产量为xxjj.由题意可画出如下的生产与消耗的关系图由题意可画出如下的生产与消耗的关系图由题意可画出如下的生产与消耗的关系图由题意可画出如下的生产与消耗的关系图:
B1B2BmAnA2A11b2bmb1d2dnd消耗消耗消耗消耗ija13数学模型数学模型数学模型数学模型111212max.(,)(,)njjjnijjijjjcxstaxbimxdjn=LL14例例例例1.1.31.1.3指派问题指派问题指派问题指派问题设有四项任务设有四项任务设有四项任务设有四项任务BB11,B,B22,B,B33,B,B44派四个人派四个人派四个人派四个人AA11,A,A22,A,A33,AA44去完成去完成去完成去完成.每个人都可以承担四项任务中的每个人都可以承担四项任务中的每个人都可以承担四项任务中的每个人都可以承担四项任务中的任何一项任何一项任何一项任何一项,但所消耗的资金不同但所消耗的资金不同但所消耗的资金不同但所消耗的资金不同.设设设设AAii完成完成完成完成BBjj所需资金为所需资金为所需资金为所需资金为ccijij.如何分配任务如何分配任务如何分配任务如何分配任务,使总支出最少使总支出最少使总支出最少使总支出最少?
设变量设变量设变量设变量10ijx=指派指派指派指派AAii完成完成完成完成bbjj不指派不指派不指派不指派AAii完成完成完成完成bbjj15则总支出可表示为则总支出可表示为则总支出可表示为则总支出可表示为:
4411ijijjiScx=数学模型数学模型数学模型数学模型:
41.1,1,2,3,4ijjstxi=411,1,2,3,4ijixj=4411minijijjiScx=011234,ijxij16例例例例1.1.41.1.4数据拟合问题数据拟合问题数据拟合问题数据拟合问题在实验数据处理或统计资料分析在实验数据处理或统计资料分析在实验数据处理或统计资料分析在实验数据处理或统计资料分析中常遇到如下问题中常遇到如下问题中常遇到如下问题中常遇到如下问题.设两个变量设两个变量设两个变量设两个变量xx和和和和y,y,已知已知已知已知存在函数关系存在函数关系存在函数关系存在函数关系,但其解析表达式或者是未知但其解析表达式或者是未知但其解析表达式或者是未知但其解析表达式或者是未知的或者虽然为已知的但过于复杂的或者虽然为已知的但过于复杂的或者虽然为已知的但过于复杂的或者虽然为已知的但过于复杂.设已取得一组数据设已取得一组数据设已取得一组数据设已取得一组数据:
(x(xii,y,yii)i=1,2,m.)i=1,2,m.根据这一组数据导出函数根据这一组数据导出函数根据这一组数据导出函数根据这一组数据导出函数y=f(x)y=f(x)的一个简单的一个简单的一个简单的一个简单而近似的解析表式而近似的解析表式而近似的解析表式而近似的解析表式.17最小二乘法最小二乘法最小二乘法最小二乘法解这种问题常用的方法是最小二乘法解这种问题常用的方法是最小二乘法解这种问题常用的方法是最小二乘法解这种问题常用的方法是最小二乘法,以一以一以一以一个简单的函数序列个简单的函数序列个简单的函数序列个简单的函数序列11(x),(x),22(x),(x),nn(x)(x)为基本函数为基本函数为基本函数为基本函数.一般选取一般选取一般选取一般选取1,x,x1,x,x22,x,xnn为基本函数为基本函数为基本函数为基本函数,即以即以即以即以0()njjjfxax=作为近似表达式作为近似表达式作为近似表达式作为近似表达式.18最小二乘法最小二乘法最小二乘法最小二乘法系数的选取要使得下面得平方和最小系数的选取要使得下面得平方和最小系数的选取要使得下面得平方和最小系数的选取要使得下面得平方和最小:
210()mnijjiijQyaxjj=-=-邋邋因此因此因此因此,数据拟合问题得数学模型为数据拟合问题得数学模型为数据拟合问题得数学模型为数据拟合问题得数学模型为210min()mnijjiijyaxjj=-邋邋其中其中其中其中xxii,yyii(ii=1,2,=1,2,mm)及及及及jj(xx)()(jj=0,1,=0,1,nn)为已为已为已为已知知知知.191.21.2最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念最优化问题的基本概念20最优化问题的一般形式为最优化问题的一般形式为最优化问题的一般形式为最优化问题的一般形式为:
min()fx012.(),isthxim=L012(),jgxjpL(1.1)(1.1)(目标函目标函目标函目标函数数数数)(1.31.3)()(不等式约不等式约不等式约不等式约束束束束)(1.2)(1.2)(等式约等式约等式约等式约束束束束)其中其中其中其中xx是是是是nn维向量维向量维向量维向量.在实际应用中在实际应用中在实际应用中在实际应用中,可以将求最大值的目标函数取可以将求最大值的目标函数取可以将求最大值的目标函数取可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式相反数后统一成公式中求最小值的形式相反数后统一成公式中求最小值的形式相反数后统一成公式中求最小值的形式.我们总是讨论我们总是讨论我们总是讨论我们总是讨论PP:
min()fx21相关定义相关定义相关定义相关定义定义定义定义定义1.2.1(1.2.1(可行解可行解可行解可行解)满足约束条件满足约束条件满足约束条件满足约束条件(1.2)(1.2)和和和和(1.3)(1.3)的的的的xx称为可行解称为可行解称为可行解称为可行解,也称为可行点或容许也称为可行点或容许也称为可行点或容许也称为可行点或容许点点点点.定义定义定义定义1.2.2(1.2.2(可行域可行域可行域可行域)全体可行解构成的集合称全体可行解构成的集合称全体可行解构成的集合称全体可行解构成的集合称为可行域为可行域为可行域为可行域,也称为容许集也称为容许集也称为容许集也称为容许集,记为记为记为记为DD,即即即即:
DD=xx|hhii(xx)=0,)=0,ii=1,=1,mm,ggjj(xx)0,)0,jj=1,=1,pp,xxRRnn.若若若若hhii(xx),),ggjj(xx)为连续函数为连续函数为连续函数为连续函数,则则则则DD为闭集为闭集为闭集为闭集.22相关定义相关定义相关定义相关定义定义定义1.2.3(整体最优解整体最优解)若若x*D,对于一对于一切切xD恒有恒有f(x*)f(x),则称则称x*为最优化问为最优化问题题(P)的整体最优解的整体最优解.若若x*D,xx*,恒有恒有f(x*)f(x),则称则称x*为为最优化问题最优化问题(P)的严格整体最优解的严格整体最优解.23定义定义定义定义1.2.4(1.2.4(局部最优解局部最优解局部最优解局部最优解)若若若若x*D,存在存在存在存在x*的某邻域的某邻域的某邻域的某邻域NN(xx*),*),使得对于一切使得对于一切使得对于一切使得对于一切xxDDNN(xx*),*),恒有恒有恒有恒有f(x*)f(x),则称则称则称则称x*为最优化问题为最优化问题为最优化问题为最优化问题(P)(P)的局的局的局的局部最优解部最优解部最优解部最优解,其中其中其中其中NN(xx*)=*)=xx|xx-xx*|*|0.0.当当当当xxxx*时时时时,若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称xx*为问题为问题为问题为问题(P)(P)的严格局部最优解的严格局部最优解的严格局部最优解的严格局部最优解.显然显然显然显然,整体最优解一定是局部最优解整体最优解一定是局部最优解整体最优解一定是局部最优解整体最优解一定是局部最优解,而局部而局部而局部而局部最优解不一定是整体最优解最优解不一定是整体最优解最优解不一定是整体最优解最优解不一定是整体最优解.x*对应的目标函数值对应的目标函数值f(x*)称为最优值,记为称为最优值,记为f*.24相关定义相关定义相关定义相关定义求解最优化问题求解最优化问题求解最优化问题求解最优化问题(PP),),就是求目标函数就是求目标函数就是求目标函数就是求目标函数ff(xx)在在在在约束条件约束条件约束条件约束条件(1.2),(1.3)(1.2),(1.3)下的极小点下的极小点下的极小点下的极小点,实际上是求实际上是求实际上是求实际上是求可行域可行域可行域可行域DD上的整体最优解上的整体最优解上的整体最优解上的整体最优解.但是但是但是但是,在一般情况在一般情况在一般情况在一般情况下下下下,整体最优解是很难求出的整体最优解是很难求出的整体最优解是很难求出的整体最优解是很难求出的,往往只能求出往往只能求出往往只能求出往往只能求出局部最优解局部最优解局部最优解局部最优解.在求解时需要范数的概念,以下给出定义。
在求解时需要范数的概念,以下给出定义。
在求解时需要范数的概念,以下给出定义。
在求解时需要范数的概念,以下给出定义。
25向量范数向量范数向量范数向量范数定义定义定义定义1.2.51.2.5如果向量如果向量如果向量如果向量xxRRnn的某个实值函数的某个实值函数的某个实值函数的某个实值函数|xx|,|,满足条件满足条件满足条件满足条件
(1)|
(1)|xx|0(|0(|xx|=0|=0当且仅当当且仅当当且仅当当且仅当xx=0)(=0)(正定性正定性正定性正定性););
(2)|
(2)|xx|=|=|xx|(|(对于任意对于任意对于任意对于任意RR););(3)|(3)|xx+yy|xx|+|+|yy|(|(三角不等式三角不等式三角不等式三角不等式););则称则称则称则称|xx|为为为为RRnn上的一个向量范数上的一个向量范数上的一个向量范数上的一个向量范数.26常用的向量范数常用的向量范数常用的向量范数常用的向量范数1-1-范范范范数数数数11|niixx=2-2-范数范数范数范数(欧氏范欧氏范欧氏范欧氏范数数数数)12221|(|)niixx=-范数范数范数范数1|max|iinxx=pp-范数范数范数范数11|(|)npppiixx=|lim|ppxx=-范数是范数是范数是范数是pp-范数的极限范数的极限范数的极限范数的极限27常用的向量范数常用的向量范数常用的向量范数常用的向量范数对向量对向量对向量对向量xx=(1,-2,3)=(1,-2,3)TT,有有有有1|6,x=2|143.74166,x=33|363.30193,x=|3.x=|xx|pp是是是是pp的单调递减函数的单调递减函数的单调递减函数的单调递减函数.28最优化问题的分类最优化问题的分类最优化问题的分类最优化问题的分类根据数学模型中有无约束函数分为有约束的根据数学模型中有无约束函数分为有约束的根据数学模型中有无约束函数分为有约束的根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题最优化问题和无约束的最优化问题最优化问题和无约束的最优化问题最优化问题和无约束的最优化问题.根据目标函数和约束函数的函数类型分类根据目标函数和约束函数的函数类型分类根据目标函数和约束函数的函数类型分类根据目标函数和约束函数的函数类型分类:
线性最优化问题线性最优化问题线性最优化问题线性最优化问题,非线性最优化问题非线性最优化问题非线性最优化问题非线性最优化问题,二次规二次规二次规二次规划划划划,多目标规划多目标规划多目标规划多目标规划,动态规划动态规划动态规划动态规划,整数规划整数规划整数规划整数规划,0-1,0-1规规规规划划划划.291.31.3梯度与梯度与梯度与梯度与HesseHesse矩阵矩阵矩阵矩阵30cxbxxqxxxfniiininjjiijn1112121),(iijbq,cxbQxxxfTT21)(nn元函数元函数元函数元函数其中都是实常数,且。
jiijqq矩阵形式矩阵形式其中是对称矩阵,)(ijqQ.),(21Tnbbbb31,:
01DxRRDfn且设如果存在维向量维向量,对于任意的维对于任意的维向量使得向量使得那么称函数在点处可微。
若令便得到(1.4)的等价形式(1.5)(1.4)nlnp0)()(000limpplxfpxfTp)(xf0xpplxfpxfT)()(00)()()(00poplxfpxfTnn元函数的可微性元函数的可微性元函数的可微性元函数的可微性32nn元函数的梯度元函数的梯度元函数的梯度元函数的梯度梯度:
多元函数关于的梯度:
多元函数关于的梯度:
多元函数关于的梯度:
多元函数关于的一阶一阶一阶一阶导数导数导数导数12()(,)Tnffffxxxx抖抖L()fxx定理:
若在点处可微,则在该点关于各个变量的一阶偏导数存在,并且1:
RRfn0xTnxxfxxfxxfl)(,)(,)(02010331:
RRfn方向导数设在点处可微,是非零向量方向上的单位向量。
则称其为函数在点处沿方向的方向导数,方向导数,记作思考:
与的异同?
0xeptxftexft)()(000lim)(xf0xppxf)(.)(0pxfnxxfxxfxxf)(,)(,)(21如果极限存在,如果极限存在,34HesseHesse矩阵:
多元函数关于的二矩阵:
多元函数关于的二矩阵:
多元函数关于的二矩阵:
多元函数关于的二阶偏导数矩阵阶偏导数矩阵阶偏导数矩阵阶偏导数矩阵()()()()()()()()()()()()22222111222221222222212fXfXfXxxxxnxfXfXfXfXfXxxxxnxfXfXfXxxxxnnxn轾轾犏犏抖抖犏犏犏犏抖抖抖抖犏犏犏犏抖抖犏犏蜒=蜒=犏犏抖抖犏犏犏犏犏犏犏犏抖抖犏犏抖抖犏犏犏犏臌臌LLLLMMMMMMLL()fxx35Txxxxxxxxf233122122,3222,2223322xxxxf21122xxxxf32223122xxxxxf例:
求目标函数的梯度和例:
求目标函数的梯度和Hesse矩阵。
矩阵。
解:
因为解:
因为则则23221232221322)(xxxxxxxxxf362202220222Xf2,2,20,2,2232322222312212212xfxxfxfxxfxxfxf例:
求目标函数的梯度和例:
求目标函数的梯度和Hesse矩阵。
矩阵。
又因为:
又因为:
故故Hesse阵为:
阵为:
23221232221322)(xxxxxxxxxf37nnxfbxf0.2Ixfxxf2.2QxfQxxf.:
1RRfn.:
11RR下面几个公式是今后常用到的:
下面几个公式是今后常用到的:
(1),则),则
(2),则),则xbxfT)(xxxfT21)(QxxxfT21)((3),),Q对称,则对称,则(4)若)若,其中:
,其中:
则:
则:
)()(0tpxftptpxfptptpxftTT)()()()(020381.41.4多元函数的多元函数的多元函数的多元函数的TaylorTaylor展开式展开式展开式展开式39多元函数的多元函数的多元函数的多元函数的TaylorTaylor展开展开展开展开多元函数多元函数TaylorTaylor展开式在最优化理论中十分展开式在最优化理论中十分重要。
许多方法及其收敛性的证明都是从它出重要。
许多方法及其收敛性的证明都是从它出发的。
发的。
1:
nfRRpxfppxfxfpxfTT)(21)()()(2pxx10定理:
设具有二阶连续偏定理:
设具有二阶连续偏导数,则:
导数,则:
其中而其中而40)|(|21|)(|202000000popxfppxfxfpxfpopxfxfpxfTTT多元函数多元函数TaylorTaylor展开其他形式:
展开其他形式:
()()()()000220000()1()()(|)2TTfxfxfxxxxxfxxxoxx=+=+-+-+-+-41练习:
练习:
练习:
练习:
11、求、求、求、求的梯度和的梯度和的梯度和的梯度和HesseHesse矩阵。
矩阵。
矩阵。
矩阵。
22、把二次函数、把二次函数、把二次函数、把二次函数写成矩阵形式。
写成矩阵形式。
写成矩阵形式。
写成矩阵形式。
22212313()3234fxxxxxx=+-221122()23fxxxxx=+
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 方法 课件 01.1
![提示](https://static.bingdoc.com/images/bang_tan.gif)