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

DOI10.1007/S10898-012-9855-XzbMATH Open1291.90185arXiv1902.10348OpenAlexW2010434061MaRDI QIDQ2393062FDOQ2393062

Authors: Jerzy Filar, Michael Haythorpe, Walter Murray 

Publication date: 7 August 2013

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

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.

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

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

zbMATH Keywords

Markov chaindeterminantderivativedoubly stochasticgenerator matrixLU decompositionHamiltonian cycle problemcofactorsrank-one correction

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Cites Work

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

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)