最优化方法复习题

1、、123456789101112最优化方法复习题第一章概述(包括凸规划)判断与填空题argmaxf(x)二argmin-f(x).VxeRnxeRnmaxf(x):xeD匸Rn丿=min设f:D匸RntR.若x*eRn，对于一切xeRn恒有f(x*)<f(x)，则称x*为最优化问题minf(x)的全局最优解.xxeD设f:D匸RntR.若x*eD，存在x*的某邻域N(x*)，使得对一切£xeN(x*)恒有f(x*)<f(x)，则称x*为最优化问题minf(x)的严格局部最£xeD优解.x给定一个最优化问题，那么它的最优值是一个定值.V非空集合D匸Rn为凸集当且仅

2、当D中任意两点连线段上任一点属于D.V非空集合D匸Rn为凸集当且仅当D中任意有限个点的凸组合仍属于D.V任意两个凸集的并集为凸集.x函数f:D匸RnTR为凸集D上的凸函数当且仅当-f为D上的凹函数.V设f:D匸RnTR为凸集D上的可微凸函数，x*eD.则对VxeD，有f(x)f(x*)<Vf(x*)T(xx*).x若c(x)是凹函数，则D=xeRnc(x)>0是凸集。V设b为由求解minf(x)的算法A产生的迭代序列，假设算法A为下降算法，xeD则对Vkeb,l,2,，恒有f(x)<f(x).k+1k13算法迭代时的终止准则(写出三种)：。14凸规划的全体极小点组成的集合是凸

3、集。V15函数f:D匸RnTR在点xk沿着迭代方向dkeRn0进行精确一维线搜索的步长a，则其搜索公式为.k16函数f:D匸RnTR在点Xk沿着迭代方向dkeRn0进行精确一维线搜索的步长a，则Vf(xk+adk)tdk=o.kk17设dkeRn0为点xkeD匸Rn处关于区域D的一个下降方向，则对于Va>0，3ae(0,a)使得xk+adkeD.x二、简述题1写出Wolfe-Powell非精确一维线性搜索的公式。2怎样判断一个函数是否为凸函数.(例如：判断函数f(x)二x2+2xx+2x2-10x+5x是否为凸函数)112212三、证明题1证明一个优化问题是否为凸规划.(例如minf(x

4、)=-xtGx+ctx+b判断s.t.Ax=b其中G是正定矩阵)是凸规划.2熟练掌握凸规划的性质及其证明.第二章线性规划考虑线性规划问题：(LP)mincTxs.t.Ax=b,x>0,其中，ceRn,AeRmxn,beRm为给定的数据，且rankA=m,m<n.一、判断与选择题1(LP)的基解个数是有限的.V2若(LP)有最优解，则它一定有基可行解为最优解.V3(LP)的解集是凸的.V4对于标准型的(LP)，设L由单纯形算法产生，则对ke£,l,2,，有CTXk>CTXk+1.X5若X*为(LP)的最优解，y*为(DP)的可行解，则CTx*>bTy*.V6设x

5、是线性规划(LP)对应的基B二(P，,P)的基可行解，与基变量01mx，,x对应的规范式中，若存在b<0，贝V线性规划(LP)没有最优解。X1mk7求解线性规划(LP)的初始基可行解的方法：.8对于线性规划(LP)，每次迭代都会使目标函数值下降.X简述题1 将以下线性规划问题化为标准型maxf(x)=x一2x+3x123s.t.x+x+x<6,123x+2x+4x>12,123x一x+x>2,123x>0,x>0.232 写出以下线性规划的对偶线性规划maxf(x)=3x+2x+x+4x1234s.t.2x+4x+3x+x=6,1234一2x+4x+3x+x

6、>3,1234x,x,x,x>0.1234三、计算题熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）.见书本：例2.5.1例2.6.1例2.6.2（利用单纯形表求解）;（利用大M法求解）;（利用二阶段法求解）.四、证明题熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。第三章无约束最优化方法、判断与选择题1设GeRnxn为正定矩阵，则关于G共轭的任意n+1向量必线性相关.V2在牛顿法中，每次的迭代方向都是下降方向.X3经典Newton法在相继两次迭代中的迭代方向是正交的.X4 PRP共轭梯度法与BFGS算法都属于Broyden族

7、拟Newton算法.X5 用DFP算法求解正定二次函数的无约束极小化问题，则算法中产生的迭代方向一定线性无关.V6 FR共轭梯度法、PRP共轭梯度法、DFP算法、及BFGS算法均具有二次收敛性.X7共轭梯度法、共轭方向法、DFP算法以及BFGS算法都具有二次终止性.V8函数f:RntR在xk处的最速下降方向为.9求解minf(x)的经典Newton法在xk处的迭代方向为pk=.xeRn10若f(x)在x*的邻域内具有一阶连续的偏导数且Vf(x*)=0，则x*为的局部极小点.X11若f(x)在x*的某邻域内具有二阶连续的偏导数且x*为f(x)的严格局部极小点，则G*=V2f(x*)正定.Xx12

8、求解minf(x)的最速下降法在xk处的迭代方向为pk二.xeRn13求解minf(x)的阻尼Newton法在xk处的迭代方向为pk二.xeRn14用牛顿法求解min-xtGx+bTx(b&Rn，G&Rn“)时，至多迭代一次2xeRn可达其极小点.X15 牛顿法具有二阶收敛性.V16 二次函数的共轭方向法具有二次终止性.X17 共轭梯度法的迭代方向为：.、证明题1设f:RnTR为一阶连续可微的凸函数，X*GRn且Vf(x*)二0，则x*为minf(x)的全局极小点.xGRn2给定bGRn和正定矩阵GGRnxn.如果XkGRn为求解minf(x)=-XTGx+bTx的迭代点，dk

9、GRn为其迭代方向，且2xGRnaG0,+Q为由精确一维搜索所的步长，则a=Vf(xk)Tdk.kk(dk)TGdk3试证：Newton法求解正定二次函数时至多一次迭代可达其极小点.四、简述题1 简述牛顿法或者阻尼牛顿法的优缺点.2 简述共轭梯度法的基本思想.五、计算题1 利用最优性条件求解无约束最优化问题.31例如：求解minf(x)=x2+x2一xx-2x21221212 用FR共轭梯度法无约束最优化问题.见书本：例3.4.1.3 用PRP共轭梯度法无约束最优化问题.见书本：例3.4.1.31例如：minf(x)=x2+x2一xx一2x其中x=(0,0)t,&=0.01212212

10、10第四章约束最优化方法考虑约束最优化问题：7对于（NLP）的KT条件为：(NLP)minf(x)s.t.c(x)=0,ic(x)>0,iieE=&2,，八i&I=£+1,l+2,m其中，f,c(i=1,2,，m):RntR.i、判断与选择题1外罚函数法、内罚函数法、及乘子法均属于SUMT.X2使用外罚函数法和内罚函数法求解（NLP）时，得到的近似最优解往往不是（NLP）的可行解.X3 在求解（NLP）的外罚函数法中，所解无约束问题的目标函数为.4在（NLP）中/=0，则在求解该问题的内罚函数法中，常使用的罚函数为.5在（NLP）中/=0，则在求解该问题的乘子法

11、中，乘子的迭代公式为（九）=，对ie£,.,m.k+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外点法的优缺点.2简述SUMT内点法的优缺点.四、证明题利用最优性条件证明相关问题.例如：Q设为正定矩阵，A为列满秩矩阵.试求规划(P)1minf(x)=xtQx+ctx+as.

12、t.Atx=b的最优解，并证明解是唯一的.2第五章多目标最优化方法一、判断与选择题1求解多目标最优化问题的评价函数法包括.2通过使用评价函数,多目标最优化问题能够转化为单目标最优化问题V3设F:D匸RnTRm，则F在D上的一般多目标最优化问题的数学形式为4 对于规划VminF(x)二(f(x),，f(x)T，设x*gD,若不存在xeD1mxeDoRn使得F(x)<F(x*)且尸(x)丰F(x*)，则x*为该最优化问题的有效解.V5 一般多目标最优化问题的绝对最优解必是有效解.V6对于规划VminF(x)二(f(x),.,f(x)T,设w为相应于1mixeDoRnf(i二1,2,.,m)的权系数，则求解以上问题的线性加权和法中所求解优i化的目标函数为7利用求解Vminf(x)二(f(x),f(x)t的线性加权和法所得到的1m