权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

非线性非凸规划问题的全局/启发式算法研究

基本信息

批准号：
15560048
负责人：
KUNO Takahito
金额：
$ 1.66万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2004
项目状态：
已结题

项目摘要

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.

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