Nonmonotone strategy for minimization of quadratics with simple constraints

M. A. Diniz-Ehrhardt; Zdeněk Dostál; M. A. Gomes-Ruggiero; J. M. Martínez; Sandra Augusta Santos

Applications of Mathematics (2001)

  • Volume: 46, Issue: 5, page 321-338
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Diniz-Ehrhardt, M. A., et al. "Nonmonotone strategy for minimization of quadratics with simple constraints." Applications of Mathematics 46.5 (2001): 321-338. <http://eudml.org/doc/33090>.

@article{Diniz2001,
abstract = {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.},
author = {Diniz-Ehrhardt, M. A., Dostál, Zdeněk, Gomes-Ruggiero, M. A., Martínez, J. M., Santos, Sandra Augusta},
journal = {Applications of Mathematics},
keywords = {quadratic programming; conjugate gradients; active set methods; quadratic programming; conjugate gradients; active set methods; projection method; convergence; numerical experiments},
language = {eng},
number = {5},
pages = {321-338},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Nonmonotone strategy for minimization of quadratics with simple constraints},
url = {http://eudml.org/doc/33090},
volume = {46},
year = {2001},
}

TY - JOUR
AU - Diniz-Ehrhardt, M. A.
AU - Dostál, Zdeněk
AU - Gomes-Ruggiero, M. A.
AU - Martínez, J. M.
AU - Santos, Sandra Augusta
TI - Nonmonotone strategy for minimization of quadratics with simple constraints
JO - Applications of Mathematics
PY - 2001
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 46
IS - 5
SP - 321
EP - 338
AB - 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.
LA - eng
KW - quadratic programming; conjugate gradients; active set methods; quadratic programming; conjugate gradients; active set methods; projection method; convergence; numerical experiments
UR - http://eudml.org/doc/33090
ER -

References

top
  1. 10.1137/0320018, SIAM J. Control Optim. 20 (1982), 141–148. (1982) Zbl0507.49018MR0646950DOI10.1137/0320018
  2. An adaptive algorithm for bound constrained quadratic minimization, Investigación Oper. 7 (1997), 67–102. (1997) 
  3. 10.1145/200979.201043, ACM Trans. Math. Software 21 (1995), 123–160. (1995) DOI10.1145/200979.201043
  4. The Finite Element Method for Elliptic Problems, North Holland, Amsterdam, 1978. (1978) Zbl0383.65058MR0520174
  5. 10.1007/BF01589112, Math. Programming 45 (1989), 373–406. (1989) MR1038241DOI10.1007/BF01589112
  6. 10.1137/0725029, SIAM J.  Numer. Anal. 25 (1988), 433-460. (1988) MR0933734DOI10.1137/0725029
  7. A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM J.  Numer. Anal. 28 (1988), 545–572. (1988) MR1087519
  8. On the minimization of quadratic functions subject to box constraints, Working Paper B-71, School of Organization and Management, Yale University, New Haven (1983). (1983) 
  9. 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. (1996) MR1469263
  10. Comparing the numerical performance of two trust-region algorithms for large-scale bound-constrained minimization, Investigación Oper. 7 (1997), 23–54. (1997) 
  11. Numerical analysis of leaving-face parameters in bound-constrained quadratic minimization, Relatório de Pesquisa RP52/98, IMECC, UNICAMP, Campinas, Brazil, 1998. (1998) 
  12. 10.1137/S1052623494266250, SIAM J. Optim. 7 (1997), 871–887. (1997) MR1462070DOI10.1137/S1052623494266250
  13. 10.1090/conm/218/03003, Contemp. Math. 218 (1998), 82–93. (1998) MR1645845DOI10.1090/conm/218/03003
  14. 10.1016/S0045-7825(00)00180-8, Comput. Methods Appl. Mech. Engrg. 190 (2000), 1611–1627. (2000) DOI10.1016/S0045-7825(00)00180-8
  15. Duality based solution of contact problems with Coulomb friction, Arch. Mech. 49 (1997), 453–460. (1997) MR1468556
  16. 10.1023/A:1018990014974, Ann. Oper. Res. 81 (1998), 75–95. (1998) MR1638391DOI10.1023/A:1018990014974
  17. 10.1051/ro/1989230403191, RAIRO Rech. Opér. 23 (1989), 319–341. (1989) MR1036699DOI10.1051/ro/1989230403191
  18. 10.1137/0804010, SIAM J.  Optim. 4 (1994), 177–192. (1994) MR1260414DOI10.1137/0804010
  19. 10.1080/10556789508805602, Optimization Methods and Software 5 (1995), 57–74. (1995) DOI10.1080/10556789508805602
  20. 10.1007/BF01183013, Appl. Math. Optim. 30 (1994), 235–266. (1994) MR1288591DOI10.1007/BF01183013
  21. Practical Optimization, Academic Press, London and New York, 1981. (1981) MR0634376
  22. Matrix Computations, The Johns Hopkins University Press, Baltimore and London, 1989. (1989) MR1002570
  23. Methods of conjugate gradients for solving linear systems, J.  Res. NBS B 49 (1952), 409–436. (1952) MR0060307
  24. Direct methods for convex quadratic programming subject to box constraints, Investigação Operacional 9 (1989), 23–56. (1989) 
  25. 10.1007/BF01442196, Appl. Math. Optim. 13 (1985), 1–17. (1985) MR0778418DOI10.1007/BF01442196
  26. 10.1137/0905028, SIAM J.  Sci. Comput. 5 (1984), 370–393. (1984) MR0740855DOI10.1137/0905028
  27. Solving the minimal least squares problem subject to bounds on the variables, BIT 24 (1984), 206–224. (1984) MR0753549
  28. 10.1137/0801008, SIAM J.  Optim. 1 (1991), 93–113. (1991) MR1094793DOI10.1137/0801008
  29. 10.1007/BF00940348, J.  Optim. Theory Appl. 60 (1989), 453–473. (1989) MR0993010DOI10.1007/BF00940348
  30. 10.1093/imanum/13.3.321, IMA J.  Numer. Anal. 13 (1993), 321–326. (1993) Zbl0778.65045MR1225468DOI10.1093/imanum/13.3.321
  31. 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). (1986) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.