图 2.1 椭球法的迭代过程
对使得 )(xf 最小化的问题,它的椭球法求解算法如下:
Step 0:设 V∈0x ,
mS∈0P 是正定矩阵,定义椭球
}1)()(:{ 0
1
0
T
00 ≤−−∈=
− xxPxxx VE
Step k:对 ...,2,1=k
1.计算 f 在 1−kx 处的次梯度
m
k R∈−1g ,并记
1k kR V E −= I
T
1 1{ : ( ) 0 }k k− −− ≤x g x xI
2.计算 Vk ∈x 和 0>kP ,使得椭球
}1)()(:{ 1T ≤−−= − kkkkE xxPxxx
包含 kR 。以下的 kx 和 kP 具有这样的性质:
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
+
−
−
=
+
−=
−−−−
−−−
−
−−−
−−
−
1
T
111
11
T
1
12
2
11
T
1
11
1
)1(
2
1
)1(
kkkk
kkk
kk
kkk
kk
kk
mm
m
m
PggP
gPg
PP
gPg
gP
xx
3.重复 Step k。
2.3.2 内点法
内点法是求解线性矩阵不等式问题的一个更为有效的算法。它的主要思路是:利用约
束条件定义一个闸函数,该函数在可行域内部是凸的,在可行域外部则定义其值为无穷
大。通过在目标函数中添加这样一个闸函数,使得原先的约束优化问题转化成一个无约束
1