Global Minimization of Nonconvex Functions and Its Applications to Social Systems

非凸函数的全局最小化及其在社会系统中的应用

• 批准号: 03832018
• 负责人: KONNO Hiroshi
• 金额: $ 1.22万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1991
• 资助国家: 日本
• 起止时间: 1991 至 1992
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-03832018/
• 关键词: Global optimization; Nonconvex minimization; Outer approximation method; Parametrization; Convex mulitiplicative program; Bilinear programming problem; Nonconvex duality; Average polynomial order algorithm; 非〓型最適化; 分解原理; 非〓集合の次数; パレート最適化; 多目的最

In 1989, we succeeded in solving the minimization problem of a product of two affine functions on a polytope. This result was soon extended to the minimization of a sum and a product of two fractional functions. The key idea behind these algorithms is the combination of parametrization and outer approximation. We extended this approach to several other global optimization problems including (a) minimization of the product of several convex functions, (b) minimization of a generalized convex multiplicative functions, (c) lower rank bilinear programming problems, (d) minimization of a convex function subject to linear multiplicative constraints. Also, we proved a surprising result that the algorithm for (c) is a an average-polynomial order algorithm. Also, we applied the result of (c) to a class of problems in computational geometry. In addition, we proposed (e) a decomposition algorithm for a class of global optimization problems with a decomposable structure, (f) an outer approximation algorithm for d.c. programming problems with low nonconvexity rank.Further, we studied mathematical structures of global optimization problems. Some of the important results are (g) duality theory for d.c. programming problems, and (h) degree of nonconvexity of nonconvex functions and nonconvex sets in Hilbert space.

1989年，我们成功地解决了多型仿射功能的产物的最小化问题。该结果很快扩展到了两个分数函数的总和和产物的最小化。这些算法背后的关键思想是参数化和外部近似的组合。我们将这种方法扩展到其他几个全局优化问题，包括（a）最小化多个凸功能的乘积，（b）最小化广义凸乘函数的最小化，（c）较低的等级双线性编程问题，（d）最小化convex功能受线性乘法约束的约束。另外，我们证明了（c）的算法是平均多项式阶算法的令人惊讶的结果。另外，我们将（c）的结果应用于计算几何形状的一类问题。此外，我们提出了（e）一种具有可分解结构的全局优化问题的分解算法，（f）D.C.的外近似算法。编程问题较低的非概念排名。算，我们研究了全球优化问题的数学结构。一些重要的结果是（g）Duality理论的二元理论。编程问题，以及（H）Hilbert Space中非凸功能和非covex集的非概念性程度。

项目成果

今野 浩,田辺 国士,藤田 宏: "岩波応用数学講座「最適化」" 岩波書店, (1992)

Hiroshi Konno、Kunio Tanabe、Hiroshi Fujita：“岩波应用数学课程‘优化’”岩波书店，（1992）

P.T.Thach: "A Nonconvex Duality with a Zero Gap and Applicotions" SIAM J.of Optimization. (1993)

P.T.Thach：“零间隙的非凸对偶及其应用”SIAM J.of Optimization。

KONNO,H.and SUZUKI,K.: "A Fast Algorithm for Solving Large-Scale Mean-Variance Model by Compad Factiorization of Cavanance Matrices" J.of the Operations Research Society of Japan. 35. 93-104 (1992)

KONNO,H. 和 SUZUKI,K.：“通过卡凡斯矩阵的 Compad 分解求解大规模均值方差模型的快速算法”，日本运筹学会杂志。

P. T. Thach: "A Nonconvex Duality with a Zero Gap and Applications" SIAM J. of Optimization. (1993)

P. T. Thach：“零间隙的非凸对偶及其应用”SIAM J. of Optimization。

Konno,H.,Kuno,T.and,Yajima: "Parametric Sumplex Algotithms for a Class of NP Complete Problems Whose Average Number of Steps is Polynomial" J.of Computational Optivization and Applications. 1. 1 (1992)

Konno,H.、Kuno,T. 和 Yajima：“平均步骤数为多项式的一类 NP 完全问题的参数求和算法”J.of 计算优化与应用。