最优化方法(试题+答案)
一、 填空题
1
．
若
()()???
? ??+????
?????? ??=212121
312112)(x x x x x x x f ，则
=?)(x f ，=?)(2x f .
２．设f 连续可微且0)(≠?x f ，若向量d 满足 ，则它是f 在x 处的一个下降方向。
3.向量T
)
3,2,1(关于3阶单位方阵的所有线性无关的共轭向量
有 ．
4. 设R R f n
→:二次可微，则f 在x 处的牛顿方向为 . 5.举出一个具有二次终止性的无约束二次规划算
法: .
6.以下约束优化问题：
)(01)(..)(min 212121
≥-==+-==x x x g x x x h t s x x f
的K-K-T 条件为：
.
7．以下约束优化问题：
1
..)(min 212
2
21=++=x x t s x x x f
的外点罚函数为(取罚参数为μ) .
二、证明题（７分+8分)
1.设1,2,1,:m i R R g n i =→和m m i R R h n
i ,1,:1+=→都是线性函数,证明下
面的约束问题:
}
,,1{,
0)(},1{,
0)(..)(min 1112
m m E j x h m I i x g t s x x f j i n
k k
+=∈==∈≥=∑=
是凸规划问题。
2.设R R f →2
:连续可微，n i R a ∈,R h i ∈,m i ,2,1=,考察如下的约束条件问题:
}
,1{,0}
2,1{,0..)
(min 11m m E i b x a m I i b x a t s x f i T i i T
i +=∈=-=∈≥-
设d 是问题
1
||||,0,0..)(min ≤∈=∈≥?d E i d a I
i d a t s d x f T
i T
i T
的解，求证：d 是f 在x 处的一个可行方向。
三、计算题（每小题１2分)
１.取初始点T x )1,1()
0(=.采用精确线性搜索的最速下降法求解下面的无约束优化问题
(迭代２步）:
2
2212)(m in x x x f +=
2.采用精确搜索的BFGS 算法求解下面的无约束问题：
212
2212
1)(min x x x x x f -+=
3.用有效集法求解下面的二次规划问题:
.
0,001..42)(min 21212
12
221≥≥≥+----+=x x x x t s x x x x x f
4．用可行方向算法(Zoutend ｉj ｋ算法或Ｆrank Wol ｆｅ算法）求解下面的问题（初值设为)0,0()
0(=x
,计算到)2(x 即可）：
.
0,033..22
1)(min 212112
22121≥≥≤+-+-=
x x x x t s x x x x x x f
参考答案
一、填空题 １. ???
?
??++++3421242121x x x x ???
?
??4224 ２. 0)(
3. T
)0,1,2(-，T
)1,0,3(-(答案不唯一)。 4. )()(12
x f x f ??--
５. 牛顿法、修正牛顿法等(写出一个即可） 6.
)(,0,00
10021),,(21212121=-≥-≥=+-?
??
?
??=???? ??-+-=?x x x x x x x x L x λλμλμλμλ
７． 2212
22
1)1(2
1
)(-++
+=x x x x x F μμ 二、证明题
１.证明：要证凸规划，即要证明目标函数是凸函数且可行域是凸集。
一方面,由于f 二次连续可微，I x f 2)(2
=?正定，根据凸函数等价条件可知目标函数是凸函数。
另一方面，约束条件均为线性函数，若任意D y x ∈,可行域，则
E
i y h x h y x h I i y g x g y x g j j j i i i ∈=-+=-+∈≥-+=-+0
)()1()())1((0)()1()())1((αααααααα
故D y x ∈-+)1(αα，从而可行域是凸集。
2.证明：要证d 是f 在x 处的一个可行方向，即证当D x ∈，n
R d ∈时，0>?δ，使得
D d x ∈+α，],0(δα∈
当I i ∈时，0≥-i T
i b x a ，0≥d a T
i ,故0)(≥+-=-+d a b x a b d x a T
i i T
i i T
i αα； 当E i ∈时，0=-i T
i b x a ，0=d a T
i ，故0)(=+-=-+d a b x a b d x a T
i i T
i i T
i αα. 因此,d 是f 在x 处的一个可行方向。
三、计算题
1.解:2
222
11)(2)()()(d x d x d x f ααααφ+++=+= 令0)('=αφ 得2
2
2
1221122d d x d x d ++-=α；???
?
??=?2142)(x x x f
第一次迭代： ???
? ??=?42)()0(x f ,?
??
?
??--=-?=42)()
0()0(x f d , )()()
0()0(d x f ααφ+=,令0)('=αφ,求得18/50=α；
第二次迭代：?????? ??-=+=9194)
0(0)0()1(d x x α，?????? ??-=?9298)()1(x f ，?????
? ??-=-?=9298)()1()1(x f d ， )()()1()1(d x f ααφ+=，令0)('=αφ,求得2/11=α,故????
??=+=00)1(1)1()2(d x x α,由于
???
? ??=?00)()2(x f ,故)
2(x 为最优解。
2.解:取T x
)1,1()
0(= I B =0
????
??--=?12
212)(x x x x x f
第一步迭代:
?
???
??=?10)()0(x f ?
??
? ??-=?-=-10)()0(1
0)0(x f B d ，
ααααφ+-+=+=2)0()0()1(2
1)()(d x f ，令0)('=αφ，求得2/10=α；
第二步迭代：
????? ??=+=211)
0(0)0()1(d x x α，????? ??=?021)()1(x f ，???
?
?
??-=-=210)0()1()0(x x s
???
?
?
??-=?-?=121)()()0()1()
0(x f x f y
??
????--=??????--+??????-??????=2112/32112/1100010011B
-=)
1(d ????
?
?
??--=?-4121)()1(1
1x f B ，)()()1()1(d x f ααφ+=,令0)('=αφ，求得21=α。故
???? ??=+=00)
1(1)
1()
2(d
x
x
α，由于???
? ??=?00)()2(x f ，故)2(x 为最优解。
３. 解:取初始可行点(0)
(0)0(0,0),(){2,3}.x
A A x ===求解等式约束子问题
22
1212
12min 24..0,0
d d d d s t d d +--==
得解和相应的Lagr ａnge 乘子
(0)(1)(0)10(0,0),(2,4)(0,0),\{3}{2}
T T
T d x x A A λ==--====故得
转入第二次迭代。求解等式约束子问题
22
1212
1min 24..0
d d d d s t d +--=
得解
(1)(1)(1)(1)
111(1)(1)(0,2)0
1min{1,1,3,0}2
T T T T i i i T T i i d b a x b a x i a d a d a d α=≠--==<==
计算
令
(2)
(1)(1)121(0,1),{1}{1,2}T x
x d A A α=+===
转入第三次迭代。求解等式约束子问题
22
1212
121min 22..0,0
d d d d s t d d d +--+==
得解和相应的Lagr ａnge 乘子
(2)(0,0),(2,0)T T
d λ==
由于(2)
0λ
≥，故得所求二次规划问题的最优解为
(2)
(0,1)T x x *
==，
相应的Ｌa ｇr ａnge 乘子为 (2,0,0)T
λ*=
４．解：计算梯度得
T x x x x x f )2,22()(1221---=?
当0=k 时，)0,0()
0(=x
,T x f )0,2()(-=?．)0(y 是下面线性规划问题的解:
.
0,033..2)(min 21211)0(≥≥≤+-=?y y y y t s y y x f
解此线性规划(作图法）得T y
)0,3/2()
0(=,于是T x y d )0,3/2()0()0()0(=-=．由线性搜索
t t td x f t 3
4
92)(min 2)0()0(1
0-=
+≤≤
得10=t .因此,T d t x x
)0,3/2()0(0)0()
1(=+=．重复以上计算过程得下表：