Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games. (English) Zbl 0571.90086
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 \(\lambda^*\) denotes the optimal value there will be given an interval I and a polynomial P(\(\lambda)\) such that I contains \(\lambda^*\) and \(\lambda^*\) is the unique root of P(\(\lambda)\) in I. It is shown that with this representation the solutions to convex quadratic fractional programs and ratio games can be obtained in polynomial time.
MSC:
| 90C32 | Fractional programming |
| 68Q25 | Analysis of algorithms and problem complexity |
| 91A05 | 2-person games |
| 91A10 | Noncooperative games |
Keywords:
algebraic numbers; algebraic optimization problems; rational objective function; convex quadratic fractional programs; ratio games; polynomial timeReferences:
| [1] | A. Baker,Transcendental number theory (Cambridge University Press, Cambridge, 1975). · Zbl 0297.10013 |
| [2] | E. Bombieri, ”Sull’approssimazione di numeri algebrici mediante numeri algebrici”,Bollettino della Unione Mathematica Italiana III 13 (1958) 351–354. · Zbl 0082.04001 |
| [3] | A. Chandrasekaran, ”The weighted Euclidean 1-center problem”,Operations Research Letters 1 (1982) 111–112. · Zbl 0487.90048 · doi:10.1016/0167-6377(82)90009-8 |
| [4] | 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). · Zbl 0571.90086 |
| [5] | A. Charnes and R.G. Schroeder, ”On some stochastic tactical antisubmarine games”,Naval Research Logistic Quarterly 14 (1967) 291–307. · Zbl 0164.20205 · doi:10.1002/nav.3800140303 |
| [6] | W. Dinkelbach, ”On nonlinear fractional programming”,Management Science 13 (1967) 492–498. · Zbl 0152.18402 · doi:10.1287/mnsc.13.7.492 |
| [7] | P. Gács and L. Lovász, ”Khachiyan’s algorithm for linear programming”,Mathematical Programming Study 14 (1981) 61–68. · Zbl 0463.90066 |
| [8] | R. Güting, ”Approximation of algebraic numbers by algebraic numbers”,Michigan Mathematical Journal 8 (1961) 149–159. · Zbl 0107.04203 · doi:10.1307/mmj/1028998566 |
| [9] | A.S. Householder, The numerical treatment of a single nonlinear equation (McGraw Hill, New York, 1970). · Zbl 0242.65047 |
| [10] | T. Ibaraki, ”Parametric approaches to fractional programs”,Mathematical Programming 26 (1983) 345–362. · Zbl 0506.90078 · doi:10.1007/BF02591871 |
| [11] | 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. · Zbl 0534.90088 |
| [12] | 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. · Zbl 0349.90073 |
| [13] | S. Karlin, Mathematical methods and theory in games, programming and economics, Volume 1 (Addison Wesley, Reading, MA, 1959). · Zbl 0139.12704 |
| [14] | 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. · Zbl 0414.90086 |
| [15] | 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. · Zbl 0434.90071 |
| [16] | A.K. Lenstra, H.W. Lenstra, Jr. and L. Lovász, ”Factoring polynomials with rational coefficients”,Mathematische Annalen 261 (1982) 513–534. · Zbl 0488.12001 · doi:10.1007/BF01457454 |
| [17] | K. Mahler, ”On a theorem by E. Bombieri”,Indagationes Mathematicae 22 (1960) 245–253. |
| [18] | N. Megiddo, ”Combinatorial optimization with rational objective functions”,Mathematics of Operations Research 4 (1979) 414–424. · Zbl 0425.90076 · doi:10.1287/moor.4.4.414 |
| [19] | N. Megiddo, ”The weighted Euclidean 1-center problem,”Mathematics of Operations Research 8 (1983) 498–504. · Zbl 0533.90030 · doi:10.1287/moor.8.4.498 |
| [20] | M. Mignotte, ”Identification of algebraic numbers”,Journal of Algorithms 3 (1982) 197–204. · Zbl 0498.12004 · doi:10.1016/0196-6774(82)90019-0 |
| [21] | K.G. Murty, Linear and combinatorial programming (Wiley, New York, 1976). · Zbl 0334.90032 |
| [22] | K.G. Murty, ”Computational complexity of parametric linear programming”,Mathematical Programming 19 (1980) 213–219. · Zbl 0443.90102 · doi:10.1007/BF01581642 |
| [23] | A.M. Ostrowski, Solution of equations in Euclidean and Banach spaces (Academic Press, New York, 1973). · Zbl 0304.65002 |
| [24] | C.H. Papadimitriou, ”Efficient search for rationals”,Information Processing Letters 8 (1979) 1–4. · Zbl 0411.65037 · doi:10.1016/0020-0190(79)90079-6 |
| [25] | A. Ralston, A first course in numerical analysis (McGraw Hill, New York, 1965). · Zbl 0139.31603 |
| [26] | S.P. Reiss, ”Rational search,”Information Processing Letters 8 (1979) 89–90. · Zbl 0393.68068 · doi:10.1016/0020-0190(79)90150-9 |
| [27] | K. Ritter, ”A parametric method for solving certain nonconvex maximization problems”,Journal of Computer and System Sciences 1 (1967) 44–54. · Zbl 0152.18403 · doi:10.1016/S0022-0000(67)80006-0 |
| [28] | K. Ritter, ”A method for solving nonlinear maximum problems depending on parameters”,Naval Research Logistic Quarterly 14 (1967) 147–162. · Zbl 0149.38101 · doi:10.1002/nav.3800140203 |
| [29] | S. Schaible, ”Fractional programming II”,Management Science 22 (1976) 868–873. · Zbl 0346.90052 · doi:10.1287/mnsc.22.8.868 |
| [30] | 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. · Zbl 0535.90092 |
| [31] | S. Schaible and T. Ibaraki, ”Invited review: Fractional programming”,European Journal of Operational Research 12 (1983) 325–338. · Zbl 0529.90088 · doi:10.1016/0377-2217(83)90153-4 |
| [32] | R.G. Schroeder, ”Linear programming solutions to ratio games”,Operations Research 18 (1970) 300–305. · Zbl 0195.21201 · doi:10.1287/opre.18.2.300 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
