mi 1 m *m j * g j (x*) 0最优化理论、方法及应用试题一、(30 分)1、针对二次函数f(x) 1x T Qx b T x c，其中Q是正定矩阵，试写出最速下降算法的详细步骤，并简要说明其优缺点？答：求解目标函数的梯度为g(x) Qx b，g k g(x k) Qx k b，搜索方向：从X k出发，沿g k作直线搜索以确定x k 1。
Stepl:选定X。
,计算f o,g oStep2:做一维搜索，f k i min f X k tg k , x k 1 X k tg k.Step3 :判别，若满足精度要求，则停止；否则，置 k=k+1,转步2优缺点：最速下降法在初始点收敛快，收敛速度慢。
算法简单，在最优点附近有锯齿现象,2、有约束优化问题min f (x)g i(x) 0,i 1,2,L ,ms.th j (x) 0,j 1,2,L ,l最优解的必要条件是什么？答：假设x*是极小值点。
必要条件是f，g，h函数连续可微，而且极小值点的所有起作用约束的梯度h(x*)(i 1,2丄，1)和g j(x*)( j 1,2,L ,m)线性无关，则* * * *存在1 , 2丄，I, 1, 2丄，m,使得lf(x*) i* h i(x*)i 1j*g j(x*) 0,j 1,2,L* * * * *1 ,2 ,L , l , 1 , 2 ,L ,*0, j 03、什么是起作用约束？什么是可行方向？什么是下降方向？什么是可行下降方向？针对上述有约束优化问题，如果应用可行方向法，其可行的下降方向怎样确定？答：起作用约束：若g j(x0) 0，这时点x0处于该约束条件形成的可行域边界上,它对x0的摄动起到某种限制作用可行方向：x0是可行点，某方向 p，若存在实数0 0,使得它对任意2、应用共轭梯度方法求解无约束优化问题 min X 28X |，初始点为X 0 1 1 丁 。
答：假设误差范围是0.001。
0 16f(X )2为 16X2，初始搜索方向F2f(X0)16步长:tTf °(x) f °(x)F 0T QP °2604104 0.0634，X 1 X 01 0.063412 160.8732 0.0144 第二步迭代:1.7464 f(X1)0.2304f(N )1.7615,Tf(X 1)QF 0P )T QP 。
5!昱68 0.0127, P 1 4104f (X i )0P1.7718 0.0272 ，步长： t 1皿 0.4933P T QP6.29040, 0，均有x 0p 可行点集合，则称方向p 是点X 0的可行方向。
下降方向：某一可行点X 0，对该点的任一方向p 来说，若存在实数o '0 , 使对任意 0, 01均有f X 0p f X 0，就称方向p 为X 0点的一个下降方 向。
可行下降方向：既是可行方向，又是下降方向。
可行方向的确定：可行方向法就是沿下降容许方向搜索并保持迭代点为可行 点的一种迭代方法。
(25 分)1、回答出n 维空间中非零向量系口，卩2丄P n 相互共轭的定义。
答：设C 是n x n 对称正定矩阵。
若n 维空间中非零向量系 山心丄p n满足pQP j ,i,j 1,2,L ,n, i j,则称丄p .是Q 共轭的,或称山心丄p .的方向是Q共轭方向。
x 2x 1t | P0.8732 0.01440.49331.7718 0.0008 0.02720.0013、对于无约束优化问题 min x 2 8x 2，写出其下降的牛顿方向, 并应用牛顿算 法迭代两步，初始点仍取为 TX o 1 1 。
答: g 1160,GQ0 16，求解方程G 1Rg 1， G 1 11/21/16 '1/2 1/16 216于是x 2X11、针对有约束优化问题 min f(x),stg i (x) h j (x)0,i 0,j1,2,L ,m 1,2,L ,l答：F(x,)f(x) (x)(x) h j (x)2g(x) u(g i (x))，(x)0,x 0,x其它选择(x)h j (x)mi n(0,g i (x))i 1将问题转化为如下的(20 分)试构造出两种外部惩罚函数F(x,)2、最小二乘问题mi nJ (x) f T (x) f (x) f (x)用台劳公式进行一阶线性化得f(x) f(x k) A(x k)(x x k)，问题2min | f k AP|| ，其中P x x k, f k f (x k), A k A(x k)是函数在x k处的Jacobi矩阵。
证明算法2)当 A k A k 接近奇异时，若 kS 是一个适当的常数，则(NA k1kI ) 存在，从而 J(x k )P k2g k (A k A kk I) 1g k 0，因此方向 P k ( A k T A kkI ) A k f k 也是答：先求满足 K-T 条件的点 f(x)2 x 1 2 2 x 2 1g 1 ( x)2x 1, g 2( x)1 2 x1x 22 x1x220，解得2x 12x 2x 1x22 0x 11x 21 1 2/32 2/3x| Ax b,Cx d(1) 当A ：A k 非奇异时，方向P 是下降的(2) 当A T A k 接近奇异时，方向R (A ：A kkI)1A l f k 也是下降的。
其中k是一个适当的常数。
证明：(1)即证明 J T(x k )P k 0，J(x k ) 2A k T f k 2A k T (x x k ) 2A T(x k ) f(x k )，A ( x)是 f(x)的 Jacobi 矩阵，g kA kT f k，故 J(xQ 2A T (x k) f (x k) 2g k,T1J(x k )P k2g k A T(x k )A(x k ) g k 0。
下降的。
四、 (15 分) 求解如下的约束优化问题 f(x) (x 1 2)2(x 2 1)2 x 12x 2s.t.x 1 x 22 02(x 12) 21x 1 22(x 22)1 2五、 (10分)将Zoutendijk 可行方向法应用于优化问题 min f (x)，其中x中，其中A ，b,C,d 是响应的矩阵。
试给出可行下降方向和最优步长的确定方法。
答：假设 x 是题中的某个容许点。
适当调换 A 的行向量和 b 的响应分量，然后分解 A A' b'A''，相应的分解b b''，使得A'x宀咲"'。
则非零向量P 为从点 x 出发的容许方向向量的充要条件是 A'P 0,CP 012b' b''tP*) b''。
min f T (x)P.A'p 0 st CP 01 P j 1,j 1,2,L ,n由此可得到的有限的最优解，设为 P*, P*为点x 处的一个下降容许方向向量。
为了确定一个新的迭代点 %可以从点x 出发沿下降容许方向P*直线搜索, 即 f(x t*P*) minf(x tP*), x x t* P* 最优步长t*的确定A(x tP*) bmin f (x tP*), st C(x tP*) d(多余)t 0, A'(x tP*)A(x tP *) b分解成 A''(x tP*)A''(x，简化成 minf (x tPg t 0求可行区间：A''x 时，对t 0，u 时，为使u b'' tA'' P* tv 总成立。
tv 成立，即u i u tv , u ， 从而 A''x b'' tv i (i 1,2,L , v 的维数与b''相同，u tA''P*成立，此时t )成立，只需考虑vi ' i 0，当 v 0 ，当v 0 0的不等式 若取r m in{u i V i V i 0｝，则对 t 0,F ，都有 u i tv i (i 1,2,L ,)成立，从而 tmi n{Uiv i 0}, v i 0。