| Title:
|
Nonmonotone strategy for minimization of quadratics with simple constraints (English) |
| Author:
|
Diniz-Ehrhardt, M. A. |
| Author:
|
Dostál, Z. |
| Author:
|
Gomes-Ruggiero, M. A. |
| Author:
|
Martínez, J. M. |
| Author:
|
Santos, S. A. |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
46 |
| Issue:
|
5 |
| Year:
|
2001 |
| Pages:
|
321-338 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
An algorithm for quadratic minimization with simple bounds is introduced, combining, as many well-known methods do, 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 as in the monotone case. Numerical experiments with bound-constrained quadratic problems from 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. (English) |
| Keyword:
|
quadratic programming |
| Keyword:
|
conjugate gradients |
| Keyword:
|
active set methods |
| MSC:
|
65F15 |
| MSC:
|
65K05 |
| MSC:
|
65K10 |
| MSC:
|
90C20 |
| MSC:
|
90C52 |
| idZBL:
|
Zbl 1066.65065 |
| idMR:
|
MR1925191 |
| DOI:
|
10.1023/A:1013752209845 |
| . |
| Date available:
|
2009-09-22T18:07:20Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134471 |
| . |
| Reference:
|
[1] D. P. Bertsekas: Projected Newton methods for optimization problems with simple constraints.SIAM J. Control Optim. 20 (1982), 141–148. Zbl 0507.49018, MR 0646950, 10.1137/0320018 |
| Reference:
|
[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. |
| Reference:
|
[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. 10.1145/200979.201043 |
| Reference:
|
[4] P. Ciarlet: The Finite Element Method for Elliptic Problems.North Holland, Amsterdam, 1978. Zbl 0383.65058, MR 0520174 |
| Reference:
|
[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. MR 1038241, 10.1007/BF01589112 |
| Reference:
|
[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. MR 0933734, 10.1137/0725029 |
| Reference:
|
[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. MR 1087519 |
| Reference:
|
[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). |
| Reference:
|
[9] J. E. Dennis, L. N. Vicente: Trust-region interior-point algorithms for minimization problems with simple bounds.In: Applied Mathematics and Parallel Computing (Festschrift for Klaus Ritter) (H. Fischer, B. Riedmüller and S. Schäffer, eds.), Physica-Verlag, Springer-Verlag, 1996, pp. 97–107. MR 1469263 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[12] Z. Dostál: Box constrained quadratic programming with proportioning and projections.SIAM J. Optim. 7 (1997), 871–887. MR 1462070, 10.1137/S1052623494266250 |
| Reference:
|
[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. MR 1645845, 10.1090/conm/218/03003 |
| Reference:
|
[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. 10.1016/S0045-7825(00)00180-8 |
| Reference:
|
[15] Z. Dostál, V. Vondrák: Duality based solution of contact problems with Coulomb friction.Arch. Mech. 49 (1997), 453–460. MR 1468556 |
| Reference:
|
[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. MR 1638391, 10.1023/A:1018990014974 |
| Reference:
|
[17] A. Friedlander, J. M. Martínez: On the numerical solution of bound constrained optimization problems.RAIRO Rech. Opér. 23 (1989), 319–341. MR 1036699, 10.1051/ro/1989230403191 |
| Reference:
|
[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. MR 1260414, 10.1137/0804010 |
| Reference:
|
[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. 10.1080/10556789508805602 |
| Reference:
|
[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. MR 1288591, 10.1007/BF01183013 |
| Reference:
|
[21] P. E. Gill, W. Murray and M. H. Wright: Practical Optimization.Academic Press, London and New York, 1981. MR 0634376 |
| Reference:
|
[22] G. H. Golub, Ch. F. Van Loan: Matrix Computations.The Johns Hopkins University Press, Baltimore and London, 1989. MR 1002570 |
| Reference:
|
[23] M. R. Hestenes, E. Stiefel: Methods of conjugate gradients for solving linear systems.J. Res. NBS B 49 (1952), 409–436. MR 0060307 |
| Reference:
|
[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. |
| Reference:
|
[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. MR 0778418, 10.1007/BF01442196 |
| Reference:
|
[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. MR 0740855, 10.1137/0905028 |
| Reference:
|
[27] P. Lötstedt: Solving the minimal least squares problem subject to bounds on the variables.BIT 24 (1984), 206–224. MR 0753549 |
| Reference:
|
[28] J. J. Moré, G. Toraldo: On the solution of large quadratic programming problems with bound constraints.SIAM J. Optim. 1 (1991), 93–113. MR 1094793, 10.1137/0801008 |
| Reference:
|
[29] R. H. Nickel, J. W. Tolle: A sparse sequential programming algorithm.J. Optim. Theory Appl. 60 (1989), 453–473. MR 0993010, 10.1007/BF00940348 |
| Reference:
|
[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, MR 1225468, 10.1093/imanum/13.3.321 |
| Reference:
|
[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). |
| . |
