多項式規劃之最佳化系統設計

Abstract

多線性規劃(Signomial Programming)已被廣泛地使用在各種領域，例如：工程設計、財務規劃、物流及運輸等。本研究的主要目的在於提出一套完整的系統架構，得以整合傳統的數學理論，例如：凸化近似(convex underestimation)、逐段線性法(piecewise linearization )；以及啟發式演算法，例如：基因演算法(genetic algorithm)。並再搭配分散式計算處理和改良式的演算法，將非線性規劃問題加以拆解並交由將一群個人電腦加以計算，最後再彙整得出全域最佳解。本系統的優點在於：

1、相較於傳統的數學方法而言求解過程得以更有效率。 2、克服啟發式演算法無法保證答案品質的缺點。 3、相對於目前的平行計算，成本更低，而且不受限於作業系統。 4、整合現有的最佳化軟體，除了可以使系統運作得以更加穩定、有效率之外，也能夠處理更廣泛的問題。

Signomial programming techniques have been applied in many areas such as Engineering Design, Financial planning and Transportation. Deterministic and heuristic approaches are two popular methods to deal with the Signomial programming problem. Either of the two methods has its own strengths and weaknesses. This study proposes a framework integrating deterministic programming approaches (e.g., convexification and piecewise linearization) and heuristic approaches (e.g., genetic algorithm). Furthermore, the proposed system is enhanced by several refurbished algorithms. The core of the proposed system is a distributed processing mechanism which decomposes the problem into independent pieces. Distributes these sub problems to a group of available personal computers, and compare the solutions found by these individual computers to conclude the globally optimal solution for the generalized signomial problems. In sum, the proposed system contributes to the current literature in the following aspects: 1. Compared to traditional deterministic approaches, the new system can handle problems with higher efficiency. 2. Relative to heuristic approaches which suffer from instable solution quality, it can guarantee solutions with better quality. 3. The proposed distributed processing mechanism is OS independent with incredible cost-savings compared to the currently available parallel processing system. 4. The system integrates existent high-performance optimization software packages, which enables it to handle more general problems in a stable and efficient manner.