Previous |  Up |  Next


large sparse optimization; numerical examples; sparse Hessian matrices; finite-differences; graph-coloring; ordering scheme; coloring scheme
Necessity of computing large sparse Hessian matrices gave birth to many methods for their effective approximation by differences of gradients. We adopt the so-called direct methods for this problem that we faced when developing programs for nonlinear optimization. A new approach used in the frame of symmetric sequential coloring is described. Numerical results illustrate the differences between this method and the popular Powell-Toint method.
[1] T. F. Coleman J. J. Moré: Estimation of Sparse Hessian Matrices and Graph Coloring Problems. Math. Prog. 28 (1984), 243-270. DOI 10.1007/BF02612334 | MR 0736293
[2] G. C. Everstine: A Comparison of Three Resequencing Algorithms for the Reduction of Matrix Profile and Wavefront. International Journal on Numerical Methods in Engineering 14 (1979), 837-853. DOI 10.1002/nme.1620140606 | Zbl 0401.73082
[3] A. George J. W. H. Liu: Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Inc. Englewood Cliffs. N. J. 07632, 1981. MR 0646786
[4] P. Hanzálek J. Hřebíček J. Kučera: A Conversational Program System for Mathematical Optimization. Computer Physics Communications 41 (1986), 403 - 408. DOI 10.1016/0010-4655(86)90080-9
[5] D. M. Matula L. L. Beck: Smallest-last Ordering and Clustering and Graph Coloring Algorithms. JACM 30 (1983), 417-427. DOI 10.1145/2402.322385 | MR 0709826
[6] S. T. McCormick: Optimal Approximation of Sparse Hessians and its Equivalence to a Graph Coloring Problem. Math. Prog. 26 (1983), 153-171. DOI 10.1007/BF02592052 | MR 0700644 | Zbl 0507.65027
[7] M. J. D. Powell, Ph. L. Toint: On the Estimation of Sparse Hessian Matrices. SIAM on Num. Anal. 16 (1979), 1060-1074. DOI 10.1137/0716078 | MR 0551326 | Zbl 0426.65025
[8] M. N. Thapa: Optimization of Unconstrained Functions with Sparse Hessian Matrices: Newton-type Methods. Math. Prog. 19 (1984), 156-186. MR 0745406 | Zbl 0538.49023
[9] O. C. Zienkiewicz: The Finite Element Method. McGraw Hill, London, 1977. Zbl 0435.73072
Partner of
EuDML logo