在本論文中，我們關心兩類的二次分式型規劃問題：其一是帶有雙邊二次限制式之二次分式型問題(P)，其二是分式和規劃問題(Q)。雖然我們的問題(P)與(Q)是以二次函數的分式型態展現，透過參數化技巧，分式的結構可以被轉換成一系列特殊型的二次限制式二次規劃(QCQP)問題。QCQP問題是文獻中備受關注，存在已久且困難求解的非凸最佳化問題。因此，在處理(P)與(Q)，我們不只面對傳統QCQP問題，另外還有從分式結構衍生出的參數要處理。由於我們是直接著手處理二次分式型規劃問題，顯然許多結果對QCQP來說是也會是新且有用的。儘管(P)與(Q)本身是非凸的， 我們主要的想法是探討(P)與(Q)的隱藏凸性。我們主要的工具包含一個強大的機制，即已知的S-引理，以及半正定鬆弛、秩一分解技術。為了引用上述的工具來求解(P)與(Q)，我們將問題轉化或拆開成一些子問題，並研究S-引理的新版本、修改秩一分解程序。結果是，我們證明了問題(P)的計算複雜度屬於P類問題，而NP-困難的問題(Q)可以被簡化成一個一維度搜尋問題。我們的解法是創新的，而且容易在電腦上執行。我們的計算結果顯示，在求解全局最佳解方面我們的演算法比其他現有的求解方法更有效率。

In this dissertation, we are concerned with two types of quadratic fractional programming problems: one is a single ratio quadratic fractional problem with a twosided quadratic constraint (P) and the other is a sum-of-ratios problem (Q). Although we pose the problems (P) and (Q) in the form of ratios of quadratic functions, after some parameterization scheme, the fractional structure can be exchanged with a family of special types of quadratically constrained quadratic programming (QCQP) problems. The QCQP problem is a long-standing difficult non-convex optimization problem which has attracted much attention in literature. Therefore, in dealing with (P) and (Q), we not only face the traditional QCQP problem, but also an additional parameter coming from the ratio structure. Since we feel that we can address the two issues all together, we directly attack the quadratic fractional programming but apparently many results are new and useful to QCQP alone. Our main idea is to probe the hidden convexity of (P) and (Q), in spite that both (P) and (Q) are themselves non-convex. Our main tool is a powerful mechanism, known as the S-lemma, together with the semi-definite relaxation and the rank-one decomposition technique.
In order to apply the aforementioned tools for solving (P) and (Q), we transform or divide the problems into a few subcases; study new versions of S-lemma; and modify the rank-one decomposition procedure. As a result, we prove that (P) is indeed in the class of P, and the NP-hard problem (Q) can be reduced to a much simpler one-dimensional search problem. Our solution method is novel, and can be easily implemented on the computer. Our computational results show that the algorithms are very efficient in finding the global optimal solution compared with other existing methods.

[1] Ai, W., Zhang, S. Z.: Strong duality for the CDT subproblem: A necessary
and sufficient condition. SIAM J. Optim., vol. 19, No. 4; 1735-1756 (2009)
[2] Almogy, Y., Levin, O.: Parametric analysis of a multistage stochastic
shipping problem. In: Proceedings of the 5th IFORS Conference, 359-370(1964)
[3] Antoniou, A., Lu, W. S.: Practical Optimization: Algorithms and Engineering
Applications, Springer Science+ Business Media, LLC (2007)
[4] Avriel, M., Diewert, W.E., Schaible, S., Zang, I.: Generalized Concavity.
Plenum Press, New York (1988)
[5] Barros, A. I., Frenk, J. B. G., Schaible, S., Zhang, S.: A new algorithm
for generalized fractional programs. Math. Program., 72; 147-175(1996)
[6] Bazaraa, M. S., Sherali, H. D., Shetty, C. M.: Nonliear Programming:
Theory and Algorithms. Third Edition. John Wiley and Sons, Inc.,
Hoboken, New Jersey (2006)
[7] Beck, A., Eldar, Y. C.: Strong Duality in Nonconvex Quadratic Optimization
with Two Quadratic Constraint. SIAM J. Optim., 17(3); 844-860(2006)
[8] Beck, A., Teboulle, M.: A convex optimization approach for minimizing
the ratio of indefinite quadratic functions over an ellipsoid. Math.
Program., Ser. A, 118, 13 - 35(2009)
[9] Beck, A., Teboulle, M.: On Minimizing Quadratically Constrained Ratio
of Two Quadratic Functions. J. Convex Anal., 17; 789- 804(2010)
[10] Benson, H. P.: Global optimization algorithm for the nonlinear sum of ratios problem. J. Optim. Theory Appl., 112; 1-29(2002)
[11] Benson, H. P.: Using concave envelopes to globally solve the nonlinear
sum of ratios problems. J. Global Optim., 22; 343-364(2002)
[12] Benson, H. P.: On the global optimization of sum of linear fractional
functions over a convex set. J. Optim. Theory Appl., 121; 19-39(2004)
[13] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization.
MPS-SIAM Series on Optimization (2001)
[14] Ben-Tal, A., Teboulle, M.: Hidden convexity in some nonconvex
quadratically constrained quadratic programming. Math. Program., 72; 51 -63(1996)
[15] Bernard, J. C., Ferland, J. A.: Convergence of interval-type algorithms
for generalized fractional programming. Math. Program., Ser. A, 43(3); 349 - 363(1989)
[16] Brickman, L.: On the field of values of a matrix. Proc. Amer. Math. Soc., 12, 61 -66(1961)
[17] Bruce D. C.: Fractional Programming. Sigma serries in Applied Mathematics.
IV, Heldermann (1988)
[18] Celis, M. R., Dennis, J. E., Tapia, R. A.: A trust region algorithm for nonlinear equality constrained optimization, in Numerical Optimization, R. T. Boggs, R. H. Byrd, and R. B. Schnabel, eds., SIAM, Philadelphia, 71 - 82(1984)
[19] Charnes, A., Cooper, W. W.: Programming with linear fractional functionals.
Naval Res. Logist. Quarterly, vol. 9, 181 - 186; (1962)
[20] Chen, H. J., Schaible, S., Sheu, R. L.: Generic Algorithm for Generalized
Fractional Programming. J. Optim. Theory Appl., 141; 93-105(2009)
[21] Colantoni, C.S., Manes, R.P., Whinston, A.: Programming, profit rates,
and pricing decisions. Account. Rev., 44; 467-481(1969)
[22] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. SIAM,
Philadelphia (2000)
[23] Craven, B.D.: Fractional programming. Sigma Series in Applied Mathematics,
vol. 4, Heldermann Verlag Berlin (1988)
[24] Crouzeix, J. P., Ferland, J. A., Schaible, S.: An Algorithm for Generalized
Fractional Programs. J. Optim. Theory Appl., 47, No.1 35-49(1985)
[25] Crouzeix, J. P., Ferland, J. A.: Algorithms for generalized fractional
programming. Math. Program., 52; 191 -207(1991)
[26] Dines, L. L.: On the mapping of quadratic forms. Bull. Amer. Math.
Soc., 47, 494 - 498(1941)
[27] Dinkelbach, W.: On nonlinear fractional programming. Management
Science, 13; 492- 498(1967)
[28] Dundar, M. M., Fung, G., Bi, J., Sandilya, S. Rao, B.: Sparse Fisher discriminant
analysis for computer aided detection. Proceedings of SIAM International Conference on Data Mining (2005)
[29] Eberhard, A., Hadjisavvas, N., The Luc, D.: Generalized convexity,
generalized monotonicity and application: Proceedings of the 7th International
Symposium On Generalized Convexity and Generalized Monotonicity.
Springer, Nonconvex Optim. Appl., vol. 77 (2005)
[30] Faigle, U., Kern, W., Still, G.: Algorithm Principles of Mathematical
Programming. Kluwer Academic, Dordrecht, (2002)
[31] Fang, S. C., Gao, D. Y., Sheu, R. L., Xing, W.: Global optimization for
a class of fractional programming problems. J. Global Optim., 45, No.
3, 337 - 353(2009)
[32] Feng, J. M., Lin, G. X., Sheu, R. L., Xia, Y.: Duality and solutions for
quadratic programming over single non-homogeneous quadratic constraint.
J. Global Optim., 54, No. 2, 275 - 293(2012)
[33] Floudas, C. A., Pardalos, P. M., editors: Encyclopedia of Optimization.
Second Edition. Springer (2009)
[34] Fortin, C., Wolkowicz, H.: The trust region subproblem and semidefinite
programming. Optim. Methods Softw., 19(1), 41 - 67(2004)
[35] Freund, R. W., Jarre, F.: An interior-point method for fractional programs
with convex constraints. Math. Program., 67, No. 3; 407 -440(1994)
[36] Freund, R. W., Jarre, F.: Solving the sum-of-ratios problem by an
interior-point method. J. Global Optim., 19; 83-102(2001)
[37] Fung, E., Michael, K. Ng.: On sparse Fisher discriminant method for
microarray data analysis. Bioinformation, 2; 230 - 234(2007)
[38] Gilmore, P. C., Gomory, R. E.: A linear programming approach to the
cutting stock problem - Part II, Oper. Res., 11, 863 - 888(1963)
[39] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming,
version 1. 21 Web. http://cvxr. com/cvx (2010)
[40] Hadjisavvas, N., Komlósi, S., Schaible, S., editors: Handbook of generalized
convexity and generalized monotonicity. Nonconvex Optim.
Appl., vol. 76, Springer- Verlag. New York (2005)
[41] Hiriart-Urruty, J. B.: Potpourri of Conjectures and Open Questions in
Nonlinear Analysis and Optimization. SIAM Rev., 49, No. 2; 255 -273(2007)
[42] Horn, R., Johnson, C. R.: Matrix Analysis. Cambridge University Press,
Cambridge, UK (1985)
[43] Hsia, Y., Lin, G. X., Sheu, R. L.: A Revisit to Quadratic Programming
with One Inequality Quadratic Constraint via Matrix Pencil. Pac. J. Optim.,
10(3), 461- 481(2014)
[44] Ibaraki, T.: Parametric approaches to fractional Programs. Math. Program.,
26, 345-362(1983)
[45] Jeyakumar, V., Li, G. Y.: Trust-region problems with linear inequality
constraints: exact SDP relaxation, global optimality and robust optimization.
Math. Program., Ser. A DOI 10.1007/s10107-013-0716-2
[46] Karmarkar, N.: A new polynomial-time algorithm for linear programming.
Combinatorica, 4(4); 373 - 395(1984)
[47] Khan, Z.A., Hanson, M.A.: On ratio invexity in mathematical programming.
J. of Math. Ana. and App., 205, No. 2; 330 - 336(1997)
[48] Konno, H., Fukaishi, K.: A branch and bound algorithm for solving
low rank linear multiplicative and fractional programming problems. J.
Global Optim., 18; 283 -299(2000)
[49] Konno, H., Inori, M.: Bond portfolio optimization by bilinear fractional
programming. J. Oper. Res. Soc. Jpn., 32; 143- 158(1989)
[50] Konno, H., Watanabe, H.: Bond portfolio optimization problems and
their application to index tracking: a partial optimization approach. J.
Oper. Res. Soc. Jpn., 39; 295 - 306(1996)
[51] Kuno, T.: A branch-and-bound algorithm for maximizing the sum of
several linear ratios. J. Global Optim., 22; 155 - 174(2002)
[52] Liang, Z.A., Huang, H.X., Pardalos, P.M.: Optimality conditions and
duality for a class of nonlinear fractional programming problems. J. of
Optim. Theory Appl., 110, No. 3; 611- 619(2001)
[53] Lin, J. Y., Chen, H. J., Sheu, R. L.: Augmented Lagrange Primal-dual
Approach for Generalized fractional programming Problems. J. Ind.
Manag. Optim., vol. 9, No.4, 723- 741(2013)
[54] Lo, A., MacKinlay, C.: Maximizing predictability in the stock and bond
markets, Macroeconomic Dynamics, 1, 102 - 134(1997)
[55] Luenberger, D. G., Ye, Y.: Linear and Nonlinear Programming. Third
Edition, Springer Science+Business Media, LLC. (2008)
[56] Lu, C., Fang, S. C., Jin, Q., Wang, Z., Xing, W.: KKT solution and conic
relaxation for solving quadratically constrained quadratic programming
problems, SIAM J. Optim., 21; 1475 - 1490(2011)
[57] Luo, Z. Q., Zhang, S. Z.: On Extensions of the Frank-Wolfe Theorems.
Comput. Optim. Appl., 13; 87 - 110(1999)
[58] Martos, B.: Hyperbolic programming. Naval Res. Logist. Quarterly,
11; 135 - 155(1964)
[59] Martos, B.: Nonlinear Programming. Theory and Methods. North-
Holland, Amsterdam (1975)
[60] Meszaros, Cs., Rapcs ak, T.: On sensitivity analysis for a class of decision
systems. Decision Support Systems, 16, 231 - 240(1996)
[61] Mjelde, K.M.: Methods of the Allocation of Limited Resources, Wiley,
New York (1983)
[62] Mordecai, A., Walter, D. E., Siegfried, S., Israel, Z.: Generalied Concavity.
Society for Industrial and Applied Mathematics (2010)
[63] Moré, J. J.: Generalization of the trust region problem. Optim. Methods
Softw., 2; 189 - 209(1993)
[64] Nguyen, V. B., Sheu, R. L., Xia, Y.: An SDP approach for quadratic
fractional problems with a two-sided quadratic constraint. Optim. Methods
Softw., DOI: 10.1080/10556788.2015.1029575 (2015)
[65] Nguyen, V. B., Sheu, R. L., Xia, Y.: Maximizing the sum of a generalized
Rayleigh quotient and another Rayleigh quotient on the unit sphere
via semidefinite programming. To appear in J. Global Optim.
[66] Pardalos, P. M., Vavasis, S.A.: Quadratic programming with one negative
eigenvalue is NP-Hard. J. Global Optim., 1; 15 - 22(1991)
[67] Pólik, I., Terlaky, T.: A Servey of S-lemma. SIAM Rev., 49(3); 371 -418(2007)
[68] Polyak, B., T.: Convexity of quadratic transformations and its use in
control and optimization, J. Optim. Theory Appl., 99; 553 - 583(1998)
[69] Pong, T. K., Wolkowicz, H.: The Generalized Trust Region Subprobelm.
Comput. Optim. Appl., 58; 273 - 322(2014)
[70] Primolevo, G., Simeone, O., Spagnolini, U.: Towards a joint optimization
of scheduling and beamforming for MIMO downlink. In: IEEE
Ninth International Symposium on Spread Spectrum Techniques and
Applications, 493 - 497(2006)
[71] Rao, M.R.: Cluster analysis and mathematical programming. J. Am.
Stat. Assoc., 66; 622 - 626(1971)
[72] Reddy, L.V., Mukherjee, R.N.: Some results on mathematical programming
with generalized ratio invexity. J. Math. Anal. Appl., 240, No.
2; 299 - 310(1999)
[73] Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region
subproblems with applications to large scale minimization. Math. Program.,
77; 273 - 299(1997)
[74] Schaible, S.: Parameter-free convex equivalent and dual programs of
fractional programming problems. Zeitschrift für Oper. Res., 18; 187 -196(1974)
[75] Schaible, S.: Fractional programming I: duality. Management Science,
22, No. 8; 858 - 867(1976)
[76] Schaible, S.: Fractional programming with sums of ratios. In: Castagnoli,
E., Giorgi, G. (eds.) Scalar and Vector Optimization in Economicand Financial Problems, Proceedings of the Workshop in Milan, 1995. Elioprint, Milan (1996)
[77] Stancu-Minasian, I.M.: Bibliography of fractional programming. 1960-1976, Pure Appl. Math. Sci., 13 (1-2), 35-69 (1981)
[78] Stancu-Minasian, I.M.: A second bibliography of fractional programming:
1977-1981, Pure Appl. Math. Sci., 17 (1-2), 87-102 (1983)
[79] Stancu-Minasian, I.M.: A third bibliography of fractional programming.
Pure Appl. Math. Sci., 22 (1-2), 109-122 (1985)
[80] Stancu-Minasian, I.M.: A fourth bibliography of fractional programming.
Optimization, 23 (1), 53-72 (1992)
[81] Stancu-Minasian, I.M.: A fifth bibliography of fractional programming.
Optimization, 45 (1-4), 343-367 (1999), Dedicated to the memory of
Professor Karl-Heinz Elster.
[82] Stancu-Minasian, I.M.: A sixth bibliography of fractional programming.
Optimization, 55 (4), 405-428 (2006)
[83] Stern, R. J., Wolkowicz, H.: Indefinite trust region subproblems and
nonsymmetric eigenvalue perturbations. SIAM J. Optim., 5; 286-313(1995)
[84] Sturm, J. F., Zhang, S. Z.: On cones of nonnegative quadratic functions.
Math. Oper. Res., 28; 246 - 267(2003)
[85] Tuy, H., Tuan, H. D.: Generalized S-Lemma and strong duality
in nonconvex quadratic programming. J. Global Optim., DOI 10:1007/s10898 -012 - 9917 - 0
[86] Vanderberghe, L., Boyd, S.: Semidefinite programming, SIAM Rev.,
38; 49 - 95(1995)
[87] Wang, S., Xia, Y.: Strong duality for generalized trust region subproblem:
S-lemma with interval bounds. Optim. Lett., DOI 10.1007/s11590-
014-0812-0 (2014)
[88] Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of semidefinite
programming: Theory, Aigorithms, and Applications. Springer Science+
Business Media New York, Second printing (2003)
[89] Wu, W. Y., Sheu, R. L., Birbil, I.: Solving the sum-of-ratios problem by
a stochastic search algorithm. J. Global Optim., vol. 42, Issue 1; 91 -109(2008)
[90] Wu, M.C., Zhang, L.S., Wang, Z.X., Christiani, D.C., Lin, X.H.: Sparse
linear discriminant analysis for simultaneous testing for the significance
of a gene set/pathway and gene selection. Bioinformatics, 25; 1145 - 1151(2009)
[91] Xia, Y.: On Minimizing the Ratio of Quadratic Functions
over an Ellipsoid. Optimization, (2013) http:// dx.doi.org/10.1080/02331934.2013.840623
[92] Xia, Y., Wang, S., Sheu, R. L.: S-Lemma with Equality and Its Applications.
To appear in Math. Program., Ser. A.
[93] Yakubovich, V. A.: S-procedure in nonlinear control theory. Vestnik
Leningrad. Univ., 4; 73 -93(1977)
[94] Yang, Q.: A new proof of the strong duality theorem for semidefinite
programming. J. Math. Anal. Appl., 303; 622 - 626(2005)
[95] Ye, Y., Zhang, S. Z.: New results on quadratic minimization. SIAM J.
Optim., 14, No. 1, 245 - 267(2003)
[96] Yuan, Y.: On a subproblem of Trust region algorithm for constrained
optimization. Math. Program., North-Holland, 47; 53 - 63 (1990)
[97] Zhang, L. H.: On optimizing the sum of the Rayleigh quotient and the
generalized Rayleigh quotient on the unit sphere. Comput. Optim. Appl.,
54; 111 - 139(2013)
[98] Zhang, L. H.: On a self-consistent-field-like iteration for maximizing
the sum of the Rayleigh quotients. J. Comput. Appl. Math., 257; 14 -
28(2014)
[99] Zhang, A., Hayashi, S.: Celis-Dennis-Tapia based approach to quadratic
fractional programming problems with two quadratic constraints. Numer.
Algebra Control Optim. (NACO)., 1, Issue 1; 83 - 98(2011)