非線性規劃專題

Topics in Nonlinear Programming

劉永誠(Yeong-Cheng Liou)

指導教授 ： 古思明

元智大學/工程學院/工業工程與管理學系/博士(2000年)

摘要

本論文研究特定類的非線性規劃問題及其相關的應用。我們的研究分成二大部份；第一部份是研究一類非凸二次規劃受限於等二次函數約束問題，我們給了此類問題大域最佳解的一個刻劃條件，即刻劃了局部解成為大域解的充分必要條件，它可作為此類非凸問題數值解法的解是否為大域解之停止判據。以此為基礎，我們對於所求得之KKT點，若其不為大域解則我們必可找到一改善方向，使得問題的目標值獲得改善。據此想法，我們便可發展一個方法來求解此類問題。
在第二部份中，我們將聚焦在分數規劃的問題上，特別是目標函數為線性分式函數與其合成函數，對此我們將分二個主題來討論。在第一個主題中，我們將分析一類沒限制條件之線性分式規劃受限於變數具有上下界的問題，其來源是從處理模糊加權平均算子的評估問題上抽象而來的。對於這種結構特殊的問題，我們發展二個線性時間解法來求出此問題的最佳解，並探討了早期對此問題處理的不完備性。文中亦研究了此類問題的等價性問題與演算法的收斂性。
第二個主題乃延續第一部份的研究。探討的線性分式函數的合成函數受限於線性約束的問題(簡稱線性比值和的問題)。目前已有學者針對二個線性比值和的問題做了研究，不過算法均屬參數形態的方法。我們提出一單體形態的啟發式演算法並發展了一個表格求解的代數，且猜測我們算法求出的解不僅是個KKT點而且還是個大域解。

關鍵字

非凸二次規劃 ； KKT點 ； 線性分式規劃 ； 模糊加權平均法 ； 線性比值和的問題 ； 參數形態的方法 ； 單體形態的演算法

並列摘要

This dissertation studies certain nonlinear programming problems and its algorithms. We divided it roughly into two categories. The first category states a necessary and sufficient optimality condition for a local optimal solution to be global one, providing various numerical routines with these conditions as a stopping criteria to yield a global solution in nonconvex quadratic programming problems with equal quadratic constraints. Based on the condition, for a KKT point given, if it is not global then it is possible to find an improved feasible point. By this point, we develop an algorithm to solve it.
In the second category, we focus on the fractional programming problems, especially in linear fractional programming and its composite problems, and describe them in two parts. In part one, we develop two fast, effective linear-time iterative algorithms for searching the global minimum of linear fractional programming problems without constraints, arised from fuzzy weighted average (FWA) problems. Completeness as well as convergence of algorithm are discussed.
The second part will study one type of nonlinear programming problems whose objective is the sum of linear ratios (SLR) with linear constraints. We propose a heuristic simplex-like algorithm to solve this problem and develop the tableau algebra of algorithm as well. Furthermore, we propose a conjecture to claim this solution obtained by our algorithm is not only a KKT point but a global one.
KEY WORDS. nonconvex quadratic programmin, KKT point, linear fractional programming, fuzzy weighted average, sum of ratios of linear ratios, parametric method, simplex-like algorithm.

並列關鍵字

nonconvex quadratic programming ； KKT points ； linear fractional programming ； fuzzy weighted average ； sum of linear ratios problems ； parametric method ； simplex-like algorithm

參考文獻

Bar-On, J.R., K.A. Grasse (1997), ''''Global optimization of a quadratic functional with quadratic equality constraints, Part 2,'''' Journal of Optimization Theory and Applications 93, No.3., pp.547-556.

Bar-On, J.R., K.A. Grasse (1994), ''''Global Optimization of a Quadratic Functional with Quadratic Equality Constraints,'''' Journal of Optimization Theory and Applications 82, No.2, pp.379-386.

Berberian, S.K. (1992), Linear Algrbra, Oxford University Press, Walton Street, Oxford.

Bhatt, S.K. (1989), ''''Equivalence of various linearization algorithms for linear fractional programming,'''' ZOR-Methods and Models of Operations Research 33, pp.39-43.

Craven, B.D. (1988), Fractional Programming, Heldermann Verlag, Berlin.