A Globally Convergent Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds
Authors:
A. R. Conn, Nick Gould and Ph. L. Toint
Journal:
Math. Comp. 66 (1997), 261288
MSC (1991):
Primary 90C30; Secondary 65K05
Supplement:
Additional information related to this article.
MathSciNet review:
1370850
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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 firstorder 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.
 1.
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 nonlinear Programming, pages 166176, Stanford, USA, 1958. Stanford University Press.
 2.
Mordecai
Avriel, Nonlinear programming, PrenticeHall, Inc., Englewood
Cliffs, N.J., 1976. Analysis and methods; PrenticeHall Series in Automatic
Computation. MR
0489892 (58 #9264)
 3.
Dimitri
P. Bertsekas, Constrained optimization and Lagrange multiplier
methods, Computer Science and Applied Mathematics, Academic Press,
Inc. [Harcourt Brace Jovanovich, Publishers], New YorkLondon, 1982. MR 690767
(84k:90068)
 4.
M. G. Breitfeld and D. Shanno. Preliminary computational experience with modified logbarrier functions for largescale nonlinear programming. In W. W. Hager, D. W. Hearn and P. M. Pardalos, editors, Large Scale Optimization: State of the Art, pages 4567, Dordrecht, 1994. Kluwer Academic Publishers. CMP 95:05
 5.
M. G. Breitfeld and D. F. Shanno. Computational experience with penaltybarrier methods for nonlinear programming. Annals of Operations Research, 62: 439463, 1996. CMP 96:12
 6.
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
(89i:90068), http://dx.doi.org/10.1137/0725068
 7.
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
(91f:90114), http://dx.doi.org/10.1007/BF01580867
 8.
Paul
H. Calamai and Jorge
J. Moré, Projected gradient methods for linearly constrained
problems, Math. Programming 39 (1987), no. 1,
93–116. MR
909010 (89f:90132), http://dx.doi.org/10.1007/BF02592073
 9.
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
(89h:90192), http://dx.doi.org/10.1137/0725029
A.
R. Conn, N.
I. M. Gould, and Ph.
L. Toint, Correction to the paper: “Global convergence of a
class of trust region algorithms for optimization with simple bounds”
[SIAM J.\ Numer.\ Anal.\ {25} (1988), no.\ 2, 433–460; MR0933734
(89h:90192)], SIAM J. Numer. Anal. 26 (1989),
no. 3, 764–767. MR 997667
(90d:90071), http://dx.doi.org/10.1137/0726044
 10.
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
(89e:65061), http://dx.doi.org/10.1090/S00255718198809295443
 11.
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
(91k:90158), http://dx.doi.org/10.1137/0728030
 12.
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.
 13.
A. R. Conn, N. I. M. Gould, and Ph. L. Toint. LANCELOT: a Fortran package for largescale nonlinear optimization (Release A ). Number 17 in Springer Series in Computational Mathematics. Springer Verlag, Heidelberg, Berlin, New York, 1992. CMP 93:12
 14.
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 4968. Longmans, 1992. CMP 92:16
 15.
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.
 16.
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
(95h:90124), http://dx.doi.org/10.1007/BF01582214
 17.
A.
R. Conn, Nick
Gould, and Ph.
L. Toint, A note on using alternative secondorder models for the
subproblems arising in barrier function methods for minimization,
Numer. Math. 68 (1994), no. 1, 17–33. MR 1278446
(95a:90119), http://dx.doi.org/10.1007/s002110050046
 18.
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
(85b:90072)
 19.
Anthony
V. Fiacco and Garth
P. McCormick, Nonlinear programming: Sequential unconstrained
minimization techniques, John Wiley and Sons, Inc., New
YorkLondonSydney, 1968. MR 0243831
(39 #5152)
 20.
R.
Fletcher, Practical methods of optimization, 2nd ed., A
WileyInterscience Publication, John Wiley & Sons, Ltd., Chichester,
1987. MR
955799 (89j:65050)
 21.
Robert
M. Freund, Theoretical efficiency of a shiftedbarrierfunction
algorithm for linear programming, Linear Algebra Appl.
152 (1991), 19–41. Interior point methods for linear
programming. MR
1107543 (92e:90031), http://dx.doi.org/10.1016/00243795(91)90265X
 22.
K. R. Frisch. The logarithmic potential method of convex programming. Memorandum of May 13, University Institute of Economics, Oslo, Norway, 1955.
 23.
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
(88h:90123), http://dx.doi.org/10.1007/BF02592025
 24.
P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright. Shifted barrier methods for linear programming. Technical Report SOL889, Department of Operations Research, Stanford University, Stanford, California 94305, USA, 1988.
 25.
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
(89i:90072), http://dx.doi.org/10.1093/imanum/6.3.357
 26.
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
(82j:49029)
 27.
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.
 28.
Harwell Subroutine Library. A catalogue of subroutines (release 11 ). Advanced Computing Department, Harwell Laboratory, Harwell, UK, 1993.
 29.
Magnus
R. Hestenes, Multiplier and gradient methods, J. Optimization
Theory Appl. 4 (1969), 303–320. MR 0271809
(42 #6690)
 30.
Florian
Jarre and Michael
A. Saunders, A practical interiorpoint method for convex
programming, SIAM J. Optim. 5 (1995), no. 1,
149–171. MR 1315709
(95k:90058), http://dx.doi.org/10.1137/0805008
 31.
D. Jensen and R. Polyak. On the convergence of a modified barrier method for convex programming. IBM J. Res. Develop., 38(3):307321, 1994.
 32.
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.
 33.
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
(80k:65046), http://dx.doi.org/10.1017/S033427000000240X
 34.
N.
Karmarkar, A new polynomialtime algorithm for linear
programming, Combinatorica 4 (1984), no. 4,
373–395. MR
779900 (86i:90072), http://dx.doi.org/10.1007/BF02579150
 35.
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, D5800 Hagen 1, WestGermany, May 1991. The bibliography can be accessed electronically by sending email to 'netlib.att.com' or 'netlib.ac.uk' with the message 'send intbib.bib from bib'.
 36.
F.
A. Lootsma, Hessian matrices of penalty functions for solving
constrainedoptimization problems, Philips Res. Rep.
24 (1969), 322–330. MR 0305594
(46 #4724)
 37.
Irvin
J. Lustig, Roy
E. Marsten, and David
F. Shanno, Computational experience with a primaldual interior
point method for linear programming, Linear Algebra Appl.
152 (1991), 191–222. Interior point methods for
linear programming. MR 1107553
(92d:90041), http://dx.doi.org/10.1016/00243795(91)902752
 38.
G. P. McCormick. The superlinear convergence of a nonlinear primaldual algorithm. Technical Report OR T550/91, Department of Operations Research, George Washington University, Washington DC 20052, 1991.
 39.
Robert
Mifflin, Convergence bounds for nonlinear programming
algorithms, Math. Programming 8 (1975),
251–271. MR 0376154
(51 #12340)
 40.
W.
Murray, Analytical expressions for the eigenvalues and eigenvectors
of the Hessian matrices of barrier and penalty functions, J.
Optimization Theory Appl. 7 (1971), 189–196. MR 0284212
(44 #1441)
 41.
W. Murray. Illconditioning in barrier methods. In Advances in numerical partial differential equations and optimization, Proceedings of the Sixth MexicoUnited States Workshop, Philadelphia, USA, 1992. SIAM.
 42.
W. Murray and M. H. Wright. Project Lagrangian methods based on the trajectories of penalty and barrier functions. Technical Report SOL7823, Department of Operations Research, Stanford University, Stanford, California 94305, USA, 1978.
 43.
S. G. Nash, R. Polyak, and A. Sofer. A numerical comparison of barrier and modified barrier methods for largescale constrained optimization. In W. W. Hager, D. W. Hearn and P. M. Pardalos, editors, Large Scale Optimization: State of the Art, pages 319338, Dordrecht, 1994. Kluwer Academic Publishers. CMP 95:05
 44.
S. G. Nash and A. Sofer. A barrier method for largescale constrained optimization. ORSA Journal on Computing, 5(1):4053, 1993. CMP 93:07
 45.
Y. Nesterov and A. Nemirovsky. Selfconcordant functions and polynomialtime methods in convex programming. SIAM, Philadelphia, USA, 1993.
 46.
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 47.
R.
Polyak, Modified barrier functions (theory and methods), Math.
Programming 54 (1992), no. 2, Ser. A, 177–222.
MR
1158819 (93c:90083), http://dx.doi.org/10.1007/BF01586050
 48.
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.
 49.
D. B. Ponceleón. Barrier methods for largescale quadratic programming. PhD thesis, Department of Computer Science, Stanford University, Stanford, California 94305, USA, 1990.
 50.
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
(42 #7284)
 51.
M. J. D. Powell. Log barrier methods for semiinfinite programming calculations. In E. A. Lipitakis, editor, Advances on Computer Mathematics and its Applications, pages 121, Singapore, 1993. World Scientific.
 52.
M. J. D. Powell. Some convergence properties of the modified log barrier method for linear programming. SIAM Journal on Optimization, 5(4): 695740, 1995. CMP 96:03
 53.
F. Rendl, R. J. Vanderbei, and H. Wolkowicz. Primaldual interior point algorithms for maxmin eigenvalue problems. Technical Report CORR9320, Faculty of Mathematics, University of Waterloo, 1993.
 54.
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 0418919
(54 #6954)
 55.
M. H. Wright. Numerical methods for nonlinearly constrained optimization. PhD thesis, Department of Computer Science, Stanford University, Stanford, California 94305, USA, 1976.
 56.
Margaret
H. Wright, Interior methods for constrained optimization, Acta
numerica, 1992, Acta Numer., Cambridge Univ. Press, Cambridge, 1992,
pp. 341–407. MR 1165729
(93d:90037)
 1.
 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 nonlinear Programming, pages 166176, Stanford, USA, 1958. Stanford University Press.
 2.
 M. Avriel. Nonlinear Programming: Analysis and Methods. PrenticeHall, Englewood Cliffs, N.J., 1976. MR 58:9264
 3.
 D. P. Bertsekas. Constrained Optimization and Lagrange Multiplier Methods. Academic Press, London, 1982. MR 84k:90068
 4.
 M. G. Breitfeld and D. Shanno. Preliminary computational experience with modified logbarrier functions for largescale nonlinear programming. In W. W. Hager, D. W. Hearn and P. M. Pardalos, editors, Large Scale Optimization: State of the Art, pages 4567, Dordrecht, 1994. Kluwer Academic Publishers. CMP 95:05
 5.
 M. G. Breitfeld and D. F. Shanno. Computational experience with penaltybarrier methods for nonlinear programming. Annals of Operations Research, 62: 439463, 1996. CMP 96:12
 6.
 J. V. Burke and J. J. Moré. On the identification of active constraints. SIAM Journal on Numerical Analysis, 25(5):11971211, 1988. MR 89i:90068
 7.
 J. V. Burke, J. J. Moré, and G. Toraldo. Convergence properties of trust region methods for linear and convex constraints. Mathematical Programming, Series A, 47(3):305336, 1990. MR 91f:90114
 8.
 P. H. Calamai and J. J. Moré. Projected gradient methods for linearly constrained problems. Mathematical Programming, 39:93116, 1987. MR 89f:90132
 9.
 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 Journal on Numerical Analysis, 25:433460, 1988. See also same journal 26:764767, 1989. MR 89h:90192; MR 90d:90071
 10.
 A. R. Conn, N. I. M. Gould, and Ph. L. Toint. Testing a class of methods for solving minimization problems with simple bounds on the variables. Mathematics of Computation, 50:399430, 1988. MR 89e:65061
 11.
 A. R. Conn, N. I. M. Gould, and Ph. L. Toint. A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds. SIAM Journal on Numerical Analysis, 28(2):545572, 1991. MR 91k:90158
 12.
 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.
 13.
 A. R. Conn, N. I. M. Gould, and Ph. L. Toint. LANCELOT: a Fortran package for largescale nonlinear optimization (Release A ). Number 17 in Springer Series in Computational Mathematics. Springer Verlag, Heidelberg, Berlin, New York, 1992. CMP 93:12
 14.
 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 4968. Longmans, 1992. CMP 92:16
 15.
 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.
 16.
 A. R. Conn, Nick Gould, and Ph. L. Toint. A note on exploiting structure when using slack variables. Mathematical Programming, Series A, 67(1):8997, 1994. MR 95h:90124
 17.
 A. R. Conn, Nick Gould, and Ph. L. Toint. A note on using alternative secondorder models for the subproblems arising in barrier function methods for minimization. Numerische Mathematik, 68:1733, 1994. MR 95a:90119
 18.
 A. V. Fiacco. Introduction to sensitivity and stability analysis in nonlinear programming. Academic Press, New York, 1983. MR 85b:90072
 19.
 A. V. Fiacco and G. P. McCormick. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. J. Wiley and Sons, New York, 1968. Reprinted as Classics in Applied Mathematics 4, SIAM, 1990. MR 39:5152
 20.
 R. Fletcher. Practical Methods of Optimization. J. Wiley and Sons, Chichester, second edition, 1987. MR 89j:65050
 21.
 R. M. Freund. Theoretical efficiency of a shiftedbarrierfunction algorithm for linear programming. Linear Algebra and its Applications, 152:1941, 1991. MR 92e:90031
 22.
 K. R. Frisch. The logarithmic potential method of convex programming. Memorandum of May 13, University Institute of Economics, Oslo, Norway, 1955.
 23.
 P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin, and M. H. Wright. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method. Mathematical Programming, 36:183209, 1986. MR 88h:90123
 24.
 P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright. Shifted barrier methods for linear programming. Technical Report SOL889, Department of Operations Research, Stanford University, Stanford, California 94305, USA, 1988.
 25.
 N. I. M. Gould. On the accurate determination of search directions for simple differentiable penalty functions. IMA Journal of Numerical Analysis, 6:357372, 1986. MR 89i:90072
 26.
 W. A. Gruver and E. Sachs. Algorithmic Methods in Optimal Control. Pitman, Boston, USA, 1981. MR 82j:49029
 27.
 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.
 28.
 Harwell Subroutine Library. A catalogue of subroutines (release 11 ). Advanced Computing Department, Harwell Laboratory, Harwell, UK, 1993.
 29.
 M. R. Hestenes. Multiplier and gradient methods. Journal of Optimization Theory and Applications, 4:303320, 1969. MR 42:6690
 30.
 F. Jarre and M. A. Saunders. A practical interior point method for convex programming. SIAM Journal on Optimization, 5(1):149171, 1995. MR 95k:90058
 31.
 D. Jensen and R. Polyak. On the convergence of a modified barrier method for convex programming. IBM J. Res. Develop., 38(3):307321, 1994.
 32.
 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.
 33.
 K. Jittorntrum and M. Osborne. A modified barrier function method with improved rate of convergence for degenerate problems. Journal of the Australian Mathematical Society (Series B ), 21:305329, 1980. MR 80k:65046
 34.
 N. Karmarkar. A new polynomialtime algorithm for linear programming. Combinatorica, 4:373395, 1984. MR 86i:90072
 35.
 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, D5800 Hagen 1, WestGermany, May 1991. The bibliography can be accessed electronically by sending email to 'netlib.att.com' or 'netlib.ac.uk' with the message 'send intbib.bib from bib'.
 36.
 F. A. Lootsma. Hessian matrices of penalty functions for solving constrained optimization problems. Philips Research Reports, 24:322331, 1969. MR 46:4724
 37.
 I.J. Lustig, R.E. Marsten, and D.F. Shanno. Computational experience with a primaldual interior point method for linear programming. Linear Algebra and its Applications, 152:191222, 1991. MR 92d:90041
 38.
 G. P. McCormick. The superlinear convergence of a nonlinear primaldual algorithm. Technical Report OR T550/91, Department of Operations Research, George Washington University, Washington DC 20052, 1991.
 39.
 R. Mifflin. Convergence bounds for nonlinear programming algorithms. Mathematical Programming, 8:251271, 1975. MR 51:12340
 40.
 W. Murray. Analytical expressions for eigenvalues and eigenvectors of the Hessian matrices of barrier and penalty functions. Journal of Optimization Theory and Applications, 7:189196, 1971. MR 44:1441
 41.
 W. Murray. Illconditioning in barrier methods. In Advances in numerical partial differential equations and optimization, Proceedings of the Sixth MexicoUnited States Workshop, Philadelphia, USA, 1992. SIAM.
 42.
 W. Murray and M. H. Wright. Project Lagrangian methods based on the trajectories of penalty and barrier functions. Technical Report SOL7823, Department of Operations Research, Stanford University, Stanford, California 94305, USA, 1978.
 43.
 S. G. Nash, R. Polyak, and A. Sofer. A numerical comparison of barrier and modified barrier methods for largescale constrained optimization. In W. W. Hager, D. W. Hearn and P. M. Pardalos, editors, Large Scale Optimization: State of the Art, pages 319338, Dordrecht, 1994. Kluwer Academic Publishers. CMP 95:05
 44.
 S. G. Nash and A. Sofer. A barrier method for largescale constrained optimization. ORSA Journal on Computing, 5(1):4053, 1993. CMP 93:07
 45.
 Y. Nesterov and A. Nemirovsky. Selfconcordant functions and polynomialtime methods in convex programming. SIAM, Philadelphia, USA, 1993.
 46.
 J. M. Ortega and W. C. Rheinboldt. Iterative solution of nonlinear equations in several variables. Academic Press, New York, 1970. MR 42:8686
 47.
 R. Polyak. Modified barrier functions (theory and methods). Mathematical Programming, 54(2):177222, 1992. MR 93c:90083
 48.
 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.
 49.
 D. B. Ponceleón. Barrier methods for largescale quadratic programming. PhD thesis, Department of Computer Science, Stanford University, Stanford, California 94305, USA, 1990.
 50.
 M. J. D. Powell. A method for nonlinear constraints in minimization problems. In R. Fletcher, editor, Optimization, London and New York, 1969. Academic Press, pages 283298. MR 42:7284
 51.
 M. J. D. Powell. Log barrier methods for semiinfinite programming calculations. In E. A. Lipitakis, editor, Advances on Computer Mathematics and its Applications, pages 121, Singapore, 1993. World Scientific.
 52.
 M. J. D. Powell. Some convergence properties of the modified log barrier method for linear programming. SIAM Journal on Optimization, 5(4): 695740, 1995. CMP 96:03
 53.
 F. Rendl, R. J. Vanderbei, and H. Wolkowicz. Primaldual interior point algorithms for maxmin eigenvalue problems. Technical Report CORR9320, Faculty of Mathematics, University of Waterloo, 1993.
 54.
 R. T. Rockafellar. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Research, 1:97116, 1976. MR 54:6954
 55.
 M. H. Wright. Numerical methods for nonlinearly constrained optimization. PhD thesis, Department of Computer Science, Stanford University, Stanford, California 94305, USA, 1976.
 56.
 M. H. Wright. Interior methods for constrained optimization. volume 1 of Acta Numerica, pages 341407. Cambridge University Press, New York, 1992. MR 93d:90037
Similar Articles
Retrieve articles in Mathematics of Computation of the American Mathematical Society
with MSC (1991):
90C30,
65K05
Retrieve articles in all journals
with MSC (1991):
90C30,
65K05
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
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, B5000 Namur, Belgium
Email:
pht@math.fundp.ac.be
DOI:
http://dx.doi.org/10.1090/S0025571897007771
PII:
S 00255718(97)007771
Keywords:
Constrained optimization,
barrier methods,
inequality constraints,
convergence theory
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 F4962091C0079. 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 joyousgard.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)
Article copyright:
© Copyright 1997
American Mathematical Society
