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

1、12345678910111213最优化方法复习题第一章 概述(包括凸规划)判断与填空题argmaxf(x)=arg minX rzRmax(x): x ：二 D _ Rn ： - - min ' f (x): x ：二 DRn:设f : DRn > R.若x： Rn，对于一切Rn恒有f(x”)f(x)，则称x为最优化问题mWf (x)的全局最优解设f : D二Rn > R.若x” D，存在X”的某邻域N (x ),使得对一切minf (x)的严格局部最xN (x )恒有f(x”)： f (x)，则称x”为最优化问题优解给定一个最优化问题，那么它的最优值是一个定值 V非空集

2、合DRn为凸集当且仅当D中任意两点连线段上任一点属于D. V非空集合DRn为凸集当且仅当D中任意有限个点的凸组合仍属于D. V任意两个凸集的并集为凸集.函数f:DRn > R为凸集D上的凸函数当且仅当 -f为D上的凹函数. V设f : D Rn > R为凸集D上的可微凸函数，X： D .则对D ,有 f(X)- f(x )乞 I f (x )T(x -x ).若c(x)是凹函数，则 D二xRn c(x)0是凸集。 V设"x*为由求解minx：-Df (x)的算法A产生的迭代序列，假设算法A为下降算法,则对k0,1,2,i恒有f(xk乞 f (xk).算法迭代时的终止准则(

3、写出三种)14凸规划的全体极小点组成的集合是凸集。15函数f : D Rn > R在点xk沿着迭代方向dk Rn C进行精确一维线搜索的步长:k，则其搜索公式为16函数f : DRn > R在点xk沿着迭代方向d Rn 0进行精确一维线搜索的步长:-k，则 i f （x '-.d ） d =0.17设dk Rn 0为点xk DRn处关于区域D的一个下降方向，则对于kk_ >0，二* 三（0, 丁）使得 x hid - D.、简述题1写出Wolfe-Powell非精确一维线性搜索的公式。2怎样判断一个函数是否为凸函数.（例如：判断函数f （x）2X1X2 2x； -10

4、X1 5X2是否为凸函数）三、证明题1证明一个优化问题是否为凸规划.（例如1 Ttmin f （x）x Gx c x b2判断s.t. Ax =b（其中G是正定矩阵）是凸规划x _02熟练掌握凸规划的性质及其证明.第二章线性规划考虑线性规划问题：(LP)min cTxs.t. Ax = b, x _0,其中，Rn, A Rm n, b Rm为给定的数据，且ran kA = m, m空n.一、判断与选择题1 (LP)的基解个数是有限的. V2若(LP)有最优解，则它一定有基可行解为最优解. V3 (LP)的解集是凸的.V4对于标准型的(LP)，设乂“由单纯形算法产生，则对 匕0,1,2，有T k

5、 T k 1、/c x c x . x*t *T *5若x为(LP)的最优解，y为(DP)的可行解，则c x _b y . V6设x。是线性规划(LP)对应的基B = (R,，Pm)的基可行解，与基变量为，xm对应的规范式中，若存在 二k ”：0，则线性规划(LP)没有最优解。X7求解线性规划(LP)的初始基可行解的方法：8对于线性规划(LP)，每次迭代都会使目标函数值下降.X简述题1将以下线性规划问题化为标准型：max f(x)-2x2 3x3s.t.捲 x2 x3 _ 6,2x2 4x3 亠 12,xi - x2* X3 一 2,X2 _ 0, X3 _ 0.2写出以下线性规划的对偶线性规

6、划:max f(x) =3为 2x2 x3 4x4s.t. 2x4x2 3x3 x4 =6, -2x4x2 3x3 x4 _ 3,Xi, X2, X3, X4 0.M法及二阶段三、计算题法）. 见书本：例 2.5.1例 2.6.1例 2.6.2熟练掌握利用单纯形表求解线性规划问题的方法（包括大（利用单纯形表求解）；（利用大M法求解）; （利用二阶段法求解）.四、证明题熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用 对偶理论证明相关结论。、判断与选择题设G Rn n为正定矩阵，则关于G共轭的任意n - 1向量必线性相关.V 在牛顿法中，每次的迭代方向都是下降方向 X 经典New

7、ton法在相继两次迭代中的迭代方向是正交的.XPRP共轭梯度法与BFGS算法都属于Broyden族拟Newton算法.X用DFP算法求解正定二次函数的无约束极小化问题，则算法中产生的迭 代方向一定线性无关 VFR共轭梯度法、PRP共轭梯度法、DFP算法、及BFGS算法均具有二次 收敛性.X共轭梯度法、共轭方向法、DFP算法以及BFGS算法都具有二次终止性.V函数f :Rn > R在xk处的最速下降方向为 求解minf (x)的经典Newton法在xk处的迭代方向为pk =若f(x)在X*的邻域内具有一阶连续的偏导数且f(x*) = 0,则X*为的局部极小点 X若f(x)在x*的某邻域内具

8、有二阶连续的偏导数且x*为f (x)的严格局部xk处的迭代方向为Pk二极小点，贝U G* =0：f(x*)正定.X求解mjn f (x)的最速下降法在求解min f (x)的阻尼Newton法在xk处的迭代方向为pk =用牛顿法求解1 T1 . TmRn 2xGx bx(bRn，G Rn n)时，至多迭代一次可达其极小点 X牛顿法具有二阶收敛性 V二次函数的共轭方向法具有二次终止性.X 共轭梯度法的迭代方向为:1234567891011121314151617二、证明题1设f:RnR为一阶连续可微的凸函数，x”. Rn且i f(x”)=O，贝U x为mRnf (x)的全局极小点.b Rn和正定

9、矩阵G Rn n果x Rn为求解mRnf(x)TxTGxbTx的迭代点，dkRnO为其迭代方向，且(dk)TGdk讥 0, ：)为由精确一维搜索所的步长，则:k试证：Newton法求解正定二次函数时至多一次迭代可达其极小点四、简述题1简述牛顿法或者阻尼牛顿法的优缺点.2简述共轭梯度法的基本思想.五、计算题1利用最优性条件求解无约束最优化问题31例如：求解 min f(x)x：x； -x -2论2 22用FR共轭梯度法无约束最优化问题.见书本：例341.3用PRP共轭梯度法无约束最优化问题.见书本：例3.4.1.3 1例如：min f (x)xjxf - x1 x2 -2x1 其中 x0 二(0

10、,0)T, ； = 0.0122考虑约束最优化问题：(NLP)min f (x)s.t. G (x) = 0, i E = i1, 2, l ；C(x) _0, i I I 1, l 2, , ml其中，f, q (i = 1, 2, m): Rn > R.-、判断与选择题1外罚函数法、内罚函数法、及乘子法均属于SUMT. X2使用外罚函数法和内罚函数法求解(NLP )时，得到的近似最优解往往 不是(NLP )的可行解.X3在求解(NLP )的外罚函数法中，所解无约束问题的目标函数 为.4在(NLP)中l =0，则在求解该问题的内罚函数法中，常使用的罚函数为.5在(NLP )中l = 0

11、，贝U在求解该问题的乘子法中，乘子的迭代公式为(k 1)i =，对 i 1, ,m6在(NLP)中m = l，则在求解该问题的乘子法中，增广的 Lagrange函数 为：7对于(NLP)的KT条件为：计算题1利用最优性条件（KT条件）求解约束最优化问题2 用外罚函数法求解约束最优化问题 见书本：例421;例 422.3 用内罚函数法求解约束最优化问题见书本：例423.4 用乘子法求解约束最优化问题.见书本：例4.2.7;例 4.2.8.三、简述题1简述SUMT外点法的优缺点2简述SUMT内点法的优缺点四、证明题利用最优性条件证明相关问题.例如：Q设为正定矩阵，A为列满秩矩阵.试求规划(P) m

12、in f (x) = 1 x Qx c x a2s.t. A x 二 b的最优解，并证明解是唯一的第五章多目标最优化方法、判断与选择题1求解多目标最优化问题的评价函数法包 括.2通过使用评价函数，多目标最优化问题能够转化为单目标最优化问题 .V3设F : D 乂 Rn > Rm，则F在D上的一般多目标最优化问题的数学形式为.对于规划V -miQF(x) = (fx), fm(x)T，设 X D，若不存在 X D使得F (x) _ F (x )且F (x)严F (x )，则x为该最优化冋题的有效解.V5 一般多目标最优化问题的绝对最优解必是有效解. VF(X)=(£(X)厂，fm(x)T设Wi为相应于fi (i =1,2，m)的权系数，则求解以上问题的线性加权和法中所求解优化的目标函数为.F(X)= (fjx)，你&)丁的线性加权和法所得到的解，