幾何規劃之全域最佳化新法及其管理與工程之應用
Abstract
許多管理與工程設計問題多可轉化為幾何規劃(Generalized Geometric Program)問題。GGP問題若以一般數值方法如牛頓法(Newton』s method)、基因演算法(genetic algorithm)、類神經網路法(neuro-net methods)求解，常只能得到局部最佳解(local optimum)。如何求解非線性模式以求得全域最佳解，是近十年來最佳化領域的重要課題。目前最常用的全域最佳化法為指數轉化法(exponential-based method)。此法缺點有二：一為變數不許可為零或負數，另一為引用的0-1變數太多以致計算時間甚長。本研究用意在深入探討全域最佳化理論與方法，如凸形化(convexification)、值域減化(range reduction)、乘積線性化(product linearization)、分支價量(branch-price)等，以發展新一代的全域最佳化解法。此一新方法將與目前常用的全域最佳化軟體(如LINGO)相比較，並以之應用於求解機械與土木設計問題、決策球問題、基因序列定址問題等
Many management and engineering problems can be reformulated as generalized geometric programming (GGP) problems. Resolving GGP problems by traditional methods such as Newton』s methods, genetic algorithms and neuro-net methods may only find locally optimal solutions. How to treat GGP problems to find globally optimal solutions is one of critical issues in the optimization field. Currently, a widely used method for solving nonlinear models to obtain the globally optimal solution is the exponential-based approach (Maranas and Floudas, 1997; Floudas, 1999; Floudas2000). Floudas』 approach, however, has two drawbacks. Firstly, the variables within that approach are not allowed to be non-positive. Secondly, Floudas』 approach requires embedding large number of binary variables, which causes heavy computational burden. This study intends to investigate the related theories of global optimization thus to develop a novel method for solving GGP problems. These theories include convexification, range reduction, product linearization and branch-and-price algorithms. The developed method will also be applied to solve the engineering design problems, the decision-ball problem, and the DNA consensus sequence identification problems.
Many management and engineering problems can be reformulated as generalized geometric programming (GGP) problems. Resolving GGP problems by traditional methods such as Newton』s methods, genetic algorithms and neuro-net methods may only find locally optimal solutions. How to treat GGP problems to find globally optimal solutions is one of critical issues in the optimization field. Currently, a widely used method for solving nonlinear models to obtain the globally optimal solution is the exponential-based approach (Maranas and Floudas, 1997; Floudas, 1999; Floudas2000). Floudas』 approach, however, has two drawbacks. Firstly, the variables within that approach are not allowed to be non-positive. Secondly, Floudas』 approach requires embedding large number of binary variables, which causes heavy computational burden. This study intends to investigate the related theories of global optimization thus to develop a novel method for solving GGP problems. These theories include convexification, range reduction, product linearization and branch-and-price algorithms. The developed method will also be applied to solve the engineering design problems, the decision-ball problem, and the DNA consensus sequence identification problems.