×

A solver for nonconvex bound-constrained quadratic optimization. (English) Zbl 1330.49029

The paper displays a new algorithm for solving bound-constrained quadratic problems which, and this is the contribution of this work, are not necessarily convex optimization problems. The solver is based on the conjugate gradient iteration approach and it deals simultaneously with lower and upper bounds on the optimization variables. The conjugate gradient is used to reduce the objective function within subspaces by variables considered to be inactive in the solution.

MSC:

49M15 Newton-type methods
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C60 Abstract computational complexity for mathematical programming problems
65H10 Numerical computation of solutions to systems of equations
68Q25 Analysis of algorithms and problem complexity
58C15 Implicit function theorems; global Newton methods on manifolds
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, {\it On augmented Lagrangian methods with general lower-level constraints}, SIAM J. Optim., 18 (2007), pp. 1286-1309. · Zbl 1151.49027
[2] R. Barrett, M. W. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. Van der Vorst, {\it Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods}, SIAM, Philadelphia, 1994. · Zbl 0814.65030
[3] D. P. Bertsekas, {\it Projected Newton methods for optimization problems with simple constraints}, SIAM J. Control Optim., 20 (1982), pp. 221-246. · Zbl 0507.49018
[4] R. H. Bielschowsky, A. Friedlander, F. Gomes, J. Mart\inez, and M. Raydan, {\it An adaptive algorithm for bound constrained quadratic minimization}, Investigación Oper., 7 (1997), pp. 67-102.
[5] L. A. Caffarelli and A. Friedman, {\it The free boundary for elastic-plastic torsion problems}, Trans. Amer. Math. Soc., 252 (1979), pp. 65-97. · Zbl 0426.35033
[6] A. R. Conn, N. I. Gould, and P. L. Toint, {\it Trust Region Methods}, Vol. 1, SIAM, Philadelphia, 2000. · Zbl 0958.65071
[7] A. R. Conn, N. I. M. Gould, and P. L. Toint, {\it A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds}, SIAM J. Numer. Anal., 28 (1991), pp. 545-572. · Zbl 0724.65067
[8] A. R. Conn, N. I. M. Gould, and P. L. Toint, {\it Trust-Region Methods}, SIAM, Philadelphia, 2000. · Zbl 0958.65071
[9] B. Contesse, {\it Une caractérisation complète des minima locaux en programmation quadratique.}, Numer. Math., 34 (1980), pp. 315-332. · Zbl 0422.90061
[10] F. E. Curtis, N. I. M. Gould, H. Jiang, and D. P. Robinson, {\it Adaptive augmented Lagrangian methods: Algorithms and practical numerical experience}, Optim. Methods Softw., (2015), pp. 1-30, DOI:10.1080/10556788.2015.1071813. · Zbl 1339.49023
[11] F. E. Curtis, H. Jiang, and D. P. Robinson, {\it An adaptive augmented lagrangian method for large-scale constrained optimization}, Math. Program., (2013), pp. 1-45.
[12] Y.-H. Dai and R. Fletcher, {\it Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming}, Numer. Math., 100 (2005), pp. 21-47. · Zbl 1068.65073
[13] R. S. Dembo and U. Tulowitzki, {\it On the Minimization of Quadratic Functions Subject to Box Constraints}, Department of Computer Science, Yale University, 1984.
[14] M. Diniz-Ehrhardt, Z. Dostál, M. Gomes-Ruggiero, J. Martínez, and S. A. Santos, {\it Nonmonotone strategy for minimization of quadratics with simple constraints}, Appl. Math., 46 (2001), pp. 321-338. · Zbl 1066.65065
[15] Z. Dostál, {\it Box constrained quadratic programming with proportioning and projections}, SIAM J. Optim., 7 (1997), pp. 871-887. · Zbl 0912.65052
[16] Z. Dostál, {\it A proportioning based algorithm for bound constrained quadratic programming with the rate of convergence}, Numer. Algorithms, 34 (2003), pp. 293-302. · Zbl 1037.65061
[17] Z. Dostál, {\it Optimal Quadratic Programming Algorithms: With Applications to Variational Inequalities}, Springer Optim. Appl., 23, Springer, New York, 2009. · Zbl 1401.90013
[18] Z. Dostál and J. Schöberl, {\it Minimizing quadratic functions subject to bound constraints with the rate of convergence and finite termination}, Comput. Optim. Appl., 30 (2005), pp. 23-43. · Zbl 1071.65085
[19] L. Feng, V. Linetsky, J. L. Morales, and J. Nocedal, {\it On the solution of complementarity problems arising in American options pricing}, Optim. Methods Softw., 26 (2011), pp. 813-825. · Zbl 1229.90230
[20] R. Fletcher, {\it On the Barzilai-Borwein method}, in Optimization and Control with Applications, Springer, New York, 2005, pp. 235-256. · Zbl 1118.90318
[21] A. Forsgren, P. Gill, and W. Murray, {\it On the identification of local minimizers in inertia-controlling methods for quadratic programming}, SIAM J. Matrix Anal. Appl., 12 (1991), pp. 730-746. · Zbl 0737.65047
[22] A. Friedlander, J. Mario Martínez, and M. Raydon, {\it A new method for large-scale box constrained convex quadratic minimization problems}, Optim. Methods Softw., 5 (1995), pp. 57-74.
[23] A. Friedlander and J. M. Martínez, {\it On the numerical solution of bound constrained optimization problems}, RAIRO Oper. Res., 23 (1989), pp. 319-341. · Zbl 0683.90073
[24] A. Friedlander and J. M. Martínez, {\it On the maximization of a concave quadratic function with box constraints}, SIAM J. Optim., 4 (1994), pp. 177-192. · Zbl 0801.65058
[25] A. A. Goldstein, {\it Convex programming in Hilbert space}, Bull. Amer. Math. Soc., 70 (1964), pp. 709-710. · Zbl 0142.17101
[26] N. I. M. Gould, D. Orban, and P. L. Toint, {\it CUTEst: A Constrained and Unconstrained Testing Environment with Safe Threads}, Technical report, Rutherford Appleton Laboratory, Chilton, UK, 2013. · Zbl 1325.90004
[27] M. Hestenes and E. Stiefel, {\it Methods of conjugate gradients for solving linear systems}, J. Res. Nat. Bur. Standards, 49 (1952), pp. 409-436. · Zbl 0048.09901
[28] M. Kočvara and M. Stingl, {\it PENNON: A code for convex nonlinear and semidefinite programming}, Optim. Methods Softw., 18 (2003), pp. 317-333. · Zbl 1037.90003
[29] M. Kočvara and J. Zowe, {\it An iterative two-step algorithm for linear complementarity problems}, Numer. Math., 68 (1994), pp. 95-106. · Zbl 0820.65033
[30] C. Lanczos, {\it An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators}, U.S. Government Press Office, 1950. · Zbl 0045.39702
[31] E. S. Levitin and B. T. Polyak, {\it Constrained minimization methods}, USSR Comput. Math. Math. Phys., 6 (1966), pp. 1-50. · Zbl 0184.38902
[32] Y. Lin and C. Cryer, {\it An alternating direction implicit algorithm for the solution of linear complementarity problems arising from free boundary problems}, Appl. Math. Optim., 13 (1985), pp. 1-17. · Zbl 0575.65119
[33] P. Lötstedt, {\it Numerical simulation of time-dependent contact and friction problems in rigid body mechanics}, SIAM J. Sci. Statist. Comput., 5 (1984), pp. 370-393. · Zbl 0542.73146
[34] J. J. Moré and G. Toraldo, {\it Algorithms for bound constrained quadratic programming problems}, Numer. Math., 55 (1989), pp. 377-400. · Zbl 0675.65061
[35] J. J. Moré and G. Toraldo, {\it On the solution of large quadratic programming problems with bound constraints}, SIAM J. Optim., 1 (1991), pp. 93-113. · Zbl 0752.90053
[36] U. Oreborn, {\it A Direct Method for Sparse Nonnegative Least Squares Problems,} Ph.D. thesis, Linköping University, Linköping, Sweden, 1986.
[37] D. P. Robinson, L. Feng, J. M. Nocedal, and J.-S. Pang, {\it Subspace accelerated matrix splitting algorithms for asymmetric and symmetric linear complementarity problems}, SIAM J. Optim., 23 (2013), pp. 1371-1397. · Zbl 1291.49023
[38] E. K. Yang and J. W. Tolle, {\it A class of methods for solving large, convex quadratic programs subject to box constraints}, Math. Program., 51 (1991), pp. 223-228. · Zbl 0737.90046
[39] C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal, {\it Algorithm {\it 778}: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization}, ACM Trans. Math. Software, 23 (1997), pp. 550-560. · Zbl 0912.65057
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.