本論文研究特定類的非線性規劃問題及其相關的應用。我們的研究分成二大部份；第一部份是研究一類非凸二次規劃受限於等二次函數約束問題，我們給了此類問題大域最佳解的一個刻劃條件，即刻劃了局部解成為大域解的充分必要條件，它可作為此類非凸問題數值解法的解是否為大域解之停止判據。以此為基礎，我們對於所求得之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.

Cover
摘要
Abstract
Contents
1 Introduction
1.1 Background
1.2 Notations
2 Global optimization of quadratic problem with quadratic constraints
2.1 Introduction
2.2 Characterization of a global solution
2.3 Algorithm
3 Linear fractional programming problems
3.1 Applications to fuzzy weighted average
3.2 Sum of linear ratios problems
4 Bibliography

Almogy, Y., O. Levin (1969), ''''Parametric analysis of a multi-stage stochastic shipping problem,'''' Proc. Fifth IFORS Conference, Venice, pp.359-370.
Avriel, M., W. Diewert, S. Schaible, and I. Zang (1988), Generalized Concavity, Plenum Press, New York.
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.
Bazaraa, M.S., H.D. Sherali, and C.M. Shetty (1993), Nonlinear Programming: Theory and Algorithms, 2/e, John Wiley \& Sons, Inc., New York.
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.
Cambini, A., L. Martein, S. Schaible (1989), ''''On maximizing a sum of ratios,'''' Journal of Information and Optimization Sciences 10, No.1, pp.65-79.
Craven, B.D. (1988), Fractional Programming, Heldermann Verlag, Berlin.
Dong, W.M., F.S. Wong (1987), ''''Fuzzy weighted averages and implementation of extension principle,'''' Fuzzy sets and Systems 21, pp.183-199.
Falk, J.E., S.W. Palocsay (1992), ''''Optimizing the sum of linear fractional functions,'''' Collection: Recent Advances in Global Optimization (1992), C.A Floudas et al. ed., Princeton University Press, Princeton, pp.221-258.
Falk, J.E., S.W. Palocsay (1994), ''''Image space analysis of generalized fractional programs,'''' Journal of Global Optimization 4, pp.63-88.
Flippo, O.E., Jansen, B. (1996), ''''Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid,'''' European Journal of Operational Research 94, pp.167-178.
Forgo, F. (1988), Nonconvex Programming,, Akademiai Kiado, Budapest.
Fradkov, A.L., V.A. Yakubovich (1979), ''''The S-procedure and a duality relations in nonconvex problems of quadratic programming,'''' Vestnik St. Petersburg University Mathematics 6, No.1, pp.101-109.
Fradkov, A.L. (1973), ''''Duality theorems in certain nonconvex extremal problems,'''' Siberian Mathematical Journal of the Academy of Sciences of the USSR 14, No.2, pp.247-264.
Guh, Y.-Y., C.-C. Hon, K.-M. Wang, and E.S. Lee (1996), ''''Fuzzy weighted average: a max-min paired elimination method,'''' Computers and Mathematics with Applications 32, No.8, pp.115-123.
Guu, S.-M., Y.-C. Liou (1999), ''''A linear-time algorithm for the fuzzy weighted average method,'''' Workshop on the Chinese Institute of Industrial Engineering (Submitted).
Guu, S.-M., Y.-C. Liou (1998), ''''On a quadratic optimization problem with equality constraints,'''' Journal of Optimization Theory and Applications 98, No. 3, pp.733-741.
Hansen, P., M.V.P. de Aragao, and C.C. Ribeiro (1991), ''''Hyperbolic 0-1 programming and optimization in information retrieval,'''' Mathematical Programming 52, pp.255-263.
Hirche, J. (1996), ''''Optimizing of sums and products of linear fractional functions under linear constraints,'''' Optimization 38, No.1, pp.39-48.
Hirche, J. (1996), ''''A note on programming problems with linear-plus-linear-fractional objective functions,'''' Eur. J. Oper. Res. 89, No.1, pp.212-214.
Horst, R., H. Tuy (1996), Global Optimization: Deterministic Approaches, 3/e, Springer-Verlag, Heidelberg.
Konno, H., Y. Yajima, T. Matsui (1991), ''''Parametric simplex algorithms for solving a special class of nonconvex minimization problems,'''' Journal of Global Optimization 1, pp.65-81.
Konno, H., H. Yamashita (1999), ''''Minimizing sums and products of linear fractional functions over a polytope,'''' Naval Research Logistics 46, pp.583-596.
Kornbluth, J.S.H., R.E. Steuer (1981), ''''Multiple objective linear fractional programming,'''' Management Science 27, pp.1024-1039.
Lee, D.H., D. Park (1997), ''''An efficient algorithm for fuzzy weighted average,'''' Fuzzy Sets and Systems 87, pp.39-45.
Levitin, E.S. (1994), Perturbation Theory in Mathematical Programming and Its Applications, John Wiley & Sons, Inc., New York.
Liou, T.S., M.J. Wang (1992), ''''Fuzzy weighted average: an improved algorithm,'''' Fuzzy sets and Systems 49, pp.307-315.
Luc, D.T., Jahn, J. (1992), ''''Axiomatic approach to duality in optimization,'''' Numerical Functional Analysis and Optimization 13 (3ƀ), pp.305-326.
Lucidi, S., L. Palagi, and M. Roma (1994), Quadratic programs with quadratic constraint: characterization of KKT points and equivalence with an unconstrainted problem, Technical Reports 24.94, Dipartimento di Informatica e Sistemistica, Universita di Roma ''''La Sapienza'''', Roma, Italy.
Luenberger, D.G. (1984), Linear and Nonlinear Programming, Addison-Wesley Publishing Company, Massachusetts, Massachusetts.
Mangasarian, O.L. (1969), Nonlinear Programming, McGraw-Hill, Inc., New York.
Martos, B. (1975), Nonlinear Programming: Theory and Methods, Akademiai Kiado, Budapest.
Matveev, A.S., Yakubovich, V.A. (1997), ''''Nonconvex problems of global optimization: linear-quadratic control problems with quadratic constraints,'''' Dynamics and Control 7, pp.99-134.
Matveev, A.S., Yakubovich, V.A. (1993), ''''Nonconvex problems of global optimization,'''' St. Petersburg Mathematical Journal 4, No.6, pp.1217-1243.
Matveev, A.S. (1994), ''''Absence of local minima for a class of nonconvex optimization problems,'''' Vestnik St. Petersburg University Mathematics 27, No.1, pp.38-42.
Nemirovsky, A.S., D.B. Yudin (1983), Problem Complexity and Method Efficiency in Optimization, John Wiley & Sons, Ltd., New York.
Pratt, V., M. Blum, R.W. Floyd, R.L. Rivest and R.E. Tarjan (1973), ''''Time bounds for selection,'''' Journal of Computer and System Sciences 7, 448-461.
Robillard, P. (1971), ''''(0,1) hyperbolic programming problems,'''' Naval Research Logistics Quarterly 18, pp.47-57.
Schaible, S. (1994), Fractional Programming with Sums of Ratios, University of Pisa Press, Report n.83, Pisa, Italy.
Schaible, S. (1977), ''''A note on the sums of a linear and linear-fractional function,'''' Naval Research Logistics 24, No.4, pp.691-693.
Scott, C.H., T.R. Jefferson (1998), ''''Duality of a nonconvex sums of ratios,'''' Journal of Optimization Theory and Applications 98, No.1, pp.151-159.
Stancu-Minasian, I.M., ''''On a class of nonlinear fractional programming problems,'''' Rev. Ronmaine Math. Pures Appl., pp.285-290.
Stancu-Minasian, I.M.(1997), Fractional Programming: Theory, Methods and Applications, Kluwer Academic Publishers, Dordrecht, Netherlands.
Steuer R.E. (1986), Multiple Criteria Optimization: Theory, Computation, and Application, John Wiley & Sons, Inc., New York.
Strang, G. (1986), Linear Algebra and Its Applications, Harcourt Brace Jovanovich Publisher, San Diego.
Swarup, K. (1975), ''''Convex simplex method and nonlinear programming problems,'''' Indian Journal of Pure and Applied Mathematics 6, No.2, pp.190-209.
Tuy, H. (1998), Convex Analysis and Global Optimization, Kluwer Academic Publishers, Netherlands.
Yamashita, H. (1997), Efficient Algorithm for Minimizing the Sum and the Product of Linear Fractional Functions, Thesis 95M14186, Department of Industrial Engineering and Management, Tokyo Institute of Technology, Tokyo (in Japanese).
Yakubovich, V.A. (1992), ''''A method for solution of special problems of global minimization,'''' Vestnik St. Petersburg University Mathematics 25, No.2, pp.55-63.
Yakubovich, V.A. (1974), ''''The S-procedure in nonlinear control theory,'''' Vestnik St. Petersburg University Mathematics 4, No.1, pp.73-93.
Yakubovich, V.A. (1973), ''''Minimization of quadratic functionals under quadratic constraints and the necessity of a frequency conditions in the quadratic criterion for absolute stability of nonlinear control systems,'''' Russian Academy of Sciences Doklady Mathematics 14, No.2, pp.593-597.
Zangwill, W.I. (1967), ''''The convex simplex method,'''' Management Science 14, No.3., pp.221-238.
Zangwill, W.I. (1969), Nonlinear Programming: A Unified Approach, Prentice-Hall, Inc., N.J..