Title: Graph-Based Ascent Algorithms for Function Maximization,
Abstract: We study the problem of finding the maximum of a function defined on the
nodes of a connected graph. The goal is to identify a node where the function
obtains its maximum. We focus on local iterative algorithms, which traverse the
nodes of the graph along a path, and the next iterate is chosen from the
neighbors of the current iterate with probability distribution determined by
the function values at the current iterate and its neighbors. We study two
algorithms corresponding to a Metropolis-Hastings random walk with different
transition kernels: (i) The first algorithm is an exponentially weighted random
walk governed by a parameter $\gamma$. (ii) The second algorithm is defined
with respect to the graph Laplacian and a smoothness parameter $k$. We derive
convergence rates for the two algorithms in terms of total variation distance
and hitting times. We also provide simulations showing the relative convergence
rates of our algorithms in comparison to an unbiased random walk, as a function
of the smoothness of the graph function. Our algorithms may be categorized as a
new class of "descent-based" methods for function maximization on the nodes of
a graph.