非凸規劃問題之全域最佳化系統

A Global Optimization System for Nonconvex Programming Problems

莊勝淵(Sheng-Yuan Chuang)

指導教授 ： 蔡榮發

國立臺北科技大學/管理學院/商業自動化與管理研究所/碩士(2007年)

https://doi.org/10.6841/NTUT.2007.00133

摘要

雖然已經有許多最佳化方法和建模工具可求解廣義幾何規劃問題，但是他們在解決實務問題時，仍然耗費過多的運算時間，更重要的是他們沒有辦法保證求得問題之全域最佳解。為了解決上述問題，本研究期望改良現有的凸化方法，設計出更有效率的全域最佳化方法幫助企業實現最佳的資源分配。在理論上，本研究運用凸化策略與凸下界將廣義幾何規劃問題轉換成凸規劃問題，並且透過分支界定法說明本文所提方法可求得問題之全域最佳解。在計算上，則將本文所提方法與LINGO NLP Solver整合成全域最佳化系統，如此，不僅可以克服LINGO無法保證求解品質的缺點，更大大增加本研究的價值。
此外，為了證明本文所提方法優於現有的最佳化方法，我們用文獻上的範例測試，實驗結果發現：（1）不同於Tsai提出的方法，本文用凸下界取代逐段線性技術能解決逐段線性技術須事先決定斷點的困難；（2）相較於BARON，本文所提方法能用更好的下界將廣義幾何規劃問題轉換成凸規劃問題。

關鍵字

全域最佳化 ； 廣義幾何規劃 ； 凸化策略 ； 凸下界

並列摘要

Although many algorithms and packages which can solve generalized geometric programming problems have been proposed, most of them are too time consuming and cannot guarantee to obtain a global optimum. To overcome the difficulties, this study would like to improve current optimization approaches and attempt to merge these ideas to suit the needs of strategic models. Theoretically, this study utilizes convexification strategies and convex underestimation to convert the source problem into a convex program. A global optimum can then be found by a branch-and-bound algorithm. Computationally, this study develops a global optimizer with embedded LINGO NLP Solver capable of deriving solutions with better quality.
Moreover, several numerical examples are used to demonstrate the effectiveness of the developed optimizer. The results of experiments show: (1) compared with Tsai’s methods, this study uses convex underestimation instead of piecewise linearization technique to alleviate the difficulty in deciding the number of break points in advance; (2) the developed optimizer can yield tighter convex relaxations than BARON for solving some generalized geometric programming problems.

並列關鍵字

Global Optimization ； Generalized Geometric Programming ； Convexification Strategies ； Convex Underestimation

參考文獻

[1]Avriel, M. and Williams, A.C., An extension of geometric programming with applications in engineering optimization, Journal of Engineering Mathematics, 1971, 5(2), 187-194.

[2]Björk, K.M. and Westerlund, T., Global optimization of heat exchanger network synthesis problems with and without the isothermal mixing assumption, Computers and Chemical Engineering, 2002, 26, 1581-1593.

[3]Björk, K.M., Lindberg, P.O. and Westerlund, T., Some convexifications in global optimization of problems containing signomial terms, Computers and Chemical Engineering, 2003, 27, 669-679.

[4]BARON Release 7.7.2, GAMS Development Corp., Washington, DC, 2006.

[5]Faina, L., A global optimization algorithm for the three-dimensional packing problem, European Journal of Operational Research, 2000, 126, 340-354.