## A globally convergent Lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds

HTML articles powered by AMS MathViewer

- by A. R. Conn, Nick Gould and Ph. L. Toint PDF
- Math. Comp.
**66**(1997), 261-288 Request permission

## Abstract:

We consider the global and local convergence properties of a class of Lagrangian barrier methods for solving nonlinear programming problems. In such methods, simple bound constraints may be treated separately from more general constraints. The objective and general constraint functions are combined in a Lagrangian barrier function. A sequence of such functions are approximately minimized within the domain defined by the simple bounds. Global convergence of the sequence of generated iterates to a first-order stationary point for the original problem is established. Furthermore, possible numerical difficulties associated with barrier function methods are avoided as it is shown that a potentially troublesome penalty parameter is bounded away from zero. This paper is a companion to previous work of ours on augmented Lagrangian methods.## References

- K. J. Arrow and R. M. Solow. Gradient methods for constrained maxima, with weakened assumptions. In K. J. Arrow, L. Hurwicz, and H. Uzawa, editors,
*Studies in Linear and non-linear Programming*, pages 166–176, Stanford, USA, 1958. Stanford University Press. - Mordecai Avriel,
*Nonlinear programming*, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1976. Analysis and methods. MR**0489892** - Dimitri P. Bertsekas,
*Constrained optimization and Lagrange multiplier methods*, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR**690767** - M. G. Breitfeld and D. Shanno. Preliminary computational experience with modified log-barrier functions for large-scale nonlinear programming. In W. W. Hager, D. W. Hearn and P. M. Pardalos, editors,
*Large Scale Optimization: State of the Art*, pages 45–67, Dordrecht, 1994. Kluwer Academic Publishers. - M. G. Breitfeld and D. F. Shanno. Computational experience with penalty-barrier methods for nonlinear programming.
*Annals of Operations Research*, 62: 439–463, 1996. - James V. Burke and Jorge J. Moré,
*On the identification of active constraints*, SIAM J. Numer. Anal.**25**(1988), no. 5, 1197–1211. MR**960873**, DOI 10.1137/0725068 - James V. Burke, Jorge J. Moré, and Gerardo Toraldo,
*Convergence properties of trust region methods for linear and convex constraints*, Math. Programming**47**(1990), no. 3, (Ser. A), 305–336. MR**1068268**, DOI 10.1007/BF01580867 - Paul H. Calamai and Jorge J. Moré,
*Projected gradient methods for linearly constrained problems*, Math. Programming**39**(1987), no. 1, 93–116. MR**909010**, DOI 10.1007/BF02592073 - A. R. Conn, N. I. M. Gould, and Ph. L. Toint,
*Global convergence of a class of trust region algorithms for optimization with simple bounds*, SIAM J. Numer. Anal.**25**(1988), no. 2, 433–460. MR**933734**, DOI 10.1137/0725029 - Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint,
*Testing a class of methods for solving minimization problems with simple bounds on the variables*, Math. Comp.**50**(1988), no. 182, 399–430. MR**929544**, DOI 10.1090/S0025-5718-1988-0929544-3 - Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint,
*A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds*, SIAM J. Numer. Anal.**28**(1991), no. 2, 545–572. MR**1087519**, DOI 10.1137/0728030 - A. R. Conn, N. I. M. Gould, and Ph. L. Toint. A globally convergent Lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds. Technical Report 92/07, Department of Mathematics, FUNDP, Namur, Belgium, 1992.
- A. R. Conn, N. I. M. Gould, and Ph. L. Toint.
*LANCELOT: a Fortran package for large-scale nonlinear optimization (Release A )*. Number 17 in Springer Series in Computational Mathematics. Springer Verlag, Heidelberg, Berlin, New York, 1992. - A. R. Conn, N. I. M. Gould, and Ph. L. Toint. On the number of inner iterations per outer iteration of a globally convergent algorithm for optimization with general nonlinear equality constraints and simple bounds. In D.F Griffiths and G.A. Watson, editors,
*Proceedings of the 14th Biennial Numerical Analysis Conference Dundee 1991*, pages 49–68. Longmans, 1992. - A. R. Conn, N. I. M. Gould, and Ph. L. Toint. On the number of inner iterations per outer iteration of a globally convergent algorithm for optimization with general nonlinear inequality constraints and simple bounds. Computational Optimization and Applications, to appear, 1996.
- A. R. Conn, Nick Gould, and Ph. L. Toint,
*A note on exploiting structure when using slack variables*, Math. Programming**67**(1994), no. 1, Ser. A, 89–97. MR**1300820**, DOI 10.1007/BF01582214 - A. R. Conn, Nick Gould, and Ph. L. Toint,
*A note on using alternative second-order models for the subproblems arising in barrier function methods for minimization*, Numer. Math.**68**(1994), no. 1, 17–33. MR**1278446**, DOI 10.1007/s002110050046 - Anthony V. Fiacco,
*Introduction to sensitivity and stability analysis in nonlinear programming*, Mathematics in Science and Engineering, vol. 165, Academic Press, Inc., Orlando, FL, 1983. MR**721641** - Anthony V. Fiacco and Garth P. McCormick,
*Nonlinear programming: Sequential unconstrained minimization techniques*, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR**0243831** - R. Fletcher,
*Practical methods of optimization*, 2nd ed., A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1987. MR**955799** - Robert M. Freund,
*Theoretical efficiency of a shifted-barrier-function algorithm for linear programming*, Linear Algebra Appl.**152**(1991), 19–41. Interior point methods for linear programming. MR**1107543**, DOI 10.1016/0024-3795(91)90265-X - K. R. Frisch. The logarithmic potential method of convex programming. Memorandum of May 13, University Institute of Economics, Oslo, Norway, 1955.
- Philip E. Gill, Walter Murray, Michael A. Saunders, J. A. Tomlin, and Margaret H. Wright,
*On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method*, Math. Programming**36**(1986), no. 2, 183–209. MR**866988**, DOI 10.1007/BF02592025 - P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright. Shifted barrier methods for linear programming. Technical Report SOL88-9, Department of Operations Research, Stanford University, Stanford, California 94305, USA, 1988.
- Nicholas Ian Mark Gould,
*On the accurate determination of search directions for simple differentiable penalty functions*, IMA J. Numer. Anal.**6**(1986), no. 3, 357–372. MR**967676**, DOI 10.1093/imanum/6.3.357 - W. A. Gruver and E. Sachs,
*Algorithmic methods in optimal control*, Research Notes in Mathematics, vol. 47, Pitman (Advanced Publishing Program), Boston, Mass.-London, 1981. MR**604361** - O. Güler, D. den Hertog, C. Roos, T. Terlaky, and T. Tsuchiya. Degeneracy in interior point methods for linear programming. Technical report, Faculty of Technical Mathematics and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands, 1993.
- Harwell Subroutine Library.
*A catalogue of subroutines (release 11 )*. Advanced Computing Department, Harwell Laboratory, Harwell, UK, 1993. - Magnus R. Hestenes,
*Multiplier and gradient methods*, J. Optim. Theory Appl.**4**(1969), 303–320. MR**271809**, DOI 10.1007/BF00927673 - Florian Jarre and Michael A. Saunders,
*A practical interior-point method for convex programming*, SIAM J. Optim.**5**(1995), no. 1, 149–171. MR**1315709**, DOI 10.1137/0805008 - D. Jensen and R. Polyak. On the convergence of a modified barrier method for convex programming.
*IBM J. Res. Develop.*, 38(3):307–321, 1994. - D. L. Jensen, R. Polyak, and R. Schneur. Numerical experience with modified barrier functions method for linear programming. Research Report RC 18415, IBM T. J. Watson Research Center, Yorktown Heights, NY, USA, 1992.
- Krisorn Jittorntrum and M. R. Osborne,
*A modified barrier function method with improved rate of convergence for degenerate problems*, J. Austral. Math. Soc. Ser. B**21**(1979/80), no. 3, 305–329. MR**551434**, DOI 10.1017/S033427000000240X - N. Karmarkar,
*A new polynomial-time algorithm for linear programming*, Combinatorica**4**(1984), no. 4, 373–395. MR**779900**, DOI 10.1007/BF02579150 - E. Kranich. Interior point methods for mathematical programming: A bibliography. Discussion Paper 171, Institute of Economy and Operations Research, FernUniversität Hagen, P.O. Box 940, D–5800 Hagen 1, West–Germany, May 1991. The bibliography can be accessed electronically by sending email to ’netlib@research.att.com’ or ’netlib@ukc.ac.uk’ with the message ’send intbib.bib from bib’.
- F. A. Lootsma,
*Hessian matrices of penalty functions for solving constrained-optimization problems*, Philips Res. Rep.**24**(1969), 322–330. MR**305594** - Irvin J. Lustig, Roy E. Marsten, and David F. Shanno,
*Computational experience with a primal-dual interior point method for linear programming*, Linear Algebra Appl.**152**(1991), 191–222. Interior point methods for linear programming. MR**1107553**, DOI 10.1016/0024-3795(91)90275-2 - G. P. McCormick. The superlinear convergence of a nonlinear primal-dual algorithm. Technical Report OR T-550/91, Department of Operations Research, George Washington University, Washington DC 20052, 1991.
- Robert Mifflin,
*Convergence bounds for nonlinear programming algorithms*, Math. Programming**8**(1975), 251–271. MR**376154**, DOI 10.1007/BF01580447 - W. Murray,
*Analytical expressions for the eigenvalues and eigenvectors of the Hessian matrices of barrier and penalty functions*, J. Optim. Theory Appl.**7**(1971), 189–196. MR**284212**, DOI 10.1007/BF00932477 - W. Murray. Ill-conditioning in barrier methods. In
*Advances in numerical partial differential equations and optimization, Proceedings of the Sixth Mexico-United States Workshop*, Philadelphia, USA, 1992. SIAM. - W. Murray and M. H. Wright. Project Lagrangian methods based on the trajectories of penalty and barrier functions. Technical Report SOL78-23, Department of Operations Research, Stanford University, Stanford, California 94305, USA, 1978.
- S. G. Nash, R. Polyak, and A. Sofer. A numerical comparison of barrier and modified barrier methods for large-scale constrained optimization. In W. W. Hager, D. W. Hearn and P. M. Pardalos, editors,
*Large Scale Optimization: State of the Art*, pages 319–338, Dordrecht, 1994. Kluwer Academic Publishers. - S. G. Nash and A. Sofer. A barrier method for large-scale constrained optimization.
*ORSA Journal on Computing*, 5(1):40–53, 1993. - Y. Nesterov and A. Nemirovsky.
*Self-concordant functions and polynomial-time methods in convex programming*. SIAM, Philadelphia, USA, 1993. - J. M. Ortega and W. C. Rheinboldt,
*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810** - R. Polyak,
*Modified barrier functions (theory and methods)*, Math. Programming**54**(1992), no. 2, Ser. A, 177–222. MR**1158819**, DOI 10.1007/BF01586050 - R. A. Polyak. Smooth optimization methods for solving nonlinear extremal and equilibrium problems with constraints. Paper presented at the XIth International Symposium on Mathematical Programming, Bonn, Federal Republic of Germany, August 1982.
- D. B. Ponceleón.
*Barrier methods for large-scale quadratic programming*. PhD thesis, Department of Computer Science, Stanford University, Stanford, California 94305, USA, 1990. - M. J. D. Powell,
*A method for nonlinear constraints in minimization problems*, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 283–298. MR**0272403** - M. J. D. Powell. Log barrier methods for semi-infinite programming calculations. In E. A. Lipitakis, editor,
*Advances on Computer Mathematics and its Applications*, pages 1–21, Singapore, 1993. World Scientific. - M. J. D. Powell. Some convergence properties of the modified log barrier method for linear programming.
*SIAM Journal on Optimization*, 5(4): 695–740, 1995. - F. Rendl, R. J. Vanderbei, and H. Wolkowicz. Primal-dual interior point algorithms for max-min eigenvalue problems. Technical Report CORR93-20, Faculty of Mathematics, University of Waterloo, 1993.
- R. T. Rockafellar,
*Augmented Lagrangians and applications of the proximal point algorithm in convex programming*, Math. Oper. Res.**1**(1976), no. 2, 97–116. MR**418919**, DOI 10.1287/moor.1.2.97 - M. H. Wright.
*Numerical methods for nonlinearly constrained optimization*. PhD thesis, Department of Computer Science, Stanford University, Stanford, California 94305, USA, 1976. - Margaret H. Wright,
*Interior methods for constrained optimization*, Acta numerica, 1992, Acta Numer., Cambridge Univ. Press, Cambridge, 1992, pp. 341–407. MR**1165729**, DOI 10.1017/s0962492900002300

## Additional Information

**A. R. Conn**- Affiliation: IBM T.J. Watson Research Center, P.O.Box 218, Yorktown Heights, New York 10598
- Email: arconn@watson.ibm.com
**Nick Gould**- Affiliation: Rutherford Appleton Laboratory, Chilton, OX11 0QX, England
- MR Author ID: 75720
- Email: nimg@letterbox.rl.ac.uk
**Ph. L. Toint**- Affiliation: Département de Mathématiques, Facultés Universitaires ND de la Paix, 61, rue de Bruxelles, B-5000 Namur, Belgium
- Email: pht@math.fundp.ac.be
- Received by editor(s): September 13, 1994
- Received by editor(s) in revised form: September 19, 1995
- Additional Notes: The research of Conn and Toint was supported in part by the Advanced Research Projects Agency of the Departement of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.

Current reports available by anonymous ftp from the directory “pub/reports” on joyous-gard.cc.rl.ac.uk (internet 130.246.9.91)

Current reports available by anonymous ftp from the directory “pub/reports” on thales.math.fundp.ac.be (internet 138.48.20.102) - © Copyright 1997 American Mathematical Society
- Journal: Math. Comp.
**66**(1997), 261-288 - MSC (1991): Primary 90C30; Secondary 65K05
- DOI: https://doi.org/10.1090/S0025-5718-97-00777-1
- MathSciNet review: 1370850