Abstract
We introduce a new model algorithm for solving nonlinear programming problems. No slack variables are introduced for dealing with inequality constraints. Each iteration of the method proceeds in two phases. In the first phase, feasibility of the current iterate is improved; in second phase, the objective function value is reduced in an approximate feasible set. The point that results from the second phase is compared with the current point using a nonsmooth merit function that combines feasibility and optimality. This merit function includes a penalty parameter that changes between consecutive iterations. A suitable updating procedure for this penalty parameter is included by means of which it can be increased or decreased along consecutive iterations. The conditions for feasibility improvement at the first phase and for optimality improvement at the second phase are mild, and large-scale implementation of the resulting method is possible. We prove that, under suitable conditions, which do not include regularity or existence of second derivatives, all the limit points of an infinite sequence generated by the algorithm are feasible, and that a suitable optimality measure can be made as small as desired. The algorithm is implemented and tested against the LANCELOT algorithm using a set of hard-spheres problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abadie, J., and Carpentier, J., Generalization of the Wolfe Reduced-Gradient Method to the Case of Nonlinear Constraints, Optimization, Edited by R. Fletcher, Academic Press, New York, NY, pp. 37–47, 1968.
Bielschowsky, R. H., Nonlinear Programming Algorithms with Dynamic Definition of Near-Feasibility: Theory and Implementations, PhD Thesis, IMECC-UNICAMP, Campinas, SP, Brazil, 1996.
Lasdon, L. S., Reduced Gradient Methods, Nonlinear Optimization, 1981, Edited by M. J. D. Powell, Academic Press, New York, NY, pp. 235–242, 1982.
MartÍnez, J. M., and Santos, S. A., A Trust Region Strategy for Minimization on Arbitrary Domains, Mathematical Programming, Vol. 68, pp. 267–302, 1995.
Miele, A., Huang, H. Y., and Heideman, J. C., Sequential Gradient-Restoration Algorithm for the Minimization of Constrained Functions: Ordinary and Conjugate Gradient Version, Journal of Optimization Theory and Applications, Vol. 4, pp. 213–246, 1969.
Miele, A., Levy, A. V., and Cragg, E. E., Modifications and Extensions of the Conjugate-Gradient Restoration Algorithm for Mathematical Programming Problems, Journal of Optimization Theory and Applications, Vol. 7, pp. 450–472, 1971.
Miele, A., Sims, E. M., and Basapur, V. K., Sequential Gradient-Restoration Algorithm for Mathematical Programming Problem with Inequality Constraints, Part 1: Theory, Aero-Astronautics Report 168, Rice University, 1983.
Rom, M., and Avriel, M., Properties of the Sequential Gradient-Restoration Algorithm (SGRA), Part 1: Introduction and Comparison with Related Methods, Journal of Optimization Theory and Applications, Vol. 62, pp. 77–98, 1989.
Rom, M., and Avriel, M., Properties of the Sequential Gradient-Restoration Algorithm (SGRA), Part 2: Convergence Analysis, Journal of Optimization Theory and Applications, Vol. 62, pp. 99–126, 1989.
Rosen, J. B., The Gradient Projection Method for Nonlinear Programming, Part 1: Linear Constraints, SIAM Journal on Applied Mathematics, Vol. 8, pp. 181–217, 1960.
Rosen, J. B., The Gradient Projection Method for Nonlinear Programming, Part 2: Nonlinear Constraints, SIAM Journal on Applied Mathematics, Vol. 9, pp. 514–532, 1961.
Rosen, J. B., Two-Phase Algorithm for Nonlinear Constraint Problems, Nonlinear Programming 3, Edited by O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, Academic Press, London, England, pp. 97–124, 1978.
Wright, M. H., Interior-Point Methods for Constrained Optimization, Acta Numerica, Vol. 1, pp. 341–407, 1992.
MartÍnez, J. M., A Two-Phase Trust-Region Model Algorithm with Global Convergence for Nonlinear Programming, Journal of Optimization Theory and Applications, Vol. 96, pp. 397–436, 1998.
Gay, D. M., A Trust-Region Approach to Linearly Constrained Optimization, Proceedings of the Dundee Biennial Conference on Numerical Analysis, Dundee, Scotland, 1983.
Gill, P. E., Murray, W., and Wright, M. H., Practical Optimization, Academic Press, London, England, 1981.
Murtagh, R. B., and Saunders, M. A., Large-Scale Linearly Constrained Optimization, Mathematical Programming, Vol. 14, pp. 41–72, 1978.
Celis, M. R., Dennis, J. E., and Tapia, R. A., A Trust-Region Strategy for Nonlinear Equality Constrained Optimization, Numerical Optimization, Edited by P. Boggs, R. Byrd, and R. Schnabel, SIAM Publications, Philadelphia, Pennsylvania, pp. 71–82, 1985.
Dennis, J. E., El-alem, M., and Maciel, M. C., A Global Convergence Theory for General Trust-Region-Based Algorithms for Equality Constrained Optimization, SIAM Journal on Optimization, Vol. 7, pp. 177–207, 1997.
El-alem, M., A Robust Trust-Region Algorithm with a Nonmonotonic Penalty Parameter Scheme for Constrained Optimization, SIAM Journal on Optimization, Vol. 5, pp. 348–378, 1995.
Omojokun, E., Trust-Region Strategies for Optimization with Nonlinear Equality and Inequality Constraints, PhD Thesis, Department of Computer Science, University of Colorado, Boulder, Colorado, 1989.
Powell, M. J. D., and Yuan, Y., A Trust-Region Algorithm for Equality Constrained Optimization, Mathematical Programming, Vol. 49, pp. 190–211, 1991.
Gomes, F. M., Maciel, M. C., and Marti´nez, J. M., Nonlinear Programming Algorithms Using Trust Regions and Augmented Lagrangians with Nonmonotone Penalty Parameters, Mathematical Programming, Vol. 84, pp. 161–200, 1999.
Byrd, R. H., Robust Trust-Region Methods for Constrained Optimization, Contributed Presentation, SIAM Conference on Optimization, Houston, Texas, 1987.
Byrd, R. H., Gilbert, J. C., and Nocedal, J., A Trust-Region Method Based on Interior-Point Techniques for Nonlinear Programming, Technical Report OTC 96y02, Optimization Technology Center, Argonne National Laboratory and Northwestern University, Evanston, Illinois, 1996.
Lalee, M., Nocedal, J., and Plantenga, T., On the Implementation of an Algorithm for Large-Scale Equality Constrained Optimization, Technical Report NAM 08, Electrical Engineering and Computer Science Department, Northwestern University, Evanston, Illinois, 1993.
Dennis, J. E., and Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall, Englewood Cliffs, New Jersey, 1983.
Conway, J. H., and Sloane, N. J. C., Sphere Packings, Lattice, and Groups, Springer Verlag, New York, NY, 1988.
Saff, E. B., and Kuijlaars, A. B. J., Distributing Many Points on a Sphere, Mathematical Intelligencer, Vol. 19, pp. 5–11, 1997.
Murtagh, B. A., and Saunders, M. A., MINOS 5.4 User's Guide, Technical Report SOL 83–20, Stanford University, 1995.
Conn, A. R., Gould, N. I. M., and Toint, P. L., LANCELOT: A FORTRAN Package for Large-Scale Nonlinear Optimization (Release A), Springer Series in Computational Mathematics, Springer Verlag, New York, NY, Vol. 17, 1992.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Martínez, J.M., Pilotta, E.A. Inexact-Restoration Algorithm for Constrained Optimization1. Journal of Optimization Theory and Applications 104, 135–163 (2000). https://doi.org/10.1023/A:1004632923654
Issue Date:
DOI: https://doi.org/10.1023/A:1004632923654