《CAN-File-10-10-08-13-实用优化方法引言PPT优秀课件》由会员分享，可在线阅读，更多相关《CAN-File-10-10-08-13-实用优化方法引言PPT优秀课件（17页珍藏版）》请在金锄头文库上搜索。
1、实用优化方法实用优化方法(最优化理论与算法最优化理论与算法B)54课时课时/3学分学分刘红英刘红英数学与系统科学学院数学与系统科学学院(个人邮箱个人邮箱)buaa_(公共邮箱，密码：公共邮箱，密码： 111222)http:/ 介绍线性与非线性规划的介绍线性与非线性规划的基本理论、实用算法和部分应用基本理论、实用算法和部分应用 具体的主题包括：具体的主题包括：线性规划线性规划 基本性质、单纯形法、对偶理论、基本性质、单纯形法、对偶理论、网络流问题、整数规划网络流问题、整数规划非线性规划非线性规划 最优性条件、凸性、最优性条件、凸性、LagrangeLagrange对偶、半定规划对偶、半定规划
2、无约束优化的算法：线搜索法和无约束优化的算法：线搜索法和信赖域法信赖域法 约束优化的算法：二次规划、罚函数法、约束优化的算法：二次规划、罚函数法、SQPSQP法法多目标决策简介多目标决策简介 ParetoPareto最优性和折衷曲线最优性和折衷曲线 目标规划目标规划先修课程：先修课程：线性代数，高等数学，线性代数，高等数学，最好会某种高级语言最好会某种高级语言考核：考核：活动活动平时和作业平时和作业实践环节实践环节期中考试期中考试期末考试期末考试百分比百分比20%10%30%40%实践环节：实践环节：1. 学习并使用优化软件学习并使用优化软件 2. 撰写课程小论文撰写课程小论文/实现某些算法实
3、现某些算法课本与教辅材料：课本与教辅材料：1. 刘红英，实用优化方法讲义，北京航空航天大学，数学与系统科学学刘红英，实用优化方法讲义，北京航空航天大学，数学与系统科学学院，院，2010年年2月月.2. 陈宝林，最优化理论与算法陈宝林，最优化理论与算法(第二版第二版)，清华大学出版社，清华大学出版社3. 其它任何您熟悉或者喜欢的其它任何您熟悉或者喜欢的实用优化方法实用优化方法第章引言第章引言刘红英刘红英理学院数学系理学院数学系1.1 数学描述与例子数学描述与例子目目 标标：系统性能的一种：系统性能的一种“量的度量量的度量”( (利润、时间、势能利润、时间、势能) )任何数量或某些任何数量或某些量
4、的组合数量的组合数变变 量量：目标所依赖的系统的：目标所依赖的系统的“某些某些可可控的特征控的特征”约束条件约束条件：经常变量以某种方式受限制：经常变量以某种方式受限制( (分分子中电子密度的量、贷款利率的量，不能子中电子密度的量、贷款利率的量，不能是负的是负的) )-优化问题的一般模型优化问题的一般模型数学规划问题数学规划问题优化建模优化建模(modeling)：识别出给定识别出给定问题的目标、变量和约束的过程。问题的目标、变量和约束的过程。建立恰当模型：第一步、最重要的一步建立恰当模型：第一步、最重要的一步(太太简单简单不能给实际问题提供有用的信息；不能给实际问题提供有用的信息；太复杂太复
5、杂不易求解不易求解)选择特定算法：很重要选择特定算法：很重要-决定求解速度及质决定求解速度及质量量(无通用无通用优化算法，有优化算法，有求解特定类型求解特定类型优化优化问题的算法问题的算法)优化实例：优化实例：运输问题运输问题(transportation problem)背背 景：景：化学制品公司考虑某种产品的产销问题化学制品公司考虑某种产品的产销问题. .数据：数据： 问题：问题：确定从每个工厂运送到每个销地的产品确定从每个工厂运送到每个销地的产品数量，使其满足需求，同时极小化费用数量，使其满足需求，同时极小化费用变变 量：量： 的产品数量的产品数量目标函数：目标函数：产量约束：产量约束：
6、销量约束：销量约束：非负约束：非负约束：问题中问题中目标目标和和约束函数约束函数都是都是线性函数线性函数, , 称此类型的问题为称此类型的问题为线性规划问题线性规划问题. .优化实例优化实例2：数据拟合数据拟合(data fitting problem)已知已知：推测推测：信号具有指数衰减和振荡行为！：信号具有指数衰减和振荡行为！模型函数模型函数( (经验函数经验函数) )：其中其中 是是待定参数待定参数变量：变量：余量余量/残差残差(residual)：非线性最小二乘问题非线性最小二乘问题确定参数！确定参数！注注1 1： 它说明即使变量数很小，计算目标函数也可能它说明即使变量数很小，计算目标
7、函数也可能很昂贵很昂贵. .这里，这里，n=6n=6， m m很大很大( (比如比如105).105).注注2 2：数据拟合、参数估计、回归分析数据拟合、参数估计、回归分析等许多问题中等许多问题中均涉及此类优化问题均涉及此类优化问题. .有专用的算法求解有专用的算法求解. .1.2 数学规划问题的分类与特征数学规划问题的分类与特征某些或全部变量某些或全部变量取整数值取整数值才有意义才有意义-整数规划整数规划 (IP). (IP). (上述运输问题中，工厂生产拖拉机而非化上述运输问题中，工厂生产拖拉机而非化学产品学产品).).分为分为整数线性规划整数线性规划和整数非线性规划；和整数非线性规划；整
8、数规划整数规划和混合整数规划；一般整数规划和和混合整数规划；一般整数规划和0-10-1整数规划整数规划简单松弛策略简单松弛策略. . 忽略整数要求，当成实变量来求忽略整数要求，当成实变量来求解问题，然后将所有分量舍入到最近的整数解问题，然后将所有分量舍入到最近的整数-可可给出问题的界给出问题的界. .LagrangeLagrange松弛策略松弛策略. . 整数规划属整数规划属NPNP难问题难问题. . 常用算法：分支定界法、常用算法：分支定界法、或其他启发式算法或其他启发式算法( (求解一系列连续优化问题求解一系列连续优化问题) )连续与离散连续与离散约束与无约束约束与无约束无约束优化肯定是非
9、线性的、约束优化又分线性规划无约束优化肯定是非线性的、约束优化又分线性规划和非线性规划和非线性规划局部与全局局部与全局单目标与多目标单目标与多目标随机与确定随机与确定 有的问题进行优化建模时，模型与一些不能提前确定的有的问题进行优化建模时，模型与一些不能提前确定的参数有关参数有关( (运输问题中，零售市场的需求在实际中不能够精运输问题中，零售市场的需求在实际中不能够精确确定确确定. . 许多经济和金融规划模型也具有该特征许多经济和金融规划模型也具有该特征, , 哪里经常哪里经常与未来的利息率和经济的未来趋向有关与未来的利息率和经济的未来趋向有关).).多目标规划最重要的是多目标规划最重要的是P
10、eratoPerato解解/ /有效解有效解的概念；一般的概念；一般可用可用标量化方法标量化方法求求PeratoPerato解解优化问题的简单分类与求解难度优化问题的简单分类与求解难度问题的求解难度问题的求解难度依次增加依次增加！1.3 1.3 优化算法和优化软件优化算法和优化软件迭代法迭代法从最优解的从最优解的某个初始猜测某个初始猜测出发，生成一个出发，生成一个提高的提高的估计序列，直到达到一个解估计序列，直到达到一个解. .大部分利用大部分利用目标函数和约束目标函数和约束，可能还有，可能还有这些函数这些函数的一阶和二阶导数的一阶和二阶导数. .通常收敛到通常收敛到 ( (无约束问题无约束问
11、题) )驻点驻点或者或者 ( (约束问题约束问题) )KKTKKT点点( (极大点、极小点或鞍点极大点、极小点或鞍点).). 如果问题是如果问题是凸规划凸规划，则可确保算法，则可确保算法收敛到全局极小点收敛到全局极小点. 优化算法优化算法AMPL: A Modeling Language for Mathema-tical Programming Lindo/Lingo软件软件(verb http:/Matlab优化工具箱优化工具箱(见姜启源等编的见姜启源等编的数学实验数学实验,高教出版社高教出版社)Cplex其它其它(Mathematica, Minos, Excel等的优化功能等的优化功能). 优化软件优化软件
