Optimal approximation of sparse hessians and its equivalence to a graph coloring problem |
| |
Authors: | S Thomas McCormick |
| |
Institution: | (1) Department of Operations Research, Stanford University, 94305 Stanford, CA, USA |
| |
Abstract: | We consider the problem of approximating the Hessian matrix of a smooth non-linear function using a minimum number of gradient
evaluations, particularly in the case that the Hessian has a known, fixed sparsity pattern. We study the class of Direct Methods
for this problem, and propose two new ways of classifying Direct Methods. Examples are given that show the relationships among
optimal methods from each class. The problem of finding a non-overlapping direct cover is shown to be equivalent to a generalized
graph coloring problem—the distance-2 graph coloring problem. A theorem is proved showing that the general distance-k graph coloring problem is NP-Complete for all fixedk≥2, and hence that the optimal non-overlapping direct cover problem is also NP-Complete. Some worst-case bounds on the performance
of a simple coloring heuristic are given. An appendix proves a well-known folklore result, which gives lower bounds on the
number of gradient evaluations needed in any possible approximation method.
This research was partially supported by the Department of Energy Contract AM03-76SF00326. PA#DE-AT03-76ER72018; Army Research
Office Contract DAA29-79-C-0110; Office of Naval Research Contract N00014-74-C-0267; National Science Foundation Grants MCS76-81259,
MCS-79260099 and ECS-8012974. |
| |
Keywords: | Sparse Hessian Approximation Graph Coloring Heuristics Elimination Methods NP-Complete Direct Methods |
本文献已被 SpringerLink 等数据库收录! |
|