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

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

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.