逐段線性與凸下界方法之研究

A Study of Piecewise Linearization and Convex Underestimation Methods

蔡梅玉(Mei-Yu Tsai)

指導教授 ： 蔡榮發

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

摘要

許多管理或工程上的問題都建構成非線性規劃(nonlinear programming, NLP)模式，各種求解非線性規劃問題的方法也陸續被提出，由於非線性規劃問題包含許多區域最佳解(local optimum)，故要求解非線性規劃問題之全域最佳解(global optimum)就變得比較困難。因此，本研究整理出三個實用且保證可以在一個使用者可接受的誤差範圍內，得到全域最佳解的方法，並依此三種方法發展出一套自動化產生最佳化數學規劃模式的系統，而且以實際應用問題作為測試，並比較此三種確定性全域最佳化方法(deterministic global optimization methods)的特性和效率。

關鍵字

全域最佳化 ； 逐段線性 ； 凸下界

並列摘要

Many problems in management and engineering are constructed as nonlinear programming models. Various nonlinear programming techniques have been proposed in the past. Since the nonlinear programming models contain a lot of local optimal solutions, current methods have difficulty to obtain a globally optimal solution. This study presents three deterministic global optimization methods for nonlinear programming problems. The three methods guarantee to find a global optimum within a tolerable error. Moreover, an optimization system is developed to construct the mathematical model according to the three optimization methods automatically. Finally, practical examples are presented to compare the efficiency and properties of the optimization approaches.

並列關鍵字

global optimization ； piecewise linearization ； convex underestimation

參考文獻

[2] Floudas, C.A., Deterministic Global Optimization: Theory, Algorithms and Applications, Kluwer Academic Publishers, 2000.

[4] Horst, R. and Pardalos, P.M., Handbook of Global Optimization, Kluwer, Dordrecht, 1995.

[6] Adjiman, C.S., Androulakis, I.P. and Floudas, C.A., Global Optimization of Mixed Integer Nonlinear Problems, AIChE Journal, 2000, 46, pp.1769-1797.

[7] Al-Khayyal, F.A., Jointly Constrained Bilinear Programs and Related Problems: An Overview, Computers in Mathematical Applications, 1990, 19, pp.53–62.

[8] Chen, C.S, Lee, S. M. and Shen, Q.S., An analytical model for the container loading problem, European Journal of Operational Research, 1995, 80, pp.68-76.