《最优化方法》复习题.docx

《最优化方法》复****题
一、 简述题
1、 怎样判断一个函数是否为凸函数•
（例如：判断函数f（x） • 2x1x2 - 2x2 -10X! 5x2是否为凸函数）
2、 写出几种迭代的收敛条件.
3、 熟练掌握利用单纯形表求解线性规划问题的方法 （包括大M法及二阶段法）
见书本61页（利用单纯形表求解）；
69页例题（利用大M法求解、二阶段法求解）;
4、 简述牛顿法和拟牛顿法的优缺点.
简述共轭梯度法的基本思想.
写出Goldstein、Wolfe非精确一维线性搜索的公式。
5、 叙述常用优化算法的迭代公式.
："
已=ak +i(bk —aQ.
f
人=ak +卩心亠(bk —aQ,
Fib on acci法的迭代公式：彳 心十 (k = 1,2,川，n—1).
-k 二 ak (bk - ak)
[ F n_k 卅
Newton一维搜索法的迭代公式： Xk = x^G^ gk •
1
推导最速下降法用于问题 min f(x)二-xTGx - bTx c的迭代公式：
2
T
xk 1 =Xk gf7rk f (xk)
9k Gk gxk
Newton法的迭代公式：Xk .1 =Xk -p 2 f (xj]七 f (Xk).
1
（6）共轭方向法用于问题min f（x） bTx c的迭代公式:
dkTQdk
、计算题
双折线法练****题 课本135页
FR共轭梯度法例题：课本150页
二次规划有效集：,
所有留过的课后****题
二、练****题：
1、 设A运R仪是对称矩阵，b € Rn, c e R ,求f (x) = *丁 Ax + bTx + c在任意点x处 的梯度和Hesse矩阵.
解 ' f (x)二 Ax b, I f (x)二 A .
2、 设「()=f(x d ),其中 f ：Rn》R 二阶可导，Rn,d • Rnt R ,试求;：(t).
解 ：(t)八 f(x td)Td,「(t)二 dT'、2f (x td)d .
3、 证明：凸规划min f(x)的任意局部最优解必是全局最优解.
证明 (x)的局部最优解，即存在x的某
X辛
个：邻域N (x)，使f (xH f (x), -x •叫.(刃门S .若x不是全局最优解，则存在
x S，使f (x) ：：： f (x).由于f(x)为S上的凸函数，因此
-'(0,1)，有
f( ■ x (1 - •)x>「f 仅)(1 一’ )f (x^： f (x).
当■充分接近1时，可使・x (1 —，)x N」x)ns，于是f(x)乞f( x (1-，)x)，
.
min f (x) =2為 _x2 十花；
3x1 十 X2 +怡兰 60,
4、 已知线性规划：* x^ -2x2 +2x3 <10,
为+屜一X3兰20,
I X1,X2,X3》0.
用单纯形法求解该线性规划问题；
写出线性规划的对偶问题；
解 (1)引进变量X4,X5,X6，将给定的线性规划问题化为标准形式：
min f (x) = 2片 _x2 + x3;
3捲 +x2 +x3 +x4 =60,
’为—2x2+2x3+X5 =10,
N 十乂？ —X3 +X5 =20,
为兀，川必KO.
所给问题的最优解为X二(0, 20,0)T，最优值为亍=_20 .
(2)所给问题的对偶问题为：
”maxg(y) =-60y)-10y2 -20y3;
- 3yi - y2 - y3 一 2,
' 一 yi +2y2 — y3 兰一1,
-2丫2 + y3 兰1，
[ 力丛以ho.
, 初
5、「(t) =(t -3)2，要求缩短后的区间长度不超过
始区间取[0,10] •
解第一次迭代：
取⑻力]=[0,10], ； 72 .
确定最初试探点'1,^1分别为
1 =印 (0 —aj = ,・Vai (6—6)= .
求目标函数值： 「1)=( -3)2 = ,:(叫)=( -3)2 = .
比较目标函数值：(J」*).
比较叫 = -0 =；.
第二次迭代：
a2 =a<i =0, d =叫=, "2 = \ =, '("2) = (\) = .
2
■2 二 a2 (5 —a2)=( -0) = , (■ 2)=