A study on efficient algorithms for nonlinear nonconvex network programming problems

在这项研究中，我们研究了某些非凸费用网络流问题，并提出了产生全局最优解的有效算法。主要结果如下：1在通常的两端网络中，我们提出了一种最小化总运输费用和同时最大化总流的方法。为此，我们对这两个值的乘积进行了优化，证明了连续最短路径算法在伪多项式时间内得到了全局最优解，在多项式时间内得到了几乎最优解。2.提出了一种伪多项式算法来求解一个等价于最多三个非线性变量的带能力的最小凹费用流问题的生产运输问题。该算法分为两个阶段：第一阶段产生一个可行解；第二阶段从可行解开始，用与求解最小线性费用流问题相同的方法寻找全局最优解。3我们扩展了文2中求解该问题的思想，在伪多项式时间内求解了一个带有附加反凸约束的最大流问题。我们首先应用二进制搜索过程来产生最优解的候选者，然后使用类似于文2的算法来检验其全局最优性。所有上述算法都是利用问题所具有的低阶(拟)凹性来设计的，并且在实际和理论意义上都是有效的。我们推广了这种特殊的问题结构，得到了如下结果：4我们证明了多个凸目标规划可以归结为单个非凸目标规划，并给出了产生全局最优解的外逼近算法。计算实验表明，当目标个数少于5个时，该算法是有效的。

In this research, we studied certain classes of nonconvex cost network flow problems and proposed efficient algorithms for generating globally optimal solutions. A few of the results are listed below :1 In the usual two-terminal network, we proposed a method for minimizing the total transportation cost and for simultaneously maximizing the total flow. To accomplish it, we optimized the product of these two values and showed that a successive shortest path algorithm yields a globally optimal solution in pseudo-polynomial time and an epsilon-optimal solution in polynomial time.2 We developed pseudo-polynomial algorithm to solve a production-transportation problem equivalent to the capacitated minimum concave cost flow problems with at most three nonlinear variables. The algorithm consists of two phases : the first phase generates a feasible solution ; starting from it, the second phase searches for a globally optimal solution in the same way as solving a minimum linear-cost flow problem3 We extended the idea used to solve the problem in 2 and solved a maximum flow problem with an additional reverse convex constraint in pseudo-polynomial time. We first applied a binary search procedure to generate a candidate for an optimal solution, and then checked its globally optimality using the algorithm similar to the one in 2.All the above mentioned algorithms were designed by exploiting low-rank (quasi) concavity possessed by the problems, and were shown to be efficient in both practical and theoretical senses. We generalized this special problem structure and obtained the following result :4 We showed that a multiple convex objective program can be reduced to a single nonconvex objective program, and developed an outer approximation algorithm for generating a globally optimal solution. Computational experiments indicated that the algorithm is practically efficient when the number of objectives is less than five.