在這個博士論文中，我們研究連續型最小最大問題的演算法並將這方法延伸到解決分數型態規劃問題。我們建構一個疊代的熵正則化演算法。這個方法把連續型最小最大問題分解一連串的有限型的最小最大問題，並且可以估計誤差。這個方法和 Dinkelbach-type 演算法結合被用來解決連續型的分數規劃問題。最後我們推廣 Dinkelbach-type 演算法去解決更一般化的分數型規劃問題。而最佳化比值和問題也可以被歸類到這種問題。每個演算法我們均作收斂性分析及數值驗證以顯示其正確性及有效性。

　In this dissertation, we study algorithms for solving continuous min-max problem with an extension to fractional programs. We propose an iterative entropic regularization method that reduces the continuous min-max problem into a sequence of finite min-max problems and also allows estimation for the error bounds. The method is then combined with the Dinkelbach-type algorithm to solve the continuous min-max fractional program. Finally, the Dinkelbach-type algorithm is extended to solve more general fractional programs including the difficult sum-of-ratio problem. All algorithms are equipped with convergence analysis as well as numerical examples to show the correctness and the robustness.

L.~Abbe. A logarithmic barrier approach and its regularization applied to convex semi-infinite programming problems. Ph. D. dissertation, Universit"at Trier, Trier, Germany, 2001.

Y.~Almogy and O.~Levin. A class of fractional programming problems. Operations Ressearch, 19:57--61, 1971.

A.~Auslender. Penalty and barrier methods: a unified framework. Siam Journal on Optimization, 10:211--230, 1999.

A.~M. Bagirov and A.~M. Rubinov. On minimization of max-min functions. In Optimization and control with applications, volume~96 of Application Optimization, pages 3--33. Springer, New York, 2005.

A.~I. Barros and J.~B.~G. Frenk. Generalized fractional programming and cutting plane algorithms. Journal of Optimization Theory and Applications, 87:103--120, 1995.

A.~I. Barros, J.~B.~G. Frenk, S.~Schaible, and S.~Zhang. A new algorithm for generalized fractional programs. Mathematical Programming, 72:147--175, 1996.

A.~Ben-Tal and M.~Teboulle. A smoothing technique for nondifferentiable optimization problems. In S.~Dolecki, editor, Lecture Notes in Mathematics 1405. Springer-Verlag, Berlin, 1989.

H.~P. Benson. Global optimization of nonlinear sums of ratios. Journal of Mathematical Analysis and Applications, 263(1):301--315, 2001.

H.~P. Benson. Global optimization algorithm for the nonlinear sum of ratios problem. Journal of Optimization Theory and Applications, 112(1):1--29, 2002.

H.~P. Benson. Using concave envelopes to globally solve the nonlinear sum of ratios problem. Journal of Global Optimization, 22(1-4):343--364, 2002. Dedicated to Professor Reiner Horst on his 60th birthday.

D.~P. Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic Press, New York, 1996.

M.~C. Biggs. Constrained minimization using recursive equality quadratic programming. In Numerical methods for non-linear optimization (Conference, University Dundee, Dundee, 1971), pages 411--428. Academic Press, London, 1972.

P.~L. Chang. A minimax approach to nonlinear programming. Doctoral Disssertation, University of Washington, Department of Mathematics, 1980.

J.~P. Crouzeix and J.~A. Ferland. Algorithms for generalized fractional programming. Mathematical
Programming, 52:191--207, 1991.

J.~P. Crouzeix, J.~A. Ferland, and S.~Schaible. Duality in generalized linear fractional programming. Mathematical Programming, 27:342--354, 1983.

J.~P. Crouzeix, J.~A. Ferland, and S.~Schaible. An algorithm for generalized fractional programs. Journal of Optimization Theory and Applications, 47:35--49, 1985.

J.~P. Crouzeix, J.~A. Ferland, and S.~Schaible. A note on an algorithm for generalized fractional programs. Journal of Optimization Theory and Applications, 50:183--187, 1986.

D.~den Hertog. Interior point approach to linear, quadratic and convex programming. Kluwer Academic

Publishers, The Netherlands, 1994.J.~Dieudonne. Foundations of modern analysis 10-1. Academic Press, New York, 1969.

W.~Dinkelbach. On nonlinear fractional programming. Management Science}, 13:492--498, 1967.

M.~D{"u}r, R.~Horst, and N.~Van~Thoai. Solving sum-of-ratios fractional programs using efficient points.

Optimization, 49(5-6):447--466, 2001.
James~E. Falk and Susan~W. Palocsay. Optimizing the sum of linear fractional functions. In Recent advances in global optimization (Princeton, NJ, 1991), Princeton Series in Computer Science., pages 221--258. Princeton University Press, Princeton, NJ, 1992.

S.~C. Fang, J.~R. Rajasekera, and H.S.~J. Tsao. Entropy optimization and mathematical programming. International Series in Operations Research & Management Science, 8. Kluwer Academic Publishers, Boston, MA, 1997.

R.~W. Freund and F.~Jarre. Solving the sum-of-ratios problem by an interior-point method. Journal of Global Optimization, 19(1):83--102, 2001.

C.~Gigola and S.~Gomez. A regularization method for solving the finite convex min-max problem. SIAM Journal on Numerical Analysis, 27:1621--1634, 1990.

C.~C. Gonzaga and E.~Polak. On constraint dropping schemes and optimality functions for a class of outer approximations algorithms. SIAM Journal on Control and Optimization, 17:477--493, 1979.

M.~Gugat. A fast algorithm for a class of generalized fractional programs. Managem. Sci, 42:1493--1499, 1996.

J.~Gwinner and V.~Jeyakumar. A solvability theorem and minimax fractional programming. Zeitschrift f"ur Operations Research, 37(1):1--12, 1993.

R.~Hettich and K.~O. Kortanek. Semi-infinite programming: theory, methods, and applications. SIAM Review, 35:380--429, 1993.

H.~Konno and N.~Abe. Minimization of the sum of three linear fractional functions. Journal of Global Optimization, 15(4):419--432, 1999. Dedicated to Professor Hoang Tuy's 70th birthday.

H.~Konno, Y.~Yajima, and T.~Matsui. Parametric simplex algorithms for solving a special class of nonconvex minimization problems. Journal of Global Optimization, 1(1):65--81, 1991.

T.~Kuno. A branch-and-bound algorithm for maximizing the sum of several linear ratios. Journal of Global Optimization, 22(1-4):155--174, 2002. Dedicated to Professor Reiner Horst on his 60th birthday.

X.~S. Li and S.~C. Fang. On the entropic regularization method for solving min-max problems with applications. Zeischrift f"ur Operations Research, 46:119--130, 1997.

J.~Y. Lin and R.~L. Sheu. Modified {D}inkelbach-type algorithm for generalized fractional programs with infinitely many ratios. Journal of Optimization Theory and Applications, 126(2):323--343, 2005.

D.G. Luenberger. Linear and Nonlinear programming. Addison-Wesley, Canada, 1984.
H.~Mine, M.~Fukushima, and Y.~Tanaka. On the use of {$varepsilon$}-most-active constraints in an exact penalty function method for nonlinear optimization. Institute of Electrical and Electronics Engineers. Transactions on Automatic Control, 29(11):1040--1042, 1984.

R.~D.~C Monteiro and I.~Adler. An extension of karmarkar type algorithm to a class of convex separable programming problems with global linear rate of convergence. Mathematics of Operations Research, 15:408--422, 1990.

N.~T.~H. Phuong and H.~Tuy. A unified monotonic approach to generalized linear fractional programming. Journal of Global Optimization, 26(3):229--259, 2003.

F.~Plastria. Lower subdifferentiable functions and their minimization by cutting planes. Journal of Optimization Theory and Application, 46:37--53, 1985.

E.~Polak. Optimization: Algorithms and Consistent Approximations. Springer-Verlag, New York, 1994.

E.~Polak, J.~E. Higgins, and Q.~D. Mayne. A barrier function method for minimax problems. Mathematical Programming, 54:155--176, 1992.

E.~Polak, D.~Q. Mayne, and J.~E. Higgins. Superlinearly convergent algorithm for min-max problems. Journal of Optimization Theory and Applications, 69:407--439, 1991.

E.~Polak and Q.~D. Mayne. An algorithm for optimization problems with functional inequality constraints. Institute of Electrical and Electronics Engineers. Transactions on Automatic Control, AC-21(2):184--193, 1976.

E.~Polak and A.~L. Tits. A recursive quadratic programming algorithm for semi-infinite optimization problems. Applied Mathematics and Optimization. An International Journal, 8(4):325--349, 1982.

R.~A. Polyak. Smooth optimization methods for minmax problems. SIAM Journal on Control and Optimization, 26:1274--1286, 1988.

M.~J.~D. Powell. An efficient method for finding the minimum of a function of several variables without calculating derivatives. The Computer Journal, 7:155--162, 1964.

M.~J.~D. Powell. A tolerant algorithm for linearly constrained optimization calculations. Mathematical Programming, 45(3, (Ser. B)):547--566, 1989.

R.~Reemtsen and S.~G"orner. Numerical methods for semi-infinite programming: A survey. In R.~Reemtsen and J.-J. R"uckmann, editors, Semi-Infinite Programming. Kluwer Academic publishers, 1998.

S.~Schaible. Fractional programming. In R.~Horst and P.~M. Pardalos, editors, Handbook Global Optimization, pages 495--608. Kluwer Academic Publishers, 1995.

K.~Schittkowski. Solving nonlinear programming problems with very many constraints. Optimization, 25(2-3):179--196, 1992.

R.~L. Sheu. A generalized interior-point barrier function approach for smooth convex programming with linear constraints. Journal of Information and Optimization Sciences, 20:187--202, 1999.

R.~L. Sheu and J.~Y. Lin. Solving continuous min-max problems by an iterative entropic regularization method. Journal of Optimization Theory and Applications, 121(3):597--612, 2004.

R.~L. Sheu and S.~Y. Wu. Combined entropic regularization and path-following method for solving finite convex min-max problems subject to infinitely many linear constraints. Journal of Optimization Theory and Applications, 101(1):167--190, 1999.

Jianming Shi. A combined algorithm for fractional programming. Annals of Operation Research, 103:135--147, 2001.

I.~M. Stancu-Minasian. Fractional programming: Theory, methods and applications. Kluwer Academic Publishers,1997.

G.~W. Steward. A modification of Davidon's minimization method to accept difference approximations of derivatives. Journal of the Association for Computing Machinery, 14:72--83, 1967.

Y.~Tanaka, M.~Fukushima, and T.~Ibarkai. A comparative study of several semi-infinite nonlinear programming algorithms. European Journal of Operational Research, 36:92--100, 1988.

S.~Y. Wu and S.~C. Fang. Solving min-max problems and linear semi-infinite programs. Computers and
Mathematics with applications, 32:87--93, 1996.

W.~Y. Wu and R.~L. Sheu. Minimization of the sum of three linear fractional functions. Submitted to Journal of Global Optimization.

I.~Zang. A smooth-out technique for min-max optimization. Mathematical Programming, 19:61--77, 1980.

J.~Zhu. A path-following algorithm for a class of convex programming problems. Zeischrift f"ur Operations Research, 36:359--377, 1992.