北航最优化教材
- 格式:pdf
- 大小:5.06 MB
- 文档页数:78
1 流量工程问题1.1 问题重述定义一个有向网络G=(N,E),其中N是节点集,E是弧集。
令A是网络G的点弧关联矩阵,即N×E阶矩阵,且第l列与弧里(I,j)对应,仅第i行元素为1,第j行元素为-1,其余元素为0。
再令b m=(b m1,…,b mN)T,f m=(f m1,…,f mE)T,则可将等式约束表示成:Af m=b m本算例为一经典TE算例。
算例网络有7个节点和13条弧,每条弧的容量是5个单位。
此外有四个需求量均为4个单位的源一目的对,具体的源节点、目的节点信息如图所示。
这里为了简单,省区了未用到的弧。
此外,弧上的数字表示弧的编号。
此时,c=((5,5…,5)1 )T,×13)。
根据上述四个约束条件,分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1×13图 1 网络拓扑和流量需求1.2 7节点算例求解1.2.1 算例1(b1=[4;-4;0;0;0;0;0]T)转化为线性规划问题:Minimize c T x1Subject to Ax1=b1x1>=0利用Matlab编写对偶单纯形法程序,可求得:最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T对应的最优值c T x1=201.2.2 算例2(b2=[4;0;-4;0;0;0;0]T)Minimize c T x2Subject to Ax2=b2X2>=0利用Matlab编写对偶单纯形法程序,可求得:最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T对应的最优值c T x2=201.2.3 算例3(b3=[0;-4;4;0;0;0;0]T)Minimize c T x3Subject to Ax3=b3X3>=0利用Matlab编写对偶单纯形法程序,可求得:最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T对应的最优值c T x3=401.2.4 算例4(b4=[4;0;0;0;0;0;-4]T)Minimize c T x4Subject to Ax4=b4X4>=0利用Matlab编写对偶单纯形法程序,可求得:最优解为x4*=[4 0 0 4 0 0 0 0 0 4 0 0 0]T对应的最优值c T x4=601.3 计算结果及结果说明1.3.1 算例1(b1=[4;-4;0;0;0;0;0]T)算例1中,由b1可知,节点2为需求节点,节点1为供给节点,由节点1将信息传输至节点2的最短路径为弧1。
结构优化设计课程总结通过对本课程的学习,我了解到工程设计的过程中,一般都是先粗略估计一些数值,然后进行校核分析,如果不合适,则需进一步修正数值后校核,使数值进一步去拟合理想值,如此多次进行以达到最优的效果。
但是这样做周期会比较长,计算量也比较大。
这门课就是讲解这些算法如何优化的。
由此总结出本课程前后主要由三部分构成。
第一,优化设计的基本理论,包括结构优化设计的数学模型、线性规划基本理论和计算方法、无约束非线性规划和约束非线性规划的基本理论、多种计算方法的公式、性质和流程、多目标优化的基本理论和计算方法;第二,工程结构优化设计,包括适用于工程设计的优化准则法、对飞行器结构设计具有重要意义的结构可靠性优化设计;第三,飞行器优化设计技术的新发展,包括多学科设计优化(MDO)、遗传算法及改进、智能优化设计技术。
这些分析方法都是以计算机为工具,将非线性数学规划的理论和力学分析方法结合,使用于受各种条件限制的承载结构设计情况。
优化问题的数学意义是在不等式约束条件下,求出使目标函数为最小或最大值的一组设计变量值。
在实际工程应用中,优化问题所包含的函数通常是非线性的和隐式的。
因此建立在数学规划基础上的优化算法,是依据当前设计方案所对应的函数值与导数值等信息,按照某种规则在多维设计变量空间中进行搜索,一步一步逼近优化解,也就是一个迭代的过程。
故在计算机上进行该类运算会更加具有实际意义。
一、有限元素法这是基于在结构力学、材料力学和弹性力学基础上的一种分析方法。
研究杆、梁,经简化薄板组成的结构的应力、变形等问题。
其方法是首先通过力学分析将结构离散化成单一元素,然后对单一元素进行分析,算出各单元刚度矩阵后,进行整体分析,根据方程组K·u=P求解。
这种方法求解的问题受限于结构的规模、形式和效率。
在有限元素法中,用网格将结构划分为若干小块,这些小块称为有限元素,简称有限元。
它们可以是三角形、四边形、四面体、六面体或其他形状,易于为计算机记录和鉴别。
《最优化方法》课程教学大纲Methods of Optimization课程代码: 课程性质:专业基础理论课/选修适用专业:信息计算、统计学开课学期:6总学时数:56总学分数:3.5编写年月:2002年3月修订年月:2007年7月执笔:刘伟一、课程的性质和目的最优化计算方法是在生产实践和科学实验中选取最佳决策,研究在一定限制条件下,选取某种方案,以达到最优目标的一门学科,广泛应用与空间科学、军事科学、系统识别、通讯、工程设计、自动控制、经济管理等各个领域,是工科院校高年纪学生、研究生、应用数学专业学生和搞优化设计的工程技术人员的一门重要课程。
通过本课程教学,使学生掌握最优化计算方法的基本概念和基本理论,初步学会处理应用最优化方法解决实际中的碰到的各个问题,培养解决实际问题的能力。
二、课程教学内容及学时分配(一)教学内容1. 最优化方法和最优化模型最优化方法定义、最优化问题的数学模型与分类;根据问题特点(无约束最优化与约束最优化),根据函数类型(线性规划,非线性规划);最优化方法(解析法,直接法),最优解与极值点。
2.基础知识多元函数泰勒公式的矩阵形式,古典极值理论问题,二次函数求梯度公式,凸集,凸函数,凸规划,几个重要的不等式。
3. 常用的一维搜索方法一维搜索法是最优化的基础,“成功-失败”法的思想与算法,黄金分割法(0.618法)的思想与算法,二次插值法,三次插值法,D。
S。
C法,Powell 法等方法的思想与算法。
4. 无约束最优化方法无约束最优化方法是最优化方法中的基本方法。
最速下降法的思想与算法步骤,牛顿法的思想与算法步骤,共轭方向法的思想与算法步骤,共轭梯度法的思想与算法步骤,变尺度法(DFP法和BFGS法)的思想与算法步骤5. 约束最优化方法约束最优化方法通常约束问题转化为无约束问题求解。
序列无约束极小化方法(SUMT-外点法与SUMT-内点法)的思想与算法步骤,内点的求法,其他罚函数法,Frank-Wolfe法的思想与算法步骤6. 直接搜索法Powell方向加速法的思想与算法步骤学时分配三、课程教学的基本要求1. 最优化模型了解最优化的数学模型与分类, 理解最优化模型的分类标准及最优化模型解法分类。
《最优化方法》课程教学大纲课程编号:英文名称:Optimization Methods一、课程说明1. 课程类别理工科学位基础课程2. 适应专业及课程性质理、工、经、管类各专业,必修文、法类各专业,选修3.课程目的(1)使学生掌握最优化问题的建模、无约束最优化及约束最优化问题的理论和各种算法;(2)使学生了解二次规划与线性分式规划的一些特殊算法;(3)提高学生应用数学理论与方法分析、解决实际问题的能力以及计算机应用能力。
4. 学分与学时学分2,学时405. 建议先修课程微积分、线性代数、Matlab语言6. 推荐教材或参考书目推荐教材:(1)《非线性最优化》(第一版). 谢政、李建平、汤泽滢主编.国防科技大学出版社. 2003年(2)《最优化方法》(第一版). 孙文瑜、徐成贤、朱德通主编. 高等教育出版社. 2004年参考书目:(1)《最优化原理》(第一版). 胡适耕、施保昌主编. 华中理工大学出版社. 2000年(2)《运筹学》》(修订版). 《运筹学》教材编写组主编. 清华大学出版社. 1990年7. 教学方法与手段(1)教学方法:启发式(2)教学手段:多媒体演示、演讲与板书相结合8. 考核及成绩评定考核方式:考试成绩评定:考试课(1)平时成绩占20%,形式有:考勤、课堂测验、作业完成情况。
(2)考试成绩占80%,形式有:笔试(开卷)。
9. 课外自学要求(1)课前预习;(2)课后复习;(3)多上机实现各种常用优化算法。
二、课程教学基本内容及要求第一章最优化问题与数学预备知识基本内容:(1)最优化的概念;(2)经典最优化中两种类型的问题--无约束极值问题、具有等式约束的极值问题的求解方法;(3)最优化问题的模型及分类;(4)向量函数微分学的有关知识;(5)最优化的基本术语。
基本要求:(1)理解最优化的概念;(2)掌握经典最优化中两种类型的问题--无约束极值问题、具有等式约束的极值问题的求解方法;(3)了解最优化问题的模型及分类;(4)掌握向量函数微分学的有关知识;(5)了解最优化的基本术语。
北京航空航天大学研究生课程试卷2018-2019学年第1学期“最优化方法”期中考试2018年11月14日姓名:学号:说明:•闭卷考试.•共有8个大题,满分110分,超过100分按100分计分;考试时间120分钟.•您的解答务必详细、清晰.•Good Luck!题目12345678总分分数1.(30分,每小题2分)判断下列每个命题的正误,并说明理由.理由可以是1-3行的解释或者反例;理由不正确的答案不得分.(a)多面集上极大化∑ni=1|x i|能表述为线性规划问题. (b)线性规划标准形问题一定有最优解,且可以在某个基本可行解处取到最优值.(c)如果某个基本可行解的所有既约费用系数非负,则它是最优解.(d)考虑问题minimize c T xsubject to Ax≤b.若增加b的某个分量,则最优费用不会增加.(e)如果原始问题无界,则对偶问题一定不可行.(f)如果x和λ分别是线性规划标准形和它的对偶问题的最优解,由互补定理知原始变量和对偶变量的乘积总是零,即x iλi=0对所有i成立.(g)两阶段法中,第I阶段的辅助问题的对偶问题不可能无界.(h)在最小费用网络流问题中,弧上的费用是整数,则可行树解的每个分量是整数.(i)求解整数线性规划的分枝定界法中,宽度优先搜索(广探法)要优于深度优先搜索(深探法).(j)二次函数q(x)=12x T Gx−b T x是凸函数,其中G是n×n阶对称矩阵,b是n维列向量.(k)x ln x是凸函数.(l)可微凸函数的稳定点一定是函数的全局极小点.(m)最速下降法产生的序列是否收敛高度依赖于初始点.(n)二次函数的Hessian阵的条件数越大,牛顿法收敛的越慢.(o)问题maxx∈R2−2x21−x22在点(1,1)T处的牛顿方向是(4,2)T.2.(20分)考虑线性规划标准形问题的单纯形表x1x2x3x4B−1b00−11221β0αr T10γ?3(a)(2分)请给出确失元素?的值.为什么?(b)(3分)当前解是什么?当前的目标值是多少?(c)(5分)给出特定的α,β,γ(如果存在的话)值使得对偶问题是不可行的.(d)(6分)给出一个关于α,β,γ的充分条件使得这张表是最优的,且问题有多个最优解.(e)(4分)假定与这张表格对应的基是最优的.假设原始问题中的c1(变量x1的费用系数)变成c1+ϵ.给出使这个基保持最优的ϵ的范围.续第2题3.(10分)考虑minimize12x1+8x2+16x3+12x4subject to−2x1−x2−4x3+x5=−2−2x1−2x2−4x4+x6=−3x i≥0,i=1, (6)(a)(5分)利用对偶单纯形法求解问题;(b)(5分)写出对偶问题,并用图解法求解对偶问题;4.(15分)图1给出了一个网络,节点旁的数字表示该节点的供给(负值表示需求,未标出数字的默认为0),弧上的数字表示这条弧上的单位费用.对所给网络和数据,完成问题:(a)(5分)写出具体的最小费用流问题(b)(4分)写出(a)中问题的对偶问题.(c)(6分)考虑由弧(b,c ),(c,a ),(d,c )和(e,b )构成的生成树(见图2).设e 为根节点.请给出与这棵生成树对应的树解、与节点e,b 和c 对应的单纯形乘子和与弧(c,e )对应的既约费用系数.-251图1网络及其数据.图2一个生成树.5.(10分)考虑问题min x ∈Rn ∥Ax −b ∥22,其中A 是m ×n 矩阵,b 是m 维向量,且m >n .(a)(5分)写出最优性的必要条件.请说明它是否为充分条件?请给出理由.(b)(3分)最优解唯一吗?理由是什么?(c)(2分)你能给出最优解的一种闭合形式(解析式)吗?在题目所给条件下,允许规定任何你所需要的假设.继第5题6.(10分)考虑将最速下降法应用于二次函数,即minimize x∈R n 12x T Gx−b T x其中G是对称正定矩阵,b是常向量.(a)(5分)考虑变量的线性变换y=T x,其中T是可逆的n×n矩阵.将上述关于x的极小化问题写成关于变量y的极小化问题.确定变换后所得目标函数的Hessian阵.(b)(5分)运行最速下降法时,收敛速度对矩阵G的特征值结构很敏感.假设你知道特征值结构,即已知正交矩阵U和对角矩阵Λ使得G=UΛU T.利用矩阵U和Λ设计矩阵T,对于这个矩阵而言,最速下降法仅需一步即收敛.7.(15分)设f(x)=10(x2−x21)2+(1−x1)2.考虑信赖域法在点x(k)=(0,−1)T的牛顿型信赖域子问题,即求目标函数在当前迭代点的二阶Taylor展式在以当前点为中心的球上的极小点.(a)(7分)完整写出信赖域法的子问题,并画出子问题目标函数的等值线.(b)(3分)取信赖域半径∆=2,求解(a)中的子问题.(b)(2分)针对该子问题,画出信赖域半径从∆=0变到∆=2时,信赖域子问题解族的示意图.(c)(3分)对∆=1,求该信赖域子问题的Cauchy点.。
第一章1)不同的最优估计准则是否会导致相同的估计结果2)参数估计与状态估计的区别是什么3)极大似然估计与极大验后估计的区别、联系是什么;4)怎样理解极大似然估计;5)多维随机变量下,对于MMSE,目标函数估计误差协方差阵最小、估计误差分量平方和最小,是否会导致有相同的估计效果;6) E{E [ x|Z]}的计算过程中对哪一随机变量进行积分?7)似然函数的构造思想是什么?最优估计解的求解方法怎样?8)多维随机向量的正态分布概率密度计算公式怎样?如何理解;9)矩阵微分的计算方法是怎样规定的?常用公式都有哪些?10)什么是马尔科夫估计?11)各种估计准则之间相互关系如何?12)造成最小二乘估计误差的主要因素有哪些?13)线性最小方差估计与最小方差估计的关系如何?第二章14)若噪声为零均值白噪声,连续线性系统离散化后噪声统计特性有何变化?15)离散化噪声统计特性获得的方法是什么?16)连续系统离散化的具体计算方法17)卡尔曼滤波的问题分类有哪些?18)卡尔曼滤波中的各种符号~、A、(k|k-1 )的具体含义是什么?19)卡尔曼滤波的准则是什么?20)正交投影的定义是什么?21)正交投影的物理意义是什么?22)正交定理与正交投影的关系怎样?23)正交定理与线性最小方差估计之间的关系如何?24)最优预测滤波公式推导的原理与过程怎样25)最优预测问题滤波公式26)最优滤波问题公式的推导思路27)最优预测与最优滤波公式的对比,相同点、不同点以及原因28)卡尔曼滤波的重要特征或主要优点是什么29)卡尔曼滤波的通解形式怎样?出于什么样的考虑?关键问题是什么?30)最优滤波问题、最优预测问题中什么协方差阵会出现负项?为什么?31)最优增益阵与噪声统计特性之间的关系怎样?32)理解卡尔曼滤波中协方差阵内各种因素的构成及其原因33)理解卡尔曼滤波中状态估计值、估计误差与噪声的相关性,考虑不同时刻34)卡尔曼滤波是否具有无偏性?如果有,需要什么样的条件?35)系统、观测噪声相关情况下,卡尔曼滤波算法会发生什么样的变化?36)输入对卡尔曼滤波方程的影响怎样?37)成型滤波器的思想是什么?38)出现有色噪声时怎样进行卡尔曼滤波?39)控制系统、观测系统附着不同性质噪声情况下,如何求解?连续系统与离散系统处理方法是否一样?40)卡尔曼滤波中对R k、Q k的理解(统计的对象中的时间)第三章41)平滑问题的分类,各自处理的方法如何?42)为什么可以用极大验后估计推导卡尔曼平滑问题公式?43)平滑处理的意义在哪里?44)实际应用中是否平滑处理利用历史观测越多,获得的估计结果会越精确?45)平滑算法中平滑协方差在卡尔曼滤波计算上有什么作用?意义如何?46)固定区间平滑的解算过程如何?47)固定区间平滑算法中用于修正的因素有哪些?48)固定点平滑与固定滞后平滑公式的获得思想是什么?解算过程怎样?第四章49)滤波稳定性的意义是什么?50)滤波稳定性的判定准则是什么?是否是充要条件?51)滤波稳定性判别条件与线性系统可控、可观判定条件的区别是什么?为什么会不同?52)为什么可控性与可观性会影响到滤波的稳定性?53)滤波误差协方差阵的渐进性是怎样定义的?54)滤波误差协方差阵的有界性55)定常线性系统在滤波稳定性判别上有什么特殊之处?第五章56)滤波发散的原因有哪些?57)衰减记忆滤波的原理是什么,怎样实现的?58)限定记忆滤波的原理是什么,怎样实现?59)限定记忆滤波在开始限定记忆计算时有哪些考虑?60)Kalman滤波的估计误差协防阵P稳定且很小,能否说明滤波系统估计精度一定较高?61)平方根滤波算法的目的是什么,处理思想是怎样的?62)输出相关法的处理思想是什么?63)若Kalman滤波达到最优,具有什么样的性质,为什么?64)新息相关法的处理思想是什么?65)Sage-husa法的中遗忘因子的作用是什么?66)强跟踪滤波器的处理思想是什么?为什么能够达到跟踪的目的?67)序贯处理的思想是什么,每步计算中K的维数是多少?68)非线性系统线性化后采用经典Kalman滤波存在哪些问题?69)什么是标称轨道与标称轨道滤波?标称轨道滤波的滤波对象是什么?70)什么是雅可比阵,如何计算?71)EKF中针对非线性系统中哪些内容进行了线性化?72)EKF的滤波对象是什么?73)针对连续系统的EKF算法中,离散化后的状态转移阵是什么?74)近似条件均值滤波的思想是什么?75)非线性滤波中Kalman增益是否具有离线解算的性质,为什么?76)基于对称采样的UT变换的思想是什么?77) UKF的主要思想是什么?78) UKF是否具有增益阵离线解算的特点?79) UKF的主要优点有哪些?第七章80) 标准Kalman滤波的计算量与维数之间的关系怎样?81) 次优滤波器的设计思想有哪些?82) 什么是a、3滤波器?83) 一信号s(t)=a+bt+ct2能否用a、3滤波器滤波?。
1.可行解 求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题。
满足某线性规划所有的约束条件(指全部前约束条件和后约束条件)的任意一组决策变量的取值,都称为该线性规划的一个可行解,2.可行域所有可行解构成的集合称为该线性规划的可行域(类似函数的定义域)3.凸函数设f(X)为定义在n 维欧氏空间中一个凸集D 上的函数,若对任何实数(0≤ξ≤1)及D 域中任意两点)(1X 与)(2X 存在如下关系:)X (1)X ()X 1X (2121f f f )()()()()(ξξξξ-+≤-+ 则称函数f(X)是定义在凸集D 上的一个凸函数。
4.K-T 条件如果)(k X 是一个局部极小点,则该点的目标函数梯度)()(k X f ∇可表示成该点诸约束面梯度)()(k i X g ∇的如下线性组合:5.模糊子集模糊性是事物的一种不确定性。
是由于某些事物概念不可能给出明确的定义和评定标准,即概念的外延不清楚造成的。
具有模糊边界的子集成为“模糊子集”。
各元素对模糊子集的隶属性质并不明确,即不能确定是绝对属于还是绝对不属于,而需用隶属函数()[]1,0A ∈x μ来描述元素x 对模糊子集 的隶属程度。
6.隶属函数对论域的每一个元素i u ,在闭区间[0,1]中为它选一个数值指标,来表明 i u 对模糊子集 的隶属程度,这个数值指标一般记作 )(i A u μ,并称为元素对模糊子集 的“隶属度” i μ 。
所有隶属度均满足 1u 0i A≤≤)(μ 当论域U 为连续论域时,模糊子集可记为()()1()0m k k i i f X w g X =∇-∇=∑()()()01,,01,,k i i i w g X i m w i m ==≥= ~A~A ~A)(i A u μ数值愈大,表示i u 对 的隶属程度愈高;连续论域的模糊子集 可以完全用其隶属函数)(i Au μ来描述。
7.水平截集设定论域X 上的模糊子集 λA 和任意实数 ∈λ[0,1],则称普通子集为 的λ-水平截集,λ 称为 λA 的水平或阈值。