8.4极值体积椭圆

1. Lowner-John椭球
2. 最大体积内接椭球
3. 椭球逼近的效率

Lowner-John椭球

包含集合C的最小体积椭球被成为集合C的Lowner-John椭球，记为，为方便描述的特征，将一般的椭球参数化为

即Euclid球在仿射映射下的原象。可以不是一般性地假设，此时的体积正比于。计算包含C的最小体积椭球的问题可以表述为：

其中，且存在一个隐含约束。目标函数和约束函数都是凸函数，问题是凸问题。

覆盖有限集合的最小体积椭球

考虑改了有限集合的最小体积椭球问题。一个椭球覆盖C当且仅当覆盖起凸包，因此寻找覆盖C的最小体积椭球，相当于寻找多面体的最小体积椭球。于是此问题可以表述为：

其中，且存在一个隐含约束。

最大体积内接椭球

考虑寻找C中具有最大体积的椭球问题，假设C有界且非空。将椭球参数化为单位球在仿射变换下的象：

再一次假设，于是体积正比于，于是问题可以表述为：

其中，于是约束函数可以理解为。

多面体中的最大体积椭球

考虑C是由线性不等式是哟面熟的多面体。于是

于是问题可以表述为

椭球逼近的效率

Lowner-John椭球逼近的效率

令是有界且内部非空的凸集的Lowner-John椭球，是其中心，如果我们讲Lowner-John椭球向起中心收缩比例n，可以得到一个位于C中的椭球：

如上图，外面的椭圆是集合C的Lowner-John椭球的边界，内部的椭球是按比例n=2向中心缩小得到的椭球的边界。可以保证该椭球在集合C内部。

最大体积内接球逼近的效率

如果是凸、有界且内部非空的，那么将最大体积内接椭球对其中心进行扩展n倍将覆盖集合C，如果C关于一点是对称的，那么倍数n可以收紧为

 

如上图，内部的椭球是最大体积内接椭球，外部的椭圆显示了将内接椭球对其中心扩大n=2倍所得的边界。