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.