Global Minimization of Nonconvex Functions and Its Applications to Social Systems

1989年，我们成功地解决了多面体上两个仿射函数乘积的最小化问题。这个结果很快被推广到两个分式函数的和和乘积的最小化问题。这些算法背后的关键思想是参数化和外逼近的结合。我们将这种方法推广到其他几个全局优化问题，包括(A)几个凸函数乘积的最小化，(B)广义凸乘函数的最小化，(C)低阶双线性规划问题，(D)受线性乘法约束的凸函数的最小化。此外，我们还证明了一个令人惊讶的结果：(C)的算法是一个平均多项式阶算法。同时，我们将(C)的结果应用于计算几何中的一类问题。此外，我们还提出了(E)一类具有可分解结构的全局优化问题的分解算法，(F)D.C.的外逼近算法。在此基础上，研究了全局优化问题的数学结构。其中一些重要结果是(G)D.C.的对偶理论。以及(H)非凸函数和非凸集在Hilbert空间中的非凸性。

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.