最优化方法复习题.doc

1、最优化方法复习题第一章 概述( 包括凸规划)一、 判断与填空题1 ).(arg)(argminxxffn RxR2 .:mnRDfDf 3 设 若 ，对于一切 恒有 ，则称.:fnnxnx)(xff为最优化问题 的全局最优解. x)(ifDx4 设 若 ，存在 的某邻域 ，使得对一切.:Rfnxx)(xN恒有 ，则称 为最优化问题 的严格局部最)(xN )(ff minfDx优解. 5 给定一个最优化问题，那么它的最优值是一个定值. 6 非空集合 为凸集当且仅当 中任意两点连线段上任一点属于 . nRDD7 非空集合 为凸集当且仅当 中任意有限个点的凸组合仍属于 . D8 任意两个凸集的并集为

2、凸集. 9 函数 为凸集 上的凸函数当且仅当 为 上的凹函数. RDfn:Df10 设 为凸集 上的可微凸函数， . 则对 ，有DxDx).()(xfxfT11 若 是凹函数，则 是凸集。 c 0(cRDn12 设 为由求解 的算法 A 产生的迭代序列，假设算法 A 为下降算法，kx)(mixfDx则对 ，恒有 .,210)(1kkxff13 算法迭代时的终止准则（写出三种）：_。14 凸规划的全体极小点组成的集合是凸集。 15 函数 在点 沿着迭代方向 进行精确一维线搜索的RDfn:kx0nkRd步长 ，则其搜索公式为 .k16 函数 在点 沿着迭代方向 进行精确一维线搜索的RDfn:kx0

3、nkRd步长 ，则 0 .kTkdf)(17 设 为点 处关于区域 的一个下降方向，则对于0nkdnkxD， 使得 ),(.dk二、 简述题1 写出 Wolfe-Powell 非精确一维线性搜索的公式。2 怎样判断一个函数是否为凸函数.（例如: 判断函数 是否为凸函数）21212 50)( xxxf 三、 证明题1 证明一个优化问题是否为凸规划.（例如 判断 （其中 G 是正定矩阵）是凸规划 .0 .21)(minxbAtsbxcGfT2 熟练掌握凸规划的性质及其证明.第二章 线性规划考虑线性规划问题： ,0,.min)( xbAtscLPT其中， 为给定的数据，且 rankmnnRRc, .

4、,nmA一、 判断与选择题1 (LP)的基解个数是有限的. 2 若(LP) 有最优解，则它一定有基可行解为最优解. 3 (LP)的解集是凸的. 4 对于标准型的(LP)，设 由单纯形算法产生，则对 ，有kx,210k.1kTkxc5 若 为(LP)的最优解， 为(DP)的可行解，则 * *y .*ybxcT6 设 是线性规划(LP)对应的基 的基可行解，与基变量0x ),(1mPB对应的规范式中，若存在 ，则线性规划(LP)没有最优解。m,1 0k7 求解线性规划(LP)的初始基可行解的方法：_.8 对于线性规划(LP)，每次迭代都会使目标函数值下降. 二、 简述题1 将以下线性规划问题化为标

5、准型： .0,214,6. 3)(max321322xtsxf2 写出以下线性规划的对偶线性规划：.0, ,346.4)(ma432121xxtsf三、 计算题熟练掌握利用单纯形表求解线性规划问题的方法（包括大 M 法及二阶段法）. 见书本：例 2.5.1 (利用单纯形表求解);例 2.6.1 (利用大 M 法求解); 例 2.6.2 (利用二阶段法求解).四、 证明题熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。第三章 无约束最优化方法一、 判断与选择题1 设 为正定矩阵，则关于 共轭的任意 向量必线性相关. nRGG1n2 在牛顿法中，每次的迭代方向

6、都是下降方向. 3 经典 Newton 法在相继两次迭代中的迭代方向是正交的. 4 PRP 共轭梯度法与 BFGS 算法都属于 Broyden 族拟 Newton 算法. 5 用 DFP 算法求解正定二次函数的无约束极小化问题，则算法中产生的迭代方向一定线性无关. 6 FR 共轭梯度法、PRP 共轭梯度法、DFP 算法、及 BFGS 算法均具有二次收敛性. 7 共轭梯度法、共轭方向法、DFP 算法以及 BFGS 算法都具有二次终止性. 8 函数 在 处的最速下降方向为 .Rfn:kx9 求解 的经典 Newton 法在 处的迭代方向为 .)(minxkxkp10 若 在 的邻域内具有一阶连续的

7、偏导数且 ，则 为的局)(f* 0)(*xf*x部极小点. 11 若 在 的某邻域内具有二阶连续的偏导数且 为 的严格局部)(xf* *)(f极小点，则 正定. )(*2xfG12 求解 的最速下降法在 处的迭代方向为 .)(infRxk kp13 求解 的阻尼 Newton 法在 处的迭代方向为 .mn x14 用牛顿法求解 时，至多迭代一)(21i nnTRx RGbGn ，次可达其极小点. 15 牛顿法具有二阶收敛性. 16 二次函数的共轭方向法具有二次终止性. 17 共轭梯度法的迭代方向为：_.二、证明题1 设 为一阶连续可微的凸函数， 且 ，则 为Rfn: nRx0)(xfx的全局极

8、小点.)(mixnRx2 给定 和正定矩阵 . 如果 为求解bnRGnkRx的迭代点， 为其迭代方向，且xbxfTRxn 21)(i 0nkRd为由精确一维搜索所的步长，则),0k .)(kTkkGdxf3 试证：Newton 法求解正定二次函数时至多一次迭代可达其极小点.四、 简述题1 简述牛顿法或者阻尼牛顿法的优缺点.2 简述共轭梯度法的基本思想.五、 计算题1 利用最优性条件求解无约束最优化问题.例如：求解 121213)(minxxxf 2 用 FR 共轭梯度法无约束最优化问题 .见书本：例 3.4.1.3 用 PRP 共轭梯度法无约束最优化问题.见书本：例 3.4.1.例如： 01.

9、,)( 2213)(min 011 Txxxf 中第四章 约束最优化方法考虑约束最优化问题： ,21,0)(,.min)( mlIixcEtsfNLPi 其中， .:,21(, Ricf n一、判断与选择题1 外罚函数法、内罚函数法、及乘子法均属于 SUMT. 2 使用外罚函数法和内罚函数法求解（NLP）时，得到的近似最优解往往不是（NLP）的可行解. 3 在求解（NLP）的外罚函数法中，所解无约束问题的目标函数为 . 4 在（NLP）中 ，则在求解该问题的内罚函数法中，常使用的罚函数0l为 .5 在（NLP）中 ，则在求解该问题的乘子法中，乘子的迭代公式为l，对 .ik)(1 mi,16 在

10、（NLP）中 ，则在求解该问题的乘子法中，增广的 Lagrange 函lm数为：_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 内点法的优缺点.四、证明题利用最优性条件证明相关问题. 例如： 设为正定矩阵， 为列满秩矩阵.试求规划QAbxtsaxcQfP . 21)(m

11、in)(的最优解，并证明解是唯一的.第五章 多目标最优化方法一、判断与选择题1 求解多目标最优化问题的评价函数法包括 .2 通过使用评价函数，多目标最优化问题能够转化为单目标最优化问题. 3 设 ，则 在 上的一般多目标最优化问题的数学形式mnRDF:FD为 .4 对于规划 ，设 ，若不存在TmRDx xffFVn )(,)(1i D使得 ，则 为该最优化问题的有效解. x)(x且5 一般多目标最优化问题的绝对最优解必是有效解. 6 对于规划 ，设 为相应于TmRDx xffFVn )(,)(1i iw的权系数，则求解以上问题的线性加权和法中所求解),21(mif优化的目标函数为 .7 利用求解 的线性加权和法所得到的解，TmRDx xffFVn )(,)(1i或者为原问题的有效解，或者为原问题的弱有效解. 二、简述题1 简单证明题 绝对最优解、有效解、及弱有效解之间的关系. 第 5.2 节中几个主要结论的证明.2 简单叙述题 简述求解一般多目标规划的评价函数法的基本思想. 简述求解一般多目标规划的线性加权和法的基本思想. 简述求解一般多目标规划的理想点法的基本思想. 简述在求解一般多目标规划的评价函数法中，确定权系数方法的 基本思想.