A new trust region algorithm for bound constrained minimization. (English) Zbl 0821.90101

Friedlander, A.; Martínez, J. M.; Santos, S. A.

Appl. Math. Optimization 30, No. 3, 235-266 (1994).

Summary: We introduce a new algorithm of trust-region type for minimizing a differentiable function of many variables with box constraints. At each step of the algorithm we use an approximation to the minimizer of a quadratic in a box. We introduce a new method for solving this subproblem, that has finite termination without dual nondegeneracy assumptions. We prove the global convergence of the main algorithm and a result concerning the identification of the active constraints in finite time. We describe an implementation of the method and we present numerical experiments showing the effect of solving the subproblem with different degrees of accuracy.

MSC:

90C30	Nonlinear programming
65K05	Numerical mathematical programming methods
90-08	Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

global convergence; trust-region; differentiable function; box constraints; different degrees of accuracy

Software:

LANCELOT

References:

[1]	Conn AR, Gould NIM, Toint PhL (1988) Global convergence of a class of trust-region algorithms for optimization with simple bounds. SIAM Journal on Numerical Analysis 25:433-460.See also SIAM Journal on Numerical Analysis 26:764-767 (1989). · Zbl 0643.65031 · doi:10.1137/0725029
[2]	Conn AR, Gould NIM, Toint PhL (1988) Testing a class of methods for solving minimization problems with simple bounds on the variables. Mathematics of Computation 50:399-430. · Zbl 0645.65033 · doi:10.1090/S0025-5718-1988-0929544-3
[3]	Conn AR, Gould NIM, Toint PhL (1990) A comprehensive description of LANCELOT. Technical Report of the Department of Mathematics, FUNDP, Namur, Belgium.
[4]	Conn AR, Gould NIM, Toint PhL (1988) A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds. SIAM Journal on Numerical Analysis 28:545-572. · Zbl 0724.65067 · doi:10.1137/0728030
[5]	Dembo RS, Tulowitzki U (1987) On the minimization of quadratic functions subject to box constraints. Working paper series B-71, School of Organization and Management, Yale University.
[6]	Dennis JE, Schnabel RB (1983) Numerical methods for unconstrained optimization and nonlinear equations, Prentice-Hall, Englewood Cliffs, NJ. · Zbl 0579.65058
[7]	Fletcher R (1987) Practical Methods of Optimization, 2nd edn. Wiley, Chichester. · Zbl 0905.65002
[8]	Friedlander A, Martinez JM (1994) On the maximization of a concave quadratic with box constraints. SIAM Journal on Optimization 4(1).
[9]	Friedlander A, Martínez JM, Santos SA (1994) On the resolution of large scale linearly constrained convex minimization problems. SIAM Journal on Optimization 4(2).
[10]	Golub GH, Van Loan Ch (1989) Matrix Computations. The Johns Hopkins University Press, Baltimore. · Zbl 0733.65016
[11]	Moré JJ (1983) Recent development in algorithms and software for trust-region methods. Mathematical Programming Bonn 1982. The State of Art (A. Bachem, M. Grötschel and B. Korte, eds.). Springer-Verlag, New York.
[12]	Moré JJ, Toraldo G (1989) Algorithms for bound constrained quadratic programming problems. Numerische Mathematik 55:377-400. · Zbl 0675.65061 · doi:10.1007/BF01396045
[13]	Moré JJ, Toraldo G (1991) On the solution of large quadratic programming problems with bound constraints. SIAM Journal on Optimization 1:93-113. · Zbl 0752.90053 · doi:10.1137/0801008
[14]	Sorensen DC (1982) Newton’s method with a model trust-region modification. SIAM Journal on Numerical Analysis 19:409-426. · Zbl 0483.65039 · doi:10.1137/0719026