Nonmonotone strategy for minimization of quadratics with simple constraints. (English) Zbl 1066.65065
Summary: An algorithm for quadratic minimization with simple bounds is introduced, combining many well-known methods like active set strategies and projection steps. The novelty is that here the criterion for acceptance of a projected trial point is weaker than the usual ones, which are based on monotone decrease of the objective function. It is proved that convergence follows in the monotone case. Numerical experiments with bound-constrained quadratic problems from the CUTE collection show that the modified method is in practice slightly more efficient than its monotone counterpart and has a performance superior to the well-known code LANCELOT for this class of problems.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C20 | Quadratic programming |
| 90C52 | Methods of reduced gradient type |
Keywords:
quadratic programming; conjugate gradients; active set methods; projection method; convergence; numerical experimentsReferences:
| [1] | D. P. Bertsekas: Projected Newton methods for optimization problems with simple constraints. SIAM J. Control Optim. 20 (1982), 141-148. · Zbl 0507.49018 · doi:10.1137/0320018 |
| [2] | R. H. Bielschowsky, A. Friedlander, F. A. M. Gomes, J. M. Martínez and M. Raydan: An adaptive algorithm for bound constrained quadratic minimization. Investigación Oper. 7 (1997), 67-102. |
| [3] | I. Bongartz, A. R. Conn, N. I. M. Gould and Ph. L. Toint: CUTE: Constrained and Unconstrained Testing Environment. ACM Trans. Math. Software 21 (1995), 123-160. · Zbl 0886.65058 · doi:10.1145/200979.201043 |
| [4] | P. Ciarlet: The Finite Element Method for Elliptic Problems. North Holland, Amsterdam, 1978. · Zbl 0383.65058 |
| [5] | T. F. Coleman, L. A. Hulbert: A direct active set algorithm for large sparse quadratic programs with simple bounds. Math. Programming 45 (1989), 373-406. · Zbl 0691.90070 · doi:10.1007/BF01589112 |
| [6] | 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), 433-460. · Zbl 0643.65031 · doi:10.1137/0725029 |
| [7] | 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 J. Numer. Anal. 28 (1988), 545-572. · Zbl 0724.65067 · doi:10.1137/0728030 |
| [8] | R. Dembo, U. Tulowitzki: On the minimization of quadratic functions subject to box constraints. Working Paper B-71, School of Organization and Management, Yale University, New Haven (1983). |
| [9] | J. E. Dennis, L. N. Vicente: Trust-region interior-point algorithms for minimization problems with simple bounds. Applied Mathematics and Parallel Computing (Festschrift for Klaus Ritter) (H. Fischer, B. Riedmüller and S. Schäffer, Physica-Verlag, Springer-Verlag, 1996, pp. 97-107. · Zbl 0907.65056 |
| [10] | M. A. Diniz-Ehrhardt, M. A. Gomes-Ruggiero and S. A. Santos: Comparing the numerical performance of two trust-region algorithms for large-scale bound-constrained minimization. Investigación Oper. 7 (1997), 23-54. |
| [11] | M. A. Diniz-Ehrhardt, M. A. Gomes-Ruggiero and S. A. Santos: Numerical analysis of leaving-face parameters in bound-constrained quadratic minimization. Relatório de Pesquisa RP52/98, IMECC, UNICAMP, Campinas, Brazil, 1998. · Zbl 1009.90078 |
| [12] | Z. Dostál: Box constrained quadratic programming with proportioning and projections. SIAM J. Optim. 7 (1997), 871-887. · Zbl 0912.65052 · doi:10.1137/S1052623494266250 |
| [13] | Z. Dostál, A. Friedlander and S. A. Santos: Solution of contact problems of elasticity by FETI domain decomposition. Contemp. Math. 218 (1998), 82-93. · Zbl 0962.74056 · doi:10.1090/conm/218/03003 |
| [14] | Z. Dostál, F. A. M. Gomes Neto and S. A. Santos: Solution of contact problems by FETI domain decomposition with natural coarse space projection. Comput. Methods Appl. Mech. Engrg. 190 (2000), 1611-1627. · Zbl 1005.74064 · doi:10.1016/S0045-7825(00)00180-8 |
| [15] | Z. Dostál, V. Vondrák: Duality based solution of contact problems with Coulomb friction. Arch. Mech. 49 (1997), 453-460. · Zbl 0877.73056 |
| [16] | L. Fernandes, A. Fischer, J. J. Júdice, C. Requejo and C. Soares: A block active set algorithm for large-scale quadratic programming with box constraints. Ann. Oper. Res. 81 (1998), 75-95. · Zbl 0906.90138 · doi:10.1023/A:1018990014974 |
| [17] | A. Friedlander, J. M. Martínez: On the numerical solution of bound constrained optimization problems. RAIRO Rech. Opér. 23 (1989), 319-341. · Zbl 0683.90073 |
| [18] | A. Friedlander, J. M. Martínez: On the maximization of a concave quadratic function with box constraints. SIAM J. Optim. 4 (1994), 177-192. · Zbl 0801.65058 · doi:10.1137/0804010 |
| [19] | A. Friedlander, J. M. Martínez and M. Raydan: A new method for large-scale box constrained quadratic minimization problems. Optimization Methods and Software 5 (1995), 57-74. · doi:10.1080/10556789508805602 |
| [20] | A. Friedlander, J. M. Martínez and S. A. Santos: A new trust region algorithm for bound constrained minimization. Appl. Math. Optim. 30 (1994), 235-266. · Zbl 0821.90101 · doi:10.1007/BF01183013 |
| [21] | P. E. Gill, W. Murray and M. H. Wright: Practical Optimization. Academic Press, London and New York, 1981. |
| [22] | G. H. Golub, Ch. F. Van Loan: Matrix Computations. The Johns Hopkins University Press, Baltimore and London, 1989. · Zbl 0733.65016 |
| [23] | M. R. Hestenes, E. Stiefel: Methods of conjugate gradients for solving linear systems. J. Res. NBS B 49 (1952), 409-436. · Zbl 0048.09901 |
| [24] | J. J. Júdice, F. M. Pires: Direct methods for convex quadratic programming subject to box constraints. Investigação Operacional 9 (1989), 23-56. |
| [25] | Y. Lin, C. W. Cryer: An alternating direction implicit algorithm for the solution of linear complementarity problems arising from free boundary problems. Appl. Math. Optim. 13 (1985), 1-17. · Zbl 0575.65119 · doi:10.1007/BF01442196 |
| [26] | P. Lötstedt: Numerical simulation of time-dependent contact and friction problems in rigid body mechanics. SIAM J. Sci. Comput. 5 (1984), 370-393. · Zbl 0542.73146 · doi:10.1137/0905028 |
| [27] | P. Lötstedt: Solving the minimal least squares problem subject to bounds on the variables. BIT 24 (1984), 206-224. · Zbl 0546.65041 |
| [28] | J. J. Moré, G. Toraldo: On the solution of large quadratic programming problems with bound constraints. SIAM J. Optim. 1 (1991), 93-113. · Zbl 0752.90053 · doi:10.1137/0801008 |
| [29] | R. H. Nickel, J. W. Tolle: A sparse sequential programming algorithm. J. Optim. Theory Appl. 60 (1989), 453-473. · Zbl 0632.90053 · doi:10.1007/BF00940348 |
| [30] | M. Raydan: On the Barzilai and Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. 13 (1993), 321-326. · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321 |
| [31] | E. K. Yang, J. W. Tolle: A class of methods for solving large, convex quadratic programs subject to box constraints. Tech. Rep. UNC/ORSA/TR-86-3, Dept. of Oper. Research and Systems Analysis, Univ. of North Carolina, Chapel Hill, NC. (1986). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
