《最优化方法》复习题第一章 引论一、 判断与填空题1)].([arg )(arg m in m ax x f x f n n R x R x -=∈∈ √ 2{}{}.:)(min :)(max n n R D x x f R D x x f ⊆∈-=⊆∈ ⨯3 设.:R R D f n →⊆ 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题)(min x f D x ∈的全局最优解. ⨯4 设.:R R D f n →⊆ 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f Dx ∈的严格局部最优解. ⨯5 给定一个最优化问题，那么它的最优值是一个定值. √6 非空集合n R D ⊆为凸集当且仅当D 中任意两点连线段上任一点属于D . √7 非空集合nR D ⊆为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √8 任意两个凸集的并集为凸集. ⨯9 函数R R D f n →⊆:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √10 设R R D f n →⊆:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈∀，有).()()()(***-∇≤-x x x f x f x f T ⨯11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。

√12 设{}kx 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为单调下降算法，则对{} ,2,1,0∈∀k ，恒有 )()(1k k x f x f ≤+ .13 算法迭代时的终止准则（写出三种）：_____________________________________。

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

√15 函数R R D f n →⊆:在点kx 沿着迭代方向}0{\n k R d ∈进行精确一维线搜索的步长k λ，则其搜索公式为 .16 函数R R D f n →⊆:在点k x 沿着迭代方向}0{\n k R d ∈进行精确一维线搜索的步长k α，则=+∇k T k k k d d x f )(α 0 .17 设}0{\n k R d ∈为点n k R D x ⊆∈处关于区域D 的一个下降方向，则对于0>∀α，),0(αα∈∃使得.D d x k k ∈+α ⨯二、 简述题1 写出Wolfe-Powell 非精确一维线性搜索的公式。

2 怎样判断一个函数是否为凸函数.（例如: 判断函数2122212151022)(x x x x x x x f +-++=是否为凸函数）三、 证明题1 证明一个优化问题是否为凸规划.（例如 判断0 ..21)(min ≥=++=x bAx t s b x c Gx x x f T T （其中G 是正定矩阵）是凸规划.2 熟练掌握凸规划的性质及其证明.第二章 线性规划考虑线性规划问题：,0,..min )(≥=x b Ax t s xc LP T其中，m n m n R b R A R c ∈∈∈⨯,, 为给定的数据，且rank .,n m m A ≤=一、 判断与选择题1 (LP)的基解个数是有限的. √2 若(LP)有最优解，则它一定有基可行解为最优解. √3 (LP)的最优解集是凸的. √4 对于标准型的(LP)，设{}k x 由单纯形算法产生，则对{} ,2,1,0∈k ，有.1+>k T k T x c x c ×5 若*x 为(LP)的最优解，*y 为(DP)的可行解，则.**y b x c T T ≥ √6 设0x 是线性规划(LP)对应的基),,(1m P P B =的基可行解，与基变量m x x ,,1 对应的规范式中，若存在0<k σ，则线性规划(LP)没有最优解。

×7 求解线性规划(LP)的初始基可行解的方法：____________________.8 对于线性规划(LP)，每次迭代都会使目标函数值下降. ×二、 简述题1 将以下线性规划问题化为标准型：.0,0,2,1242,6..32)(max 32321321321321≥≥≥+-≥++≤+++-=x x x x x x x x x x x t s x x x x f2 写出以下线性规划的对偶线性规划：.0,,,,3342,6342..423)(max4321432143214321≥≥+++-=++++++=x x x x x x x x x x x x t s x x x x x f三、 计算题熟练掌握利用单纯形表求解线性规划问题的方法（包括大M 法及二阶段法）.见书本：例2.3.1 (利用单纯形表求解);例2.3.2 (利用大M 法求解);例2.3.3 (利用二阶段法求解).四、 证明题熟练掌握对偶理论（弱对偶理论、强对偶理论以及互补松弛条件）及利用对偶理论证明相关结论。

第三章 无约束优化方法一、 判断与选择题1 设n n R G ⨯∈为正定矩阵，则关于G 共轭的任意1+n 向量必线性相关. √2 在牛顿法中，每次的迭代方向都是下降方向. ×3 经典Newton 法在相继两次迭代中的迭代方向是正交的. ×4 PRP 共轭梯度法与BFGS 算法都属于Broyden 族拟Newton 算法. ×5 用DFP 算法求解正定二次函数的无约束极小化问题，则算法中产生的迭代方向一定线性无关. √6 FR 共轭梯度法、PRP 共轭梯度法、DFP 算法、及BFGS 算法均具有二次收敛性. ×7 共轭梯度法、共轭方向法、DFP 算法以及BFGS 算法都具有二次终止性. √ 8 函数R R f n →:在k x 处的最速下降方向为 . 9 求解)(min x f nR x ∈的经典Newton 法在k x 处的迭代方向为=k d .10 若)(x f 在*x 的邻域内具有一阶连续的偏导数且0)(*=∇x f ，则*x 为的局部极小点. ×11 若)(x f 在*x 的某邻域内具有二阶连续的偏导数且*x 为)(x f 的严格局部极小点，则)(*2*x f G xx ∇=正定. ×12 求解)(min x f nR x ∈的最速下降法在k x 处的迭代方向为=k d .13 求解)(min x f nR x ∈的阻尼Newton 法在k x 处的迭代方向为=k d .14 用牛顿法求解)(21min n n n T T R x R G R b x b Gx x n ⨯∈∈∈+，时，至多迭代一次可达其极小点. ×15 牛顿法具有二阶收敛性. √16 共轭方向法、共轭梯度法具有二次终止性. √17共轭梯度法的迭代方向为：_____________________.二、证明题1 设R R f n →:为一阶连续可微的凸函数，n R x ∈*且0)(=∇*x f ，则*x 为)(min x f n R x ∈的全局极小点.2 给定n R b ∈和正定矩阵n n R G ⨯∈. 如果n k R x ∈为求解x b Gx x x f T T R x n +=∈21)(min 的迭代点， {}0\n k R d ∈为其迭代方向，且),0[∞+∈k α为由精确一维搜索所的步长，则.)()(kT k kT k k Gd d d x f ∇-=α 3 试证：古典Newton 法求解正定二次函数时至多一次迭代可达其极小点.四、 简述题1 简述牛顿法的优缺点.2 简述共轭方向法的基本思想.五、 计算题1 利用最优性条件求解无约束最优化问题. 例如：求解121222122123)(min x x x x x x f --+= 2 用FR 、PRP 共轭梯度法求解无约束最优化问题.见书本：例3.4.1. 例如：01.0,)0,0( 22123)(min 01212221==--+=εT x x x x x x x f 其中 3 利用DFP 算法求解无约束最优化问题.第四章 约束优化方法考虑约束最优化问题：{}{},,,2,1,0)(,,,2,1,0)(..)(min )(m l l I i x c l E i x c t s x f NLP i i ++=∈≥=∈=其中，.:),,2,1(,R R m i c f n i →=一、判断与选择题1 外罚函数法、内罚函数法、及乘子法均属于SUMT. √2 使用外罚函数法和内罚函数法求解（NLP ）时，得到的近似最优解往往不是（NLP ）的可行解. ×3 在求解（NLP ）的外罚函数法中，所解无约束问题的目标函数为 .4 在（NLP ）中0=l ，则在求解该问题的内罚函数法中，常使用的罚函数为 .5 在（NLP ）中0=l ，则在求解该问题的乘子法中，乘子的迭代公式为=+1k i λ ，对{}m i ,,1 ∈.6 在（NLP ）中l m =，则在求解该问题的乘子法中，增广的Lagrange 函数为：_________________________________7 对于(NLP)的KT 条件为：_______________二、计算题1利用最优性条件(KT条件)求解约束最优化问题.2用外罚函数法求解约束最优化问题.见书本：例4.4.1；3用内罚函数法求解约束最优化问题.见书本：例4.4.3.4用乘子法求解约束最优化问题.见书本：例4.4.5；三、简述题1简述SUMT外点法的优缺点.2简述SUMT内点法的优缺点.四、证明题利用最优性条件证明相关问题.例如：Q设为正定矩阵，A为列满秩矩阵.试求规划bxAt saxcQxxxfP=+ += TT T..21 )(min)(的最优解，并证明解是唯一的.第五章 多目标规划简介一、判断与选择题1 求解多目标最优化问题的评价函数法包括 .2 通过使用评价函数，多目标最优化问题能够转化为单目标最优化问题. √3 设m n R R D F →⊆:，则F 在D 上的一般多目标最优化问题的数学形式为 .4 对于规划T m R D x x f x f x F V n))(,),(()(1m in =-⊆∈，设D x ∈*，若不存在Dx ∈使得)()()()(**≠≤x F x F x F x F 且，则*x 为该最优化问题的有效解. √5 一般多目标最优化问题的绝对最优解必是有效解. √6 对于规划T m R D x x f x f x F V n))(,),(()(1m in =-⊆∈，设i w 为相应于),,2,1(m i f i =的权系数，则求解以上问题的线性加权和法中所求解优化的目标函数为 .7 利用求解T m R D x x f x f x F V n))(,),(()(1m in =-⊆∈的线性加权和法所得到的解，或者为原问题的有效解，或者为原问题的弱有效解. √二、简述题1简单证明题☆绝对最优解、有效解、及弱有效解之间的关系.●第5.2节中几个主要结论的证明.2简单叙述题★简述求解一般多目标规划的评价函数法的基本思想.●简述求解一般多目标规划的线性加权和法的基本思想.★简述求解一般多目标规划的理想点法的基本思想.●简述在求解一般多目标规划的评价函数法中，确定权系数方法的基本思想.。