《最优化方法》复习题第一章概述(包括凸规划)一、判断与填空题1ar§ max /(x) = arg min【一/(兀)]・7xeR n xeR n2max |/(x): x G D o /?n }= - min {/(x): x e £> o /?n} x3设f . D j RJ R・若x* G/?\对于一切"R”恒有兀)，贝称X为最优化问题min /W的全局最优解.xxeD4设f : D匸RJ R.若x* G D,存在F的某邻域N3 ,使得对一切xwNg恒有/(x*)< /(X),则称T为最优化问题min/E的严格局部最xeD优解.X5给定一个最优化问题，那么它的最优值是一个定值.V6非空集合D o /?"为凸集当且仅当D中任意两点连线段上任一点属于D. V7非空集合D c /?"为凸集当且仅当D中任意有限个点的凸组合仍属于D. V 8任意两个凸集的并集为凸集.x9 函数f : D匚R n T /?为凸集D上的凸函数当且仅当—/为D上的凹函数.V10设f : D u R” T R为凸集D上的可微凸函数，Z eD .则対Vx G D ,有/⑴-/(%*)< v/*U*)r (x - * )• x11若c(x)是凹函数，则D = {xeR n\ c(x) > 0}是凸集。
V12设{/}为由求解min/U)的算法A产生的迭代序列，假设算法A为下降算法，xeD 则对\/k e {0,1, 2, •••},恒有_______ (林) ________________________ .13算法迭代时的终止准则(写击三种)： _______________________________________ 0 14凸规划的全体极小点组成的集合是凸集。
V15函数/ : P o R n T/?在点/沿着迭代方向d" \{()}进行精确一维线搜索的步长则其搜索公式为______________________________________________ .16函数f・.D匸R” T/?在点十•沿着迭代方向d* wR" \{0}进行精确一维线搜索的步长匕，则Vf(x k ^a k d k Yd k = _________ 0 _____________ .17设d k eR n\{0}为点x k eD^R n处关于区域D的一个下降方向，则对于Va >0, 3CTG(0,a)使得x' +ad k eD. x二、简述题1写出Wolfc-Powcll非粘确一维线性搜索的公式。
2怎样判断一个函数是否为凸函数.(例如:判断函数/(%) =时+ 2x1 x2 + 2分-10坷+ 5兀2是否为凸函数)三、证明题1证明一个优化问题是否为凸规划.(例如min/(x) = —x I Gx + c1x-\-h2判断M Ax = b(其中G是正定矩阵)是凸规划.x>02熟练掌握凸规划的性质及具证明.第二章线性规划考虑线性规划问题:(LP)min c l xs.t. Ax = b, x > 0,其中,ceR\ AwR"： b G R m为给定的数据,>rankA = m, m<n.一、判断与选择题1 (LP)的基解个数是有限的.V2若(LP)有最优解，则它一定有基可行解为最优解.V3(LP)的解集是凸的.V4对于标准型的(LP),设{*'}由单纯形算法产生，则对Rw{0,l,2,・・・},有cW >c“. X5若/为(LP)的最优解，)「为(DP)的可行解，则c T x>b T y\ V6设是线性规划(LP)对应的基B = …几)的基可行解，与基变量州，…竝对应的规范式屮，若存在qvO,则线性规划(LP)没有最优解。
X7求解线性规划(LP)的初始基可行解的方法：_______________________ .8对于线性规划(LP),每次迭代都会使冃标函数值下降.X二、简述题1将以下线性规划问题化为标准型:max /(x)=兀］一2X2 + 3x3 s.t. X］+ 兀2 +兀3 - 6,%! + 2兀2 + 4兀3 ' 12,- x2 + x3 > 2,x2 > 0, x3 > 0.2写出以下线性规划的对偶线性规划: max /(x) = 3x)+ lx2 +x3 + 4x4s.t. 2x l + 4X2 + 3 兀3 + 兀4 = 6,一2x{ + 4兀2 + 3X3+X4 > 3,兀］,£，兀3，X4 - 0・三、计算题熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）. 见书本:例 2.5.1例261例 2.6.2（利用单纯形表求解）；（利用大M法求解）；（利用二阶段法求解）.四、证明题熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。
-、判断与选择题1设G G R flXfl为正定矩阵，贝IJ关于G共轨的任意” + 1向量必线性相关.J 2在牛顿法屮，每次的迭代方向都是下降方向.X3经典Newton法在相继两次迭代中的迭代方向是正交的.X4PRP共轨梯度法与BFGS算法都属于Broyden族拟Newton算法.X5用DFP算法求解正定二次函数的无约束极小化问题，则算法中产生的迭代方向一定线性无关.V6 FR共辘梯度法、PRP共轨梯度法、DFP算法、及BFGS算法均具有二次收敛性.X7共轨梯度法、共轨方向法、DFP算法以及BFGS算法都具有二次终止性.V 8函数f : RJ R在*'处的最速下降方向为 ____________________________ .9求解min /W的经典Newton法在十处的迭代方向为p k = _________________ .xeR n10若/(兀)在T的邻域内具有一阶连续的偏导数且V/(/) = 0,则T为的局部极小点.x11若.门兀)在T的某邻域内具有二阶连续的偏导数且/为几对的严格局部极小点，则G* 正定.X12求解min/")的最速下降法在十处的迭代方向为p k = _________________ .xeR n13求解mi n /(x)的阻尼Newton法在*处的迭代方向为p k = _________________ .xeR n14用牛顿法求解min丄x T Gx + b r x (bwR“, GeR HXn)时，至多迭代一次xwR” 2可达其极小点.X15牛顿法具有二阶收敛性.V16二次函数的共轨方向法具有二次终止性.X17共饥梯度法的迭代方向为： ______________________ .二、证明题1设f : R" I R为一阶连续可微的凸函数，x* G R n且巧（疋）=0,则F为min /（兀）的全局极小点.xeR n2给定bwR”和正定矩阵Ge耐”.如果x* R n为求解in fM =丄的迭代点，d k e/?n\{o}为其迭代方向，且xeR n2ma k e[0, + oo）为由精确一维搜索所的步长，则a k=~Vf^）T f・3试证：Newton法求解止定二次函数时至多一次迭代可达其极小点.四、简述题1简述牛顿法或者阻尼牛顿法的优缺点.2简述共轨梯度法的基木思想.五、计算题1利用最优性条件求解无约束最优化问题. 例如：求解min f（x） = —xf + 丄卅-x{x2 -2x l2用FR共轨梯度法无约束最优化问题. 见书本：例3.4.1.3用PRP共饥梯度法无约束最优化问题.见书本：例3.4.1.3 ]例如：min f(x) = —x^ + —x；-x l x2一2兀]其中兀。
=(0,0)r,e = 0.01考虑约束最优化问题：(NLP)min /(x)s.t. c t(x) = 0, i e E ={1, 2, •••, /},c. (%) > 0, z G/ = {/ +1, / + 2, • • •, m},其中，几q(心1,2,…，/n):R" T R一、判断与选择题1外罚函数法、内罚函数法、及乘子法均属于SUMT. X2使用外罚函数法和内罚函数法求解（NLP）时，得到的近似最优解往往不是（NLP）的可行解.X3在求解（NLP）的外罚函数法中，所解无约束问题的目标函数为•4在（NLP）中/=0,则在求解该问题的内罚函数法中，常使用的罚函数为•5在（NLP） +/ = 0,则在求解该问题的乘子法屮，乘子的迭代公式为（血 + ］）（ = __________________ ，对沁｛1, •••,〃｝•6在（NLP）中m = I,则在求解该问题的乘了法中，增广的Lagrange函数为： _________________________________7对于（NLP）的KT条件为：______________二、计算题1利用最优性条件（KT条件）求解约束最优化问题.2用外罚函数法求解约束最优化问题.见书本：例4.2.1；例4.2.2.3用内罚函数法求解约束最优化问题.见书本:例4.2.3.4用乘子法求解约束最优化问题.见书本：例4.2.7；例 4.2.8.三、简述题1简述SUMT外点法的优缺点.2简述SUMT内点法的优缺点.四、证明题利用最优性条件证明相关问题.例如：0设为正定矩阵，A为列满秩矩阵•试求规划(P) min /(x) = —X T Q X +c1 x + as.t. A7 x = b的最优解，并证明解是唯一的.一、判断与选择题1求解多目标最优化问题的评价函数法包括.2通过使用评价函数，多忖标最优化问题能够转化为单忖标最优化问题.V3设F : D u RJ R'"，则F在D上的一般多目标最优化问题的数学形式为_________________________________ •4对于规划V-m i n F(x) = (/,(%),...,/w(x))r,设T wD，若不存在兀XE D Q R11使得F(x) < F(x*)MF(x) H F(x*),则T为该最优化问题的有效解.V 5一般多冃标最优化问题的绝对最优解必是有效解.V6对-T规划V-minF(x)=(/心)，…，九⑴V，设叱为相应于xwDuR"f-t (21, 2,…皿)的权系数，则求解以上问题的线性加权和法屮所求解优化的目标函数为__________________________________ .7利用求解v - min F(Q =(/；⑴,…，九⑴卩的线性加权和法所得到的xeD^R0解，或者为原问题的有效解，或者为原问题的弱有效解.V二、简述题1简单证明题☆ 绝对最优解、有效解、及弱有效解Z间的关系.•第5.2节中几个主要结论的证明.2简单叙述题★简述求解一般多日标规划的评价函数法的基木思想.•简述求解一般多冃标规划的线性加权和法的基本思想.★简述求解一般多目标规划的理想点法的基本思想.• 简述在求解一般多目标规划的评价函数法屮，确定权系数方法的基本思想.。