天津大学最优化方法复习题

《天津大学最优化方法复习题》由会员分享，可在线阅读，更多相关《天津大学最优化方法复习题（12页珍藏版）》请在装配图网上搜索。

1、最优化方法复习题第一章概述(包括凸规划)判断与填空题1argmaxf(x)=argmin一f(x).vx,Rn,x,RmaxI(x):x,DRn=-min(x):x,DRn3 设f:DRnR.若x*,Rn,对于一切x,Rn恒有f(x*)f(x),则称x*为最优化问题minf(x)的全局最优解.xx,D4 设f:DRnTR.若x*,D,存在x*的某邻域N(x*),使得对一切x,n(x*)恒有f(x*)f(x)，则称x*为最优化问题minf(x)的严格局部最x,D优解.x5 给定一个最优化问题，那么它的最优值是一个定值.v6 非空集合DRn为凸集当且仅当D中任意两点连线段上任一点属于D.V7 非空

2、集合DRn为凸集当且仅当D中任意有限个点的凸组合仍属于D.V8 任意两个凸集的并集为凸集.x9 函数f:DRnTR为凸集D上的凸函数当且仅当-f为D上的凹函数.V10设f:DRntR为凸集D上的可微凸函数，x*,D.则对Vx,D,有f(x)-f(x*)0是凸集。V12设L为由求解minf(x)的算法a产生的迭代序列，假设算法A为下降算法，x,D则对Vk,0,1,2,，恒有f(x)0,3a,(0,a)使得xk+adk,D.x二、简述题1写出Wolfe-Powell非精确一维线性搜索的公式。2怎样判断一个函数是否为凸函数.(例如：判断函数f(x)x2+2xx+2x202 熟练掌握凸规划的性质及其证

3、明.第二章线性规划考虑线性规划问题：(LP)mincTxs.t.Ax=b,x0,其中，c,Rn,A,Rmxn,b,Rm为给定的数据，且rankA=m,mn.、判断与选择题1(LP)的基解个数是有限的.V2若(LP)有最优解，则它一定有基可行解为最优解.V3(LP)的解集是凸的.V4对于标准型的(LP),设L由单纯形算法产生，则对k,o,l,2,，有cTxkcTxk+1.X5若x*为(LP)的最优解，y*为(DP)的可行解，则cTx*bTy*.V6设x是线性规划(LP)对应的基B=(P,P)的基可行解，与基变量01mx,x对应的规范式中，若存在Q0，贝熾性规划(LP)没有最优解。X1mk7求解线

4、性规划(LP)的初始基可行解的方法：.8对于线性规划(LP),每次迭代都会使目标函数值下降.X简述题1将以下线性规划问题化为标准型：maxf（x）x一2x+3x123s.t.x+x+x6,123x+2x+4x12,123x一x+x2,123x0,x0.232写出以下线性规划的对偶线性规划：maxf（x）3x+2x+x+4x1234s.t.2x+4x+3x+x6,1234一2x+4x+3x+x3,1234x,x,x,x0.1234三、计算题熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）.见书本：例2.5.1（利用单纯形表求解）;例2.6.1（利用大M法求解）；例2.6.2（利

5、用二阶段法求解）.四、证明题熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。第三章无约束最优化方法、判断与选择题1设GeRnn为正定矩阵，则关于G共轭的任意n,1向量必线性相关.V2在牛顿法中，每次的迭代方向都是下降方向.X3经典Newton法在相继两次迭代中的迭代方向是正交的.X4PRP共轭梯度法与BFGS算法都属于Broyden族拟Newton算法.X5用DFP算法求解正定二次函数的无约束极小化问题，则算法中产生的迭代方向一定线性无关.V6FR共轭梯度法、PRP共轭梯度法、DFP算法、及BFGS算法均具有二次收敛性.X7共轭梯度法、共轭方向法、DFP算

6、法以及BFGS算法都具有二次终止性.V8函数f:Rn-R在xk处的最速下降方向为.9求解minf(x)的经典Newton法在xk处的迭代方向为pk.xeRn10若f(x)在x*的邻域内具有一阶连续的偏导数且f(x*)0，则x*为的局部极小点.X11若f(x)在x*的某邻域内具有二阶连续的偏导数且x*为f(x)的严格局部极小点，则G*V2f(x*)正定.Xx12求解minf(x)的最速下降法在xk处的迭代方向为pk.xeRn13求解minf(x)的阻尼Newton法在xk处的迭代方向为pk.xeRn14用牛顿法求解min1xTGx+bTx(beRn，GeRm)时，至多迭代一次2xeRn可达其极小

7、点.X15 牛顿法具有二阶收敛性.V16 二次函数的共轭方向法具有二次终止性.X17 共轭梯度法的迭代方向为：.、证明题1设f：RnR为一阶连续可微的凸函数，X，GRn且f（x，）=0，则x，为minf（x）的全局极小点.xGRn2给定bGRn和正定矩阵GGRnn.如果XkGRn为求解minf(x)=-xTGx+bTx的迭代点，dkGRnO为其迭代方向，且2xGRnag0,+8)为由精确k维搜索所的步长，则akVf(xk)Tdk(dk)TGdk3试证：Newton法求解正定二次函数时至多一次迭代可达其极小点.四、简述题1 简述牛顿法或者阻尼牛顿法的优缺点.2 简述共轭梯度法的基本思想.五、计算

8、题1利用最优性条件求解无约束最优化问题.例如：求解min2122122x12用FR共轭梯度法无约束最优化问题.见书本：例3.4.1.3用PRP共轭梯度法无约束最优化问题.见书本：例3.4.1.例如：min2122122x其中x=(0,0)T,=0.0110第四章约束最优化方法考虑约束最优化问题：(NLP)minf(x)s.t.c(x)=0,iE=1,2,l,c(x)0,iI=+1,l+2,，m,i其中，f,c(i=1,2,，m):RnTR.i、判断与选择题1外罚函数法、内罚函数法、及乘子法均属于SUMT.X2使用外罚函数法和内罚函数法求解（NLP）时，得到的近似最优解往往不是（NLP）的可行解

9、.X3在求解（NLP）的外罚函数法中，所解无约束问题的目标函数为.4在（NLP）中i=0,则在求解该问题的内罚函数法中，常使用的罚函数为.5在（NLP）中i=0,则在求解该问题的乘子法中，乘子的迭代公式为（九）=，对i,mk,1i6在（NLP）中m=l，则在求解该问题的乘子法中，增广的Lagrange函数为：二、计算题*、1利用最优性条件(KT条件)求解约束最优化问题.2 用外罚函数法求解约束最优化问题.见书本：例4.2.1；例4.2.2.3 用内罚函数法求解约束最优化问题.见书本：例4.2.3.4 用乘子法求解约束最优化问题.见书本：例4.2.7；例4.2.8.三、简述题1简述SUMT外点法

10、的优缺点.2简述SUMT内点法的优缺点.四、证明题利用最优性条件证明相关问题.例如：q设为正定矩阵，a为列满秩矩阵.试求规划1(P)minf(x)x,Qx+c,x+a2s.t.Atxb的最优解，并证明解是唯一的.第五章多目标最优化方法一、判断与选择题1求解多目标最优化问题的评价函数法包括:2通过使用评价函数，多目标最优化问题能够转化为单目标最优化问题：J3设F:D匸RnRm，则F在D上的一般多目标最优化问题的数学形式为:4 对于规划V-minF(x)，(f(x),f(x)T，设xD，若不存在xD1mxDuRn使得F(x)F(x)且F(x)工F(x)，则x为该最优化问题的有效解.V5 一般多目标

11、最优化问题的绝对最优解必是有效解.V6对于规划v-minf(x),(f(x)，,f(x)t，设w为相应于1mixDuRnf(i，1,2,m)的权系数，则求解以上问题的线性加权和法中所求解优i化的目标函数为:7利用求解v-minf(x),(f(x),，f(x)t的线性加权和法所得到的1mxDuRn解，或者为原问题的有效解，或者为原问题的弱有效解:V、简述题1简单证明题绝对最优解、有效解、及弱有效解之间的关系. 第5.2节中几个主要结论的证明.2简单叙述题 简述求解一般多目标规划的评价函数法的基本思想.简述求解一般多目标规划的线性加权和法的基本思想. 简述求解一般多目标规划的理想点法的基本思想. 简述在求解一般多目标规划的评价函数法中，确定权系数方法的基本思想.