修订过的最优化方法复习题.doc

《最优化方法》复习题

第一章 引论
一、 判断与填空题
1 √
2

3 设 若，对于一切恒有，则称为最优化问题的全局最优解.

4 设 若，存在的某邻域，使得对一切恒有，则称为最优化问题的严格局部最优解.

5 给定一个最优化问题，那么它的最优值是一个定值. √

6 非空集合为凸集当且仅当中任意两点连线段上任一点属于. √
7 非空集合为凸集当且仅当中任意有限个点的凸组合仍属于. √

8 任意两个凸集的并集为凸集.
9 函数为凸集上的凸函数当且仅当为上的凹函数. √
10 设为凸集上的可微凸函数，. 则对有
11 若是凹函数，则是凸集。 √

12 设为由求解的算法A产生的迭代序列，假设算法A为单调下降算法，则对，恒有 .
13 算法迭代时的终止准则（写出三种）：_____________________________________。

14 凸规划的全体极小点组成的集合是凸集。 √

15 函数在点沿着迭代方向进行精确一维线搜索的步长，则其搜索公式为 .

16 函数在点沿着迭代方向进行精确一维线搜索的步长，则 0 .

17 设为点处关于区域的一个下降方向，则对于，使得

二、 简述题
1 写出Wolfe-Powell非精确一维线性搜索的公式。

2 怎样判断一个函数是否为凸函数.
（例如: 判断函数是否为凸函数）

三、 证明题
1 证明一个优化问题是否为凸规划.（例如
判断（其中G是正定矩阵）是凸规划.

2 熟练掌握凸规划的性质及其证明.

第二章 线性规划

考虑线性规划问题：

其中， 为给定的数据，且rank

一、 判断与选择题
1 (LP)的基解个数是有限的. √

2 若(LP)有最优解，则它一定有基可行解为最优解. √

3 (LP)的最优解集是凸的. √

4 对于标准型的(LP)，设由单纯形算法产生，则对，有 ×

5 若 为(LP)的最优解， 为(DP)的可行解，则 √

6 设是线性规划(LP)对应的基的基可行解，与基变量对应的规范式中，若存在，则线性规划(LP)没有最优解。×

7 求解线性规划(LP)的初始基可行解的方法：____________________.

8 对于线性规划(LP)，每次迭代都会使目标函数值下降. ×

二、 简述题
1 将以下线性规划问题化为标准型：

2 写出以下线性规划的对偶线性规划：

三、 计算题
熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法）.
见书本：
例2.3.1 (利用单纯形表求解);
例2.3.2 (利用大M法求解);
例2.3.3 (利用二阶段法求解).

四、 证明题
熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。

第三章 无约束优化方法

一、 判断与选择题
1 设为正定矩阵，则关于共轭的任意向量必线性相关. √
2 在牛顿法中，每次的迭代方向都是下降方向. ×
3 经典Newton法在相继两次迭代中的迭代方向是正交的. ×
4 PRP共轭梯度法与BFGS算法都属于Broyden族拟Newton算法. ×
5 用DFP算法求解正定二次函数的无约束极小化问题，则算法中产生的迭代方向一定线性无关. √
6 FR共轭梯度法、PRP共轭梯度法、DFP算法、及BFGS算法均具有二次收敛性. ×
7 共轭梯度法、共轭方向法、DFP算法以及BFGS算法都具有二次终止性. √
8 函数在处的最速下降方向为 .
9 求解的经典Newton法在处的迭代方向为 .
10 若在的邻域内具有一阶连续的偏导数且，则为的局部极小点. ×
11 若在的某邻域内具有二阶连续的偏导数且为的严格局部极小点，则正定. ×
12 求解的最速下降法在处的迭代方向为 .
13 求解的阻尼Newton法在处的迭代方向为 .
14 用牛顿法求解时，至多迭代一次可达其极小点. ×
15 牛顿法具有二阶收敛性. √
16 共轭方向法、共轭梯度法具有二次终止性. √
17共轭梯度法的迭代方向为：_____________________.

二、证明题
1 设为一阶连续可微的凸函数，且，则为的全局极小点.
2 给定和正定矩阵. 如果为求解的迭代点， 为其迭代方向，且为由精确一维搜索所的步长，则
3 试证：古典Newton法求解正定二次函数时至多一次迭代可达其极小点.
四、 简述题
1 简述牛顿法的优缺点.
2 简述共轭方向法的基本思想.
五、 计算题
1 利用最优性条件求解无约束最优化问题.
例如：求解
2 用FR、PRP共轭梯度法求解无约束最优化问题.
见书本：例3.4.1.
例如：
3 利用DFP算法求解无约束最优化问题.

第四章 约束优化方法

考虑约束最优化问题：

其中，

一、判断与选择题
1 外罚函数法、内罚函数法、及乘子法均属于SUMT. √

2 使用外罚函数法和内罚函数法求解（NLP）时，得到的近似最优解往往不是（NLP）的可行解. ×

3 在求解（NLP）的外罚函数法中，所解无约束问题的目标函数为 .

4 在（NLP）中，则在求解该问题的内罚函数法中，常使用的罚函数为 .

5 在（NLP）中，则在求解该问题的乘子法中，乘子的迭代公式为 ，对.

6 在（NLP）中，则在求解该问题的乘子法中，增广的Lagrange函数为：_________________________________

7 对于(NLP)的KT条件为：_______________

二、计算题
1 利用最优性条件(KT条件)求解约束最优化问题.

2 用外罚函数法求解约束最优化问题.
见书本：例4.4.1；

3 用内罚函数法求解约束最优化问题.
见书本：例4.4.3.

4 用乘子法求解约束最优化问题.
见书本：例4.4.5；
三、简述题
1 简述SUMT外点法的优缺点.

2 简述SUMT内点法的优缺点.
四、证明题
利用最优性条件证明相关问题.
例如：设为正定矩阵，为列满秩矩阵.试求规划
的最优解，并证明解是唯一的.

第五章 多目标规划简介

一、判断与选择题
1 求解多目标最优化问题的评价函数法包括 .

2 通过使用评价函数，多目标最优化问题能够转化为单目标最优化问题. √

3 设，则在上的一般多目标最优化问题的数学形式为 .

4 对于规划，设，若不存在使得，则为该最优化问题的有效解. √

5 一般多目标最优化问题的绝对最优解必是有效解. √

6 对于规划，设为相应于的权系数，则求解以上问题的线性加权和法中所求解优化的目标函数为 .

7 利用求解的线性加权和法所得到的解，或者为原问题的有效解，或者为原问题的弱有效解. √

二、简述题
1 简单证明题
☆ 绝对最优解、有效解、及弱有效解之间的关系.
l 第5.2节中几个主要结论的证明.

2 简单叙述题
★ 简述求解一般多目标规划的评价函数法的基本思想.
l 简述求解一般多目标规划的线性加权和法的基本思想.
★ 简述求解一般多目标规划的理想点法的基本思想.
l 简述在求解一般多目标规划的评价函数法中，确定权系数方法的 基本思想.