天津大学-研究生-最优化方法复习题.docx

《最优化方法》复习题第一章概述(包括凸规划)一、判断与填空题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.1模型无约束最优化问题 min /（x ）, x =（旺,兀2,…心）'w R"・A约束最优化问题疋简（兀）》0,心1,2,・・・,加也（兀）=0,丿=1,2,・・・,"） min /（x ）;s.t. gQ ）nO,i = l,2,…，加，hj （x ） = 0,j = \,2,・・・,l ・其中.f （X ）称为目标函数，西,兀2,…，暫称为决策变量，S 称为可行域，gQ ） no （心1,2,…,加）,勺（兀） = 0。

= 1,2,…丿）称为约束条件. §1. 2多元函数的梯度、Hesse 矩阵及Tayloi •公式定义设f:R“TR,J^R“・如果％维向量〃，VAre R n,有+ Ax) -f(x) = p T\x + 0(||Ax||)・则称/（x ）在点元处町微，并称df （x ） = p T\x 为/（x ）在点元处的微分.如果/（X ）在点元处对丁」=（兀“2，・・・,£）丁的各分量的偏导数。

/(元)d x i都存在，则称/（兀）在点元处一阶可导，并称向量为/（兀）在点元处一阶导数或梯度.定理1设f :R n^R,xeR n・如果/（兀）在点元处可微,则/（兀）在点元处梯度V/(x)存在，并且有#(x) = W)7'Ar .定义 设f:R"TR,J^R“・d 是给定的n 维非零向量，e = 2・如杲 dmin /(兀)；即 vS.t. X G S.V/(x)=(df(x)T。

/（可。

/（元）Um /a + 2e ）-V （x ）久TO2存在，则称此极限为/（x ）在点元沿方向d 的方向导数，记作冬学.da定理2设f :R n^R,xeR n.如果/（兀）在点元处可微,则/（兀）在点元处沿任何非零方向d 的方向导数存在，且= VA 元）。

,其中丘=厶~・daa定义 设/（兀）是/?"上的连续函数，xeR n. d 是〃维非零向量.如果3^＞0,使得V2w （O0）,有/（x + 2J ）＜ （＞） /（x ）.则称d 为f （兀）在点元处的下降（上 升）方向.定理3设f:R n^R.xeR n,且/（兀）在点元处可微,如果日非零向量de R n9 使得Vf （x ）Td ＜ （＞） 0,则d 是/（兀）在点元处的下降（上升）方向.定义 设f:R”TR,HeR”・如果/（兀）在点元处对丁自变量x = （x p x 2,---,x /J ）7'的 各分量的二阶偏导数£単匕丿・=1,2,…,）都存在，则称函数/（兀）在点元处二阶 U Xj 可导，并称矩阵为/（x ）在点元处的二阶导数矩阵或Hesse 矩阵.定义 设h:R" 记/1（兀）=（肉（兀）,爲（兀）,・・・,饥（兀））7',如果勺• （x ） （i = 1,2,…，加）在点元处对于自变量x =（兀］,吃,…£）丁的各分量的偏导数d 2x } 扌/（元） dx }dx 2 巧(元) d 2f(x) 3 x 2d• d 2x 2• d x^d x n L n• •■d 2f(x) ■97(^) • •d 2f(x)d x n d X] d x n d x 2d 2f(x)V 2/(x)丿号⑴(i = 1,2,…，加;J = 1,2,…加 dx f都存在，则称向量函数加对在点元处是一阶可导的，并且称矩阵为/?（%）在点x 处的一阶导数矩阵或Jacobi 矩阵,例2 设aw R",xw R",bw R ,求f （x ） = a Tx-{-h 在任意点兀处的梯度和Hesse 矩阵.解 设0 =（绚卫2，・・・,％）/,兀=（旺,兀2，・・・,£）‘，则/（兀）=工绞母+b ,k=\因。

硕士研究生最优化复习题硕士研究生最优化复习题1.线性规划问题CX z =min ,0,≥=X b AX 其可行域为R ，最优目标函数值为z ，若分别发生下列情形之一时，其新的可行域为R *，新的最优目标函数值为z *，试分别写出下列三个问题中R 与R *及z 与z *之间的关系：（1）增添一个新的约束条件。

（2）减少一个原有的约束条件。

（3）目标函数变为λCXz =min ，同时约束条件方程变为1,0,>≥=λλX b AX 。

2.线性规划问题CX z =min ，0,≥=X b AX ，设X （0）为问题的最优解，若目标函数中用C *代替C 后，问题的最优解变为X *，求证：(C *-C )(X *-X （0）)≤03.若线性规划问题min z =CX ,AX ＝b, X ≥0具有最优解，试应用对偶理论证明下述线性规划问题min z =CX ,AX ＝d, X ≥0不可能具有无界解，d 可以是取任意值的向量。

4.试将图所示的求v 1到v 7点的最短路问题归结为求整数规划问题（建立整数规划模型），具体说明模型中变量、目标函数和约束条件的含义。

v 2 1 v 539 2 2v 1 5 v 4 4 v 7 8 38 4v 3 v 65．已知线性规划问题min Z=2x 1-x 2 +2x 3≥≤≤-+=++无约束 3 213 213 21x ,0x 0,x 6x x x - 4x x x -k 其最优解为x 1 = -5, x 2 =0, x 3 =-1（1）求k 的值。

（2）写出并求其对偶问题的最优解。

6.某公司要建立一线性规划模型，此模型受约束条件1或约束条件2约束。

如果满足约束条件1，必须同时满足另外p 1个约束条件中的k 1个(k 1 < p 1)约束；如果满足约束条件2，必须同时满足另外p 2个约束条件中的k 2个(k 2 < p 2)约束；要求建立整数规划的约束条件，满足上述要求。

《最优化方法》期末考试练习题声明：仅供复习时参考。

实际考试题型类似，题量小于本练习。

一. 选择题：略第一题主要考察基本概念、定理，算法的基本思想和matlab 命令。

二.简答题1． 写出线性规划问题;0, ,94 3 ,5 32 4 s.t. ,823 max 21321321321≥≥-+-≥+-+-x x x x x x x x x x x 的对偶规划。

2．如果求解某整数规划问题的松弛问题得到如下的最优单纯形表：求以1x ，2x 为源行生成的割平面方程。

3．在区间[0，3]上用黄金分割法求函数12)(3+-=t t t ϕ的极小点，只要求求出 初始的迭代点和保留区间及此时的近似最优解。

4． 用tx ex y 21-=拟合下列数据1.0,24.0,11,07.2,1=======-=y t y t y t y t写出非线性最小二乘问题三.计算题1．分别用最速下降方法和修正的牛顿法求解无约束问题 22214)(min x x x f +=。

取初始点()()Tx2,21=，.1.0=ε2．讨论约束极值问题⎪⎪⎩⎪⎪⎨⎧≥≥≤-≤++--+=0004..866)(min212121212221x x x x x x t s x x x x x f 的Kuhn-Tucker 点。

3．用外点法（外部惩罚函数法）求解2s.t.)3()1()(min 212221≤-+-+-=x x x x x f4．用内点法求解非线性规划03)( 03)( s.t. 296)(min 22112121≥-=≥-=++-=x x g x x g x x x x f5.用乘子法求解1s.t.6121)(min 212221=++=x x x x x f 6．用表格单纯形法求解线性规划⎪⎪⎩⎪⎪⎨⎧≥≥-≥-≤++++=0,,34623max 3213231321321x x x x x x x x x x x x x Z并根据最优单纯形表格写出该线性规划的最优基和最优基的逆。

理学院2010级研究生《最优化理论与方法》试题
1. （15分）设函数4:f R R →定义为
()
()()()()22441234231410510210f x x x x x x x x x =++-+-+- 证明：()*0
000T x =是f 的驻点（稳定点），并且*x 是f 在4R 上的严格全局
极小点。

2. （15分）叙述并证明满足wolfe 线搜索条件的下降算法的全局收敛性。

（提示：利用Zoutendijk 条件）
3. （20分）叙述修正的(Modified)Cholesky 分解算法。

用Cholesky 分解强迫
201
1211103231A -⎡⎤⎢⎥=+⎢
⎥⎢⎥⎣⎦正定，即令A A E =+正定，其中E 为修正矩阵。

4. （15分）设()f x =x b Ax x T T -，其中213,123A b ⎛⎫⎛⎫== ⎪ ⎪⎝⎭⎝⎭
（1） 证明010d ⎛⎫= ⎪⎝⎭与112d -⎛⎫= ⎪⎝⎭
关于A 共轭 （2） ()00
0T x =，以0d 和1d 为搜索方向，用精确线搜索求f 的极小点 5. （15分）叙述并证明牛顿法及其二次收敛性
6. （20分）写出拟牛顿法的一般步骤，叙述几种常用的拟牛顿校正公式，包括（SR1，DFP ，BFGS ，Broyden 族，Huang 族）。

天津大学《最优化方法》复习题(含答案)第一章 概述(包括凸规划)一、 判断与填空题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,。

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 =的近似解。

《最优化方法》复习题笫一章概述(包括凸规划)一、判断与填空题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非精确一维线性搜索的公式。

《最优化方法》1一、填空题：1 •最优化问题的数学模型一般为：_____________________________ ,其中___________ 为目标函数， _____________ 为约束函数，可行域D可以表示为 _______________________________ ，若 _______________________________ ，称x*为问题的局部最优解，若 _________________________________________ 称X*为问题的全局最优解。

2 •设f(x)= 2x1 2x1X2 X i 5X2 ,则其梯度为_______________________ ,海色矩阵___________ ,令x (1,2)T,d (1,0)T,则f(x)在x处沿方向d的一阶方向导数为___________ 几何意义为________________________________________ 二阶方向导数为 ____________________ ,几何意义为_____________________________3 •设严格凸二次规划形式为：min f (x) 2x； 2x| 2x1x2s.t. 2x1x21x10x20则其对偶规划为4•求解无约束最优化问题：min f(x), x R n，设x k是不满足最优性条件的第k 步迭代点，则:用最速下降法求解时，搜索方向d k= ___________用Newton法求解时，搜索方向d k= ____________用共轭梯度法求解时，搜索方向 d k= ________________二.(10分)简答题：试设计求解无约束优化问题的一般下降算法。

三.(25分)计算题1. (10分)用一阶必要和充分条件求解如下无约束优化问题的最优解：3 2min f (x) 2x! 3为6x^2(^ x21).2. ( 15分)用约束问题局部解的一阶必要条件和二阶充分条件求约束问题:min f (x) x1x22 2s.t. c(x) % X2 1 0的最优解和相应的乘子。

《最优化方法》（研究生）期末考试练习题答案二.简答题1．;0, ,843 ,2 2-,3 34 s.t. ,95- min 2121212121≤=--≥+≥++y y y y y y y y y y 2．,065 6143≥+x x （以1x 为源行生成的割平面方程） 注意：在1x 为整数的情况下，因为3x ,04≥x ，该方程自然满足，这是割平面的退化情形,2141 41 43≥+x x （以2x 为源行生成的割平面方程）3．6648.31854.1*2)854.1()(2131.01146.1*2)146.1()(854.13*618.00)(618.0146.13*382.00)(382.03,031311111111111=+-==+-==+=-+==+=-+===μϕλϕμλa b a a b a b a 0.927.21.8540]1.8540[854.1,0)()(,*2211=+===≤x b a 近似的最优解：。

，初始的保留区间为即：。

所以，不经计算也可以看出事实上μϕλϕ4．令1.01.0)(4.04.0)(11)(7.27.2)(222222221)2(*111)1(*111)0(*121)1(*11-=-=-=-=-=-=-=-=-------x x x x x x x e x e x x f ex ex x f x e x x f e x e x x f拟合问题等价于求解下列最小二乘问题：∑=412))((mini ix f三.计算题1．分别用最速下降方法和修正的牛顿法求解无约束问题 22214)(min x x x f +=。

取初始点()()Tx 2,21=，.1.0=ε()().1641642,2821121⎪⎪⎭⎫⎝⎛--=⎪⎪⎭⎫⎝⎛=∇=⎪⎪⎭⎫⎝⎛=∇d f x x x f T方向为：从而最速下降法的搜索，在初始点，解：()()()()直至满足精度。

继续迭代方向为：从而最速下降法的搜索，，在从而求解得到：其中满足最优步长,.48/6565/19248/65-65/19265/6,65/96)65/6,65/96((-4,-16)*130/172,2 130,/17.)162(4)42()162,42()()(min )(122221)1(1)1(1*)1(*⎪⎪⎭⎫⎝⎛-=⎪⎪⎭⎫ ⎝⎛=∇-=-=+==-+-=--=++=+d f x x f d x f d x f d x f TTT Tλλλλλλλλλλ()()2-2- 1648/1002/1 8/1002/1,8002 2,21111⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛-=∇-=⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛==--f G d G G x T索方向为：从而修正的牛顿法的搜，在初始点()()()()即为所求的极小点。

最优化理论与方法知识点总结最优化理论与方法知识点总结 (1)一、最优化简介： (2)1.1最优化应用举例 (2)1.2基本概念 (2)1.3向量范数 (3)1.4矩阵范数 (3)1.5极限的定义 (3)1.6方向导数存在性和计算公式 (4)1.7梯度定义 (4)1.8海塞矩阵 (5)1.9泰勒展开式： (5)1.10凸集定义 (5)1.11凸集性质 (5)1.12凸函数定义 (6)1.13凸函数判断 (6)1.14矩阵正定与半正定判断 (6)1.15例题（判断矩阵是否正定） (7)1.16凸优化 (7)二、线性规划 (7)2.1线性规划数学模型的一般形式 (7)2.2解的基本定理 (7)2.3解的分类 (8)2.4图解法 (8)2.5例题（图解法） (8)2.6标准型的化法 (9)2.7例题（化为标准型） (9)2.8单纯形法 (10)2.9例题（单纯形法） (11)三、对偶线性规划 (13)3.1对偶问题 (13)3.2单纯形法解对偶问题 (13)3.3对偶单纯形法求解线性规划问题过程 (14)四、无约束优化 (14)4.1无约束优化概述 (14)4.2搜索区间的确定 (15)4.3区间消去法原理 (16)4.4黄金分割法 (17)4.5插值方法 (17)4.6常见的终止准则 (19)4.7最速下降法 (20)4.8牛顿类方法 (20)4.9例题（牛顿类方法） (21)一、最优化简介：1.1最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，ad hoc等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSI etc.排版1.2基本概念目标函数和约束函数都是线性的，称之为线性规划问题，而有的模型中含有非线性函数，称之为非线性规划。

在线性与非线性规划中，满足约束条件的点称为可行点，全体可行点组成的集合称为可行集或可行域。

最优化方法复习题一、填空题1、 设XeD ，peR"，其 35〉0,对 V6ze(0,5),都冇向 S X+6Q?均在 Z)内部，则称/? 为点X 处的-•个 ____________ 方向。

2、 ____________ 函数是Matlab 主要的求解0-1规划的蚋数。

3、 表上作业法是 ____________ 在求解运输问题时的一种简化方法，其实质是单纯形法。

4、 牛顿法的逸代公式为；^+1)= X[▽2/(X (A ”)]_1V/(?^))，而拟牛顿法的迭代公式 为 ____________________________,其中仏是Hesse 近似的正定对称阵。

5、 对于约束非线性规划问题一类重要的求解方法就足通过解一系列无约束非线性规划问题 以获取原非线性约束问题解的 __________ 方法，它包括外(二次)罚函数法和内(内 点障碍)罚函数法。

6、 0-1背包问题用动态规划求解时，K 体积的状态转移方程为&二s k+i -a k x k 质量的状，态转移方程为 ______________________ O8、 _______________________________________ 多目标规划问题(VP)的最优解一定是 解，有效解一定是弱奋效解，即R ，R P ，R 、、P 。

9、 评价函数方法是处理多目标规划问题的主要方法之一，其基本思想足利用评价函数化多目标规划为 __________ 规划。

10、 ________________________________________________________MATLAB 川于求解多目标优化问题的函数有两个： __________________________________和fgoalattain 。

则称迭代过程是 ___________ 收敛的。

12、 若存在 X 、D 与 X’ 的一个邻域 N S (X 、= {XeR n |||X-X*||< S} (<5>0 为实数), 使得对VX e )门D 都有f(X')< /(X),则称X*是非线性规划问题的 蛣优解。

最优化考试题及答案一、单项选择题（每题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 凸规划的全体极小点组成的集合是凸集。