几何规划与凸规划有何不同?

计算科学 优化 凸优化
2021-12-03 06:10:57

(广义)几何规划与一般凸规划有何不同?

几何程序可以转化为凸程序,通常通过内点法求解。但是,与直接将问题表述为凸程序并通过内点法求解相比,有什么优势呢?

几何程序类是否仅构成凸程序类的子集,可以通过内点方法特别有效地求解?或者仅仅是一个通用几何程序可以很容易地以计算机可读形式指定的优点。

另一方面,是否存在几何程序不能很好地近似的凸程序?

2个回答

在这个问题之前,我实际上从未听说过几何编程。是 Stephen Boyd等人(Vandenberghe 也是合著者)的一篇评论论文,它是关于几何规划的教程。

最初表达的几何程序不是凸的。例如,是一个多项式,并且它不是凸的,因此几何程序不是凸规划的严格子集。x1/2

将几何程序转化为凸程序的好处是原始几何程序不一定是凸程序。如果您将几何程序作为非线性程序 (NLP) 求解,则需要使用非凸优化方法以保证全局最优解。这些方法比凸优化方法更昂贵,需要更多的算法调整,并且需要初始猜测。

此外,如果您使用来自非凸 NLP 的算法,则需要在中将可行集指定为紧凑集;在几何程序中,是一个有效的约束。Rnx>0

目前尚不清楚这组几何程序是否(通过对数指数变换)映射到一组求解特别有效的凸程序。除了转换为凸程序之外,我认为几何编程没有任何优势。

至于你的最后一个问题,我不认为几何程序集与凸程序集同构,所以我怀疑存在不能表示为几何程序的凸程序,而在这些程序中,我怀疑有是一些几何程序无法很好地近似的。但是,我没有证据或反例。

几何规划可以转化为一类凸程序,它是所有凸程序集合的严格子集。然而,任意凸程序不能表示为几何程序。几何规划中的约束被限制为的形式,其中多项式(即具有正系数的多项式)。多项式在加法、乘法和缩放下是封闭的。现在,如果您考虑约束,那么f(x)1f(x)xy1xy本身不是多项式。它不能表示为多项式的加法/乘法,也不能是另一个多项式的正缩放。因此它不能成为几何程序的一部分。但是上面的约束是线性的,因此程序是凸的。确实存在混合线性几何规划,其中可以添加任意线性约束,但也可以转换为凸程序并有效求解。由于与上述相同的原因,即使通过混合线性几何规划也无法处理更复杂的约束,例如x2y21