xzD天津大学《最优化方法》复习题(含答案)第一章 概述(包括凸规划)判断与填空题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 非空集合DR 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 nC(x)启0}是凸集。
Vf(x)的算法A 产生的迭代序列，假设算法 A 为下降算法,则对-k • 5,1, 2,…匚恒有 ________________ f(x k1)乞 f(x k ) ______________ •算法迭代时的终止准则(写出三种) ： ___________________________________________________ 凸规划的全体极小点组成的集合是凸集。
V12 345 67 8 910 11 12 13 14 1516函数f:D R n>R在点x k沿着迭代方向d_ R n {0}进行精确一维线搜索的步长：• k，则其搜索公式为____________________________________________n k k n函数f :D R > R在点x沿着迭代方向d R {0}进行精确一维线搜索的步长:-k y I f （x k亠-：：k d k）T d k= o ______________17设d k• R n {0}为点x k• D R n处关于区域D的一个下降方向，则对于k k一「0，二* 三(0,匚)使得x ： d D.简述题1 写出Wolfe-Powell非精确一维线性搜索的公式。
2怎样判断一个函数是否为凸函数•(例如：判断函数f(x) • 2x^2 - 2x| -10x! 5x2是否为凸函数)三、证明题1证明一个优化问题是否为凸规划.(例如1 T Tmin f (x) x Gx c x b2判断s.t. Ax二b (其中G是正定矩阵)是凸规划.x _02熟练掌握凸规划的性质及其证明.第二章线性规划考虑线性规划问题：(LP) min c T xs.t. Ax 二 b, x _ 0,其中，c R n, A R m n, b R m为给定的数据，且ran k A二m, m _ n.一、判断与选择题1 (LP)的基解个数是有限的. V2若(LP)有最优解，则它一定有基可行解为最优解. V3 (LP)的解集是凸的.V4对于标准型的(LP)，设由单纯形算法产生，则对k，01,2「「，有5若x为(LP)的最优解，y为(DP)的可行解，则c T x -b T y . V6设x。
是线性规划(LP)对应的基B = (R,…，Pm)的基可行解，与基变量…，X m对应的规范式中，若存在二k :： 0，贝U线性规划(LP)没有最优解。
X7求解线性规划（LP）的初始基可行解的方法：_______________________ .8对于线性规划（LP），每次迭代都会使目标函数值下降.X二、简述题1将以下线性规划问题化为标准型：max f（x） =% -2X2 3x3s.t. X i X2 X3 込6,2x24x3- 12,xi - x2 * X3 一2,x2_ 0, x3- 0.2写出以下线性规划的对偶线性规划：max f （x） = 3x1 2x2 x3 4x4s.t. 2x-i 4x2 3x3 x4 = 6,-2x i 4x2 3x3 X4 _ 3,X i, X2, X3, X4 一0.三、计算题熟练掌握利用单纯形表求解线性规划问题的方法（包括大 M法及二阶段法）.见书本：例2.5.1 （利用单纯形表求解）;例2.6.1 （利用大M法求解）;例2.6.2 （利用二阶段法求解）.四、证明题熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。
第三章无约束最优化方法-、判断与选择题1设G • R n n为正定矩阵，则关于G共轭的任意n • 1向量必线性相关.V2在牛顿法中，每次的迭代方向都是下降方向.X3经典Newton法在相继两次迭代中的迭代方向是正交的.X4 PRP共轭梯度法与BFGS算法都属于Broyden族拟Newton算法.X5用DFP算法求解正定二次函数的无约束极小化问题，则算法中产生的迭代方向一定线性无关.V6 FR共轭梯度法、PRP共轭梯度法、DFP算法、及BFGS算法均具有二次四、m R nm R nf (x)的全局极小点.b R n和正定矩阵G • R n n.如心十仏小的迭代点，d「RnU * [0J二)为由精确一维搜索所的步长，则k果x k• R n为求解0为其迭代方向，且-X(x k)T d k(d k)T Gd k试证：Newton法求解正定二次函数时至多一次迭代可达其极小点简述题简述牛顿法或者阻尼牛顿法的优缺点•12求解min二f (x)的最速下降法在x k处的迭代方向为p k~14用牛顿法求解 1 T—. . Tm R n 2x Gx b x(b・R n, G R n n)时，至多迭代一次收敛性.X7共轭梯度法、共轭方向法、DFP算法以及BFGS算法都具有二次终止性.V8 函数f:R n>R在x k处的最速下降方向为 _______________________________ . 9求解min f(x)的经典Newton法在x k处的迭代方向为p k= .1x累10若f(x)在x*的邻域内具有一阶连续的偏导数且、f(x*) = O,则x*为的局部极小点• X11若f(x)在x*的某邻域内具有二阶连续的偏导数且x*为f(x)的严格局部极小点，贝U G* (x*)正定.X13求解min f (x)的阻尼Newton法在x k处的迭代方向为p kx三R可达其极小点• X15牛顿法具有二阶收敛性• V16二次函数的共轭方向法具有二次终止性• X17 共轭梯度法的迭代方向为：_______________________证明题设f : R n—；R为一阶连续可微的凸函数，X：R n且'f(x”)=0，则/为2简述共轭梯度法的基本思想.五、计算题1利用最优性条件求解无约束最优化问题•3 i例如：求解 min f（x） x1 x f -x1x^2x12用FR共轭梯度法无约束最优化问题.见书本：例341.3用PRP共轭梯度法无约束最优化问题.见书本：例3.4.1.3 1例如：min f （x） x1 x| - x1x2-2x1其中x° 二（0,0）T, ；- 0.01第四章约束最优化方法考虑约束最优化问题：（NLP）min f （x）s.t. G（x）=0, i E 二〈1,2, ,l] C（x） _0, i I 1,1 2,, m[其中，f,c（i =1,2, , m） : R n>R.-、判断与选择题1外罚函数法、内罚函数法、及乘子法均属于SUMT. X2使用外罚函数法和内罚函数法求解（NLP ）时，得到的近似最优解往往不是（NLP ）的可行解.X3在求解（NLP ）的外罚函数法中，所解无约束问题的目标函数为.4在（NLP ）中I =0,则在求解该问题的内罚函数法中，常使用的罚函数为.5在（NLP ）中l = 0，贝U在求解该问题的乘子法中，乘子的迭代公式为（'k 计）i = ______________________________________________ ，对i"1,…,ml6 在（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) min f (x) = 1 x Qx c x a 2st. A x = b的最优解，并证明解是唯一的.第五章多目标最优化方法一、判断与选择题1求解多目标最优化问题的评价函数法包括__________________________________ .2通过使用评价函数，多目标最优化问题能够转化为单目标最优化问题 .V3设F:D R n>R m，则F在D上的一般多目标最优化问题的数学形式对于规划V - mm F(x) =(f!(x), , f m(x))T，设X D，若不存在X D为__________________________________使得F(x) EF(x )且F(x) = F(x )，则x”为该最优化问题的有效解.V5 一般多目标最优化问题的绝对最优解必是有效解. V6 对于规划V ~min F(x) =( f1(X),…,f m(x))T，设W i为相应于f i (i =1, 2，…，m)的权系数，则求解以上问题的线性加权和法中所求解优化的目标函数为___________________________________ .利用求解V 一mb F(X)=(f i(X),…，你&))丁的线性加权和法所得到的解，或者为原问题的有效解，或者为原问题的弱有效解• V、简述题1简单证明题☆ 绝对最优解、有效解、及弱有效解之间的关系第5.2节中几个主要结论的证明.2简单叙述题★简述求解一般多目标规划的评价函数法的基本思想.简述求解一般多目标规划的线性加权和法的基本思想.★简述求解一般多目标规划的理想点法的基本思想.简述在求解一般多目标规划的评价函数法中，确定权系数方法的基本思想.。