On the determinant and its derivatives of the rank-one corrected generator of a Markov chain on a graph

DOI10.1007/S10898-012-9855-XMaRDI QIDQ2393062zbMATH OpenOpenAlexFDO

Authors Jerzy Filar, Michael Haythorpe, Walter Murray

Publication date 7 August 2013

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.10348

zbMATH Keywords

Markov chaindeterminantderivativedoubly stochasticgenerator matrixLU decompositionHamiltonian cycle problemcofactorsrank-one correction

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Abstract: We present an algorithm to find the determinant and its first and second derivatives of a rank-one corrected generator matrix of a doubly stochastic Markov chain. The motivation arises from the fact that the global minimiser of this determinant solves the Hamiltonian cycle problem. It is essential for algorithms that find global minimisers to evaluate both first and second derivatives at every iteration. Potentially the computation of these derivatives could require an overwhelming amount of work since for the Hessian $N^2$ cofactors are required. We show how the doubly stochastic structure and the properties of the objective may be exploited to calculate all cofactors from a single LU decomposition.

Recommendations

• Determinants and Longest Cycles of Graphs
• Markov chains and optimality of the Hamiltonian cycle
• On the Hamiltonicity gap and doubly stochastic matrices
• Consistent behavior of certain perturbed determinants induced by graphs
• Hamiltonian Cycles and Markov Chains

Cites work

• A decomposition theorem for infinite stochastic matrices
• Determinants and Longest Cycles of Graphs
• Finding Hamiltonian cycles using an interior point method
• Hamiltonian Cycles and Markov Chains
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(3)

• Consistent behavior of certain perturbed determinants induced by graphs
• A new heuristic for detecting non-Hamiltonicity in cubic graphs
• Finding a Hamiltonian cycle by finding the global minimizer of a linearly constrained problem

This page was built for publication: On the determinant and its derivatives of the rank-one corrected generator of a Markov chain on a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2393062)