权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

非凸结构几何优化问题实用算法研究

基本信息

批准号：
05650061
负责人：
KUNO Takahito
金额：
$ 1.02万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至 1994
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-05650061/
关键词：
Mathematical Programming Global optimization Nonconvex function Computational Geometry Algorithm

项目摘要

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.

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