《最优化方法》复习题
笫一章概述(包括凸规划)
一、判断与填空题
1arg max /(x) = arg m in7
xeR n xeR n
2max {/(x): x G D e /?" }= 一min {/(x): x e Z) o /?H} x
3设f : D u RJ R.若疋wR”,对于一切xwR”恒有/(x*)
最优化问题min /(兀)的全局最优解.x
XG D
4设f : D匚R" — R.若x* ,存在F的某邻域/.(/),使得对一切
兀e 恒有/(%*)< f(x),则称T为最优化问题min fM的严格局部最
XE D
优解.X
5给定一个最优化问题，那么它的最优值是一个定值.V
6非空集合D c /?"为凸集当且仅当D中任意两点连线段上任一点属于D. V
7非空集合D匸/?"为凸集当且仅当D中任意有限个点的凸组合仍属丁D. V 8任意两个凸集的并集为凸集.x
9 函数f : D j R" T/?为凸集D上的凸函数当且仅当一/为D上的凹函数.V
10设f : D u RJ R为凸集D上的可微凸函数，eD .则对Vx G D ,有fM -/(%*)< V/(x*)' (x -x*). x
11若c(兀)是凹函数，则D = [x^R n\ c(x) > 0}是凸集。V
12设{*}为由求解min/(Q的算法A产牛的迭代序列，假设算法A为下降算法，
xeD
则对Pk e {0,1, 2,…}，恒有____ /(x,+1) < /(X,) _____________ .
13算法迭代吋的终止准则（写出三种）： _____________________________ o 14凸规划的全休极小点组成的集合是凸集。V
15函数f:D^R n TR在点戏沿着迭代方向d* eR n \{0}进行耕确一维线搜索的步长则其搜索公式为 ______________________________________________ .
16函数f:D^R n T/?在点/沿着迭代方向d* eR n \{0}进行精确一维线搜索的步长匕，则Vf（x k +a k cl k）T d k = ______ 0 _____________ .
17设d k eR n\{0}为点x k eD^R n处关于区域D的一个下降方向，则对于V 厉〉0, 3cre（0, a）使得+ad k e D. x
二、简述题
1写出Wolfe-Powell非精确一维线性搜索的公式。
2怎样判断一个函数是否为凸函数.
（例如：判断函数/⑴=彳+2“2+2兀；- 10吗+5勺是否为凸函数）
三、证明题
1证明一个优化问题是否为凸规划.（例如
min f（x） = —x T Gx + c T x-^rb
2
判断M Ax = b（其中G是正定矩阵）是凸规划.
x>0
2熟练掌握凸规划的性质及其证明.
第二章线性规划
考虑线性规划问题：
(LP)min c l x
s.t. Ax = b, x > 0,
其中，c e R”, Ae/?M,XM, beR m为给定的数据，且rankA = /n, m 一、判断与选择题 1 (LP)的基解个数是有限的.V 2若(LP)有最优解，则它一定有基可行解为最优解.V 3(LP)的解集是凸的.7 4对于标准型的(LP),设{*}由单纯形算法产生，则对e{0,1, 2,-..},有 c T x k >c T x k+\ X 5若T为(LP)的最优解，)「为(DP)的可行解，则c T x>b T y\ V 6设兀。是线性规划(LP)对应的基B = (P\,…，PJ的基可行解，与基变量对应的规范式中，若存在O-, <0,贝IJ线性规划(LP)没有最优解。X 7求解线性规划(LP)的初始基可行解的方法：_______________________ . 8对于线性规划(LP),每次迭代都会使忖标函数值下降.X 二、简述题 1将以下线性规划问题化为标准型：max /(x)=州一2X2 + 3x3 s.t. + x2 + x3 < 6, x x +2兀2 +4兀3 > 12, X)- x2 + x3 > 2, x2 > 0, x3 > 0. 2写出以下线性规划的对偶线性规划: max f (x) = 3旺 + 2x2 + 心 + 4x4 s.t. 2兀］+ 4X2 + 3 兀3 + 巾=6， 一2x I + 4X2 + 3兀3 + 兀-3, x2. x3, x4 > 0. 三、计算题 熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）. 见书本： 例 2.5.1 例261 例2.6.2（利用单纯形表求解）；（利用大M法求解）；（利用二阶段法求解）. 四、证明题 熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。 第三章无约束最优化方法 一、判断与选择题 1设G w RM为正定矩阵，则关丁共轨的任意斤+ 1向量必线性相关.V 2在牛顿法屮，每次的迭代方向都是下降方向.X 3经典Newton法在相继两次迭代中的迭代方向是正交的.X 4PRP共觇梯度法与BFGS算法都属于Broyden族拟Newton算法.X 5用DFP算法求解正定二次函数的无约束极小化问题，则算法屮产生的迭代方向一定线性无关.V 6 FR共轨梯度法、PRP共辄梯度法、DFP算法、及BFGS算法均具有二次收 敛性.X 7共轨梯度法、共辘方向法、DFP算法以及BFGS算法都具有二次终止性.V 8函数广川T/?在*处的最速下降方向为_______________________________ . 9求解min fM的经典Newton法在十处的迭代方向为p k = _________________ . xeR n 10若.f(x)在T的邻域内具有一阶连续的偏导数且V/(x*) = 0,则F为的局部极小点.x 11若/(力在/的某邻域内具有二阶连续的偏导数且/为/(兀)的严格局部极小点，则G'WfX)正定.x 12求解m f n /(x)的最速下降法在(处的迭代方向为p k = _________________ . xeR n 13求解min /⑴的阻尼Newton法在卡处的迭代方向为p k = ________________ . xeR n 14用牛顿法求解min -x T Gx + b T x (bwR”, GeR nxn)时，至多迭代一次xeR n 2可达其极小点.X 15牛顿法具有二阶收敛性.V 16二次函数的共辘方向法具有二次终止性.X 17共饥梯度法的迭代方向为： ______________________ . 二、证明题 设f ??R“ T R 为一阶连续可微的凸函数，x*丘R”且V/(T) = O ，则疋为 min /(X )的全局极小点. XE R" bwR”和正定矩阵GwRE .如果HR”为求解 /(x)=丄兀9兀+沪兀的迭代点，d k eR n \{0}为其迭代方向，且 2 务w[0,+oo)为由精确一维搜索所的步长，则创=-：貨：胖 ? 试证：Newton 法求解正定二次两数时至多一次迭代可达其极小点. 简述牛顿法或者阻尼牛顿法的优缺点. 简述共轨梯度法的基木思想. 计算题 利用最优性条件求解无约束最优化问题. 3 1 例如：求解 min f (x) = —x^ + —x ； -x,x 2 -2x } 用FR 共轨梯度法无约束最优化问题. 见书本：例3.4.1. 用PRP 共轨梯度法无约朿最优化问题. 见书本：例3.4.1. 3 1 例如：min f(x) = — +~x 2 一坷七 一2兀】其屮兀()=(0,0)卩,￡ = 0.01 第四章约束最优化方法 考虑约束最优化问题： (NLP) min /(x) s.t. c i (x) = 0, z G E = {1, 2, ? ? ?, /}, Cj (x) > 0, z G / = {/ + 1, / + 2, ???? m}, min xeR r> 四、 简述题 五、 其中，仁Cj(i = \,2,…，T R. -、判断与选择题 1外罚函数法、内罚函数法、及乘子法均属于SUMT. X 2使用外罚函数法和内罚函数法求解（NLP）时，得到的近似最优解往往不是（NLP）的可行解.X 3在求解（NLP）的外罚函数法小，所解无约束问题的H标函数为? 4在（NLP）中/ = 0,则在求解该问题的内罚函数法中，常使用的罚函数为 ______________________________________________ ? 5在（NLP）中/ =0,则在求解该问题的乘子法中，乘子的迭代公式为（儿 + 】）「? = ________________ ，对i e {I,---, in}. 6在（NLP）中m = I,则在求解该问题的乘了法中，增广的Lagrange函数为： _________________________________ 二、计算题 1利用最优性条件(KT条件)求解约束最优化问题. 2用外罚函数法求解约束最优化问题. 见书本：例4.2.1； 例 4.2.2. 3用内罚函数法求解约束最优化问题. 见书本：例4.2.3. 4用乘子法求解约束最优化问题. 见书本：例427； 例 4.2.8. 三、简述题 1简述SUMT外点法的优缺点. 2简述SUMT内点法的优缺点. 四、证明题 利用最优性条件证明相关问题. 例如:Q设为正定矩阵，4为列满秩矩阵?试求规划 (P) min /(x) = —x T Qx + c7x + a s.t. A J x = h 的最优解，并证明解是唯一的. 第五章多目标最优化方法 一、判断与选择题 1求解多H标最优化问题的评价函数法包括? 2通过使用评价函数，多冃标最优化问题能够转化为单冃标最优化问题.V 3设F:DyR” TRJ则F在D上的一般多目标最优化问题的数学形式为_________________________________ ? 4对于规划V - m i n F(x) = (/J (x),..., f m (x))r ,设兀，若不存在XE D使得F(x) < F(F)且F(Q H F(F),则F为该最优化问题的有效解.V 5一般多口标最优化问题的绝对最优解必是有效解.V 6对于规划v —min F(x)=(/】⑴,…，九⑴)，，设W,为相应于xeDQR n /? (z = 1,2,...,777)的权系数，则求解以上问题的线性加权和法中所求解优 化的目标函数为_________________________________ . 7利用求解V-m i n F⑴=(.齐(兀),???，九⑴卩的线性加权和法所得到的 xeDQR n 解，或者为原问题的有效解，或者为原问题的弱有效解.V 二、简述题 1简单证明题 ☆ 绝对最优解、有效解、及弱有效解Z间的关系. ?第5.2节屮几个主要结论的证明. 2简单叙述题 ★简述求解一般多冃标规划的评价函数法的基本思想. ?简述求解一般多冃标规划的线性加权和法的基本思想. ★简述求解一般多口标规划的理想点法的基本思想. ?简述在求解一般多冃标规划的评价函数法中，确定权系数方法的基本思想. 《最优化方法》复习题 第一章概述(包括凸规划) 一、判断与填空题 ar§ max /W =玄生min【―/(兀)】?7 1 xeR n xeR n 2max |/(x): x e D o }= - min [f(x): x e D Q R H\ x 3设f : D u RJ R?若T wR”,对于一切xeR n恒有/(Z)上的凸函数当且仅当—/为D上的凹函数.V 1()设f : D u R” T R为凸集D上的可微凸函数，Z G Z).则对V XG D,有/(x)-/(x*) 则对\^^{0,1,2,???},恒有____ /(x A.+1)< f(x k) ____________ : 13算法迭代时的终止准则（写出三种）： ____________________________ o 14凸规划的全体极小点组成的集合是凸集。V 15函数f : D u R“ T R在点（'沿着迭代方向d* eR n \ ｛（）｝进行精确一维线搜索的步长匕.，则其搜索公式为_____________________________ . 16函数f ?. D匚R“ T R在点*?沿着迭代方向d k e/?z, \｛0｝进行梢确一?维线搜索的步长匕，则V/（x A+a k d k Yd k = ___________ 0 . 17设d k eR n\｛0｝为点/ w D匸R“处关于区域D的一个下降方向，则对于Va >0, 3?G（0,a）使得x 二、简述题 1写出Wolfe-Powell非精确一维线性搜索的公式。 2怎样判断一个函数是否为凸函数. （例如:判断函数/（x） = xf +2兀|兀2 +2兀;一10兀1 +5兀2是否为凸函数） 三、证明题 1证明一个优化问题是否为凸规划.（例如 1Z* T —X Gx + c x + b 2 判断s.t. Ax = b（其小G是正定矩阵）是凸规划. x>0 2熟练掌握凸规划的性质及英证明. 《最优化方法》复习题 一、 简述题 1、怎样判断一个函数是否为凸函数. （例如: 判断函数212 2 212151022)(x x x x x x x f +-++=是否为凸函数） 2、写出几种迭代的收敛条件. 3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大M 法及二阶段法）. 见书本61页(利用单纯形表求解); 69页例题 (利用大M 法求解、二阶段法求解); 4、简述牛顿法和拟牛顿法的优缺点. 简述共轭梯度法的基本思想. 写出Goldstein 、Wolfe 非精确一维线性搜索的公式。 5、叙述常用优化算法的迭代公式． （1）0.618法的迭代公式：(1)(), ().k k k k k k k k a b a a b a λτμτ=+--??=+-? （2）Fibonacci 法的迭代公式：111(),(1,2,,1)() n k k k k k n k n k k k k k n k F a b a F k n F a b a F λμ---+--+? =+-?? =-? ?=+-?? L ． （3）Newton 一维搜索法的迭代公式： 1 1k k k k x x G g -+=-． （4）推导最速下降法用于问题1min ()2 T T f x x Gx b x c = ++的迭代公式： 1()T k k k k k T k k k g g x x f x g G gx +=-? （5）Newton 法的迭代公式：211[()]()k k k k x x f x f x -+=-??． （6）共轭方向法用于问题1min ()2 T T f x x Qx b x c = ++的迭代公式： 1()T k k k k k T k k f x d x x d d Qd +?=-． 二、计算题 双折线法练习题 课本135页 例3.9.1 FR 共轭梯度法例题：课本150页 例4.3.5 二次规划有效集：课本213页例6.3.2, 《最优化方法》复习题(含答案) 附录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 λλ+++=-+， 《最优化方法》试题 一、 填空题 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 α，则其搜索公式 课 程 编 号 : 0 7 0 0 0 2 0 3 北 京 理 工 大 学 2 0 0 7 - 2 0 0 8 学 年 第 二 学 期 2005 级数学专业最优化方法终考试卷（ A 卷） 1． (20 分 )某化工厂有三种资源 A 、 B 、 C ，生产三种产品甲、乙、丙，设甲、乙、丙的产量分别为 x 1,x 2,x 3 ,其数学模型为： max z 3 x 1 2 x 2 5 x 3 1 2 x 2 3 430 ( A 资源限制 ) x x 3 x 1 2 x 3 460 ( B 资源限制 ) s.t 4 x 2 420 (C 资源限制 ) x x 1 , x 2 , x 3 0 请回答如下问题： （ 1）给出最优生产方案； （ 2）假定市场信息表明甲产品利润已上升了一倍，问生产方案应否调整？ （3）假定增加一种添加剂可显着提高产品质量，该添加剂的资源限制约束为： x 1 2 x 2 3x 3 800 问最优解有何变化？ 2． (12 分 )用 Newton 法求解 min f ( x ) 4 x 12 x 22 2 x 12 x 2 ，初始点取为 x 0 (1, 1)T ，迭代一步。 3．(10 分 )用 FR 共轭梯度法求解三个变量的函数 f ( x ) 的极小值，第一次迭代的搜索方向为 p 0 (1, 1,2)T ，沿 p 0 做精确线搜 索，得 x 1 ( x 11 , x 21 , x 31 )T ， 设 f ( x 1 ) 2, f ( x 1 ) 2 ，求从 x 1 出发的搜索方向 p 1 。 x 11 x 21 4． (15 分 ) 给定下面的 BFGS 拟 Newton 矩阵修正公式： H k 1 ( I s k y k T )H k ( I s k y k T )T s k s k T ， y k T s k y k T s k y k T s k 其中 s k x k 1 x k , y k g k 1 g k 用对应的拟 Newton 法求解： min f ( x ) x 1 2 2x 1 x 2 2 x 22 4 x 1 ，初始点取为 x 0 (0,0) T ， H 0 I 。 5． (15 分 )写出问题 取得最优解的 Kuhn-Tucker （ K － T ）必要条件，并通过 K － T 条件求出问题 K － T 点及相应 Lagrange 乘子。 6(12 分 )．求约束问题 在 x (0,0) T 及 x 2 (1,0) T 处的下降方向集合、可行方向集合以及可行下降方向集合，并画图表示出来 1 7（ 8 分）考察优化问题 min f ( x ) s.t. x ， D 设 D 为凸集， f ( x ) 为 D 上凸函数，证明： f ( x) 在 D 上取得极小值的那些点构成的集合是凸集。 8（ 8 分）设 min f ( x ) 1 x T Ax b T x c ，其中 A 为对称正定矩阵， x * 为 f ( x ) 的极小值点，又设 x 0 ( x*) 可表示为 2 x 0 x * p ，其中 R 1， p 是 A 对应于特征值 的特征向量，证明：若从 x 0 出发，沿最速下降方向做精确一维搜索， 则一步达到极小值点。 课程编号 :07000203 北京理工大学 2008-2009 学年第一学期 2006 级数学专业最优化方法终考试卷（ A 卷） 1． (15 分 ) 用单纯形法求解线性规划问题 2． (10 分 )写出线性规划问题 的对偶问题并证明该对偶问题没有可行解。 3． (15 分 )考虑用最速下降法迭代一步 min f ( x) x 12 2x 22 ， 初始点取为 x 0 ( 1, 1)T 。（ 1）采用精确一维搜索；（ 2） 采用 Wolfe 条件进行不精确一维搜索，其中 0.1, 0.9 。 4． (15 分 )用 DFP 拟牛顿法求解 min f ( x) x 12 2x 22 初始点取为 x 0 1 ，初始矩阵 H 0 2 1 。 1 1 1 5． (15 分 )证明集合 S { x | x 1 2x 2 4, 2x 1 x 2 6} 是凸集，并计算原点 (0,0) 到集合 S 的最短距离。 6． (15 分 ?) 考虑问题 （1）用数学表达式写出在点 ( 1 , 5)T 处的下降可行方向集。 3 3 （ 2）假设当前点在 (0,0) T 处，求出用投影梯度法进行迭代时当前的下降可行方向（搜索方向）。 7（ 7 分）证明：在精确一维搜索条件下，共轭梯度法得到的搜索方向是下降方向。 x zD 天津大学《最优化方法》复习题(含答案) 第一章 概述(包括凸规划) 判断与填空题 arg max f(x)二 arg min 以儿 “ max(x): x D 二 R n 』=-min(x): x D 二 R n ； 设f : D 5 R n > R.若x ： R n ，对于一切R n 恒有f(x”)^f(x)，则称x”为 设f : D 5 R n >R.若x ” ? D ,存在x ”的某邻域N ；(x”)，使得对一切 x ?N .(x)恒有f(x”)：：： f (x)，则称x”为最优化问题 min f (x)的严格局部最 优解? 给定一个最优化问题，那么它的最优值是一个定值 ? V 非空集合D R n 为凸集当且仅当 D 中任意两点连线段上任一点属于 D . V 非空集合D R n 为凸集当且仅当D 中任意有限个点的凸组合仍属于 D . V 任意两个凸集的并集为凸集? 函数f:D R n >R 为凸集D 上的凸函数当且仅当 -f 为D 上的凹函数? V 设f : D R n >R 为凸集D 上的可微凸函数，X ：D ?则对-D ,有 f (x) - f(x )乞 f (x )T (X —X )? 若c(x)是凹函数，则 D={x^R n C(x)启0}是凸集。 V f(x)的算法A 产生的迭代序列，假设算法 A 为下降算法, 则对-k ? 5,1, 2,…匚恒有 ________________ f(x k1)乞 f(x k ) ______________ ? 算法迭代时的终止准则(写出三种) ： ___________________________________________________ 凸规划的全体极小点组成的集合是凸集。 V 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2003—2008《工程与科学计算》历届试题类型 1. 直解法 例 1. 用列主元素Gauss 消去解下列线性方程组（结果保留5位小数） ?? ? ??=++=++=++0000 .11000.12100.13310.18338.00000.10000.10000.16867.09000.08100.07290.0321321321x x x x x x x x x 例2. 设线性方程组b Ax =,其中 1 123 1 112341113 4 51 A ??? ?=?????? 求)(A Cond ∞，并分析线性方程组是否病态 ? 2.迭代法 例1. 设线性方程组b Ax =为 ?? ?? ??????=????????????????????-----221221122321x x x ααα ， 0≠α 写出求解线性方程组的Jacobi 迭代格式，并确定当α取何值时Jacobi 迭代格式收敛. 例 2. 写出求解线性方程组b Ax =的Seidel 迭代格式，并判断所写格式的收敛性，其中 b Ax =为 ?? ? ? ?=++-=+=-5 228262332 13231x x x x x x x 3.插值 例 1. 已知,12144,11121,10100=== （1）试用二次插值多项式计算115的近似值（数据保留至小数点后第5位） （2）估计所得结果的截断误差（数据保留至小数点后第5位） 例 2. 由下列插值条件 4. Runge —Kutta 格式 例 写出标准Kutta Runge -方法解初值问题 ???==+-=1 )0(,1)0(sin 2' 2'''y y x y xy y 的计算格式 2013-2014学年第一学期 数学计算经数专业《最优化方法》（课程）期末试卷 试卷来源：自拟 送卷人:赵俊英 打印：赵俊英 乔凤云 校对：赵俊英 一．填空题（20分） 1．最优化问题的数学模型一般为：____________________________， 可行域D 可以表 为_____________________________， 若____________________，称* x 为问题的全局最优解. 2.()()??? ? ??+???? ?????? ??=212121 312112)(x x x x x x x f ，则=?)(x f ， =?)(2 x f . 3.设f 连续可微且0)(≠?x f ，若向量d 满足 ，则它是f 在x 处的一个下降方向. 4. 无约束最优化问题：min (),n f x x R ∈，若k x 是不满足最优性条件的第k 步迭代点，用共轭梯度法求解时，搜索方向k d =______________ 5. 函数R R D f n →?:在点k x 沿着迭代方向}0{\n k R d ∈进行精确一维线搜索的步长k α，则其搜索公式为 . 6 .举出一个具有二次终止性的无约束二次规划算法： . 7.函数222 21 12313()226f x x x x x x x x =+++- （填是或不是） 严格凸函数. 二．（18分）简答题： 1. 设计求解无约束优化问题的一个下降算法，并叙述其优缺点. 2. 叙述单折线法的算法思想. 3. 写出以下线性规化问题的对偶： 1234123412341234134min ()2536..873411,762323,324712,0,0,0.f x x x x x s t x x x x x x x x x x x x x x x =-+-??-+++=?? +++≥??+++≤? ≤≥≥?? 《最优化方法》课程教学大纲 Methods of Optimization 课程代码： 课程性质：专业基础理论课/选修 适用专业：信息计算、统计学开课学期：6 总学时数：56总学分数：3.5 编写年月：2002年3月修订年月：2007年7月 执笔：刘伟 一、课程的性质和目的 最优化计算方法是在生产实践和科学实验中选取最佳决策，研究在一定限制条件下，选取某种方案，以达到最优目标的一门学科，广泛应用与空间科学、军事科学、系统识别、通讯、工程设计、自动控制、经济管理等各个领域，是工科院校高年纪学生、研究生、应用数学专业学生和搞优化设计的工程技术人员的一门重要课程。通过本课程教学，使学生掌握最优化计算方法的基本概念和基本理论，初步学会处理应用最优化方法解决实际中的碰到的各个问题，培养解决实际问题的能力。 二、课程教学内容及学时分配 （一）教学内容 1. 最优化方法和最优化模型 最优化方法定义、最优化问题的数学模型与分类；根据问题特点（无约束最优化与约束最优化），根据函数类型（线性规划，非线性规划）；最优化方法（解析法，直接法），最优解与极值点。 2.基础知识 多元函数泰勒公式的矩阵形式，古典极值理论问题，二次函数求梯度公式，凸集，凸函数，凸规划，几个重要的不等式。 3. 常用的一维搜索方法 一维搜索法是最优化的基础，“成功－失败”法的思想与算法，黄金分割法（０.618法）的思想与算法，二次插值法，三次插值法，Ｄ。Ｓ。Ｃ法，Ｐowell 法等方法的思想与算法。 4. 无约束最优化方法 无约束最优化方法是最优化方法中的基本方法。最速下降法的思想与算法步骤，牛顿法的思想与算法步骤，共轭方向法的思想与算法步骤，共轭梯度法的思想与算法步骤，变尺度法（ＤＦＰ法和ＢＦＧＳ法）的思想与算法步骤 5. 约束最优化方法 约束最优化方法通常约束问题转化为无约束问题求解。序列无约束极小化方法（ＳＵＭＴ－外点法与ＳＵＭＴ－内点法）的思想与算法步骤，内点的求法，其他罚函数法,Frank-Wolfe法的思想与算法步骤 华南农业大学期末考试试卷（A 卷） 2010--2011学年第 1 学期 考试科目： 运筹学与最优化方法 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 一、 用单纯形法求解下列线性规划问题（共 15 分） 12121212max 105349 ..528,0z x x x x s t x x x x =++≤?? +≤??≥? 二、灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分） 12121212max 62 ..33,0z x x x x s t x x x x =++≥?? +≤??≥? 三、解下列0-1型整数规划问题（共 10 分） 12345123451345124512345max 325232473438..116333,,,,01 z x x x x x x x x x x x x x x s t x x x x x x x x x =+--+++++≤??+-+≤?? -+-≥??=?或 四、利用库恩-塔克（K-T ）条件求解以下问题（共 15 分） 22121122 121212 max ()104446..418,0f X x x x x x x x x s t x x x x =+-+-+≤??+≤??≥? 五、用内点法求解下列非线性约束最优化问题（共 15 分） 21 121 2min ()6923..3 f X x x x x s t x =-++≥??≥? 六、给定初始点(0)(1,1)T X =，用最速下降法迭代一次研究下列函数的极大值。（共 15 分） 22 121122()46222f X x x x x x x =+--- 七、某人因工作需要购置了一辆摩托车,他可以连续使用或任一年末将旧车卖掉,换一辆新车,下表列出了于第i 年末购置或更新 的车至第j 年末的各项费用的累计(含更新所需费用、运行费用及维修费用等)，试据此确定该人最佳的更新策略，使从第一年至第五年末的各项费用的累计之和为最小。（共 15 分） 《最优化方法》复习题 第一章 引论 一、 判断与填空题 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.建立模拟仿真模型方式 对一般复杂系统，如城市轨道交通调度系统、机场调度系统、城市整个交通控制系统等问题，可以对系统概念模型中各个部件等采用变量予以量化表示，并通过系统辨识的方式建立这些变量之间关系的动力学方程组，采用一定的编程语言、仿真技术使其转化为系统仿真模型，通过模拟仿真寻找较满意的优化方案，包括离线和在线均可以，有关该方面的内容见第七章。 模拟仿真模型比解析模型更能反映系统的实际，所以在交通运输系统中被更高层次的所使用，包括 《算法设计与分析》历年期末试题整理(含答案) （1）用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实 现7、程序调试8、结果整理文档编制 （2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 （3）算法的三要素 1、操作 2、控制结构 3、数据结构算法具有以 下5 个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限 次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算 法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要 的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。 编写计算斐波那契（Fibonacci）数列的第n 项函数fib（n）。 斐波那契数列为：0、1、1、2、3、……，即： 一、 选择、判断、填空（10小题，每题2分，共20分） 1、线性规划问题化为标准型以后，原来的某自由变量被两个非负变量之差代替，在完成一次单纯形法迭代过程后，这两个非负变量的值_______________。 A 、可同时不为0； B 、必然同时为0； C 、最多只能有一个不为0； D 、必然同时不为0。 2、关于线性规划，以下叙述正确的是________。 A 、若存在最优化解，则一定是最优基本可行解； B 、若存在最优基本可行解，则其对偶问题也必存在最优解； C 、若无可行解，则对偶问题一定有无界解； D 、若存在最优解，则必存在最优基本可行解。 3、关于P 类问题、NP 类问题和P 类算法、NP 类算法，以下正确的叙述是______________。 A 、存在P 类算法的判定问题不一定是P 类问题；B 、线性规划问题的单纯形算法不是P 类算法，所以线性规划问题是NP 类问题；C 、NP 类问题包含P 类问题；D 、P 类问题与NP 类问题是互相对立的两类问题。 ***第4-6小题：判断正误，正确的填“√”，错误的填“╳”，填在括号内*** 4、用模拟退火算法求出的组合优化问题的解一定是最优解（ ）。 5、对于有约束非线性规划问题，目标函数的极值点一定是K-T 点（ ）。 6、已知LP 为求最小值问题，第i 个约束是“≤”约束，则对偶问题的第i 个对偶变量y i ≤0 7、若x (0)和y (0)分别是线性规划问题min{z =c T x | Ax ≥b , x ≥0}和其对偶问题的可行解，则x (0)和y (0)的关系是____________________（两者目标函数在x (0)和y (0)处值的关系）。 8、设x i 是某线性规划问题的一个决策变量，在单纯形法某次迭代后，若它的检验数不为零，则x i 是________变量。 9、使用黄金分割法和抛物线法进行一维搜索（设目标函数为 min f (x ) ）之前，必须首先找到三点，x 1、x 2和x 3，这三点应满足的条件为____________________________________。 10、用牛顿法求解约束优化问题min f (x )的x (1)（假设f (x )在x (1)）二阶光滑，且Hasse 矩阵正定）处的牛顿方向是_____________________________。 二、（（12分））考虑如下线性规划问题 123123123123m in 4.. 29240,1,2,3 i Z x x x s t x x x x x x x x x x i =++++≤+-≤-++≤≥= 令54,x x 和6x 表示每个约束的松弛变量．应用单纯形方法，得到最优单纯形表如下 ----------专业最好文档，专业为你服务，急你所急，供你所需------------- 《最优化方法》复习题 第一章 概述(包括凸规划) 一、 判断与填空题 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 为下降算法， 最优化理论、方法及应用试题 一、 （30分） 1、针对二次函数1()2 T T f x x Qx b x c = ++，其中Q 是正定矩阵，试写出最速下降算法的详细步骤，并简要说明其优缺点？ 答：求解目标函数的梯度为()g x Qx b =+，()k k k g g x Qx 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、有约束优化问题 min () ()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 2 12**(*)*(*)*(*)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λ>，使得它对任意 《最优化方法》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 )(是正定二次函数，证明一维问题最优化方法复习题66882.docx
《最优化方法》复习题
《最优化方法》复习题(含答案)
最优化方法试题
天津大学《最优化方法》复习题(含答案)
北京理工大学级数学专业最优化方法期末试卷试题A卷MT.doc
《最优化方法》复习题(含答案)
(完整版)天津大学最优化历年试题
13-14(1)最优化方法期末试卷
最优化方法课程教学大纲
最优化方法考试试题
修订过的最优化方法复习题
《最优化方法》期末试题
《算法设计与分析》历年期末试题整理_含答案_
最优化计算试卷模板1
天津大学最优化方法复习题
最优化试题及答案
最优化方法试卷与答案5套
相关主题
文本预览