No label defined (Q4550775)

The authors study the concave minimization problem (CP): \(\min \{f(x)\mid x\in P\}\), where \(f\) is a concave function defined on \(\mathbb{R}^n\) and \(P\) is full-dimensional polytope of \(\mathbb{R}^n\). The motivation for the study is the observation by \textit{P. B. Zwart} [Nonlinear programming counterexamples to two global optimization algorithms, Oper. Res. 21, 1260--1266 (1973; Zbl 0274.90049)] that the conical algorithm proposed by \textit{H. Tui} [Concave programming under linear constraints, Sov. Math., Dokl. 5, 1437--1440 (1965; Zbl 0132.40103)] is not finitely convergent as also the possibility of cycling. Thereafter a number of conical partitioning algorithms were developed and shown to be convergent but the question of cycling remained unanswered. The authors here propose a finite cone covering algorithm that prevents cycling. This is achieved by a subdivision process which is shown to have a descent property. For the entire collection see [Zbl 0988.00046].