| This dissertation considers two combinatorial problems arising in large-scale, sparse optimization. The first is the problem of approximating the Hessian matrix of a smooth, non-linear function by finite differencing, where the object is to minimize the required number of gradient evaluations. The second is to find as sparse a representation as possible of a given set of linear constraints.;The second problem has been shown to be NP-Complete. By adopting a fairly mild non-degeneracy assumption we are able to derive a low-order polynomial algorithm which reduces given constraints into an optimally sparse equivalent set of constraints. This algorithm is based on bipartite matching theory, and it induces a partial order on the rows of the matrix which is related to Dulmage-Mendelsohn decomposition. The proof that the algorithm is correct yields a performance guarantee when the algorithm is applied to real data, and several modifications that improve its running time are discussed. Some computational experience is presented which indicates that the algorithm may be practically useful as a preprocessor for linearly-constrained optimization. We also discuss the relationship of this research to finding optimally sparse null-space bases, and to the complexity of matroid oracles.;For the first problem, it has recently been realized that when the Hessian has a fixed, known sparsity pattern, a considerable reduction in gradient evaluations can often be achieved by a suitable choice of difference directions. This dissertation advances a way of classifying the various methods that have been proposed for choosing difference directions, and shows that finding an optimally small set of directions for any of the four sub-varieties of the Direct Methods is NP-Complete. The complexity results are obtained by showing that finding optimal sets of difference directions is equivalent to related graph coloring problems. Some results for more general methods are reported that yield good lower bounds on the minimum number of gradient evaluations needed to approximate many Hessians. |
