Global Minimization of Nonconvex Functions and Its Applications to Social Systems

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

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.