A study on global/heuristic algorithm for nonlinear nonconvex programming problems

作为求解非凸规划的全局/启发式混合算法的原型，我们首先提出了一种通过局部搜索来收紧上界的分枝定界算法。我们的目标是在任何强制终止时，使现任人员的质量与现有启发式方法的质量一样高。然而，在收敛之前，它比没有局部搜索的算法需要更多的计算时间；此外，现任者的质量并不像我们预期的那么好。然后，我们放弃了局部搜索程序，而是设计了另一个程序，分两个阶段收紧下限。(A)线性比率和问题，(B)低阶非凸性的凹极小化问题，(C)具有凹性生产成本的生产-运输问题，以及(D)设计化工过程所需的二次可微非凸规划.计算结果表明，在(A)和(B)的每个算法的早期阶段，现任者变得等于全局最优解.这意味着我们的算法服务于高质量的启发式算法。我们还发现，作为全局优化算法，这些算法在计算时间上比现有的算法要高效得多。至于(C)和(D)，虽然利用它们的特殊结构在效率上仍有改进的空间，但我们可以认识到我们的算法在实际应用中的潜力。此外，我们还研究了内点方法在松弛问题中的应用，得到了一些从理论上有利的结果。

As a prototype of the global/heuristic hybrid algorithm for solving nonconvex programs, we first developed a branch-and-bound algorithm in which upper bounds were tightened by local search. Our aim was to make the quality of the incumbent as high as those of existing heuristics at any forced termination. However, it turned out to take more computational time than algorithms without local search before convergence ; and besides the quality of the incumbent was not so good as we expected. We then dropped the local search procedure and instead designed another procedure for tightening lower bounds in two phases. We further customized it for the following and ran the resulting algorithms on them :(a)linear sum-of-ratios problems,(b)concave minimization problems with low-rank nonconvexities,(c)production-transportation problems with concave production costs, and(d)twice-differentiable nonconvex programs needed for designing chemical processes.Computational results indicated that the incumbent becomes equal to a globally optimal solution at an early stage of each algorithm for (a) and (b). This implies that our algorithms serve high-quality heuristics. We also found that as global optimization algorithms those are much more efficient than existing ones in computational time. As for (c) and (d), though there was still room for improvement in efficiency by exploiting their special structures, we could recognize potential of our algorithms for practical use. In addition, we studied the application of interior-point methods to relaxed problems solved repeatedly in our algorithms, and obtained some results favorable from the theoretical points of view.