  Logarithmic Sobolev inequalities play an important role in understanding the
mixing times of Markov chains on finite state spaces. It is typically not easy
to determine, or indeed approximate, the optimal constant for which such
inequalities hold. In this paper, we describe a semidefinite programming
relaxation for the logarithmic Sobolev constant of a finite Markov chain. This
relaxation gives certified lower bounds on the logarithmic Sobolev constant.
Numerical experiments show that the solution to this relaxation is often very
close to the true constant. Finally, we use this relaxation to obtain a
sum-of-squares proof that the logarithmic Sobolev constant is equal to half the
Poincar\'e constant for the specific case of a simple random walk on the odd
$n$-cycle, with $n\in\{5,7,\dots,21\}$. Previously this was known only for
$n=5$ and even $n$.
