椭球法的迭代过程-linux 运维手册

图 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 内点法 内点法是求解线性矩阵不等式问题的一个更为有效的算法。它的主要思路是：利用约 束条件定义一个闸函数，该函数在可行域内部是凸的，在可行域外部则定义其值为无穷 大。通过在目标函数中添加这样一个闸函数，使得原先的约束优化问题转化成一个无约束