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

Jerzy Filar, Michael Haythorpe, Walter Murray

    Research output: Contribution to journalArticle

    1 Citation (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)1425-1440
    Number of pages16
    JournalJournal of Global Optimization
    Volume56
    Issue number4
    DOIs
    Publication statusE-pub ahead of print - 2013

    Fingerprint Dive into the research topics of 'On the determinant and its derivatives of the rank-one corrected generator of a Markov chain on a graph'. Together they form a unique fingerprint.

  • Cite this