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

A study on global optimization algorithms for multiplicative programming problems

乘法规划问题的全局优化算法研究

基本信息

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

项目摘要

In this research, we studied practical algorithms for solving multiplicative programming problems, a class of optimization problems involving products of some convex functions. Although this class is known as a typical multi-extremal global optimization problem, we showed that it is possible to design efficient algorithms both in theoretical and practical senses, by exploiting its special structures. A few of the results are listed below :1 We studied a problem maximizing a single linear function over an efficient set. This problem is associated with multi-criteria decision making and belongs to multi-extremal global optimization. When the number of criteria is up to three, we showed that the problem can be solved efficiently in the same way as the low-rank linear multiplicative programming problem.2 We developed a finite branch-and-bound algorithm for minimizing a product of several affine functions over a polyhedral set. Since the logarithm of the objective function is separable into … More a sum of concave functions, we use this special structure and propose a rectangular branch-and-bound algorithm. We carried out bounding operations in two stages to strengthen the lower bound. The computational result indicated that the algorithm is remarkably efficient.3 The sum-of-linear-ratio problem is an important subclass of multiplicative programming problems. We developed a rectangular branch-and-bound algorithm for solving this problem. Since the number of ratios is less than ten in most applications, we carried out branching operations in the vector space of ratios. As a result, we could obtain globally optimal solutions much efficiently than using the existing algorithms.4 When using the branch-and-bound algorithm to solve multiplicative programming problems, we need to solve linear and/or quadratic programming problems iteratively. Therefore, the procedure for linear and/or quadratic programming problems seriously affects on the efficiency of the algorithm. We then studied some iterative algorithms for the linear complementarity problem, the class of these problems, and showed their worst-case computational complexity. Less

在这项研究中，我们研究了解决乘法规划问题的实用算法，乘法规划问题是一类涉及某些凸函数乘积的优化问题。尽管此类被称为典型的多极值全局优化问题，但我们表明，通过利用其特殊结构，可以在理论和实践意义上设计有效的算法。下面列出了一些结果：1 我们研究了在有效集合上最大化单个线性函数的问题。该问题与多准则决策相关，属于多极值全局优化。当标准数量达到三个时，我们表明可以采用与低秩线性乘法规划问题相同的方式有效地解决该问题。2我们开发了一种有限分支定界算法，用于最小化多面体集合上多个仿射函数的乘积。由于目标函数的对数可分解为凹函数之和，因此我们使用这种特殊结构并提出了矩形分支定界算法。我们分两个阶段进行了边界操作，以强化下界。计算结果表明该算法非常高效。3线性比和问题是乘法规划问题的一个重要子类。我们开发了一种矩形分支定界算法来解决这个问题。由于大多数应用中比率的数量少于十个，因此我们在比率向量空间中进行分支操作。因此，我们可以比使用现有算法更有效地获得全局最优解。4当使用分支定界算法解决乘法规划问题时，我们需要迭代地解决线性和/或二次规划问题。因此，线性和/或二次规划问题的处理过程严重影响算法的效率。然后，我们研究了线性互补问题的一些迭代算法、这些问题的类别，并展示了它们最坏情况的计算复杂度。较少的