A convergent simplicial algorithm with ω-subdvision and ω-bisection strategies
A convergent simplicial algorithm with ω-subdvision and ω-bisection strategies
复制标题
具有 ω 细分和 ω 二分策略的收敛单纯形算法
DOI：
10.1007/s10898-011-9746-6
复制
发表时间：
2012
影响因子：
1.8
通讯作者：
P.E.K.Buckland
中科院分区：
文献类型：
--
作者：
T.Kuno;P.E.K.Buckland
单纯形算法是一种求凸极大化问题全局最优解的分枝定界方法。它在ω-细分策略下的收敛性在几十年来一直是一个悬而未决的问题，直到Locatelli和Raber证明了它（J Optim Theory Appl 107：69-79，2000）。本文对他们的线性规划松弛法进行了修正，并给出了一个不同的、更简单的收敛性证明。我们还开发了一种新的收敛细分策略，并报告了与现有的策略进行比较的数值结果。
The simplicial algorithm is a kind of branch-and-bound method for computing a globally optimal solution of a convex maximization problem. Its convergence under theω-subdivision strategy was an open question for some decades until Locatelli and Raber proved it (J Optim Theory Appl 107:69–79, 2000). In this paper, we modify their linear programming relaxation and give a different and simpler proof of the convergence. We also develop a new convergent subdivision strategy, and report numerical results of comparing it with existing strategies.