幾何規劃問題之全域最佳化方法

Abstract

廣義幾何規劃(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.