椭球法

前面讨论过椭球法是第一个证明具有多项式时间求解线性规划问题的算法,尽管这个算法本身的常数项很大,但是还是有一些理论意义的,这里讨论一下相关的方法,参考这里

椭球法使用一系列的椭球框定最优值的范围,每次由梯度方向确定搜索的范围(梯度相当于是一个超平面的法方向),这等价于认为最优值在椭球的另一半中,我们计算出来包含另一半椭球的最小体积的椭球,这样就更新了对最优值的估计(新的椭球球心)。这样就涉及到这样一个问题,给定当前的椭球 E_t =\{ x\in\mathbb{R}^n \mid (x - x_t)^\top P_t^{-1} (x - x_t) \leq 1\},超平面划分出的半平面 F_t = \{ x \in \mathbb{R}^n \mid g_t^\top (x - x_t) \leq 0,确定 x_{t + 1}P_{t + 1}

wiki 上写了个更新公式,但是不清楚是怎么得到了:

  • 计算 g = \frac{1}{\sqrt{g_t^\top P_t g_t}} g_t
  • 计算新的中心 x_{t+1} = x_t - \frac{1}{n + 1} P_t g
  • 计算新的二次型 P_{t + 1} = \frac{n^2}{n^2 - 1} \Big( P_t - \frac{2}{n} P_t g g^\top P_t\Big)

显然收敛条件可以用 \sqrt{g_t P_t g_t} \leq \varepsilon。在具有约束条件(线性不等式)的情况下,似乎要去某个 subgradient,但是没看明白这个 subgradient 是干啥的 -,-b 看起来这个理论好办,看懂也不容易啊… 有空想想看看能想出来不,感觉还少个条件。

——————–
No, my lord, hear me: the field give I you, and the cave that is therein, I give it you; in the presence of the sons of my people give I it you: bury your dead.

Advertisements
椭球法

一个有关“椭球法”的想法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s