Abstract
A new method for linearly constrained nonlinear programming is proposed. This method follows affine scaling paths defined by systems of ordinary differential equations and it is fully parallelizable. The convergence of the method is proved for a nondegenerate problem with pseudoconvex objective function. In practice, the algorithm works also under more general assumptions on the objective function. Numerical results obtained with this computational method on several test problems are shown.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Karmarkar, N., A New Polynomial Time Algorithm in Linear Programming, Combinatorica, Vol. 4, pp. 373–395, 1984.
Vanderbei, R. J., Meketon, M. S., and Freedman, B. A., A Modification of Karmarkar's Linear Programming Algorithm, Algorithmica, Vol. 1, pp. 395–407, 1986.
Megiddo, N., Editor, Progress In Mathematical Programming: Interior Point and Related Methods, Springer Verlag, New York, New York, 1989.
Lagarias, J. C., and Todd, M. J., Editors, Mathematical Developments Arising from Linear Programming, Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, Vol. 114, 1990.
Ye, Y., and Tse, E., An Extension of Karmarkar's Projective Algorithm for Convex Quadratic Programming, Mathematical Programming, Vol. 44, pp. 157–179, 1989.
Freund, R. M., Projective Transformation for Interior-Point Algorithms and a Superly-Convergent Algorithm for the W-Center Problem, Mathematical Programming, Vol. 58, pp. 385–414, 1993.
Saigal, R., Linear Programming: A Modern Integrated Analysis, Kluwer Academic Publishers, Dordrecht, Holland, 1995.
Terlaky, T., Editor, Interior-Point Methods of Mathematical Programming, Kluwer Academic Publishers, Dordrecht, Holland, 1996.
Tsuchiya, R. T., and Muramatsu, M., Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming, SIAM Journal on Optimization, Vol. 5, pp. 525–551, 1995.
Monteiro, R. C., and Adler, I., Interior Path-Following Primal-Dual Algorithms, Part 1: Linear Programming, Part 2: Convex Quadratic Programming, Mathematical Programming, Vol. 44, pp. 27–66, 1989.
Bayer, D. A., and Lagarias, J. C., The Nonlinear Geometry of Linear Programming, Part 1, Transactions of the American Mathematical Society, Vol. 314, pp. 499–526, 1989.
Herzel, S., Recchioni, M. C., and Zirilli, F., A Quadratically Convergent Method of Linear Programming, Linear Algebra and Its Applications, Vol. 152, pp. 255–289, 1991.
Zirilli, F., The Use of Ordinary Differential Equations in the Solution of Nonlinear Systems of Equations, Nonlinear Optimization 1981, Edited by M. T. D. Powell, Academic Press, New York, NY, pp. 39–47, 1982.
Mangasarian, O. L., Nonlinear Programming, McGraw Hill Book Company, New York, NY, 1969.
Swarup, K., Linear Fractional Functional Programming, Operations Research, Vol. 13, pp. 1029–1036, 1965.
Wolfe, P., On the Convergence of Gradient Methods under Constraints, IBM Journal of Research and Development, Vol. 16, pp. 407–411, 1972.
Dussalt, J. P., and Fournier, G., On the Convergence of the Projected Gradient Method, Journal of Optimization Theory and Applications, Vol. 77, pp. 197–208, 1993.
Cambini, A., and Martein, L., A Modified Version of Martos Algorithm for the Linear Fractional Problem, International Workshop on Generalized Concavity, Fractional Programming, and Economic Applications, Pisa, Italy, 1988.
Ellero, A., and Moretti, E., A Parametric Simplex-iLike Algorithm for a Quadratic Fractional Programming Problem, Optimization of Generalized Convex Problems in Economics, Edited by P. Mazzoleni, Tecnoprint, Milan, Italy, pp. 163–176, 1994.
Falk, J. E., and Polacsay, S. W., Optimizing the Sum of Linear Fractional Functions, Recent Advances in Global Optimization, Edited by C. A. Floudas and P. M. Pardalos, Princeton University Press, Princeton, New Jersey, pp. 221–258, 1992.
Ortega, J. M., and Rheinboldt, W. C., Iterative Solution of Nonlinear Equations, McGraw Hill, New York, NY, 1983.
La salle, J., and Lefschetz, S., Stability by Lyapounov's Direct Method, Academic Press, New York, NY, 1961.
Perko, L., Differential Equations and Dynamical Systems, Texts in Applied Mathematics, Springer Verlag, New York, NY, Vol. 7, 1991.
Karloff, H., Linear Programming, Birkhäuser, Boston, Massachusetts, 1991.
Almogy, Y., and Levin, O., A Class of Fractional Programming Problems, Operations Research, Vol. 19, pp. 57–67, 1971.
Zwart, P. B., Nonlinear Programming: Counterexamples to Two Global Optimization Algorithms, Operations Research, Vol. 21, pp. 1260–1266, 1973.
Falk, J. E., and Hoffman, K. R., A Successive Underestimation Method for Concave Minimization Problems, Mathematics of Operations Research, Vol. 1, pp. 251–259, 1976.
Gay, D. M., Electronic Mail Distribution of Linear Programming Test Problems, Committee on Algorithms Newsletter, Mathematical Programming Society, Vol. 13, 1985.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Pacelli, G., Recchioni, M.C. Monotone Variable–Metric Algorithm for Linearly Constrained Nonlinear Programming. Journal of Optimization Theory and Applications 104, 255–279 (2000). https://doi.org/10.1023/A:1004645328197
Issue Date:
DOI: https://doi.org/10.1023/A:1004645328197