文档库 最新最全的文档下载
当前位置:文档库 › 数值最优化算法与理论 第二版 (李董辉 董小娇 万中 着) 课后答案

数值最优化算法与理论 第二版 (李董辉 董小娇 万中 着) 课后答案

数值最优化算法与理论 第二版 (李董辉 董小娇 万中 着) 课后答案
数值最优化算法与理论 第二版 (李董辉 董小娇 万中 着) 课后答案

《最优化方法》复习题(含答案)

《最优化方法》复习题(含答案)

附录5 《最优化方法》复习题 1、设n n A R ?∈是对称矩阵,,n b R c R ∈∈,求1()2 T T f x x Ax b x c =++在任意点x 处的梯度和Hesse 矩阵. 解 2(),()f x Ax b f x A ?=+?=. 2、设()()t f x td ?=+,其中:n f R R →二阶可导,,,n n x R d R t R ∈∈∈,试求()t ?''. 解 2()(),()()T T t f x td d t d f x td d ??'''=?+=?+. 3、设方向n d R ∈是函数()f x 在点x 处的下降方向,令 ()()()()() T T T T dd f x f x H I d f x f x f x ??=--???, 其中I 为单位矩阵,证明方向()p H f x =-?也是函数()f x 在点x 处的下降方向. 证明 由于方向d 是函数()f x 在点x 处的下降方向,因此()0T f x d ?<,从而 ()()()T T f x p f x H f x ?=-?? ()()()()()()()() T T T T T dd f x f x f x I f x d f x f x f x ??=-?--???? ()()()0T T f x f x f x d =-??+?<, 所以,方向p 是函数()f x 在点x 处的下降方向. 4、n S R ?是凸集的充分必要条件是12122,,,,,,,,m m m x x x S x x x ?≥?∈L L 的一切凸组合都属于S . 证明 充分性显然.下证必要性.设S 是凸集,对m 用归纳法证明.当2m =时,由凸集的定义知结论成立,下面考虑1m k =+时的情形.令1 1k i i i x x λ+==∑, 其中,0,1,2,,1i i x S i k λ∈≥=+L ,且1 1 1k i i λ+==∑.不妨设11k λ+≠(不然1k x x S +=∈, 结论成立),记11 1k i i i k y x λλ=+=-∑ ,有111(1)k k k x y x λλ+++=-+,

最优化理论与算法(第八章)

第八章 约束优化最优性条件 §8.1 约束优化问题 一、 问题基本形式 min ()f x 1()0 1,,.. ()0 ,,i e i e c x i m s t c x i m m +==?? ≥=?L L (8.1) 特别地,当()f x 为二次函数,而约束是线性约束时,称为二次规划。 记 {} 1()0 (1,,);()0 ,,i e i e X x c x i m c x i m m +===≥=L L ,称之为可行域(约束域)。 {}1,,e E m =L ,{}1,,e I m m +=L ,{}()()0 i I x i c x i I ==∈ 称()E I x U 是在x X ∈处的积极约束的指标集。积极约束也称有效约束,起作用约束或紧约束(active constraints or binding constraints )。 应该指出的是,如果x * 是(1)的局部最优解,且有某个0i I ∈,使得 0()0i c x *> 则将此约束去掉,x * 仍是余下问题的局部最优解。 事实上,若x *不是去掉此约束后所得问题的局部极小点,则意味着0δ?>,存在x δ,使得 x x δδ*-<,且()()f x f x δ*<,这里x δ满足新问题的全部约束。注意到当δ充分小时,由0() i c x 的连续性,必有0()0i c x δ≥,由此知x δ是原问题的可行解,但()()f x f x δ*<,这与x * 是局部极小 点矛盾。 因此如果有某种方式,可以知道在最优解x * 处的积极约束指标集()()A x E I x * *=U ,则问题 可转化为等式的约束问题: min ()f x .. ()0i s t c x = ()i A x *∈ (8.2) 一般地,这个问题较原问题(8.1)要简单,但遗憾的是,我们无法预先知道()A x * 。

最优化方法试题

《最优化方法》试题 一、 填空题 1.设()f x 是凸集n S R ?上的一阶可微函数,则()f x 是S 上的凸函数的一阶充要条件是( ),当n=2时,该充要条件的几何意义是( ); 2.设()f x 是凸集n R 上的二阶可微函数,则()f x 是n R 上的严格凸函数( )(填‘当’或‘当且仅当’)对任意n x R ∈,2()f x ?是 ( )矩阵; 3.已知规划问题22211212121212min 23..255,0z x x x x x x s t x x x x x x ?=+---?--≥-??--≥-≥?,则在点55(,)66T x =处的可行方向集为( ),下降方向集为( )。 二、选择题 1.给定问题222121212min (2)..00f x x s t x x x x ?=-+??-+≤??-≤?? ,则下列各点属于K-T 点的是( ) A) (0,0)T B) (1,1)T C) 1(,22 T D) 11(,)22T 2.下列函数中属于严格凸函数的是( ) A) 211212()2105f x x x x x x =+-+ B) 23122()(0)f x x x x =-< C) 2 222112313()226f x x x x x x x x =+++- D) 123()346f x x x x =+- 三、求下列问题

()22121212121211min 51022 ..2330420 ,0 f x x x x x s t x x x x x x =+---≤+≤≥ 取初始点()0,5T 。 四、考虑约束优化问题 ()221212min 4..3413f x x x s t x x =++≥ 用两种惩罚函数法求解。 五.用牛顿法求解二次函数 222123123123()()()()f x x x x x x x x x x =-++-++++- 的极小值。初始点011,1,22T x ??= ???。 六、证明题 1.对无约束凸规划问题1min ()2 T T f x x Qx c x =+,设从点n x R ∈出发,沿方向n d R ∈ 作最优一维搜索,得到步长t 和新的点y x td =+ ,试证当1T d Q d = 时, 22[() ()]t f x f y =-。 2.设12*** *3(,,)0T x x x x =>是非线性规划问题()112344423min 23..10f x x x x s t x x x =++++=的最优解,试证*x 也 是非线性规划问题 144423* 123min ..23x x x s t x x x f ++++=的最优解,其中****12323f x x x =++。

天津大学《最优化方法》复习题(含答案)

天津大学《最优化方法》复习题(含答案) 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg min max x f x f n n R x R x -=∈∈ √ 2 {}{} .:)(m in :)(m ax n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*,对于一切n R x ∈恒有)()(x f x f ≤*,则称*x 为最优化问题)(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*,存在*x 的某邻域)(*x N ε,使得对一切)(*∈x N x ε恒有)()(x f x f <*,则称*x 为最优化问题)(min x f D x ∈的 严格局部最优解. ? 5 给定一个最优化问题,那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍

属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数,D x ∈*. 则对D x ∈?,有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数,则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列,假设算法 A 为下降算法,则对{} ,2,1,0∈?k ,恒有 )()(1k k x f x f ≤+ . 13 算法迭代时的终止准则(写出三种):_____________________________________。 14 凸规划的全体极小点组成的集合是凸集。 √ 15 函数R R D f n →?:在点k x 沿着迭代方向}0{\n k R d ∈进行精确一维线搜索的步长k α,则其搜索公式

(完整版)机械优化设计试卷期末考试及答案

第一、填空题 1.组成优化设计的数学模型的三要素是 设计变量 、目标函数 和 约束条件 。 2.可靠性定量要求的制定,即对定量描述产品可靠性的 参数的选择 及其 指标的确定 。 3.多数产品的故障率随时间的变化规律,都要经过浴盆曲线的 早期故障阶段 、 偶然故障阶段 和 耗损故障阶段 。 4.各种产品的可靠度函数曲线随时间的增加都呈 下降趋势 。 5.建立优化设计数学模型的基本原则是在准确反映 工程实际问题 的基础上力求简洁 。 6.系统的可靠性模型主要包括 串联模型 、 并联模型 、 混联模型 、 储备模型 、 复杂系统模型 等可靠性模型。 7. 函数f(x 1,x 2)=2x 12 +3x 22-4x 1x 2+7在X 0=[2 3]T 点处的梯度为 ,Hession 矩阵为 。 (2.)函数()22121212,45f x x x x x x =+-+在024X ??=????点处的梯度为120-?? ????,海赛矩阵为2442-???? -?? 8.传统机械设计是 确定设计 ;机械可靠性设计则为 概率设计 。 9.串联系统的可靠度将因其组成单元数的增加而 降低 ,且其值要比可靠 度 最低 的那个单元的可靠度还低。 10.与电子产品相比,机械产品的失效主要是 耗损型失效 。 11. 机械可靠性设计 揭示了概率设计的本质。 12. 二元函数在某点处取得极值的充分条件是()00f X ?=必要条件是该点处的海赛矩阵正定。 13.对数正态分布常用于零件的 寿命疲劳强度 等情况。 14.加工尺寸、各种误差、材料的强度、磨损寿命都近似服从 正态分布 。 15.数学规划法的迭代公式是 1k k k k X X d α+=+ ,其核心是 建立搜索方向, 模型求解 两方面的内容。 17.无约束优化问题的关键是 确定搜索方向 。 18.多目标优化问题只有当求得的解是 非劣解 时才有意义,而绝对最优解存在的可能性很小。 19.可靠性设计中的设计变量应具有统计特征,因而认为设计手册中给出的数据

最优化理论与算法 fibonacci法

function [a,b,n,x]=fibonacci(fname,a,b,d,L) % fname函数句柄,d辨别常数,L最终区间长度a(1)=a; b(1)=b; F=zeros(1,10); %选择fibonacci数列k值为10,可任意更改 F(1)=1; F(2)=2; for k=2:10 %k取到10,生成fibonacci数列 F(k+1)=F(k)+F(k-1); F(k); end Fn=(b(1)-a(1))/L; Fk=[F Fn]; N=sort(Fk); n=find(Fn==N); %查找计算函数值的次数n t(1)=a(1)+F(n-2)*(b(1)-a(1))/F(n); %计算试探点t(1),u(1) u(1)=a(1)+F(n-1)*(b(1)-a(1))/F(n); for k=1:n-2 ft=feval(fname,t(k)); fu=feval(fname,u(k)); if ft>fu a(k+1)=t(k); b(k+1)=b(k); t(k+1)=u(k); u(k+1)=a(k+1)+F(n-k-1)*(b(k+1)-a(k+1))/F(n-k); while k==n-2 t(n)=t(n-1); u(n)=t(n-1)+d; ft=feval(fname,t(n)); fu=feval(fname,u(n)); if ft>fu a(n)=t(n); b(n)=b(n-1); else a(n)=a(n-1); b(n)=t(n); end end else a(k+1)=a(k); b(k+1)=u(k); u(k+1)=t(k); if k~=n-2 t(k+1)=a(k+1)+F(n-k-2)*(b(k+1)-a(k+1))/F(n-k); ft=feval(fname,t(k));

修订过的最优化方法复习题

《最优化方法》复习题 第一章 引论 一、 判断与填空题 1 )].([arg )(arg m in m ax x f x f n n R x R x -=∈∈ √ 2 {}{}.:)(min :)(max n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*,对于一切n R x ∈恒有)()(x f x f ≤*,则称*x 为最优化问题 )(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*,存在*x 的某邻域)(*x N ε,使得对一切)(*∈x N x ε恒有)()(x f x f <*,则称*x 为最优化问题)(min x f D x ∈的严格局部最 优解. ? 5 给定一个最优化问题,那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数,D x ∈*. 则对D x ∈?,有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数,则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列,假设算法A 为单调下降算 法,则对{} ,2,1,0∈?k ,恒有 )()(1k k x f x f ≤+ .

《最优化方法》期末试题

作用: ①仿真的过程也是实验的过程,而且还是系统地收集和积累信息的过程。尤其是对一些复杂的随机问题,应用仿真技术是提供所需信息的唯一令人满意的方法。 ②仿真技术有可能对一些难以建立物理模型或数学模型的对象系统,通过仿真模型来顺利地解决预测、分析和评价等系统问题。 ③通过系统仿真,可以把一个复杂的系统化降阶成若干子系统以便于分析,并能指出各子系统之间的各种逻辑关系。 ④通过系统仿真,还能启发新的策略或新思想的产生,或能暴露出在系统中隐藏着的实质性问题。同时,当有新的要素增加到系统中时,仿真可以预先指出系统状态中可能会出现的瓶颈现象或其它的问题。 2.简述两个Wardrop 均衡原理及其适用范围。 答: Wardrop提出的第一原理定义是:在道路的利用者都确切知道网络的交通状态并试图选择最短径路时,网络将会达到平衡状态。在考虑拥挤对行驶时间影响的网络中,当网络达到平衡状态时,每个 OD 对的各条被使用的径路具有相等而且最小的行驶时间;没有被使用的径路的行驶时间大于或等于最小行 驶时间。 Wardrop提出的第二原理是:系统平衡条件下,拥挤的路网上交通流应该按照平均或总的出行成本 最小为依据来分配。 第一原理对应的行为原则是网络出行者各自寻求最小的个人出行成本,而第二原理对应的行为原则是网络的总出行成本最小。 3.系统协调的特点。 答: (1)各子系统之间既涉及合作行为,又涉及到竞争行为。 (2)各子系统之间相互作用构成一个反馈控制系统,通过信息作为“中介”而构成整体 (3)整体系统往往具有多个决策人,构成竞争决策模式。 (4)系统可能存在第三方介入进行协调的可能。 6.对已经建立了概念模型的系统处理方式及其特点、适用范围。答:对系统概念模型有三种解决方式。 1.建立解析模型方式 对简单系统问题,如物流系统库存、城市公交离线调度方案的确定、交通量不大的城市交叉口交通控制等问题,可以运用专业知识建立系统的量化模型(如解析数学模型),然后采用优化方法确定系统解决方案,以满足决策者决策的需要,有关该方面的内容见第四、五章。 在三种方式中,解析模型是最科学的,但仅限于简单交通运输系统问题,或仅是在实际工程中一定的情况下(仅以一定的概率)符合。所以在教科书上很多漂亮的解析模型,无法应用于工程实际中。 2.建立模拟仿真模型方式 对一般复杂系统,如城市轨道交通调度系统、机场调度系统、城市整个交通控制系统等问题,可以对系统概念模型中各个部件等采用变量予以量化表示,并通过系统辨识的方式建立这些变量之间关系的动力学方程组,采用一定的编程语言、仿真技术使其转化为系统仿真模型,通过模拟仿真寻找较满意的优化方案,包括离线和在线均可以,有关该方面的内容见第七章。 模拟仿真模型比解析模型更能反映系统的实际,所以在交通运输系统中被更高层次的所使用,包括

预测与决策试卷及答案解析

经济预测与决策 考试形式:闭卷考试时量:150分钟总分:100分 一.单选题1*15=15分 1.经济预测的第一步是()A A.确定预测目的,制定计划 B.搜集审核资料 C.建立预测模型 D.评价预测成果 2.对一年以上五年以下的经济发展前景的预测称为()B A.长期经济预测 B.中期经济预测 C.短期经济预测 D.近期经济预测 3.()回归模型中,因变量与自变量的关系是呈直线型的。C A.多元 B.非线性 C.线性 D.虚拟变量

4.以下哪种检验方法的零假设为:B1=B2=…=Bm=0?B A.r检验 B.F检验 C.t检验 D.DW检验 5.以数年为周期,涨落相间的波浪式起伏变动称为()D A.长期趋势 B.季节变动 C.不规则变动 D.循环变动 6. 一组数据中出现次数最多的变量值,称为()A A.众数 B.中位数 C.算术平均数 D.调和平均数 7. 通过一组专家共同开会讨论,进行信息交流和相互启发,从而诱发专家们发挥其创造性思维,促进他们产生“思维共振”,达到相互补充并产生“组合效应”的预测方法为()A A.头脑风暴法 B.德尔菲法

C.PERT预测法 D.趋势判断预测法 8.()起源于英国生物学家高尔登对人类身高的研究。B A.定性预测法 B.回归分析法 C.马尔科夫预测法 D.判别分析预测法 9.抽样调查的特点不包括()D A.经济性 B.时效性 C.适应性 D.全面性 10.下图是哪种多项式增长曲线()B A.常数多项式 B.一次多项式 C.二次多项式

D.三次多项式 11.根据历年各月的历史资料,逐期计算环比加以平均,求出季节指数进行预测的方法称为()C A.平均数趋势整理法 B.趋势比率法 C.环比法 D.温特斯法 12.经济决策按照目标的性质和行动时间的不同,分为()D A.宏观经济决策和微观经济决策 B.高层、中层和基层决策 C.定性决策和定量决策 D.战术决策和战略决策 13.()是从最好情况出发,带有一定冒险性质,反映了决策者冒进乐观的态度。B A.最大最小决策准则 B.最大最大决策准则 C.最小最小后悔值决策准则 D.等概率决策准则 14.如果某企业规模小,技术装备不良,担负不起较大的经济风险,则该企业应采用()A

最优化理论与算法(第三章)

第三章 牛顿法 §3.1 最速下降法 一、最速下降法 在极小化算法中,若每次都以迭代点处的负梯度方向为搜索方向,产生的算法称为最速下降法,它是无约束最优化算法中最简单、最基本的算法。 算法描述: 1) 给出初始点0n x R ∈,允许误差0ε>,0k =; 2) 计算k k d g =-,若k g ε≤,Stop 令 * k x x ≈; 3) 由一维搜索确定步长因子k α,使得 ()min ()k k k k k f x d f x d ααα≥+=+ 4) 令1k k k k x x d α+=+,1k k =+,go to 2). 的每个聚点均为驻点。 令{}1 k K d 有界,且 2 ()(())()0T f x f x f x ?-?=-?= 故有 ()0f x ?=。 定理 3.2 设()f x 二次连续可微,且2()f x M ?≤,则对任何给定的初始点0n x R ∈,最速下降算法或有限终止,或lim ()k k f x →∞ =-∞,或lim ()0k k f x →∞ ?=。

证明:不妨设k ?,()0k f x ?≠。由定理2.5有 2 11()()()2k k k f x f x f x M +-≥ ? 于是 []1 2 010 1 ()()()()()2k k k i i i i i f x f x f x f x f x M -+==-=-≥ ?∑∑ 令k →∞,由{()}k f x 为单调下降序列,则要么 lim ()k k f x →∞ =-∞,要么 lim k →∞ ?定理3.3 设1 f C ∈证明:直接由定理2.14可得。 注:1) 2 1λ,n λ分别为G 的 ≤ ()k k I G x α- 其中k α使 (())(())k k k f I G x f I G x αα-≤-, 0α?≥ 若设 ()1k P t t α=-,()Q t ut λ=- 其中,u R λ∈。则有 ()Q G I uG λ=-,而(0)Q λ=,

最优化试题及答案

最优化理论、方法及应用试题 一、 (30分) 1、针对二次函数1()2 T T f x x Q x b x c =++,其中 Q 是正定矩阵,试写出最速下降 算法的详细步骤,并简要说明其优缺点? 答:求解目标函数的梯度为()g x Qx b =+,()k k k g g x Q x b ==+,搜索方向:从k x 出发,沿k g -作直线搜索以确定1k x +。 Step1: 选定0x ,计算00,f g Step2: 做一维搜索, ()1min k k k t f f x t g +=-,1k k k x x tg +=-. Step3:判别,若满足精度要求,则停止;否则,置k=k+1,转步2。 优缺点:最速下降法在初始点收敛快,算法简单,在最优点附近有锯齿现象,收敛速度慢。 2、有约束优化问题 m in ()()0,1,2,,.. ()0,1,2,,i j f x g x i m s t h x j l ≥=???==?? 最优解的必要条件是什么? 答:假设*x 是极小值点。必要条件是f ,g ,h 函数连续可微,而且极小值点的所有起作用约束的梯度(*)(1,2,,)i h x i l ?= 和(*)(1,2,,)j g x j m ?= 线性无关,则 存在****** 12 12,,,,,,,,l m αααβββ 使得 ()1 1* * * * * * 1 212* * (*)*(*)*(*)0 *(*)0,1,2,,,,,,,,,0 0,0 l m i i j j i i j j l m i j f x h x g x g x j m α β βα ααβββαβ==?- ?- ?===≠>≥∑∑ 3、什么是起作用约束?什么是可行方向?什么是下降方向?什么是可行下降方向?针对上述有约束优化问题,如果应用可行方向法,其可行的下降方向怎样确定? 答:起作用约束:若0()0j g x =,这时点0x 处于该约束条件形成的可行域边界上,它对0x 的摄动起到某种限制作用。 可行方向:0x 是可行点,某方向p ,若存在实数00λ>,使得它对任意

最优化理论与算法

最优化理论与算法笔记 在老师的指导下,我学习了最优化理论与算法这门课程。最优化理论与算法是一个重要的数学分支,它所研究的问题是讨论在众多方案中什么样的方案最优以及怎样找出最优方案。 由于生产和科学研究突飞猛进的发展,特别是计算机的广泛应用,使最优化问题的研究不仅成为了一种迫切的需要,而且有了求解的有力工具,因此迅速发展起来形成一个新的学科。至今已出现了线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。 整个学习安排如下,首先介绍线性与非线性规划问题,凸集和凸函数等基本知识及线性规划的基本性质;然后再这个基础上学习各种算法,包括单纯形法、两阶段法、大M 法、最速下降法、牛顿法、共轭梯度法等,以及各种算法相关的定理和结论;最后了解各种算法的实际应用。 主要学习的基础知识: 1、一般线性规划问题的标准形式 1min n j j j c x =∑ 1 .., 1,...,, 0, 1,...,. n ij j i j j s t a x b i m x j n ===≥=∑ 学会引入松弛变量将一般问题化为标准问题;同时掌握基本可行解的存在问题,通过学习容易发现线性规划问题的求解,可归结为求最优基本可行解的问题。 2、熟练掌握单纯形法、两阶段法和大M 法的概念及其计算步骤。 单纯形法是一种是用方便、行之有效的重要算法,它已成为线性规划的中心内容。其计算步骤如下: 1)解,B Bx b =求得1B x B b b -==,令0,N x =计算目标函数值B B f c x =;

2)求单纯形乘子ω,解B B c ω= ,得到1B c B ω-=; 3)解k k By p =,若0k y ≤,即k y 的每个分量均非正数,则停止计算,问 题不存在有限最优解,否则,进行步骤(4); 4)确定下标r ,使min{0}r r rk rk rk b b y y y =>,得到新的基矩阵B ,返回第一 步。 两阶段法:第一阶段是用单纯形法消去人工变量,即把人工变量都变换成非基变量,求出原来问题的一个基本可行解;第二阶段是从得到的基本可行解出发,用单纯形法求线性规划的最优解。 大M 法:在约束中增加人工变量a x ,同时修改目标函数,加上罚项T a Me x ,其中M 是很大的正数,这样,在极小化目标函数的过程中,由于M 的存在,将迫使人工变量离基。 3、掌握最速下降法的概念及其算法,并且能够讨论最速下降算法的收敛性。掌握牛顿法,能够熟练运用牛顿迭代公式:(1) ()2()()()()k k k k x x f x x x +=-?- ,掌 握共轭梯度法及其相关结论,以及其收敛性的讨论,掌握最小二乘法及其基本步骤。 最速下降法:迭代公式为(1) ()()k k k k x x d λ+=-。 计算步骤:1)给定点(1)n x R ∈,允许误差0,ε>臵1k =; 2)计算搜索方向() ()()k k d f x =-?; 3)若() k d ε≤,则停止计算,否则,从()k x 出发,沿()k d 进行一维搜索,求k λ,使()()()() ()min ()k k k k k f x d f x d λλλ≥+=+; 4)令(1) ()()k k k k x x d λ+=-,臵:1k k =+,转步骤(2)。

最优化方法(试题+答案)

一、 填空题 1 . 若 ()()??? ? ??+???? ?????? ??=212121 312112)(x x x x x x x f ,则 =?)(x f ,=?)(2x f . 2.设f 连续可微且0)(≠?x f ,若向量d 满足 ,则它是f 在x 处的一个下降方向。 3.向量T ) 3,2,1(关于3阶单位方阵的所有线性无关的共轭向量 有 . 4. 设R R f n →:二次可微,则f 在x 处的牛顿方向为 . 5.举出一个具有二次终止性的无约束二次规划算 法: . 6.以下约束优化问题: )(01)(..)(min 212121 ≥-==+-==x x x g x x x h t s x x f 的K-K-T 条件为: . 7.以下约束优化问题: 1 ..)(min 212 2 21=++=x x t s x x x f 的外点罚函数为(取罚参数为μ) . 二、证明题(7分+8分) 1.设1,2,1,:m i R R g n i =→和m m i R R h n i ,1,:1+=→都是线性函数,证明下 面的约束问题: } ,,1{, 0)(},1{, 0)(..)(min 1112 m m E j x h m I i x g t s x x f j i n k k +=∈==∈≥=∑= 是凸规划问题。

2.设R R f →2 :连续可微,n i R a ∈,R h i ∈,m i ,2,1=,考察如下的约束条件问题: } ,1{,0} 2,1{,0..) (min 11m m E i b x a m I i b x a t s x f i T i i T i +=∈=-=∈≥- 设d 是问题 1 ||||,0,0..)(min ≤∈=∈≥?d E i d a I i d a t s d x f T i T i T 的解,求证:d 是f 在x 处的一个可行方向。 三、计算题(每小题12分) 1.取初始点T x )1,1() 0(=.采用精确线性搜索的最速下降法求解下面的无约束优化问题 (迭代2步): 2 2212)(m in x x x f += 2.采用精确搜索的BFGS 算法求解下面的无约束问题: 212 2212 1)(min x x x x x f -+= 3.用有效集法求解下面的二次规划问题: . 0,001..42)(min 21212 12 221≥≥≥+----+=x x x x t s x x x x x f 4.用可行方向算法(Zoutend ij k算法或Frank Wol fe算法)求解下面的问题(初值设为)0,0() 0(=x ,计算到)2(x 即可): . 0,033..22 1)(min 212112 22121≥≥≤+-+-= x x x x t s x x x x x x f

最优化理论与算法

最优化理论与算法(数学专业研究生) 第一章 引论 § 引言 一、历史与现状 最优化理论最早可追溯到古老的极值问题,但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John 最优性条件(1948),Kuhn-Tucker 最优性条件(1951),和Karush 最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速,应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法,狭义的主要指非线性规划的相关内容,而广义的则涵盖:线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。 二、最优化问题的一般形式 1、无约束最优化问题 min ()n x R f x ∈ () 2、约束最优化问题 min () ()0, ..()0, i i f x c x i E s t c x i I =∈?? ≥∈? () 这里E 和I 均为指标集。 §数学基础 一、 范数 1. 向量范数 max i x x ∞= (l ∞范数) () 11n i i x x ==∑ (1l 范数) () 122 21 ()n i i x x ==∑ (2l 范数) ()

11 ()n p p i p i x x ==∑ (p l 范数) () 12 ()T A x x Ax = (A 正定) (椭球范数) () 事实上1-范数、2-范数与∞-范数分别是 p -范数当 p =1、2和p →∞时情形。 2.矩阵范数 定义 方阵A 的范数是指与A 相关联并记做A 的一个非负数,它具有下列性质: ① 对于0A ≠都有0A >,而0A =时0A =; ② 对于任意k R ∈,都有kA k A =; ③ A B A B +≤+; ④ AB A B ≤; 若还进一步满足: ⑤ p p Ax A x ≤ 则称之为与向量范数p g 相协调(相容)的方阵范数。若令 max x Ax A x ≠= (这里x 是某一向量范数) () 可证这样定义的范数是与向量范数g 相协调的,通常称之为由向量范数g 诱导的方阵范数。特别地,对方阵()ij n n A a ?=,有: 11max n ij j i A a ==∑(列和的最大者) () 1 max n ij i j A a ∞ ==∑(行和的最大者) () 1 22()T A A A λ=(T A A λ表示T A A 的特征值的最大者) 称为谱范数(注:方阵A 的特征值的模的最大者称为A 的谱半径,记为()A ρ)。 对于由向量诱导的方阵范数,总有:

最优化方法试卷与答案5套

《最优化方法》1 一、填空题: 1.最优化问题的数学模型一般为:____________________________,其中 ___________称为目标函数,___________称为约束函数,可行域D 可以表示 为_____________________________,若______________________________, 称*x 为问题的局部最优解,若_____________________________________,称*x 为问题的全局最优解。 2.设f(x)= 212121522x x x x x +-+,则其梯度为___________,海色矩阵___________,令,)0,1(,)2,1(T T d x ==则f(x)在x 处沿方向d 的一阶方向导数为___________,几何意义为___________________________________,二阶 方向导数为___________________,几何意义为_________________________ ___________________________________。 3.设严格凸二次规划形式为: 012. .222)(min 21212 12 221≥≥≤+--+=x x x x t s x x x x x f 则其对偶规划为___________________________________________。

4.求解无约束最优化问题:n R x x f ∈),(min ,设k x 是不满足最优性条件的第k 步迭代点,则: 用最速下降法求解时,搜索方向k d =___________ 用Newton 法求解时,搜索方向k d =___________ 用共轭梯度法求解时,搜索方向k d =_______________ ____________________________________________________________。 二.(10分)简答题:试设计求解无约束优化问题的一般下降算法。 三.(25分)计算题 1. (10分)用一阶必要和充分条件求解如下无约束优化问题的最优解: )1(632)(m in 21212131----=x x x x x x x f . 2. (15分)用约束问题局部解的一阶必要条件和二阶充分条件求约束问题: 1)(. .)(min 22 2 1 2 1=-+==x x x c t s x x x f 的最优解和相应的乘子。 四. 证明题(共33分) 1.(10分)设δ++=x r Gx x x f T T 2 1 )(是正定二次函数,证明一维问题

最优化理论与算法(第九章)

第九章 二次规划 §9.1 二次规划问题 称形如 1m in ()2 T T Q x x H x g x = + 1,,. 1,,T i i e T i i e a x b i m s t a x b i m m ?==??≥=+?? (9.1) 的非线性规划问题为二次规划问题。对二次规划问题,有如下的最优性条件。 定理9.1 设x *是(9.1)的局部极小点,则必存在乘子(1,,)i i m λ*= ,使得 1 0 1,, 0 1,,m i i i T i i i e i e g H x a a x b i m m i m m λλλ**=*** ?+=? ?? ??-==+????≥=+??? ∑ (9.2) 且对于一切满足于: 0, ()T i d a i E I x * =∈ 的n d R ∈,都有0T d Hd ≥。 注:1)上述定理的前后两部分分别对应于一、二阶的必要条件; 2)满足上述条件的d ,都有(,)d S x λ* * ∈; 3)当约束条件均为线性函数时,容易证明: (,)(,) (,F D x X S F D x X L F D x X * * *= =及(,)(,)S x G x λλ**** = 上面给出的是二次规划的必要性条件,下面给出充分性条件。 定理9.2 设x * 是K-T 点,λ* 是相应的Lagrange 乘子,如果对满足 0 0 () 0 () 0 T i T i T i i d a i E d a i I x d a i I x λ* **?=∈?≥∈??=∈>? 且 (9.3) 的一切非零向量n d R ∈,都有0T d Hd >,则x * 是(9.1)的局部严格极小点。

工程硕士研究生《最优化方法》试卷

华东理工大学工程硕士研究生《最优化方法》试卷 专业 班级 学号 姓名 成绩 2010年5月8日 一、简答题(20分,每小题5分) 1· 函数3()2710f x x x =-+在(,)-? 上有最优解吗?如果有,请说明是局部最优解还是全局最优解。 2·请给出最优化方法中下降迭代算法的一般步骤。 3·何谓下降方向?请给出一种判别方法?负梯度方向是下降最快的方向吗?为什么? 4·何谓可行方向?在最优点处有可行下降方向吗?为什么? 二·(15分)你学过哪些一维优化算法(一维搜索法)?请你说明它们之间的关系和特点。如果用黄金分割法求解该问题在区间[-1,1]上的最优解,要求近似精度达到0.01,那么需要迭代多少步就能找到所需要的解。 三·(10分)请用FR 共轭梯度法求解如下优化问题,只需迭代一次,并给出第二次迭代的搜索 方向,初始点 0(1,1)T x = 22212min ()23x R f x x x ?=++ 四·(20分)1、请简述共轭方向法的一般步骤,并给出你所学过的共轭方向法。 2、简述拟牛顿算法的基本步骤,说明拟牛顿算法的特点。 3、请给出你所知道的直接算法,并说明每个算法的主要思想和特点,它们之间有关系吗? 五·(10分)试用惩罚函数法求解如下的优化问题 2..3min ()365s t x f x x x 3=-+ 六·(15分)请考虑下述线性规划问题 12 121212max ()3423..23 ,0f x x x x x s t x x x x =+ì+ ??í?+ ??3 1·请给出上述问题的基本可行解与相应顶点的对应关系。上述线性规划问题有不可行的基本解吗?如果有,请给出几何解释; 2·试求上述线性规划问题的最优解。

最优化理论与算法(第十章)

第十章 罚函数法 罚函数是利用目标函数与约束函数一起构成的具有惩罚性质的函数。当约束条件被破坏时,施以惩罚,可以想象,当这种惩罚很大时,将迫使迭代点趋于可行点。 §10.1 外罚函数法 对一般非线性规划问题: 1min ()()01,,. ()0 ,,i e i e f x c x i m s t c x i m m +==?? ≥=? (10.1) 定义违反约束度函数: ()()()1,i i e c x c x i m -== (10.2) ()1()min{0,()} ,m i i e c x c x i m -+== 。 (10.3) 罚函数一般表示为: () ()()(())P x f x h c x -=+ (10.4) 其中() (())h c x -是惩罚项,这个函数一般具有 (0)0h =,lim ()c h c →+∞ =+∞。 较常用的形式为: () ()()() P x f x c x α σ-=+ (0σ>称为罚因子) (10.5) 注:1) 在上式中,范数常取为2 ,若取为∞ 或1 会导致()P x 不光滑。 2) 当取2 和1α>时,()P x 的光滑性可由 ()22(())(min{0,()})i c x c x -= 直接验证。事实上,在“转折点”处,可证得左、右导数均为0,由此可得() 2(())c x -光滑性,从而 ()P x 光滑。 Courant 函数是最早使用的罚函数,也是最方便最重要的一种罚函数。其形式为 2 () 2 (,)()()p x f x c x σσ-=+ 1 2 21` ()()(min{0,()})e e m m i i i m f x c x c x σσ+==++∑∑ (10.6)

最优化方法(试题+答案)

一、 填空题 1.若()()??? ? ??+???? ?????? ??=212121 312112)(x x x x x x x f , 则=?)(x f ,=?)(2x f . 2.设f 连续可微且0)(≠?x f ,若向量d 满足 ,则它是f 在x 处的一个下降方向。 3.向量T )3,2,1(关于3阶单位方阵的所有线性无关的共轭向量有 . 4. 设R R f n →:二次可微,则f 在x 处的牛顿方向为 . 5.举出一个具有二次终止性的无约束二次规划算法: . 6.以下约束优化问题: )(01)(..)(min 212121 ≥-==+-==x x x g x x x h t s x x f 的K-K-T 条件为: . 7.以下约束优化问题: 1 ..)(min 212 2 21=++=x x t s x x x f 的外点罚函数为(取罚参数为μ) . 二、证明题(7分+8分) 1.设1,2,1,:m i R R g n i =→和m m i R R h n i ,1,:1+=→都是线性函数,证明下 面的约束问题: } ,,1{, 0)(},1{, 0)(..)(min 1112 m m E j x h m I i x g t s x x f j i n k k +=∈==∈≥=∑= 是凸规划问题。

2.设R R f →2 :连续可微,n i R a ∈,R h i ∈,m i ,2,1=,考察如下的约束条件问题: } ,1{,0} 2,1{,0..) (min 11m m E i b x a m I i b x a t s x f i T i i T i +=∈=-=∈≥- 设d 是问题 1 ||||,0,0..)(min ≤∈=∈≥?d E i d a I i d a t s d x f T i T i T 的解,求证:d 是f 在x 处的一个可行方向。 三、计算题(每小题12分) 1.取初始点T x )1,1() 0(=.采用精确线性搜索的最速下降法求解下面的无约束优化问题 (迭代2步): 2 2212)(m in x x x f += 2.采用精确搜索的BFGS 算法求解下面的无约束问题: 212 2212 1)(min x x x x x f -+= 3.用有效集法求解下面的二次规划问题: . 0,001..42)(min 21212 12 221≥≥≥+----+=x x x x t s x x x x x f 4.用可行方向算法(Zoutendijk 算法或Frank Wolfe 算法)求解下面的问题(初值设为)0,0() 0(=x ,计算到)2(x 即可): . 0,033..22 1)(min 21211222121≥≥≤+-+-= x x x x t s x x x x x x f

相关文档