Abstract
A mathematical program with a rational objective function may have irrational algebraic solutions even when the data are integral. We suggest that for such problems the optimal solution will be represented as follows: If λ* denotes the optimal value there will be given an intervalI and a polynomialP(λ) such thatI contains λ* and λ* is the unique root ofP(λ) inI. It is shown that with this representation the solutions to convex quadratic fractional programs and ratio games can be obtained in polynomial time.
Similar content being viewed by others
References
A. Baker,Transcendental number theory (Cambridge University Press, Cambridge, 1975).
E. Bombieri, “Sull’approssimazione di numeri algebrici mediante numeri algebrici”,Bollettino della Unione Mathematica Italiana III 13 (1958) 351–354.
A. Chandrasekaran, “The weighted Euclidean 1-center problem”,Operations Research Letters 1 (1982) 111–112.
A. Chandrasekaran and A. Tamir, “Optimization problems with algebraic solutions: quadratic fractional programs and ratio games”, Department of Statistics Tel Aviv University (Tel Aviv, 1982).
A. Charnes and R.G. Schroeder, “On some stochastic tactical antisubmarine games”,Naval Research Logistic Quarterly 14 (1967) 291–307.
W. Dinkelbach, “On nonlinear fractional programming”,Management Science 13 (1967) 492–498.
P. Gács and L. Lovász, “Khachiyan’s algorithm for linear programming”,Mathematical Programming Study 14 (1981) 61–68.
R. Güting, “Approximation of algebraic numbers by algebraic numbers”,Michigan Mathematical Journal 8 (1961) 149–159.
A.S. Householder, The numerical treatment of a single nonlinear equation (McGraw Hill, New York, 1970).
T. Ibaraki, “Parametric approaches to fractional programs”,Mathematical Programming 26 (1983) 345–362.
T. Ibaraki, “Solving mathematical programming problems with fractional objective function”, in: S. Schaible and W.T. Ziemba, eds., Generalized concavity in optimization and economics (Academic Press, New York, 1981) 441–472.
T. Ibaraki, H. Ishii, J. Iwase, T. Hasegawa and H. Mine, “Algorithms for quadratic fractional programming problems”,Journal of the Operations Research Society of Japan 19 (1976) 174–191.
S. Karlin, Mathematical methods and theory in games, programming and economics, Volume 1 (Addison Wesley, Reading, MA, 1959).
L.G. Khachiyan, “A polynomial algorithm for linear programming”,Doklady Akademii Nauk SSSR 244 (1979) 1093–1096, English translation inSoviet Mathematics Doklady 20 (1979) 191–194.
M.K. Kozlov, S.P. Tarasov and L.G. Khachiyan, “Polynomial solvability of convex quadratic programming”,Doklady Akademii Nauk SSSR 248 (1979) 1049–1051, English translation inSoviet Mathematics Doklady 20 (1979) 1108–1111.
A.K. Lenstra, H.W. Lenstra, Jr. and L. Lovász, “Factoring polynomials with rational coefficients”,Mathematische Annalen 261 (1982) 513–534.
K. Mahler, “On a theorem by E. Bombieri”,Indagationes Mathematicae 22 (1960) 245–253.
N. Megiddo, “Combinatorial optimization with rational objective functions”,Mathematics of Operations Research 4 (1979) 414–424.
N. Megiddo, “The weighted Euclidean 1-center problem,”Mathematics of Operations Research 8 (1983) 498–504.
M. Mignotte, “Identification of algebraic numbers”,Journal of Algorithms 3 (1982) 197–204.
K.G. Murty, Linear and combinatorial programming (Wiley, New York, 1976).
K.G. Murty, “Computational complexity of parametric linear programming”,Mathematical Programming 19 (1980) 213–219.
A.M. Ostrowski, Solution of equations in Euclidean and Banach spaces (Academic Press, New York, 1973).
C.H. Papadimitriou, “Efficient search for rationals”,Information Processing Letters 8 (1979) 1–4.
A. Ralston, A first course in numerical analysis (McGraw Hill, New York, 1965).
S.P. Reiss, “Rational search,”Information Processing Letters 8 (1979) 89–90.
K. Ritter, “A parametric method for solving certain nonconvex maximization problems”,Journal of Computer and System Sciences 1 (1967) 44–54.
K. Ritter, “A method for solving nonlinear maximum problems depending on parameters”,Naval Research Logistic Quarterly 14 (1967) 147–162.
S. Schaible, “Fractional programming II”,Management Science 22 (1976) 868–873.
S. Schaible, “A survey of fractional programming”, in: S. Schaible and W.T. Ziemba, eds., Generalized concavity in optimization and economics (Academic Press, New York, 1981) pp. 417–440.
S. Schaible and T. Ibaraki, “Invited review: Fractional programming”,European Journal of Operational Research 12 (1983) 325–338.
R.G. Schroeder, “Linear programming solutions to ratio games”,Operations Research 18 (1970) 300–305.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Chandrasekaran, R., Tamir, A. Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games. Mathematical Programming 30, 326–339 (1984). https://doi.org/10.1007/BF02591937
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591937