《最优化方法》复习题第一章概述(包括凸规划)一、判断与填空题ar§ max /W =玄生min【―/(兀)】・71xeR n xeR n2max |/(x): x e D o }= - min [f(x): x e D Q R H\ x3设f : D u RJ R・若T wR”,对于一切xeR n恒有/(Z)</(x),则称T为最优化问题m in fM的全局最优解.xxeD4设f •・D U RJ R.若Z eD ,存在F的某邻域Ng,使得对一切恒有/U*)</(兀)，则称T为最优化问题min /(兀)的严格局部最xeD优解.X5给定一个最优化问题，那么它的最优值是一个定值.V6非空集合D匸/?"为凸集当且仅当D屮任意两点连线段上任一点属于D. V 7非空集合D o 7?"为凸集当J1仅当D中任意有限个点的凸组合仍属于D. V 8任意两个凸集的并集为凸集.x9 函数f : D匸R” T R为凸集£>上的凸函数当且仅当—/为D上的凹函数.V1()设f : D u R” T R为凸集D上的可微凸函数，Z G Z).则对V XG D,有/(x)-/(x*)<V/(x*/(x-x*). x11若c(兀)是凹函数，则D = {xeR n\ c(x) > 0}是凸集。
V12设{*}为由求解min的算法A产生的迭代序列，假设算法A为下降算法，XG D则对\^^{0,1,2,・・・},恒有____ /(x A.+1)< f(x k) ____________ :13算法迭代时的终止准则（写出三种）： ____________________________ o 14凸规划的全体极小点组成的集合是凸集。
V15函数f : D u R“ T R在点（'沿着迭代方向d* eR n \ ｛（）｝进行精确一维线搜索的步长匕.，则其搜索公式为_____________________________ .16函数f •. D匚R“ T R在点*•沿着迭代方向d k e/?z, \｛0｝进行梢确一•维线搜索的步长匕，则V/（x A+a k d k Yd k = ___________ 0 .17设d k eR n\｛0｝为点/ w D匸R“处关于区域D的一个下降方向，则对于Va >0, 3«G（0,a）使得x二、简述题1写出Wolfe-Powell非精确一维线性搜索的公式。
2怎样判断一个函数是否为凸函数.（例如:判断函数/（x） = xf +2兀|兀2 +2兀;一10兀1 +5兀2是否为凸函数）三、证明题1证明一个优化问题是否为凸规划.（例如1Z* T—X Gx + c x + b2判断s.t. Ax = b（其小G是正定矩阵）是凸规划.x>02熟练掌握凸规划的性质及英证明.第二章线性规划考虑线性规划问题：(LP)min c xs.t. Ax = b, x>Q.其中,ceR\ AeR mx\ b e R m为给定的数据，且rankA = m, m<n.一、判断与选择题1 (LP)的基解个数是有限的.J2若(LP)有最优解，则它一定有基可行解为最优解.V2(LP)的解集是凸的.V4对于标准型的(LP),设{?}由单纯形算法产生，则对"{0,1,2,・・・},冇c T x k >c T x k+}. X5若T为(LP)的最优解，/为(DP)的可行解，则c T x>b T y\ V6设兀。
是线性规划(LP)对应的基B = (P“・・,PJ的基可行解，与基变量州，…,心对应的规范式中，若存在<r, < 0 ,则线性规划(LP)没冇最优解。
X7求解线性规划(LP)的初始基可行解的方法：_______________________ .8对于线性规划(LP),每次迭代都会使目标函数值下降.X二、简述题1将以下线性规划问题化为标准型：max f（x） = x, - 2X2 + 3x3s.t. x, + x2 + < 6，%! + 2兀2 + 4X3 > 12,x, - x2 + x3 > 2,x2 > 0, x3 > 0.2写出以卜•线性规划的对偶线性规划：max /（%） = 3%j + 2x2 + 心 + 4x4s.t. 2x）+ 4X2 + 3 兀3 + 兀=6,一2xj + 4兀2 + 3兀3 + 兀4 » 3,X], x2,兀3，兀、0.三、计算题熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）.见书本：例2.5.1 （利用单纯形表求解）；例2.6.1 （利用大M法求解）；例2.6.2 （利用二阶段法求解）.四、证明题熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。
第三章无约束最优化方法一、判断与选择题1设G w R旳为正定矩阵，则关于G共觇的任意“ + 1向量必线性相关.V2在牛顿法中，每次的迭代方向都是下降方向.X3经典Newton法在相继两次迭代小的迭代方向是正交的.X3PRP共辘梯度法与BFGS算法都属于Broyden族拟Newton算法.X5用DFP算法求解正定二次函数的无约束极小化问题，则算法屮产生的迭代方向一定线性无关.V6 FR共轨梯度法、PRP共轨梯度法、DFP算法、及BFGS算法均具冇二次收敛性.X7共饥梯度法、共辘方向法、DFP算法以及BFGS算法都具有二次终止性.V 8函数广/T 一/?在卡处的最速下降方向为 _____________________________ .9求解mi n f(x)的经典Newton法在处的迭代方向为// = ___________________ .xeR n10若7(兀)在/的邻域内具有一阶连续的偏导数= 则T为的局部极小点.x11若/(兀)在F的某邻域内具有二阶连续的偏导数11F为/(Q的严格局部极小点，则G* =V；/(x^)正定.X12求解min 的最速下降法在十'处的迭代方向为〃 = ___________ .X€/?n13求解min/W的阻尼Newton法在*处的迭代方向为p k = __________________ .xeR n14用牛顿法求解min -x T Gx + b T x (/? e R\ GeR,iXn)时，至多迭代一次xcR n 2可达其极小点.X15牛顿法具有二阶收敛性.V16二次函数的共辘方向法具有二次终止性.X17共轨梯度法的迭代方向为：_______________________二、证明题1设f : R“ T R 为一阶连续可微的凸函数,X eR n且 W) = 0,则T 为 min /(X)的全局极小点.xeR n2给定beR”和正定矩阵G G ・如果/ 6/?w 为求解m in fM = -x T Gx + h T x 的迭代点，d ke/?M \{o}为-其迭代方向，且 XWR" 2 3试证：Newton 法求解正定二次函数时至多一次迭代可达其极小点.四、简述题1简述牛顿法或者阻尼牛顿法的优缺点.2简述共轨梯度法的基本思想.五、计算题1利用最优性条件求解无约束最优化问题.3 1例如：求解 min /(x) = ~^x \ + —~x \x 2 一 2兀i2用FR 共轨梯度法无约束最优化问题.见书本：例3.4.1.3用PRP 共觇梯度法无约束最优化问题.见书本：例3.4.1.3 |例如：min f(x) = — %]2 + —x ； -x [x 2 -2x,其中x 。
= (0,0)丁,£ = 0.01第四章约束最优化方法考虑约束最优化问题：(NLP) min f(x)s.t. c i (%) = 0, z G E = {1, 2, •••, /},c.(x) > 0, z G / = {/ +1, / + 2, •••, m},其中，y,c& = l,2,・・・，/n):R”TR匕e [0, + oo)为由精确一维搜索所的步长, -(d k)T Gd k一、判断与选择题1外罚函数法、内罚函数法、及乘子法均属于SUMT. X2使用外罚函数法和内罚函数法求解(NLP)时，得到的近似最优解往往不是(NLP)的可行解.X3在求解(NLP)的外罚函数法中，所解无约束问题的目标函数为•4在(NLP)中1 = 0,则在求解该问题的内罚函数法中，常使用的罚函数为•5在(NLP)中/ = 0,则在求解该问题的乘子法中，乘子的迭代公式为(佥+ 1), = ________________________ ，对沱｛1,6在(NLP)中m = I,则在求解该问题的乘子法中，增广的Lagrange函数为：二、计算题1利用最优性条件(KT条件)求解约束最优化问题.2用外罚函数法求解约束最优化问题.见书本：例4.2.1；例 4.2.2.3用内罚函数法求解约朿最优化问题.见书本:例423.4用乘了法求解约束最优化问题.见书本:例427；例 4.2.8.三、简述题1简述SUMT外点法的优缺点.2简述SUMT内点法的优缺点.四、证明题利用最优性条件证明相关问题.例如：Q设为正定矩阵，A为列满秩矩阵•试求规划(P) min/(x) = Qx + x + as.t. A T X = b的最优解，并证明解是唯一的.第五章多目标最优化方法一、判断与选择题1求解多目标最优化问题的评价函数法包括线性加权法极大极小法理想点法平方和加权法乘除法_____________________________________ .2通过使用评价函数，多目标最优化问题能够转化为单目标最优化问题• J3设F : D匸R" T R",则尸在£>上的一般多目标最优化问题的数学形式为•4对于规划V - min F(x)= (/1⑴,…，九(X))7，设x* e £>,若不存在x w DxeD^R n使得F(x) < F(T)且F(兀)工F(xJ ,则%*为该最优化问题的有效解.J 5一般多目标最优化问题的绝对最优解必是有效解.V6对丁•规划V - F(x) = (/( (x),..., f m (x))7 ,设w,为相应于xeD^R n/,•(心1,2,…，加)的权系数，则求解以上问题的线性加权和法中所求解优化的目标函数为_________________________________ .7利用求解v - min尸⑴=(/1⑴,…,九⑴)丁的线性加权和法所得到的xeDQR n解，或者为原问题的有效解，或者为原问题的弱有效解.V二、简述题1简单证明题☆ 绝对最优解、有效解、及弱有效解之间的关系.•笫5.2节中儿个主要结论的证明.2简单叙述题★简述求解一般多口标规划的评价函数法的基木思想.•简述求解一般多目标规划的线性加权和法的基本思想.★简述求解一般多目标规划的理想点法的基本思想.•简述在求解一般多目标规划的评价函数法中，确定权系数方法的基本思想.。