A Research on Practical Algorithms for Geometrical Optimization Problems with Nonconvex Structure

在这项研究中，我们研究了一些实用的算法来解决某些非凸结构的几何优化问题。我们将全局优化技术应用于平面上的问题，并构造了一些算法来获得全局最优解。主要结果如下：1.二阶逆凸规划的全局优化：给出了一种求解由两个线性无关的n维向量所定义的拟凹约束函数的逆凸规划的算法。计算实验表明，与已有算法相比，该算法能够有效地产生全局最优解。2.多面体上二阶鞍形函数的全局最小化：我们提出了一种由二维鞍形函数和n维仿射函数组成的复合函数的极小化算法。计算实验表明，该算法解决了较大规模的网络优化问题，并研究了一类非凸网络优化问题。为了有效地解决这些问题，我们使用了计算几何作为算法的一些步骤。3.生产运输问题的全局优化：提出了一类生产运输问题的伪多项式时间算法，将一个给定的问题分解为若干个凸子问题。这种求解策略也可以应用于许多其他类型的优化问题。

In this research, we studied some practical algorithme for solving certain classes of geometrical optimization problems with nonconvex structure. We applied global optimization techniques to the problems in the plane and constructed some algorithms for obtaining a globally optimal solution. A few of the results are as follows :1.Globally optimization of rank-two reverse convex programs : We proposed an algorithm for solving reverse convex program which contains a quasiconcave constraint function defined by two linearly independent n-dimensional vectors. The computational experiments indicated that the algorithm can generate globally optimal solutions very efficiently compared with any existing algorithms.2.Globally minimization of rank-two saddle functions on a polytope : We proposed an algorithm for minimizing a composite function of a two-dimensional saddle function and n-dimensional affine functions. The computational experiments indicated that the algorithm solves fairly large scale problems.In addition to the above problems, we studied a class of nonconvex network optimization problems. To solve the problems efficiently, we used computational geometry as some procedures of the algorithm. As a result, we obtained the following :3.Globally optimization of production-transportation problems : We proposed a pseudopolynomial-time algorithm for solving a class of production-transportation problem.All the above mentioned algorithms decompose a given problem into several convex subproblems. This solution strategy can also be applied to many other classes of optimization problems.