I'm trying to perform inference over a subset of the latent variables of a hierarchical hidden Markov model I built.

I've derived the relevant optimization problem, but it's a pretty nasty piece of work, I'm wondering if I have any hope of optimizing the following expression:

\begin{align} &\max_{z}\frac{\pi_{z_1}}{(\sum_{n=1}^N(x_n-z_n)^2)^\frac{N}{2}}\prod_{i=0}^K\Big[\frac{\prod_{j=0}^K\Gamma(P_{ij}+f_{ij}(z)+1)}{\Gamma(K+2+\sum_{j=0}^Kf_{ij}(z))}\Big]\\\\\\ &\text{Subject to}\hspace{5mm}0\leq z_n\leq K\\\\ &\hspace{24.5mm}z_n\in{\bf Z}\\\\ &\hspace{24.5mm}x_n\in{\bf R}\backslash{\bf Z}. \end{align} $$$$ Where $P$ is a right stochastic matrix, $\pi$ is a non-negative vector which sums to $1$, and

$$f_{ij}(z)=\#\{(n,n+1):z_n=i,\; z_{n+1}=j,\; 1\leq n<N\}.$$ $$$$

If I can't get the global optimum, then I'm open to all types and manners of heuristics and approximations.

Mostly I just don't have the first clue where to begin when it comes to integer programming except to try for a linear relaxation, and in this case that approach seems completely unworkable.

  • Perhaps try some suggestions in answer by @Septimus G .Then try throwing it in (the not entirely rigorous) global optimizer, BARON, and see what happens. You haven't told us the values of N and K. Do you have a good feasible starting point? Du you know any feasible point? You could also try a local mixed integer nonlinear optimizer, such as KNITRO. – Mark L. Stone Nov 15 '16 at 5:29
  • How large is $N$ and $K$ – Johan Löfberg Nov 16 '16 at 14:05

There are solvers for non linear mixed integer programming that can solve problems to optimality under certain conditions, or provide good quality solutions otherwise. These are based in generalized benders decomposition and outer approximation. You also have heuristics, which pretty much let you do whatever you want. You can try genetic algorithms which are relatively well studied.

Now a few suggestions to help you linearize your problem:

The product of two continuous variables cannot be linearized. So if this is entirely unavoidable to represent your problem, don't worry about linearizing. Also remember that quadratic programs are not that bad and even non convex MIQP can be solved to global optimality.

Often you can create new variables to help in the linearization process, as well as express part of the objective function as constraints.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.