Parametric simplex algorithms for solving a special class of nonconvex minimization problems. (English) Zbl 0746.90056
A parametric simplex algorithm is given to minimize the sum of a linear function and the product of two linear functions. This approach extends to a class of nonconvex quadratic programs, and also to minimizing the sum of two linear fractional functions. Computational results are given, and pivoting rules are given for degenerate cases.
Reviewer: B.D.Craven (Parkville)
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C32 | Fractional programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
| 90C31 | Sensitivity, stability, parametric optimization |
| 90C05 | Linear programming |
| 90C20 | Quadratic programming |
Keywords:
parametric simplex algorithm; nonconvex quadratic programs; linear fractional functions; pivoting rulesReferences:
| [1] | Aneja, Y. P., Aggarwal, V., and Nair, K. P. K. (1984), On a Class of Quadratic Programming, EJOR 18, 62-70. · Zbl 0599.90094 · doi:10.1016/0377-2217(84)90262-5 |
| [2] | Bector, C. R. and Dahl, M. (1974), Simplex Type Finite Iteration Technique and Reality for a Special Type of Pseudo-Concave Quadratic Functions, Cahiers du Centre d’Etudes de Recherche Operationnelle 16, 207-222. · Zbl 0297.90064 |
| [3] | Chvátal, V. (1983), Linear Programming, W. H. Freeman and Company. |
| [4] | Cottle, R. W. and Dantzig, G. B. (1968), Complementary Pivot Theory of Mathematical Programing, Linear Algebra and Its Applications 1, 103-125. · Zbl 0155.28403 · doi:10.1016/0024-3795(68)90052-9 |
| [5] | Dantzig, G. B. (1963), Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey. · Zbl 0108.33103 |
| [6] | Henderson, J. M. and Quandt, R. E. (1971), Microeconomics, McGraw-Hill, New York. |
| [7] | Klafszky, E. and Terlaky, T. (1989), Some Generalizations of the Criss-Cross Method for Quadratic Programming, Combinatorica 9, 189-198. · Zbl 0693.05020 · doi:10.1007/BF02124679 |
| [8] | Konno, H. and Inori, M. (1988), Bond Portfolio Optimization by Bilinear Fractional Programming, J. Oper. Res. Soc. of Japan 32, 143-158. · Zbl 0675.90011 |
| [9] | Konno, H. and Kuno, T. (1989), Generalized Linear Multiplicative and Fractional Programming, IHSS Report 89-14, Institute of Human and Social Sciences, Tokyo Institute of Technology. · Zbl 0725.90082 |
| [10] | Konno, H. and Kuno, T. (1989), Linear Multiplicative Programming, IHSS Report 89-13, Institute of Human and Social Sciences, Tokyo Institute of Technology. · Zbl 0761.90080 |
| [11] | Lemke, C. E. (1965), Bimatrix Equilibrium Points and Mathematical Programming, Management Science 11, 681-689. · Zbl 0139.13103 · doi:10.1287/mnsc.11.7.681 |
| [12] | Pardalos, P. M. and Rosen, J. B. (1987), Global Optimization, Springer-Verlag, Berlin. · Zbl 0638.90064 |
| [13] | Schaible, S. (1974), Maximization of Quasiconcave Quotients and Products of Finitely Many Functionals, Cahiers du Centre d’Etudes de Recherche Operationnelle 16, 45-53. · Zbl 0291.90068 |
| [14] | Swarup, K. (1966), Programming with Indefinite Quadratic Function with Linear Constraints, Cahier du Centre d’Etudes de Rescherche Operationnelle 8, 133-136. · Zbl 0141.17505 |
| [15] | Terlaky, T. (1985), A Convergent Criss-Cross Method, Math. Oper. und Stat. ser. Optimization 16, 683-690. · Zbl 0581.90052 |
| [16] | Terlaky, T. (1987), A Finite Criss-Cross Method for Oriented Matroids, J. Combin. Theory. Ser. B 42, 319-327. · Zbl 0588.05010 · doi:10.1016/0095-8956(87)90049-9 |
| [17] | Wang, Z. (1987), A Conformal Elimination Free Algorithm for Oriented Matroid Programming, Chinese Annals of Mathematics 8 B 1. · Zbl 0627.90066 |
| [18] | Zionts, S. (1969), The Criss-Cross Method for Solving Linear Programming Problems, Management Science 15, 426-445. · Zbl 1231.90294 · doi:10.1287/mnsc.15.7.426 |
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.
