In our reports on GAMM-04 and ECCOMAS-04 there has been presented a new conjugate directions method for large scale unconstrained minimization problems. High efficiency of this method is ensured by employing an orthogonalization procedure: when constructing the next conjugate vector the component of the gradient is used that is orthogonal to the subspace of preceding conjugate vectors (instead of the gradient itself). Such a procedure does not require the current point to be the minimum point along . This makes it possible to perform only one step on each iteration, without any linear searches along the vector . As very high accuracy in determining conjugate directions is achieved, the algorithm ensures considerable reduction in the number of iterations. Now this algorithm is extended to minimization problems with bound constraints. Because the linear minimization along the newly found conjugate vector is not needed for constructing the next conjugate vector on the following iteration, we are able to incorporate naturally the bound constraints into the algorithm. The algorithm is supplemented with a simple rule for determining boundary variables and a criterion for restarts. Results of a numerical experiment on several quadratic test-functions with the number of variables N up to 100’000 are presented. The influence of the bound constraints on convergence of the method is studied. Comparison with other methods, in particular, the limited memory BFGS algorithm, is given.
Citation
Edouard Boudinov and Arkadiy Manevich, "An Extension of the Conjugate Directions Method With Orthogonalization to Large-Scale Problems With Bound Constraints", PAMM, Proceedings in Applied Mathematics and Mechanics, 5, pp 737-738, DOI: 10.1002/pamm.200510343