最优化理论、方法及应用试题一、（30分）1、针对二次函数1()2TT f x x Qx b x c =++，其中Q 是正定矩阵，试写出最速下降算法的详细步骤，并简要说明其优缺点？答：求解目标函数的梯度为()g x Qx b =+，()k k k g g x Qx b ==+，搜索方向：从k x 出发，沿k g -作直线搜索以确定1k x +。
Step1: 选定0x ,计算00,f gStep2: 做一维搜索, ()1min k k k tf f x tg +=-,1k k k x x tg +=-.Step3：判别，若满足精度要求，则停止；否则，置k=k+1,转步2。
优缺点：最速下降法在初始点收敛快，算法简单，在最优点附近有锯齿现象，收敛速度慢。
2、有约束优化问题min ()()0,1,2,,..()0,1,2,,i j f x g x i m s th x j l≥=⎧⎪⎨==⎪⎩最优解的必要条件是什么？答：假设*x 是极小值点。
必要条件是f ，g ，h 函数连续可微，而且极小值点的所有起作用约束的梯度(*)(1,2,,)i h x i l ∇=和(*)(1,2,,)j g x j m ∇=线性无关，则存在******1212,,,,,,,,l m αααβββ使得()11******1212**(*)*(*)*(*)0*(*)0,1,2,,,,,,,,,00,0l mi i j j i i j j l m i j f x h x g x g x j mαββαααβββαβ==∇-∇-∇===≠>≥∑∑3、什么是起作用约束？什么是可行方向？什么是下降方向？什么是可行下降方向？针对上述有约束优化问题，如果应用可行方向法，其可行的下降方向怎样确定？ 答：起作用约束：若0()0j g x =，这时点0x 处于该约束条件形成的可行域边界上，它对0x 的摄动起到某种限制作用。
可行方向：0x 是可行点，某方向p ，若存在实数00λ>，使得它对任意[]00,λλ∈，均有0x p λ+∈可行点集合，则称方向p 是点0x 的可行方向。
下降方向：某一可行点0x ，对该点的任一方向p 来说，若存在实数0'0λ>，使对任意[]00,'λλ∈均有()()00f x p f x λ+<，就称方向p 为0x 点的一个下降方向。
可行下降方向：既是可行方向，又是下降方向。
可行方向的确定：可行方向法就是沿下降容许方向搜索并保持迭代点为可行点的一种迭代方法。
二、 （25分）1、回答出n 维空间中非零向量系12,,n p p p 相互共轭的定义。
答：设Q 是n ×n 对称正定矩阵。
若n 维空间中非零向量系12,,n p p p 满足 ,,1,2,,,,i j p Qp i j n i j =≠则称12,,n p p p 是Q 共轭的，或称12,,n p p p 的方向是Q共轭方向。
2、应用共轭梯度方法求解无约束优化问题()2212min 8x x +，初始点为[]011Tx =。
答： 假设误差范围是0.001ε=。
12220,()16016x Q f x x ⎡⎤⎡⎤=∇=⎢⎥⎢⎥⎣⎦⎣⎦，初始搜索方向002()16P f x -⎡⎤=-∇=⎢⎥-⎣⎦步长：00000()()2600.06344104T Tf x f x t P QP ∇∇===，1000120.87320.06341160.0144x x t P -⎡⎤⎡⎤⎡⎤=+=+=⎢⎥⎢⎥⎢⎥--⎣⎦⎣⎦⎣⎦ 第二步迭代：1 1.7464()0.2304f x ⎡⎤∇=⎢⎥-⎣⎦，1() 1.7615f x ∇=, 10000()51.99680.01274104T T f x QP P QP α∇===，1100 1.7718()0.0272P f x P α-⎡⎤=-∇+=⎢⎥⎣⎦， 步长：11111()() 3.10300.49336.2904T Tf x f x t P QP ∇∇===21110.8732 1.77180.00080.49330.01440.02720.001x x t P --⎡⎤⎡⎤⎡⎤=+=+=⎢⎥⎢⎥⎢⎥--⎣⎦⎣⎦⎣⎦3、对于无约束优化问题()2212min 8x x +，写出其下降的牛顿方向，并应用牛顿算法迭代两步，初始点仍取为[]011Tx =。
答：102200,16016g G ⎡⎤⎡⎤=≠=⎢⎥⎢⎥⎣⎦⎣⎦，求解方程111G P g =-，111/21/16G -⎡⎤=⎢⎥⎣⎦， 11111/2211/16161P G g --⎡⎤⎡⎤⎡⎤=-=-=⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦⎣⎦。
于是211110110x x P ⎡⎤⎡⎤⎡⎤=+=-=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦。
三、（20分）1、针对有约束优化问题()0,1,2,,min (),..()0,1,2,,i jg x i mf x s t h x j l ≥=⎧⎪⎨==⎪⎩ 试构造出两种外部惩罚函数(,)F x μ。
答：(,)()()F x f x x μμα=+，其中[]2211()()()(())lmj i i j i x h x g x u g x α==⎡⎤=+⎣⎦∑∑，0,()0,x Dx x D α∈⎧=⎨>∉⎩。
其它选择[]2211()()min(0,())lmj i j i x h x g x α==⎡⎤=+⎣⎦∑∑2、最小二乘问题2min ()()()()T J x f x f x f x ==用台劳公式进行一阶线性化得()()()()k k k f x f x A x x x =+-，将问题转化为如下的问题2min k k f A P +，其中,(),()k k k k k P x x f f x A A x =-==是函数在k x 处的Jacobi 矩阵。
证明算法()11TTk k kk k k x x A A A f -+=-（1） 当T k k A A 非奇异时，方向P 是下降的（2） 当T k k A A 接近奇异时，方向1()T T k kk k k k P A A I A f α-=-+也是下降的。
其中k α是一个适当的常数。
证明：（1）即证明()0T k k J x P ∇<，()22()2()()T TT k k k kk k k J x A f A x x A x f x ∇=+-=，A （x ）是f(x)的Jacobi 矩阵，T k k k g A f =，故()2()()2T k k k k J x A x f x g ∇==，()1()2()()0T k k k k k k J x P g A x A x g -∇=-<。
（2）当T k k A A 接近奇异时，若k αs 是一个适当的常数，则1()Tkk k A A I α-+存在，从而1()2()0T k k k kk k k J x P g A A I g α-∇=-+<，因此方向1()T Tk k k k k k P A A I A f α-=-+也是下降的。
四、 （15分）求解如下的约束优化问题221221212()(2)(1)0..20f x x x x x s tx x =-+-⎧-+≥⎨--+≥⎩ 答：先求满足K-T 条件的点()()1222()21x f x x -⎡⎤∇=⎢⎥-⎣⎦，11221(),()11x g x g x --⎡⎤⎡⎤∇=∇=⎢⎥⎢⎥-⎣⎦⎣⎦， ()()1112212211221221212122(2)202(2)020020,0x x x x x x x x x x x αααααααα-++=⎧⎪--+=⎪⎪-+=⎪⎪⎨--+=⎪-+≥⎪⎪--+≥⎪≥⎪⎩，解得：1212112/32/3x x αα=⎧⎪=⎪⎨=⎪⎪=⎩ 五、（10分）将Zoutendijk 可行方向法应用于优化问题min ()x f x ∈Ω，其中{}|,x Ax b Cx d Ω=≥=中，其中A ，b,C,d 是响应的矩阵。
试给出可行下降方向和最优步长的确定方法。
答：假设x 是题中的某个容许点。
适当调换A 的行向量和b 的响应分量，然后分解'''A A A ⎡⎤=⎢⎥⎣⎦，相应的分解'''b b b ⎡⎤=⎢⎥⎣⎦，使得'',''''A x b A x b =>。
则非零向量P 为从点x 出发的容许方向向量的充要条件是'0,0A P CP ≥=。
min ().'0..011,1,2,,T j f x P A p s t CP P j n∇⎧≥⎪=⎨⎪-≤≤=⎩由此可得到的有限的最优解，设为P*，P*为点x 处的一个下降容许方向向量。
为了确定一个新的迭代点x ，可以从点x 出发沿下降容许方向P*直线搜索，即(**)min (*),**f x t P f x tP x x t P +=+=+ 最优步长t*的确定(*)min (*),..(*)()0A x tP b f x tP s t C x tP d t +≥⎧⎪++=⎨⎪≥⎩多余(*)A x tP b +≥分解成'(*)'''(*)''A x tP b A x tP b +≥+≥，简化成''(*)''min (*),..0A x tP b f x tP s t t +≥⎧+⎨≥⎩。
求可行区间：''''''*A x b tA P u tv -≥⇔≥-，u ，v 的维数与''b 相同，0u >，当0v >时，对0t ∀>，u tv ≥-总成立。
从而''''''*A x b tA P -≥成立，此时t =+∞，当0v ≤时，为使u tv ≥-成立，即(1,2,,)i i u tv i τ≥-=成立，只需考虑0i v <的不等式若取1min{0}ii i iu t v v τ≤≤=-<，则对[]0,t t ∈，都有(1,2,,)i i u tv i τ≥-=成立，从而1,0min{0},0i iii i i v t u v v v τ≤≤+∞>⎧⎪=⎨-<≤⎪⎩。