标题: 几何规划问题之全域最佳化方法
Global Optimization Methods for Generalized Geometric Programming Problems
作者: 蔡荣发
Jung-Fa Tsai
黎汉林
Han-Lin Li
资讯管理研究所
关键字: 全域最佳化;几何规划;凸策略;逐段线性;Global optimization;Generalized Geometric Programming;Convexification strategies;Piecewise linearization
公开日期: 2002
摘要: 广义几何规划(Generalized Geometric Programming)问题在管理与工程上的应用十分普遍。本研究运用逐段线性化(Piecewise Linearization)与凸化策略(Convexification Strategies)求解各种类型的几何规划问题,以得全域最佳解(Global Optimum)。本研究先将一几何规划问题转换成一仅包含凸函数(Convex)与凹函数(Concave)的问题,再用逐段线性技术将凹函数转化为线性整数函数,则原问题就变成一个包含整数变数的凸规划(Convex Programming)问题,再以传统的分支界定法(Branch and Bound)或外部逼近(Outer Approximation)演算法求得全域最佳解。本研究也提出两种分散式运算方法求解投资组合与封装最佳化问题。本研究主要的特点有:
(1)相较于启发式方法(如:Genetic Algorithm, Simulated Annealing, Tabu Search等),本文所提方法可证明能求得问题的全域最佳解或近似全域最佳解。
(2)相较于一般指数变换法(Exponential-based decomposition) (Duffin et al., 1967; Floudas, 1999a, 1999b, 2000),本文所提方法能处理有非正(Non-positive)变数的问题。
(3)相较于Floudas提出的方法,本文所提凸化策略能快速求解不同类型之几何规划问题。
Generalized geometric programming (GGP) problems occur frequently in management and engineering science. This study utilizes piecewise linearization techniques and convexification strategies for solving GGP problems to obtain a globally optimal solution. Different optimization techniques are developed for various types of GGP problems. A GGP problem is first converted into a program which only contains convex and/or concave functions. Each of these concave functions is transformed into linear 0-1 inequalities using piecewise linearization techniques. The original problem then becomes a convex programming problem with mixed integer variables solvable by utilizing Branch and Bound or Outer Approximation algorithm to reach a global optimum. Two distributed computation schemes are also developed for solving portfolio and packing optimization problems. The advantages of the proposed methods over current approaches are given below.
(i)Compared with the heuristic algorithms (i.e., Genetic Algorithm, Simulated Annealing, Tabu Search etc.), the proposed method is guaranteed to find a global optimum of a GGP problem.
(ii)Compared with the exponential-based decomposition techniques (Duffin et al., 1967; Floudas, 1999a, 1999b, 2000), the proposed method can treat GGP problems containing non-positive variables.
(iii)The proposed method is more computationally efficient than Floudas’ methods for solving some GGP problems using convexification strategies.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT910396008
http://hdl.handle.net/11536/70281
显示于类别:Thesis