Optimization Online


An Extension of the Conjugate Directions Method With Orthogonalization to Large-Scale Problems With Bound Constraints

Edouard Boudinov (edouard.boudinov***at***mail.ru)
Arkadiy Manevich (aman***at***atlantis.dp.ua)

Abstract: 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.

Keywords: optimization, unconstrained minimization, bound constrained optimization, conjugate direction methods, large-scale problems, orthogonalization

Category 1: Nonlinear Optimization (Bound-constrained Optimization )

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Category 3: Nonlinear Optimization (Quadratic Programming )

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


Entry Submitted: 05/30/2005
Entry Accepted: 05/30/2005
Entry Last Modified: 02/09/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society