×

zbMATH — the first resource for mathematics

An interior-point method for multifractional programs with convex constraints. (English) Zbl 0824.90127
Summary: We present an interior-point method for a family of multifractional programs with convex constraints. The programs under consideration consists of minimizing the maximum of a finite number of linear fractions over some convex set. First, we present a simple short-step algorithm for solving such multifractional programs, and we show that, under suitable assumptions, the convergence of the short-step algorithm is weakly polynomial in a sense specified below. Then, we describe a practical implementation of the proposed method, and we report results of numerical experiments with this algorithm. These results suggest that the proposed method is a viable alternative to the standard Dinkelbach-type algorithms for solving multifractional programs.

MSC:
90C32 Fractional programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Karmarkar, N.,A New Polynomial-Time Algorithm for Linear Programming, Combinatorica, Vol. 4, pp. 373–395, 1984. · Zbl 0557.90065
[2] Alizadeh, F.,Optimization over the Positive-Semidefinite Cone: Interior-Point Methods and Combinatorial Applications, Advances in Optimization and Parallel Computing, Edited by P. Pardalos, North Holland, Amsterdam, Holland pp. 1–25, 1992. · Zbl 0814.90071
[3] Den Hertog, D., Jarre, F., Roos, C., andTerlaky, T.,A Unifying Investigation of Interior-Point Methods for Convex Programming, Report No. 92-89, Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, Holland, 1992.
[4] Jarre, F.,On the Method of Analytic Centers for Solving Smooth Convex Programs, Lecture Notes in Mathematics, Springer Verlag, Berlin, Germany, Vol. 1405, pp. 69–85, 1989. · Zbl 0684.90068
[5] Jarre, F.,Interior-Point Methods for Convex Programming, Applied Mathematics and Optimization, Vol. 26, pp. 287–311, 1992. · Zbl 0767.90063
[6] Nesterov, J. E., andNemirovsky, A. S.,A General Approach to Polynomial-Time Algorithms Design for Convex Programming, Report, Central Economical and Mathematical Institute, USSR Academy of Science, Moscow, Russia, 1988.
[7] Nesterov, J. E., andNemirovsky, A. S.,Self-Concordant Functions and Polynomial-Time Methods in Convex Programming, Report, Central Economical and Mathematical Institute, USSR Academy of Science, Moscow, Russia, 1989.
[8] Sonnevend, G.,An Analytical Centre for Polyhedrons and New Classes of Global Algorithms for Linear (Smooth Convex) Programming, Lecture Notes in Control and Information Sciences, Springer Verlag, Berlin, Germany, Vol. 84, pp. 866–875, 1986. · Zbl 0602.90106
[9] Renegar, J.,Linear Programming, Complexity Theory and Elementary Functional Analysis, Report, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York, 1993. · Zbl 0855.90085
[10] Freund, R. W., andJarre, F.,An Interior-Point Method for Convex Fractional Programming, AT&T Numerical Analysis Manuscript No. 93-03, Bell Laboratories, Murray Hill, New Jersey, 1993.
[11] Von Neumann, J.,A Model of General Economic Equilibrium, Review of Economic Studies, Vol. 13, pp. 1–9, 1945.
[12] Schaible, S.,Bibliography in Fractional Programming, Zeitschrift für Operations Research, Vol. 26, pp. 211–241, 1982. · Zbl 0494.90076
[13] Schaible, S.,Fractional Programming, Zeitschrift für Operations Research, Vol. 27, pp. 39–54, 1983. · Zbl 0527.90094
[14] Schaible, S.,Multi-Ratio Fractional Programming–A Survey, Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, Germany, Vol. 304, pp. 57–66, 1988. · Zbl 0645.90085
[15] Barrodale, I., Powell, M. J. D., andRoberts, F. D. K.,The Differential Correction Algorithm for Rational l Approximation, SIAM Journal on Numerical Analysis, Vol. 9, pp. 493–504, 1972. · Zbl 0251.65008
[16] Nesterov, J. E., andNemirovsky, A. S.,An Interior Point Method for Generalized Linear-Fractional Programming, Report, Central Economical and Mathematical Institute, USSR Academy of Sciences, Moscow, Russia, 1991.
[17] Boyd, S., andEl Ghaoui, L.,Method of Centers for Minimizing Generalized Eigenvalues, Linear Algebra and Its Applications, Vols. 188/189, pp. 63–111, 1993. · Zbl 0781.65051
[18] Dinkelbach, W.,On Nonlinear Fractional Programming, Management Science, Vol. 13, pp. 492–498, 1967. · Zbl 0152.18402
[19] Bector, C. R., andCambini, A.,Fractional Programming–Some Recent Results, Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, Germany, Vol. 345, pp. 86–98, 1989.
[20] Benadada, Y., Crouzeix, J. P., andFerland, J. A.,An Interval-Type Algorithm for Generalized Fractional Programming, Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, Germany, Vol. 345, pp. 106–120, 1989.
[21] Crouzeix, J. P., andFerland, J. A.,Algorithms for Generalized Fractional Programming, Mathematical Programming, Vol. 52, pp. 191–207, 1991. · Zbl 0748.90067
[22] Crouzeix, J. P., Ferland, J. A., andSchaible, S.,An Algorithm for Generalized Fractional Programs, Journal of Optimization Theory and Applications, Vol. 47, pp. 35–49, 1985. · Zbl 0548.90083
[23] Ferland, J. A. andPotvin, J. Y.,Generalized Fractional Programming: Algorithms and Numerical Experimentation, European Journal of Operational Research, Vol. 20, pp. 92–101, 1985. · Zbl 0564.90081
[24] Braess, D.,Nonlinear Approximation Theory, Springer Verlag, Berlin, Germany, 1986. · Zbl 0656.41001
[25] Fiacco, A. V., andMcCormick, G. P., Nonlinear Programming: Sequential Unconstrained Minimization Technique, Wiley, New York, New York, 1968. · Zbl 0193.18805
[26] Dikin, I.,Iterative Solution of Problems of Linear and Quadratic Programming, Soviet Mathematics Doklady, Vol. 8, pp. 674–675, 1967. · Zbl 0189.19504
[27] Sonnevend, G. andStoer, J.,Global Ellipsoidal Approximations and Homotopy Methods for Solving Convex Analytic Programs, Applied Mathematics and Optimization, Vol. 21, pp. 139–165, 1990. · Zbl 0691.90071
[28] Jarre, F.,Optimal Ellipsoidal Approximations Around the Analytic Center, Applied Mathematics and Optimization, Vol. 30, pp. 15–19, 1994. · Zbl 0819.90070
[29] Mangasarian, O. L.,Nonlinear Programming, McGraw-Hill, New York, New York, 1969.
[30] Jagannathan, R.,An Algorithm for a Class of Nonconvex Programming Problems with Nonlinear Fractional Objectives, Management Science, Vol. 31, pp. 847–851, 1985. · Zbl 0609.90102
[31] Cheney, E. W., andLoeb, H. L.,Two New Algorithms for Rational Approximation, Numerische Mathematik, Vol. 3, pp. 72–75, 1961. · Zbl 0114.32804
[32] Flachs, J.,Generalized Cheney-Loeb-Dinkelbach-Type Algorithms, Mathematics of Operations Research, Vol. 10, pp. 674–687, 1985. · Zbl 0583.90088
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.