最优化方法试题 一、填空 （1）线性规划 min 2 x x  2 1 . . 2 x x s t   2 1 5 3 x x   1 2 0 x  2 4  1 的对偶规划为 （2）用外罚函数法求解问题 min ( ) f x . . s t x x 1 2  0 ，其增广目标函数为 （3）用黄金分割法求函数在[0,1]上的极小点，第一步所取的两个点为 为严格凸函数，则 a 的取值范围是 ( ) 3 f x （4）若    2 x 1 x 2 2 ax x 1 2 用 Newton 法求该函数的极小点，取 (0) x  (2,3)T ，迭代一步得到的点为 。 。 。 ， 。 （5）在最速下降法，Newton 法，FR 方法，DFP 方法，BFGS 方法中不具备二次终止性的 算法为 。 p （6）已知两个向量 1  T (1, ) , a p 2  (1, 1)  关于矩阵 T    2 1 1 3    共轭，则 a  （7）对于二次规划 2 2 min 2 2 x x  1 2 . . 2 x s t x   1 2 5 5 x x   1 2 x 1 2       4 x 1  6 x 2 x x 1 2 0 0 0 0 ，点 (0,1)T 的有效集为 x 2 写出在 (0,1)T 沿着可行域边界的一个可行下降方向： 二、 ( ) f x 为凸集 D R 上的函数，上图 ( epi n f ) {( , x y  ) | f x 为凸函数的充要条件是 ( ( ) epi ) f 为凸集。 , x D y R y   , 。 ， 。  ( )} f x ，证明 

三、设G 为 n 阶正定对称矩阵， 1 , u u 2 , R u , n n 线性无关。 kp 按如下方式生成： p 1 u ， 1 p k 1   p k  k  i 1  T u Gp 1 k i  T p Gp i i ( p k i  , , 1 2  , n  ) 1 ，证明 1 p p 2 , , p 关于G 共轭。 , n 四、（1）用单纯形方法求解下面的线性规划 min x   1 . . 2 x x s t  2 1 5 4 x x  1 2 , 0 x x  1 x 2 2 6  20  （2）若在上面的线性规划中要求变量为整数，在相应的整数规划中，请对变量 1x 写出对应 的割平面方程。 

五、用 PRP 方法求解问题 min x 2 1  2 x 2 2  2 x x 1 2  4 x ，初始点 0 x 1 ( ) ( , ) .T 1 1 六、用内罚函数法（对数罚函数）求解 min 2 x  1 . . 1 1 s t x  x 2 2 。 

七、验证 * x  ( , , )T 1 1 1 为下面问题的 KT 点， min ( f x ) ( . . s t c x 1 ) ( c x 2 ( ) c x 3 ) ( c x 4 ( ) c x 5 ) 2 2 2 2 3 x x x     3 2 1 2 2 2 3 0 x x x      2 3 1 0 x x     1 0   0   0   x 1 x x 2 2 3 。 八 、 若 线 性 规 划 x 2 x 2 2 4   x 1 x 1 min . . 3 s t x 1 , x x x 1 3 , 2  x 3 x 3 2  0  5  u  的 最 优 解 为 ( , a b c ， 其 对 偶 规 划 的 最 优 解 为 , )T (1/ 6,1/ 2)T 。 , a b c u 四个常数中，你可以确定哪些？如果有不能确定的常数，确定其范围。 , ,