天津大学最优化方法复习题

《最优化方法》复习题第一章概述(包括凸规划)一、判断与填空题ar§ max /W =玄生min【―/(兀)】・71xeR n xeR n2max |/(x): x e D o }= - min [f(x): x e D Q R H\ x3设f : D u RJ R・若T wR”,对于一切xeR n恒有/(Z)</(x),则称T为最优化问题m in fM的全局最优解.xxeD4设f •・D U RJ R.若Z eD ,存在F的某邻域Ng,使得对一切恒有/U*)</(兀)，则称T为最优化问题min /(兀)的严格局部最xeD优解.X5给定一个最优化问题，那么它的最优值是一个定值.V6非空集合D匸/?"为凸集当且仅当D屮任意两点连线段上任一点属于D. V 7非空集合D o 7?"为凸集当J1仅当D中任意有限个点的凸组合仍属于D. V 8任意两个凸集的并集为凸集.x9 函数f : D匸R” T R为凸集£>上的凸函数当且仅当—/为D上的凹函数.V1()设f : D u R” T R为凸集D上的可微凸函数，Z G Z).则对V XG D,有/(x)-/(x*)<V/(x*/(x-x*). x11若c(兀)是凹函数，则D = {xeR n\ c(x) > 0}是凸集。

V12设{*}为由求解min的算法A产生的迭代序列，假设算法A为下降算法，XG D则对\^^{0,1,2,・・・},恒有____ /(x A.+1)< f(x k) ____________ :13算法迭代时的终止准则（写出三种）： ____________________________ o 14凸规划的全体极小点组成的集合是凸集。

V15函数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非精确一维线性搜索的公式。

【最新整理，下载后即可编辑】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 =,其中 11231112341113451A ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦求)(A Cond ∞，并分析线性方程组是否病态 ? 2.迭代法例1. 设线性方程组b Ax =为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-----221221122321x x x ααα ， 0≠α写出求解线性方程组的Jacobi 迭代格式，并确定当α取何值时Jacobi 迭代格式收敛.例2. 写出求解线性方程组b Ax =的Seidel 迭代格式，并判断所写格式的收敛性，其中b Ax =为⎪⎩⎪⎨⎧=++-=+=-522826233213231x x xx x x x3.插值例 1. 已知,12144,11121,10100===（1）试用二次插值多项式计算115的近似值（数据保留至小数点后第5位）（2）估计所得结果的截断误差（数据保留至小数点后第5位） 例 2. 由下列插值条件4. Runge —Kutta 格式例 写出标准Kutta Runge -方法解初值问题⎩⎨⎧==+-=1)0(,1)0(sin 2'2'''y y xy xy y 的计算格式5. 代数精度例 1. 数值求积公式形如)1()0()1()0()()(321010f A f A f A f A x S dx x xf '+'++=≈⎰试确定其中参数,,,,4321A A A A 使其代数精度尽量高, 并确定代数精度.例 2. 验证数值求积公式20120()(1(1)(1f x dx A f A f A f ≈+++⎰是Gauss 型求积公式.6．Romberg 方法例 对积分⎰+1021dx x ，用Romberg 方法计算积分的近似值，误差不超过510-并将结果填入下表（结果保留至小数点后第五位）.7（1）设)(x ϕ为],[b a 上关于权函数)(x ρ的n 次正交多项式，以)(x ϕ的零点为节点建立Lagrange 插值基函数)}({x l i ， 证明：⎰⎰==ba ba i i ni dx x l x dx x l x ,,2,1,)]()[()()(2 ρρ证明: 设n 次正交多项式()x ϕ的零点为12,,n x x x ，则以这n 个零点为节点建立的Lagrange 插值基函数{()},1,2,i l x i n =是n-1次多项式，[]2()i l x 是2n-2次多项式. 故当()f x 取()i l x 和[]2()i l x 时Gauss 型求积公式1()()()nb k k ak x f x dx A f x ρ=≈∑⎰等号成立, 即 1()()()nb i k i k iak x l x dx A l x A ρ===∑⎰221()()()nbi k i k ia k x l x dx A l x A ρ===∑⎰则有 ⎰⎰==b abai i ni dx x l x dx x l x ,,2,1,)]()[()()(2 ρρ（2）对线性方程组b Ax =，若A 是n 阶非奇异阵，0≠b ，*x 是b Ax =的精确解，x 是b Ax =的近似解。

天津大学《最优化方法》复习题(含答案)第一章 概述(包括凸规划)一、 判断与填空题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 Dx ∈的严格局部最优解、 ⨯5 给定一个最优化问题,那么它的最优值就是一个定值、 √6 非空集合n R D ⊆为凸集当且仅当D 中任意两点连线段上任一点属于D 、 √7 非空集合nR 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 Dx ∈的算法A 产生的迭代序列,假设算法A 为下降算法,则对{}Λ,2,1,0∈∀k ,恒有 )()(1k k x f x f ≤+ 、13 算法迭代时的终止准则(写出三种):_____________________________________。

14 凸规划的全体极小点组成的集合就是凸集。

《最优化方法》复习题一、 简述题1、怎样判断一个函数是否为凸函数.(例如:判断函数f(x) =昇+ 2兀內+ 2近一 10州+ 5兀2是否为凸函数)2、 写出几种迭代的收敛条件.3、 熟练掌握利用单纯形表求解线性规划问题的方法(包括大M 法及二阶段法).见书本61页(利用单纯形表求解)；69页例题(利用大M 法求解、二阶段法求解)； 4、 简述牛顿法和拟牛顿法的优缺点.简述共辘梯度法的基木思想.写岀Goldstein> Wolfe 非精确一维线性搜索的公式。

5、叙述常用优化算法的迭代公式.心=务+吕—％),化-知1仏二务+召一色)(3) Newton —维搜索法的迭代公式：x k+i = x k -G~'g k ・ (4) 推导最速下降法用于问题min/(x) = —++ c 的迭代公式:耳+1 二无一-VfgS k G k gx k(5) Newton 法的迭代公式：x k+] = x k -[V 2/(^)]_l V/*(x A )・ (6) 共轨方向法用于问题min/(x)=丄x rQx+b 1x + c 的迭代公式:2忑+1 =J二、计算题双折线法练习题 课本135页 例3.9.1FR 共辘梯度法例题：课本150页 例4.3.5(1) 0.618法的迭代公式:A- =ak +（1-厂）（勺一务）,(2) Fibonacci 法的迭代公式: 伙= 1,2,…,一1）二次规划有效集：课本213页例6.3.2,所有留过的课后习题.三、练习题：1、 设A G R ,iXn是对称矩阵，bwR”，cwR,求/(%) =丄*心+戻兀+ c 在任意点x 处 的梯度和Hesse 矩阵.解 V/*(x) = Ar + /?, V 2/(x) = A ・2、 设0(/) = /(兀 + 力)，其屮/:/?" T R 二阶可导，XG R\de R\te R ,试求0"(/)・解 0(/) = W(x + /d) 丁4,矿⑴=dF f(x~Hd)d .3、 证明：凸规划min f(x)的任意局部最优解必是全局最优解.xeS证明 用反证法.设住S 为凸规划问题min /(x)的局部最优解，即存在丘的某xeS个5邻域N s (x),使f(x)<f(x)yxeN 6(x)C\S ・若元不是全局最优解，则存在花S,使/(i) < /(x)・由于/(兀)为S 上的凸函数，因此VA G (0,1),有/(Ax + (1-2)x) < 2/(x) + (1-2)/(x) < f(x)・当2充分接近1时，可使2元+(1 — 2)农 皿(元)「IS,于是/(x)</(2x + (l-/i)x), 矛盾.从而元是全局最优解.min f(x) = 2x t -x 2 +x 3; s.t. 3兀］+ x 2 + x 3 < 60,x l - 2X 2 + 2X 3 <10,%! + x 2 - x 3 < 20, (1)用单纯形法求解该线性规划问题;(2)写出线性规划的对偶问题;解 (1)引进变量兀，兀5,兀6,将给定的线性规划问题化为标准形式:min /(%) = 2x t -x 2 +x 3; s.t. 3x ( + 兀 + 耳 + % = 60,%j - 2X 2 + 2X 3 + 冯=10,所给问题的最优解为x = （0,20,0）r ,最优值为/ = -20・4、已知线性规划:（2）所给问题的对偶问题为：max g（y） = -60^-10^ - 20%；皿_3”_旳_儿52,< _必+2旳_儿S_l，一开_2旳 + %<1，儿力*3»°・5、用0.618法求解min 0（f） = （f-3尸，要求缩短后的区间长度不超过0.2,初始区间取[0,10]・解第一次迭代：取y [0,10],£ = 0.2.确定最初试探点人，“分别为入=^+0.382（^-^,） = 3.82, M =坷+0.618（勺一马）=6・18 .求目标函数值：°（人）=（3.82— 3）2 =0.67, °（“）= （6.18 — 3）2 =10.11.比较目标函数值：0（人）< 0（"）・比较 //| —6f| = 6.18 — 0 > 0.2 = E ・第二次迭代：a2 = a x = 0,Z?2= “| = 6.18,/ =人=3.82,。

《最优化方法》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 2121212221≥≥≤+--+=x x x x t s x x x x x f则其对偶规划为___________________________________________。

24．求解无约束最优化问题：n R x x f ∈),(min ，设k x 是不满足最优性条件的第k 步迭代点，则：用最速下降法求解时，搜索方向k d =___________ 用Newton 法求解时，搜索方向k d =___________ 用共轭梯度法求解时，搜索方向k d =___________________________________________________________________________。

附录5 《最优化方法》复习题1、设n n A R ⨯∈是对称矩阵，,n b R c R ∈∈，求1()2TT 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 TT Tdd 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 TTT 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 ∀≥∀∈的一切凸组合都属于S ．证明 充分性显然．下证必要性．设S 是凸集，对m 用归纳法证明．当2m =时，由凸集的定义知结论成立，下面考虑1m k =+时的情形．令11k i i i x x λ+==∑，其中,0,1,2,,1i i x S i k λ∈≥=+，且111k i i λ+==∑．不妨设11k λ+≠（不然1k x x S +=∈，结论成立），记111kii i k y x λλ=+=-∑，有111(1)k k k x y x λλ+++=-+，又1110,1,2,,,111kiii k k i k λλλλ=++≥==--∑，则由归纳假设知，y S ∈，而1k x S +∈，且S 是凸集，故x S ∈．5、设n R S ⊆为非空开凸集，R S f →:在S 上可微，证明：f 为S 上的凸函数的充要条件是2112112()()()(),,T f x f x f x x x x x S ≥+∇-∀∈．证明 必要性．设f 是S 上的凸函数，则12,x x S ∀∈及(0,1)λ∈，有2121((1))()(1)()f x x f x f x λλλλ+-≤+-，于是121121(())()()()f x x x f x f x f x λλ+--≤-，因S 为开集，f 在S 上可微，故令0λ+→，得12121()()()()T f x x x f x f x ∇-≤-，即2112112()()()(),,T f x f x f x x x x x S ≥+∇-∀∈．充分性．若有2112112()()()(),,T f x f x f x x x x x S ≥+∇-∀∈， 则[0,1]λ∀∈，取12(1)x x x S λλ=+-∈，从而11()()()()T f x f x f x x x ≥+∇-，22()()()()T f x f x f x x x ≥+∇-，将上述两式分别乘以λ和1λ-后，相加得1212()(1)()()()((1))T f x f x f x f x x x x λλλλ+-≥+∇+--12()((1))f x f x x λλ==+-，所以f 为凸函数．6、证明：凸规划min ()x Sf x ∈的任意局部最优解必是全局最优解．证明 用反证法．设x S ∈为凸规划问题min ()x Sf x ∈的局部最优解，即存在x 的某个δ邻域()N x δ，使()(),()f x f x x N x S δ≤∀∈．若x 不是全局最优解，则存在x S ∈，使()()f x f x <．由于()f x 为S 上的凸函数，因此(0,1)λ∀∈，有((1))()(1)()()f x x f x f x f x λλλλ+-≤+-<．当λ充分接近1时，可使(1)()x x N x S δλλ+-∈，于是()((1))f x f x x λλ≤+-，矛盾．从而x 是全局最优解．7、设n R S ⊆为非空凸集，R S f →:是具有一阶连续偏导数的凸函数，证明：x 是问题min ()x Sf x ∈的最优解的充要条件是：()()0,T f x x x x S ∇-≥∀∈．证明 必要性．若x 为问题min ()x Sf x ∈的最优解．反设存在x S ∈，使得()()0T f x x x ∇-<，则d x x =-是函数()f x 在点x 处的下降方向，这与x 为问题min ()x Sf x ∈的最优解矛盾．故()()0,T f x x x x S ∇-≥∀∈．充分性．若()()0,T f x x x x S ∇-≥∀∈．反设存在x S ∈，使得()()f x f x <．(())()((1))()f x x x f x f x x f x λλλλλ+--+--=()(1)()()()()0((0,1)f x f x f x f x f x λλλλ+--≤=-<∀，因S 为凸集，f 在S 上可微，故令0λ+→，得()()()()0T f x x x f x f x ∇-≤-<，这与已知条件矛盾，故x 是问题min ()x Sf x ∈的最优解．8、设函数()f x 具有二阶连续偏导数，k x 是()f x 的极小点的第k 次近似，利用()f x 在点k x 处的二阶Taylor 展开式推导Newton 法的迭代公式为 211[()]()k k k k x x f x f x -+=-∇∇．证明 由于()f x 具有二阶连续偏导数，故21()()()()()()()()2T T k k k k k k f x x f x f x x x x x f x x x ϕ≈=+∇-+-∇-．且2()k f x ∇是对称矩阵，因此()x ϕ是二次函数．为求()x ϕ的极小点，可令()0x ϕ∇=，即2()()()0k k k f x f x x x ∇+∇-=，若2()k f x ∇正定，则上式解出的()x ϕ的平稳点就是()x ϕ的极小点，以它作为()f x 的极小点的第1k +次近似，记为1k x +，即211[()]()k k k k x x f x f x -+=-∇∇，这就得到了Newton 法的迭代公式.9、叙述常用优化算法的迭代公式．（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 kk k k n k n k k k k k n k F a b a F k n F a b a F λμ---+--+⎧=+-⎪⎪=-⎨⎪=+-⎪⎩．（3）Newton 一维搜索法的迭代公式： 1()()k k k k t t t t ϕϕ+'=-''． （4）最速下降法用于问题1min ()2TT f x x Qx b x c =++的迭代公式： 1()()()()()T k k k k k Tk k f x f x x x f x f x Q f x +∇∇=-∇∇∇ （5）Newton 法的迭代公式：211[()]()k k k k x x f x f x -+=-∇∇． （6）共轭方向法用于问题1min ()2TT f x x Qx b x c =++的迭代公式： 1()T k kk k k Tk kf x d x x d d Qd +∇=-． 10、已知线性规划：123123123123123min ()2;..360,2210,20,,,0.f x x x x s t x x x x x x x x x x x x =-+⎧⎪++≤⎪⎪-+≤⎨⎪+-≤⎪⎪≥⎩（1）用单纯形法求解该线性规划问题的最优解和最优值； （2）写出线性规划的对偶问题； （3）求解对偶问题的最优解和最优值．解 （1）引进变量456,,x x x ，将给定的线性规划问题化为标准形式：123123412351236126min ()2;..360,2210,20,,,,0.f x x x x s t x x x x x x x x x x x x x x x =-+⎧⎪+++=⎪⎪-++=⎨⎪+-+=⎪⎪≥⎩所给问题的最优解为(0,20,0)T x =，最优值为20f =-． （2）所给问题的对偶问题为：123123123123123max ()601020;..32,21,21,,,0.g y y y y s t y y y y y y y y y y y y =---⎧⎪---≤⎪⎪-+-≤-⎨⎪--+≤⎪⎪≥⎩（1） （3）将上述问题化成如下等价问题：123123123123123min ()601020;..32,21,21,,,0.h y y y y s t y y y y y y y y y y y y =++⎧⎪---≤⎪⎪-+-≤-⎨⎪--+≤⎪⎪≥⎩引进变量456,,y y y ，将上述问题化为标准形式：123123412351236126min ()601020;..32,21,21,,,,0.h y y y y s t y y y y y y y y y y y y y y y =++⎧⎪---+=⎪⎪-+-+=-⎨⎪--++=⎪⎪≥⎩ （2）问题（2）的最优解为(0,0,1)T y =，最优值为20h =（最小值）． 问题（1）的最优解为(0,0,1)T y =，最优值为20g =-（最大值）．11、用0.618法求解 2min ()(3)t t ϕ=-，要求缩短后的区间长度不超过0.2，初始区间取[0,10]． 解 第一次迭代： 取11[,][0,10],0.2a b ε==． 确定最初试探点11,λμ分别为11110.382() 3.82a b a λ=+-=，11110.618() 6.18a b a μ=+-=．求目标函数值：21()(3.823)0.67ϕλ=-=，21()(6.183)10.11ϕμ=-=． 比较目标函数值：11()()ϕλϕμ<． 比较11 6.1800.2a με-=->=． 第二次迭代：212121210, 6.18, 3.82,()()0.67a a b μμλϕμϕλ========．2222220.382()0.382(6.180) 2.36,()(2.363)0.4a b a λϕλ=+-=-==-=．2222()(), 3.82a ϕλϕμμε<-=>．323232320, 3.82, 2.36,()()0.4a a b μμλϕμϕλ========．2333330.382()0.382(3.820) 1.46,()(1.463) 2.37a b a λϕλ=+-=-==-=．3333()(), 3.82 1.46b ϕλϕμλε>-=->． 第四次迭代：434343431.46, 3.82, 2.36,()()0.4a b b λλμϕλϕμ========．444440.618() 1.460.0.618(3.82 1.46) 2.918,()0.0067a b a μϕμ=+-=+-==． 4444()(), 3.82 2.36b ϕλϕμλε>-=->． 第五次迭代：545454542.36, 3.82, 2.918,()()0.0067a b b λλμϕλϕμ========．555550.618() 3.262,()0.0686a b a μϕμ=+-==． 5555()(), 3.262 2.36a ϕλϕμμε<-=->． 第六次迭代：656565652.36, 3.262, 2.918,()()0.0067a a b μμλϕμϕλ========．666660.382() 2.7045,()0.087a b a λϕλ=+-==．6666()(), 3.262 2.7045b ϕλϕμλε>-=->． 第七次迭代：767676762.7045, 3.262, 2.918,()()0.0067a b b λλμϕλϕμ========．777770.618() 3.049,()0.002a b a μϕμ=+-==． 7777()(),b ϕλϕμλε>->． 第八次迭代：878787872.918, 3.262, 3.049,()()0.002a b b λλμϕλϕμ========．888880.618() 3.131,()0.017a b a μϕμ=+-==． 8888()(),a ϕλϕμμε<->．989899982.918, 3.131, 3.049,()()0.002a a b μμλϕμϕλ========．999990.382() 2.999,()0.000001a b a λϕλ=+-==． 9999()(), 3.049 2.918a ϕλϕμμε<-=-<． 故993.0242x λμ+==．12、用最速下降法求解 22112212min ()2243f x x x x x x x =++--，取(0)(1,1)T x =，迭代两次．解 1212()(224,243)T f x x x x x ∇=+-+-， 将()f x 写成1()2TT f x x Qx b x =+的形式，则224,243Q b -⎛⎫⎛⎫== ⎪ ⎪-⎝⎭⎝⎭． 第一次迭代：(0)(0)(1)(0)(0)(0)(0)()()()()()T T f x f x xxf x f x Q f x ∇∇=-∇∇∇ 0(0,3)1013220131/4(0,3)243⎛⎫ ⎪⎛⎫⎛⎫⎛⎫⎝⎭=-= ⎪ ⎪ ⎪⎛⎫⎛⎫⎝⎭⎝⎭⎝⎭⎪⎪⎝⎭⎝⎭． 第二次迭代：(1)(1)(2)(1)(1)(1)(1)()()()()()T T f x f x xx f x f x Q f x ∇∇=-∇∇∇ 3/2(3/2,0)13/27/40223/21/401/4(3/2,0)240-⎛⎫- ⎪-⎛⎫⎛⎫⎛⎫⎝⎭=-= ⎪ ⎪ ⎪-⎛⎫⎛⎫⎝⎭⎝⎭⎝⎭- ⎪⎪⎝⎭⎝⎭． 13、用FR 共轭梯度法求解222123123123min ()()()()f x x x x x x x x x x =-++-++++-，取(0)11(,1,)22T x =，迭代两次．若给定0.01,ε=判定是否还需进行迭代计算． 解 222123121323()3()2()f x x x x x x x x x x =++-++，再写成1()2T f x x Gx =，622262226G --⎛⎫⎪=-- ⎪ ⎪--⎝⎭，()f x Gx ∇=．第一次迭代：(0)()(0,4,0)T f x ∇=，令(0)0()(0,4,0)T d f x =-∇=-，从(0)x 出发，沿0d 进行一维搜索，即求(0)200min ()21648f x d λλλλ≥+=-+的最优解，得(1)(0)0001/6,(1/2,1/3,1/2)T x x d λλ==+=．第一次迭代：(1)()(4/3,0,4/3)T f x ∇=．2(1)02(0)()29()f x f x α∇==∇， (1)100()(4/3,8/9,4/3)T d f x d α=-∇+=---．从(1)x 出发，沿1d 进行一维搜索，即求(1)10142362214181418min ()(,,)262233923392261423f x d λλλλλλλλ≥⎛⎫- ⎪--⎛⎫ ⎪⎪⎪+=------ ⎪ ⎪ ⎪-- ⎪⎝⎭ ⎪- ⎪⎝⎭的最优解，得(2)(1)1111/24/333,1/38/9(0,0,0)881/24/3T x x d λλ-⎛⎫⎛⎫ ⎪ ⎪==+=+-= ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭．此时(2)(2)()(0,0,0),()00.01T f x f x ε∇=∇=<=．得问题的最优解为(0,0,0)T x =，无需再进行迭代计算．14、用坐标轮换法求解 2212112min ()242f x x x x x x =+--，取(0)(1,1)T x =，迭代一步．解 从点(0)(1,1)T x =出发，沿1(1,0)T e =进行一维搜索， 即求(0)210min ()43f x e λλλλ≥+=--的最优解，得(1)(0)0012,(3,1)T x x e λλ==+=．再从点(1)x 出发，沿2(0,1)T e =进行一维搜索， 即求(1)220min ()227f x e λλλλ≥+=--的最优解，得(2)(1)1121/2,(3,3/2)T x x e λλ==+=．15、用Powell 法求解2212112min ()3f x x x x x x =+--，取(0)(0,0)T x =，初始搜索方向组01(0,1),(1,0)T T d d ==，给定允许误差0.1ε=（迭代两次）． 解 第一次迭代：令(0)(0)(0,0)T y x ==，从点(0)y 出发沿0d 进行一维搜索，易得(1)(0)0000,(0,0)T y y d λλ==+=；接着从点(1)y 出发沿1d 进行一维搜索，得(2)(1)11133,(,0)22T y y d λλ==+=由此有加速方向 (2)(0)23(,0)2T d y y =-=．因为23/2d ε=>，所以要确定调整方向．由于 (0)(1)(2)9()0,()0,()4f y f y f y ===-，按（8.4.17）式有(1)(2)()(1)()()max{()()|0,1}j j f y f y f y f y j +-=-=，因此1m =，并且()(1)(1)(2)9()()()()4m m f y f y f y f y +-=-=． 又因(2)(0)(2)0f y y -=，故（8.4.18）式不成立．于是，不调整搜索方向组，并令(1)(2)3(,0)2T x y ==．第二次迭代：取(0)(1)3(,0)2T y x ==，从点(0)y 出发沿0d 作一维搜索，得(1)(0)000333,(,)424T y y d λλ==+=．接着从点(1)y 出发沿方向1d 作一维搜索，得(2)(1)1113153,(,)884Ty y d λλ==+=． 由此有加速方向(2)(0)233(,)84T d y y =-=．因为2d ε=>，所以要确定调整方向．因(0)(1)(2)945189(),(),()41664f y f y f y =-=-=-， 故按（8.4.17）式易知0m =，并且()(1)(0)(1)9()()()()16m m f y f y f y f y +-=-=． 由于(2)(0)45(2)16f y y -=-， 因此（8.4.18）式成立。

《最优化方法》1一、填空题:1. _______________________________________________________ 最优化问题的数学模型一般为：_____________________________________________ ,其中___________ 称为目标函数，___________ 称为约束函数，可行域D可以表示为_______________________________ ，若 ________________________________ ，称/为问题的局部最优解，若为问题的全局最优解。

2.设f(x)= 2斤+2“2-兀|+5花，则其梯度为__________ ^x = (l,2)r?6/ = (l,0)r,则f(x)在壬处沿方向d的一阶方向导数为___________ ，几何意义为_____________________________________ ，二阶方向导数为____________________ ,几何意义为_____________________________3.设严格凸二次规划形式为：min /(%) = 2兀］2 + 2x； - 2兀］-x2s.t. 2%! 4- x2 < 1> 0x2 > 0则其对偶规划为_______________________________________________min%（d ） = f （x k +ad k ）的最优步长为务=—叫）F.d kT Gd k2. （10分）证明凸规划min/（x ）,x G D （其中子（兀）为严格凸函数，D 是凸集）的最优解是唯一的3. （13分）考虑不等式约束问题min /（x ）s.t. c i （x ） < 0, Z G / = {1,2,…，加}其中/（x ）,6 （兀）a e /）具有连续的偏导数，设X 是约束问题的可行点，若在元处 d 满足巧（计<0,VC,（元）（可则d 是元处的可行下降方向。

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 =,其中 11231112341113451A ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦求)(A Cond ∞，并分析线性方程组是否病态 ? 2.迭代法例1. 设线性方程组b Ax =为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-----221221122321x x x ααα ， 0≠α写出求解线性方程组的Jacobi 迭代格式，并确定当α取何值时Jacobi 迭代格式收敛. 例 2. 写出求解线性方程组b Ax =的Seidel 迭代格式，并判断所写格式的收敛性，其中b Ax =为⎪⎩⎪⎨⎧=++-=+=-522826233213231x x xx x x x3.插值例 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 的计算格式5. 代数精度例 1. 数值求积公式形如)1()0()1()0()()(321010f A f A f A f A x S dx x xf '+'++=≈⎰试确定其中参数,,,,4321A A A A 使其代数精度尽量高, 并确定代数精度. 例 2. 验证数值求积公式20120()(1(1)(1f x dx A f A f A f ≈++⎰是Gauss 型求积公式.6．Romberg 方法 例 对积分⎰+1021dx x ，用Romberg 方法计算积分的近似值，误差不超过510-并将结果填7．证明（1）设)(x ϕ为],[b a 上关于权函数)(x ρ的n 次正交多项式，以)(x ϕ的零点为节点建立Lagrange 插值基函数)}({x l i ，证明：⎰⎰==b abai i ni dx x l x dx x l x ,,2,1,)]()[()()(2Λρρ证明: 设n 次正交多项式()x ϕ的零点为12,,n x x x L ，则以这n 个零点为节点建立的Lagrange 插值基函数{()},1,2,i l x i n =L 是n-1次多项式，[]2()i l x 是2n-2次多项式. 故当()f x 取()i l x 和[]2()i l x 时Gauss 型求积公式1()()()nb k k ak x f x dx A f x ρ=≈∑⎰等号成立, 即1()()()nb i k i k iak x l x dx A l x A ρ===∑⎰221()()()nb i k i k iak x l x dx A l x A ρ===∑⎰则有 ⎰⎰==b abai i ni dx x l x dx x l x ,,2,1,)]()[()()(2Λρρ（2）对线性方程组b Ax =，若A 是n 阶非奇异阵，0≠b ，*x 是b Ax =的精确解，x 是b Ax =的近似解。

天津大学《最优化方法》复习题（含答案）第一章 概述(包括凸规划)一、 判断与填空题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 Dx ∈的严格局部最优解. ⨯5 给定一个最优化问题，那么它的最优值是一个定值. √6 非空集合n R D ⊆为凸集当且仅当D 中任意两点连线段上任一点属于D . √7 非空集合nR 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 设{}kx 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为下降算法，则对{} ,2,1,0∈∀k ，恒有 )()(1k k x f x f ≤+ .13 算法迭代时的终止准则（写出三种）：_____________________________________。

14 凸规划的全体极小点组成的集合是凸集。

《最优化方法》复习题笫一章概述(包括凸规划)一、判断与填空题1arg max /(x) = arg m in7xeR n xeR n2max {/(x): x G D e /?" }= 一min {/(x): x e Z) o /?H} x3设f : D u RJ R.若疋wR”,对于一切xwR”恒有/(x*)</(x),W 弥 X 为最优化问题min /(兀)的全局最优解.xXG D4设f : D匚R" — R.若x* ,存在F的某邻域/.(/),使得对一切兀e 恒有/(%*)< f(x),则称T为最优化问题min fM的严格局部最XE D优解.X5给定一个最优化问题，那么它的最优值是一个定值.V6非空集合D c /?"为凸集当且仅当D中任意两点连线段上任一点属于D. V7非空集合D匸/?"为凸集当且仅当D中任意有限个点的凸组合仍属丁D. V 8任意两个凸集的并集为凸集.x9 函数f : D j R" T/?为凸集D上的凸函数当且仅当一/为D上的凹函数.V10设f : D u RJ R为凸集D上的可微凸函数，eD .则对Vx G D ,有fM -/(%*)< V/(x*)' (x -x*). x11若c(兀)是凹函数，则D = [x^R n\ c(x) > 0}是凸集。

V12设{*}为由求解min/(Q的算法A产牛的迭代序列，假设算法A为下降算法，xeD则对Pk e {0,1, 2,…}，恒有____ /(x,+1) < /(X,) _____________ .13算法迭代吋的终止准则（写出三种）： _____________________________ o 14凸规划的全休极小点组成的集合是凸集。

V15函数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非精确一维线性搜索的公式。

最优化⽅法试卷及答案5套.docx《最优化⽅法》1⼀、填空题:1. _______________________________________________________ 最优化问题的数学模型⼀般为：_____________________________________________ ,其中___________ 称为⽬标函数，___________ 称为约束函数，可⾏域D可以表⽰为_______________________________ ，若 ________________________________ ，称/为问题的局部最优解，若为问题的全局最优解。

2.设f(x)= 2⽄+2“2-兀|+5花，则其梯度为__________ ^x = (l,2)r?6/ = (l,0)r,则f(x)在壬处沿⽅向d的⼀阶⽅向导数为___________ ，⼏何意义为_____________________________________ ，⼆阶⽅向导数为____________________ ,⼏何意义为_____________________________3.设严格凸⼆次规划形式为：min /(%) = 2兀］2 + 2x； - 2兀］-x2s.t. 2%! 4- x2 < 1> 0x2 > 0则其对偶规划为_______________________________________________min%（d ） = f （x k +ad k ）的最优步长为务=—叫）F.d kT Gd k2. （10分）证明凸规划min/（x ）,x G D （其中⼦（兀）为严格凸函数，D 是凸集）的最优解是唯⼀的3. （13分）考虑不等式约束问题min /（x ）s.t. c i （x ） < 0, Z G / = {1,2,…，加}其中/（x ）,6 （兀）a e /）具有连续的偏导数，设X 是约束问题的可⾏点，若在元处 d 满⾜巧（计<0,VC,（元）（可则d 是元处的可⾏下降⽅向。

最优化方法考试试题一、选择题（每题2分，共20分）1、下列哪个选项不是最优化方法的常见应用场景？A.生产计划优化B.金融投资组合优化C.图像处理优化D.自然语言处理优化正确答案：D.自然语言处理优化。

2、下列哪个算法不是求解线性规划问题的常用算法？A.单纯形法B.内点法C.外点法D.牛顿法正确答案：D.牛顿法。

3、下列哪个选项不是整数规划问题的特点？A.变量取值必须是整数B.问题复杂度较高，通常需要特殊算法求解C.在实际应用中比线性规划更为广泛D.可以使用与线性规划相同的方法求解正确答案：D.可以使用与线性规划相同的方法求解。

4、下列哪个选项不是梯度下降法的优点？A.简单易行，易于实现B.能较快地收敛到局部最优解C.对初值不敏感，易于找到全局最优解D.对于大规模数据处理效率较高正确答案：C.对初值不敏感，易于找到全局最优解。

5、下列哪个选项不是模拟退火算法的特点？A.基于概率的搜索方法，有一定的随机性B.在解空间内随机搜索，可以跳出局部最优解的陷阱C.可以找到全局最优解，但需要设置退火温度等参数D.对于组合优化问题通常比暴力搜索算法更快找到最优解正确答案：D.对于组合优化问题通常比暴力搜索算法更快找到最优解。

二、填空题（每空2分，共20分）6.最优化方法中，通常使用__________来衡量一个解的好坏。

正确答案：目标函数。

7.在使用单纯形法求解线性规划问题时，__________是算法终止的条件。

正确答案：迭代次数达到预设的上限。

8.整数规划问题中，如果所有变量都有上限和下限的约束，则称为__________规划问题。

正确答案：背包。

9.在使用模拟退火算法求解组合优化问题时，__________是算法终止的条件。

正确答案：达到预定的迭代次数或者解的变化小于某个给定的阈值。

10.最优化方法中，__________是一种启发式搜索方法，通常用于解决组合优化问题。

正确答案：遗传算法。

最优化问题在现实世界中随处可见，从解决日常生活中的最佳路线问题，到企业寻求最大化利润和最小化成本，最优化方法都发挥着至关重要的作用。

练习题一1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。

2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。

答：针对一般优化模型()()min ()..0,1,2, 0,1,,i j f x s t g x i m h x j p≥===，讨论解的可行域D ，若存在一点*X D ∈，对于X D ∀∈ 均有*()()f X f X ≤则称*X 为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列(1)(2)(),,,K X X X ，满足(1)()()()K K f X f X +≤，则迭代法收敛；收敛的停止准则有(1)()k k x x ε+-<，(1)()()k k k x x x ε+-<，()()(1)()k k f x f x ε+-<，()()()(1)()()k k k f x f x f x ε+-<，()()k f x ε∇<等等。

练习题二1、某公司看中了例2.1中厂家所拥有的3种资源R 1、R2、和R 3，欲出价收购（可能用于生产附加值更高的产品）。

如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。

解：确定决策变量 对3种资源报价123,,y y y 作为本问题的决策变量。

确定目标函数 问题的目标很清楚——“收购价最小”。

确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。

因此有如下线性规划问题：123min 170100150w y y y =++1231231235210..23518,,0y y y s t y y y y y y ++≥⎧⎪++≥⎨⎪≥⎩ *2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。

答：略。

3、用单纯形法求解下列线性规划问题：（1）⎪⎪⎩⎪⎪⎨⎧≥≤+-≤++≤-++-=0,,43222..min32131321321321x x x x x x x x x x x t s x x x z ； （2）⎪⎪⎩⎪⎪⎨⎧=≥=++=+-=+-+-=)5,,2,1(052222..4min53243232132 i x x x x x x x x x x t s x x z i解：（1）引入松弛变量x 4，x 5，x 6123456min 0*0*0*z x x x x x x =-++++12341232 =22 5 =3..13 6=41,2,3,4,5,60x x x x x x x x s t x x x x x x x x x +-+⎧⎪+++⎪⎨-++⎪⎪≥⎩因检验数σ2<0，故确定x 2为换入非基变量，以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x 4作为换出的基变量。

附录5 《最优化方法》复习题1、设n n A R ⨯∈是对称矩阵，,n b R c R ∈∈，求1()2TT 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 TT Tdd 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 TTT T dd f x f x f x I f x d f x f x f x ∇∇=-∇--∇∇∇∇()()()()()T T T f x f x f x d f x f x =-∇∇+∇+∇∇ ()0T 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 =+时的情形．令11k i i i x x λ+==∑，其中,0,1,2,,1i i x S i k λ∈≥=+L ，且111k i i λ+==∑．不妨设11k λ+≠（不然1k x x S +=∈，结论成立），记111kii i k y x λλ=+=-∑，有111(1)k k k x y x λλ+++=-+，又1110,1,2,,,111ki ii k k i k λλλλ=++≥==--∑L ， 则由归纳假设知，y S ∈，而1k x S +∈，且S 是凸集，故x S ∈．5、设n R S ⊆为非空开凸集，R S f →:在S 上可微，证明：f 为S 上的凸函数的充要条件是2112112()()()(),,T f x f x f x x x x x S ≥+∇-∀∈．证明 必要性．设f 是S 上的凸函数，则12,x x S ∀∈及(0,1)λ∈，有2121((1))()(1)()f x x f x f x λλλλ+-≤+-，于是121121(())()()()f x x x f x f x f x λλ+--≤-，因S 为开集，f 在S 上可微，故令0λ+→，得12121()()()()T f x x x f x f x ∇-≤-，即2112112()()()(),,T f x f x f x x x x x S ≥+∇-∀∈．充分性．若有2112112()()()(),,T f x f x f x x x x x S ≥+∇-∀∈， 则[0,1]λ∀∈，取12(1)x x x S λλ=+-∈，从而11()()()()T f x f x f x x x ≥+∇-，22()()()()T f x f x f x x x ≥+∇-，将上述两式分别乘以λ和1λ-后，相加得1212()(1)()()()((1))T f x f x f x f x x x x λλλλ+-≥+∇+--12()((1))f x f x x λλ==+-，所以f 为凸函数．6、证明：凸规划min ()x Sf x ∈的任意局部最优解必是全局最优解．证明 用反证法．设x S ∈为凸规划问题min ()x Sf x ∈的局部最优解，即存在x 的某个δ邻域()N x δ，使()(),()f x f x x N x S δ≤∀∈I ．若x 不是全局最优解，则存在x S ∈%，使()()f xf x <%．由于()f x 为S 上的凸函数，因此(0,1)λ∀∈，有((1))()(1)()()f x x f x f x f x λλλλ+-≤+-<%%．当λ充分接近1时，可使(1)()x x N x S δλλ+-∈%I ，于是()((1))f x f x x λλ≤+-%，矛盾．从而x 是全局最优解．7、设n R S ⊆为非空凸集，R S f →:是具有一阶连续偏导数的凸函数，证明：x 是问题min ()x Sf x ∈的最优解的充要条件是：()()0,T f x x x x S ∇-≥∀∈．证明 必要性．若x 为问题min ()x Sf x ∈的最优解．反设存在x S ∈%，使得()()0T f x x x ∇-<%，则d x x =-%是函数()f x 在点x 处的下降方向，这与x 为问题min ()x Sf x ∈的最优解矛盾．故()()0,T f x x x x S ∇-≥∀∈．充分性．若()()0,T f x x x x S ∇-≥∀∈．反设存在x S ∈%，使得()()f xf x <%． (())()((1))()f x x x f x f x x f x λλλλλ+--+--=%%()(1)()()()()0((0,1)f x f x f x f x f x λλλλ+--≤=-<∀%%，因S 为凸集，f 在S 上可微，故令0λ+→，得()()()()0T f x x x f x f x ∇-≤-<%%，这与已知条件矛盾，故x 是问题min ()x Sf x ∈的最优解．8、设函数()f x 具有二阶连续偏导数，k x 是()f x 的极小点的第k 次近似，利用()f x 在点k x 处的二阶Taylor 展开式推导Newton 法的迭代公式为 211[()]()k k k k x x f x f x -+=-∇∇．证明 由于()f x 具有二阶连续偏导数，故21()()()()()()()()2T T k k k k k k f x x f x f x x x x x f x x x ϕ≈=+∇-+-∇-．且2()k f x ∇是对称矩阵，因此()x ϕ是二次函数．为求()x ϕ的极小点，可令()0x ϕ∇=，即2()()()0k k k f x f x x x ∇+∇-=，若2()k f x ∇正定，则上式解出的()x ϕ的平稳点就是()x ϕ的极小点，以它作为()f x 的极小点的第1k +次近似，记为1k x +，即211[()]()k k k k x x f x f x -+=-∇∇，这就得到了Newton 法的迭代公式.9、叙述常用优化算法的迭代公式．（1）0.618法的迭代公式：(1)(),().k k k k kk k k a b a a b a λτμτ=+--⎧⎨=+-⎩（2）Fibonacci 法的迭代公式：111(),(1,2,,1)()n k kk 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()()k k k k t t t t ϕϕ+'=-''． （4）最速下降法用于问题1min ()2TT f x x Qx b x c =++的迭代公式： 1()()()()()T k k k k k Tk k f x f x x x f x f x Q f x +∇∇=-∇∇∇ （5）Newton 法的迭代公式：211[()]()k k k k x x f x f x -+=-∇∇． （6）共轭方向法用于问题1min ()2TT f x x Qx b x c =++的迭代公式： 1()T k kk k k Tk kf x d x x d d Qd +∇=-． 10、已知线性规划：123123123123123min ()2;360,2210,20,,,0.f x x x x x x x x x x x x x x x x =-+⎧⎪++≤⎪⎪-+≤⎨⎪+-≤⎪⎪≥⎩s.t. （1）用单纯形法求解该线性规划问题的最优解和最优值； （2）写出线性规划的对偶问题； （3）求解对偶问题的最优解和最优值．解 （1）引进变量456,,x x x ，将给定的线性规划问题化为标准形式：123123412351236126min ()2;..360,2210,20,,,,0.f x x x x s t x x x x x x x x x x x x x x x =-+⎧⎪+++=⎪⎪-++=⎨⎪+-+=⎪⎪≥⎩L所给问题的最优解为(0,20,0)T x =，最优值为20f =-． （2）所给问题的对偶问题为：123123123123123max ()601020;..32,21,21,,,0.g y y y y s t y y y y y y y y y y y y =---⎧⎪---≤⎪⎪-+-≤-⎨⎪--+≤⎪⎪≥⎩（1） （3）将上述问题化成如下等价问题：123123123123123min ()601020;..32,21,21,,,0.h y y y y s t y y y y y y y y y y y y =++⎧⎪---≤⎪⎪-+-≤-⎨⎪--+≤⎪⎪≥⎩引进变量456,,y y y ，将上述问题化为标准形式：123123412351236126min ()601020;..32,21,21,,,,0.h y y y y s t y y y y y y y y y y y y y y y =++⎧⎪---+=⎪⎪-+-+=-⎨⎪--++=⎪⎪≥⎩L （2）问题（2）的最优解为(0,0,1)T y =，最优值为20h =（最小值）． 问题（1）的最优解为(0,0,1)T y =，最优值为20g =-（最大值）．11、用0.618法求解 2min ()(3)t t ϕ=-，要求缩短后的区间长度不超过0.2，初始区间取[0,10]． 解 第一次迭代： 取11[,][0,10],0.2a b ε==． 确定最初试探点11,λμ分别为11110.382() 3.82a b a λ=+-=，11110.618() 6.18a b a μ=+-=．求目标函数值：21()(3.823)0.67ϕλ=-=，21()(6.183)10.11ϕμ=-=． 比较目标函数值：11()()ϕλϕμ<．比较11 6.1800.2a με-=->=． 第二次迭代：212121210, 6.18, 3.82,()()0.67a a b μμλϕμϕλ========．2222220.382()0.382(6.180) 2.36,()(2.363)0.4a b a λϕλ=+-=-==-=．2222()(), 3.82a ϕλϕμμε<-=>． 第三次迭代：323232320, 3.82, 2.36,()()0.4a a b μμλϕμϕλ========．2333330.382()0.382(3.820) 1.46,()(1.463) 2.37a b a λϕλ=+-=-==-=．3333()(), 3.82 1.46b ϕλϕμλε>-=->． 第四次迭代：434343431.46, 3.82, 2.36,()()0.4a b b λλμϕλϕμ========．444440.618() 1.460.0.618(3.82 1.46) 2.918,()0.0067a b a μϕμ=+-=+-==． 4444()(), 3.82 2.36b ϕλϕμλε>-=->． 第五次迭代：545454542.36, 3.82, 2.918,()()0.0067a b b λλμϕλϕμ========．555550.618() 3.262,()0.0686a b a μϕμ=+-==． 5555()(), 3.262 2.36a ϕλϕμμε<-=->． 第六次迭代：656565652.36, 3.262, 2.918,()()0.0067a a b μμλϕμϕλ========．666660.382() 2.7045,()0.087a b a λϕλ=+-==．6666()(), 3.262 2.7045b ϕλϕμλε>-=->． 第七次迭代：767676762.7045, 3.262, 2.918,()()0.0067a b b λλμϕλϕμ========．777770.618() 3.049,()0.002a b a μϕμ=+-==．7777()(),b ϕλϕμλε>->． 第八次迭代：878787872.918, 3.262, 3.049,()()0.002a b b λλμϕλϕμ========．888880.618() 3.131,()0.017a b a μϕμ=+-==． 8888()(),a ϕλϕμμε<->． 第九次迭代：989899982.918, 3.131, 3.049,()()0.002a a b μμλϕμϕλ========．999990.382() 2.999,()0.000001a b a λϕλ=+-==． 9999()(), 3.049 2.918a ϕλϕμμε<-=-<． 故993.0242x λμ+==．12、用最速下降法求解 22112212min ()2243f x x x x x x x =++--，取(0)(1,1)T x =，迭代两次．解 1212()(224,243)T f x x x x x ∇=+-+-，将()f x 写成1()2T Tf x x Qx b x =+的形式，则224,243Q b -⎛⎫⎛⎫== ⎪ ⎪-⎝⎭⎝⎭．第一次迭代：(0)(0)(1)(0)(0)(0)(0)()()()()()T T f x f x xxf x f x Q f x ∇∇=-∇∇∇ 0(0,3)1013220131/4(0,3)243⎛⎫ ⎪⎛⎫⎛⎫⎛⎫⎝⎭=-= ⎪ ⎪ ⎪⎛⎫⎛⎫⎝⎭⎝⎭⎝⎭⎪⎪⎝⎭⎝⎭． 第二次迭代：(1)(1)(2)(1)(1)(1)(1)()()()()()T T f x f x xx f x f x Q f x ∇∇=-∇∇∇3/2(3/2,0)13/27/40223/21/401/4(3/2,0)240-⎛⎫- ⎪-⎛⎫⎛⎫⎛⎫⎝⎭=-= ⎪ ⎪ ⎪-⎛⎫⎛⎫⎝⎭⎝⎭⎝⎭- ⎪⎪⎝⎭⎝⎭． 13、用FR 共轭梯度法求解222123123123min ()()()()f x x x x x x x x x x =-++-++++-，取(0)11(,1,)22T x =，迭代两次．若给定0.01,ε=判定是否还需进行迭代计算． 解 222123121323()3()2()f x x x x x x x x x x =++-++，再写成1()2T f x x Gx =，622262226G --⎛⎫⎪=-- ⎪ ⎪--⎝⎭，()f x Gx ∇=．第一次迭代：(0)()(0,4,0)T f x ∇=，令(0)0()(0,4,0)T d f x =-∇=-，从(0)x 出发，沿0d 进行一维搜索，即求(0)200min ()21648f x d λλλλ≥+=-+的最优解，得(1)(0)0001/6,(1/2,1/3,1/2)T x x d λλ==+=．第一次迭代：(1)()(4/3,0,4/3)T f x ∇=．2(1)02(0)()29()f x f x α∇==∇， (1)100()(4/3,8/9,4/3)T d f x d α=-∇+=---．从(1)x 出发，沿1d 进行一维搜索，即求(1)10142362214181418min ()(,,)262233923392261423f x d λλλλλλλλ≥⎛⎫- ⎪--⎛⎫ ⎪⎪⎪+=------ ⎪ ⎪ ⎪-- ⎪⎝⎭ ⎪- ⎪⎝⎭的最优解，得(2)(1)1111/24/333,1/38/9(0,0,0)881/24/3Tx x d λλ-⎛⎫⎛⎫⎪ ⎪==+=+-= ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭． 此时(2)(2)()(0,0,0),()00.01T f x f x ε∇=∇=<=．得问题的最优解为(0,0,0)T x =，无需再进行迭代计算．14、用坐标轮换法求解 2212112min ()242f x x x x x x =+--，取(0)(1,1)T x =，迭代一步．解 从点(0)(1,1)T x =出发，沿1(1,0)T e =进行一维搜索， 即求(0)210min ()43f x e λλλλ≥+=--的最优解，得(1)(0)0012,(3,1)T x x e λλ==+=．再从点(1)x 出发，沿2(0,1)T e =进行一维搜索， 即求(1)220min ()227f x e λλλλ≥+=--的最优解，得(2)(1)1121/2,(3,3/2)T x x e λλ==+=．15、用Powell 法求解2212112min ()3f x x x x x x =+--，取(0)(0,0)T x =，初始搜索方向组01(0,1),(1,0)T T d d ==，给定允许误差0.1ε=（迭代两次）． 解 第一次迭代：令(0)(0)(0,0)T y x ==，从点(0)y 出发沿0d 进行一维搜索，易得(1)(0)0000,(0,0)T y y d λλ==+=；接着从点(1)y 出发沿1d 进行一维搜索，得(2)(1)11133,(,0)22T y y d λλ==+=由此有加速方向 (2)(0)23(,0)2T d y y =-=．因为23/2d ε=>，所以要确定调整方向．由于 (0)(1)(2)9()0,()0,()4f y f y f y ===-，按（8.4.17）式有(1)(2)()(1)()()max{()()|0,1}j j f y f y f y f y j +-=-=，因此1m =，并且()(1)(1)(2)9()()()()4m m f y f y f y f y +-=-=． 又因(2)(0)(2)0f y y -=，故（8.4.18）式不成立．于是，不调整搜索方向组，并令(1)(2)3(,0)2T x y ==．第二次迭代：取(0)(1)3(,0)2T y x ==，从点(0)y 出发沿0d 作一维搜索，得(1)(0)000333,(,)424T y y d λλ==+=．接着从点(1)y 出发沿方向1d 作一维搜索，得(2)(1)1113153,(,)884Ty y d λλ==+=． 由此有加速方向(2)(0)233(,)84T d y y =-=．因为2d ε=>，所以要确定调整方向．因(0)(1)(2)945189(),(),()41664f y f y f y =-=-=-， 故按（8.4.17）式易知0m =，并且()(1)(0)(1)9()()()()16m m f y f y f y f y +-=-=． 由于(2)(0)45(2)16f y y -=-， 因此（8.4.18）式成立。

最优化考试题及答案一、单项选择题（每题2分，共10题，满分20分）1. 最优化问题中，目标函数表示的是：A. 需要最小化或最大化的量B. 约束条件C. 决策变量D. 算法步骤答案：A2. 在线性规划问题中，以下哪项不是基本解？A. 基本可行解B. 非基本可行解C. 基本解D. 退化解答案：B3. 单纯形法中，如果目标函数的某一项系数为负，则该项对应的变量：A. 必须取非负值B. 必须取正值C. 可以取任意值D. 必须取零答案：D4. 以下哪个算法不是用于解决整数规划问题？A. 分支定界法B. 动态规划C. 单纯形法D. 割平面法答案：C5. 在非线性规划中，以下哪个条件是局部最优解的必要条件？A. 目标函数的梯度为零B. 目标函数的Hessian矩阵正定C. 目标函数的Hessian矩阵负定D. 目标函数的Hessian矩阵半正定答案：A6. 以下哪个算法是用于解决动态规划问题的？A. 梯度下降法B. 牛顿法C. 贝尔曼方程D. 遗传算法答案：C7. 在多目标优化问题中，以下哪个概念用于描述解的优劣？A. 可行解B. 帕累托最优解C. 基本解D. 退化解答案：B8. 以下哪个算法是用于解决大规模最优化问题的？A. 梯度下降法B. 牛顿法C. 共轭梯度法D. 内点法答案：D9. 在约束优化问题中，拉格朗日乘数法用于：A. 寻找最优解B. 寻找可行解C. 寻找鞍点D. 寻找局部最小值答案：A10. 以下哪个算法是用于解决组合优化问题的？A. 模拟退火算法B. 遗传算法C. 粒子群优化算法D. 所有上述算法答案：D二、多项选择题（每题3分，共5题，满分15分）1. 在最优化问题中，以下哪些是常见的目标函数？A. 最小化成本B. 最大化利润C. 最小化时间D. 最大化面积答案：ABCD2. 以下哪些是线性规划问题的特点？A. 目标函数是线性的B. 约束条件是线性的C. 目标函数是二次的D. 约束条件是非线性的答案：AB3. 在非线性规划问题中，以下哪些是全局最优解的必要条件？A. 目标函数的梯度为零B. 目标函数的Hessian矩阵正定C. 目标函数的Hessian矩阵负定D. 目标函数的Hessian矩阵半正定答案：AB4. 以下哪些算法是用于解决多目标优化问题的？A. 权重法B. 帕累托前沿法C. 目标规划法D. 动态规划法答案：ABC5. 以下哪些是组合优化问题的特点？A. 决策变量是离散的B. 目标函数是线性的C. 约束条件是非线性的D. 问题规模通常很大答案：ACD三、简答题（每题5分，共2题，满分10分）1. 请简述拉格朗日乘数法在最优化问题中的应用。

天津大学《最优化方法》复习题(含答案)天津大学《最优化方法》复习题（含答案）第一章 概述(包括凸规划)一、 判断与填空题1 )].([arg)(arg min maxx f x f n nR x Rx -=∈∈ √2 {}{}.:)(m in :)(m ax nnR D x x f R D x x f ⊆∈-=⊆∈ ⨯ 3 设.:R R D f n →⊆ 若nR x∈*，对于一切nR x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题)(minx f Dx ∈的全局最优解. ⨯4 设.:R RD f n→⊆ 若Dx∈*，存在*x 的某邻域)(*x Nε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(minx f Dx ∈的严格局部最优解. ⨯5 给定一个最优化问题，那么它的最优值是一个定值. √6 非空集合nR D ⊆为凸集当且仅当D 中任意两点连线段上任一点属于D . √7 非空集合nR D ⊆为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √8 任意两个凸集的并集为凸集. ⨯ 9 函数RR D f n→⊆:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √10 设RRD f n→⊆:为凸集D 上的可微凸函数，Dx ∈*.则对D x ∈∀，有).()()()(***-∇≤-x x x f x f x f T⨯ 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n是凸集。

√12 设{}kx 为由求解)(minx f Dx ∈的算法A 产生的迭代序列，假设算法A 为下降算法，则对{}Λ,2,1,0∈∀k ，恒有)()(1kk x f x f ≤+ .13 算法迭代时的终止准则（写出三种）：_____________________________________。

14 凸规划的全体极小点组成的集合是凸集。