A study on global optimization algorithms for multiplicative programming problems

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

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