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

点击翻译按钮获取中文摘要

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.