最优化方法复习题.doc

最优化方法复习题.doc《最优化方法》复****题
第一章概述(包括凸规划)
判断与填空题
arg max /■ (x) = arg min [-/Wl- V
x^Rn xeRn
max |/(x): x e D R"}= -min |/(x): x e D Rn}. x
设 f : D 匸 R" I * e R'1,对于一切 x&Rn 恒有/(%*)</(%),则称x* 为
最优化问题min /(x)
xeZ)
4设f : D j RJ * eD ,存在x*的某邻域N小,使得对一切
% e ns(.x*)恒有/(%*)< f(x),则称F为最优化问题min /W的严格局部最 x&D

5给定一个最优化问题，
6非空集合DuR"为凸集当且仅当D中任意两点连线段上任一点属于D. V
7非空集合D^R"为凸集当且仅当D中任意有限个点的凸组合仍属于D. 4

9函数f . D j R" T R为凸集D上的凸函数当見仅当—/■
10设f : D匸R" T R为凸集D上的可微凸函数，x* e D .则对Vx e D ,有 f(x)-f(x*)< Vf(x*)r(x-x*). x
11若c(x)是凹函数，则D = {xeRn\ c(x) > 0}是凸集。 V
12设{_?}为由求解minfW的算法a产生的迭代序列，假设算法a为下降算法， xeD
贝U对 Pk e {0,1, 2,…},恒有 /(xt+1)<f(xj :
13算法迭代时的终止准则(写出三种)： o
14凸规划的全体极小点组成的集合是凸集。V
15函数f : D匚R" T R在点*沿着迭代方向d* eRn\{0］进行精确一维线搜索的 步长a”，则其搜索公式为 .
16函数f : D匚R" T R在点*沿着迭代方向d* eRn\{0］进行精确一维线搜索的 步长色，则V/(x* +akdk)Tdk = 0 .
17设dk ERn\{0］为点xk &D^Rn处关于区域D的一个下降方向，则对于
\/a > 0, e (0, a)使得xk +adk e D. x
简述题
1写出Wolfe-Powell非精确一维线性搜索的公式。
2怎样判断一个函数是否为凸函数.
(例如:判断函数/(x) = +2x,x2 +2x1 — IO" +5*2是否为凸函数)
三、证明题
1证明一个优化问题是否为凸规划.(例如
min f(x) = —xTGx + cTx + b
2
判断s./. Ax = b (其中G是正定矩阵)是凸规划.
x>0
2熟练掌握凸规划的性质及其证明.
第二章线性规划
考虑线性规划问题：
(LP) min cT x
. Ax = b, x > 0,
其中，
ceRn, AeRmxn, b e Rm 为给定的数据，且 rank4 =朋,m < n.
、
判断与选择题
1
(LP)
2
若(LP)有最优解，
3
(LP)
4
对于标准型的(LP),设｛*｝由单纯形算法产生，则对kw｛0,l,2,..],有
cTxk >cTxk+1. X