天津大学《最优化方法》复习题(含答案)

天津大学《最优化方法》复习题（含答案）第一章概述(包括凸规划)一、判断与填空题1)].([arg)(argminmaxxfxfnnRxRx√2.:)(min:)(maxnnRDxxfRDxxf3设.:RRDfn若nRx，对于一切nRx恒有)()(xfxf，则称x为最优化问题)(minxfDx的全局最优解.4设.:RRDfn若Dx，存在x的某邻域)(xN，使得对一切)(xNx恒有)()(xfxf，则称x为最优化问题)(minxfDx的严格局部最优解.5给定一个最优化问题，那么它的最优值是一个定值.√6非空集合nRD为凸集当且仅当D中任意两点连线段上任一点属于D.√7非空集合nRD为凸集当且仅当D中任意有限个点的凸组合仍属于D.√8任意两个凸集的并集为凸集.9函数RRDfn:为凸集D上的凸函数当且仅当f为D上的凹函数.√10设RRDfn:为凸集D上的可微凸函数，Dx.则对Dx，有).()()()(xxxfxfxfT11若)(xc是凹函数，则}0)({xcRxDn是凸集。√12设kx为由求解)(minxfDx的算法A产生的迭代序列，假设算法A为下降算法，则对,2,1,0k，恒有)()(1kkxfxf.13算法迭代时的终止准则（写出三种）：_____________________________________。14凸规划的全体极小点组成的集合是凸集。√15函数RRDfn:在点kx沿着迭代方向}0{\nkRd进行精确一维线搜索的步长k，则其搜索公式为.16函数RRDfn:在点kx沿着迭代方向}0{\nkRd进行精确一维线搜索的步长k，则kTkkkddxf)(0.17设}0{\nkRd为点nkRDx处关于区域D的一个下降方向，则对于0，),0(使得.Ddxkk二、简述题1写出Wolfe-Powell非精确一维线性搜索的公式。2怎样判断一个函数是否为凸函数.（例如:判断函数2122212151022)(xxxxxxxf是否为凸函数）三、证明题1证明一个优化问题是否为凸规划.（例如判断0..21)(minxbAxtsbxcGxxxfTT（其中G是正定矩阵）是凸规划.2熟练掌握凸规划的性质及其证明.第二章线性规划考虑线性规划问题：,0,..min)(xbAxtsxcLPT其中，mnmnRbRARc,,为给定的数据，且rank.,nmmA一、判断与选择题1(LP)的基解个数是有限的.√2若(LP)有最优解，则它一定有基可行解为最优解.√3(LP)的解集是凸的.√4对于标准型的(LP)，设kx由单纯形算法产生，则对,2,1,0k，有.1kTkTxcxc×5若*x为(LP)的最优解，*y为(DP)的可行解，则.**ybxcTT√6设0x是线性规划(LP)对应的基),,(1mPPB的基可行解，与基变量mxx,,1对应的规范式中，若存在0k，则线性规划(LP)没有最优解。×7求解线性规划(LP)的初始基可行解的方法：____________________.8对于线性规划(LP)，每次迭代都会使目标函数值下降.×二、简述题1将以下线性规划问题化为标准型：.0,0,2,1242,6..32)(max32321321321321xxxxxxxxxxxtsxxxxf2写出以下线性规划的对偶线性规划：.0,,,,3342,6342..423)(max4321432143214321xxxxxxxxxxxxtsxxxxxf三、计算题熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）.见书本：例2.5.1(利用单纯形表求解);例2.6.1(利用大M法求解);例2.6.2(利用二阶段法求解).四、证明题熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。第三章无约束最优化方法一、判断与选择题1设nnRG为正定矩阵，则关于G共轭的任意1n向量必线性相关.√2在牛顿法中，每次的迭代方向都是下降方向.×3经典Newton法在相继两次迭代中的迭代方向是正交的.×4PRP共轭梯度法与BFGS算法都属于Broyden族拟Newton算法.×5用DFP算法求解正定二次函数的无约束极小化问题，则算法中产生的迭代方向一定线性无关.√6FR共轭梯度法、PRP共轭梯度法、DFP算法、及BFGS算法均具有二次收敛性.×7共轭梯度法、共轭方向法、DFP算法以及BFGS算法都具有二次终止性.√8函数RRfn:在kx处的最速下降方向为.9求解)(minxfnRx的经典Newton法在kx处的迭代方向为kp.10若)(xf在*x的邻域内具有一阶连续的偏导数且0)(*xf，则*x为的局部极小点.×11若)(xf在*x的某邻域内具有二阶连续的偏导数且*x为)(xf的严格局部极小点，则)(*2*xfGx正定.×12求解)(minxfnRx的最速下降法在kx处的迭代方向为kp.13求解)(minxfnRx的阻尼Newton法在kx处的迭代方向为kp.14用牛顿法求解)(21minnnnTTRxRGRbxbGxxn，时，至多迭代一次可达其极小点.×15牛顿法具有二阶收敛性.√16二次函数的共轭方向法具有二次终止性.×17共轭梯度法的迭代方向为：_____________________.二、证明题1设RRfn:为一阶连续可微的凸函数，nRx且0)(xf，则x为)(minxfnRx的全局极小点.2给定nRb和正定矩阵nnRG.如果nkRx为求解xbGxxxfTTRxn21)(min的迭代点，0\nkRd为其迭代方向，且),0[k为由精确一维搜索所的步长，则.)()(kTkkTkkGdddxf3试证：Newton法求解正定二次函数时至多一次迭代可达其极小点.四、简述题1简述牛顿法或者阻尼牛顿法的优缺点.2简述共轭梯度法的基本思想.五、计算题1利用最优性条件求解无约束最优化问题.例如：求解121222122123)(minxxxxxxf2用FR共轭梯度法无约束最优化问题.见书本：例3.4.1.3用PRP共轭梯度法无约束最优化问题.见书本：例3.4.1.例如：01.0,)0,0(22123)(min01212221Txxxxxxxf其中第四章约束最优化方法考虑约束最优化问题：,,,2,1,0)(,,,2,1,0)(..)(min)(mllIixclEixctsxfNLPii其中，.:),,2,1(,RRmicfni一、判断与选择题1外罚函数法、内罚函数法、及乘子法均属于SUMT.×2使用外罚函数法和内罚函数法求解（NLP）时，得到的近似最优解往往不是（NLP）的可行解.×3在求解（NLP）的外罚函数法中，所解无约束问题的目标函数为.4在（NLP）中0l，则在求解该问题的内罚函数法中，常使用的罚函数为.5在（NLP）中0l，则在求解该问题的乘子法中，乘子的迭代公式为ik)(1，对mi,,1.6在（NLP）中lm，则在求解该问题的乘子法中，增广的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内点法的优缺点.四、证明题利用最优性条件证明相关问题.例如：Q设为正定矩阵，A为列满秩矩阵.试求规划bxAtsaxcQxxxfP..21)(min)(的最优解，并证明解是唯一的.第五章多目标最优化方法一、判断与选择题1求解多目标最优化问题的评价函数法包括.2通过使用评价函数，多目标最优化问题能够转化为单目标最优化问题.√3设mnRRDF:，则F在D上的一般多目标最优化问题的数学形式为.4对于规划TmRDxxfxfxFVn))(,),(()(1min，设Dx，若不存在Dx使得)()()()(xFxFxFxF且，则x为该最优化问题的有效解.√5一般多目标最优化问题的绝对最优解必是有效解.√6对于规划TmRDxxfxfxFVn))(,),(()(1min，设iw为相应于),,2,1(mifi的权系数，则求解以上问题的线性加权和法中所求解优化的目标函数为.7利用求解TmRDxxfxfxFVn))(,),(()(1min的线性加权和法所得到的解，或者为原问题的有效解，或者为原问题的弱有效解.√二、简述题1简单证明题☆绝对最优解、有效解、及弱有效解之间的关系.第5.2节中几个主要结论的证明.2简单叙述题★简述求解一般多目标规划的评价函数法的基本思想.简述求解一般多目标规划的线性加权和法的基本思想.★简述求解一般多目标规划的理想点法的基本思想.简述在求解一般多目标规划的评价函数法中，确定权系数方法的基本思想.