A convergent simplicial algorithm with ω-subdivision and ω-bisection strategies

摘要

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 co-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.