# Nonlinear integer program with linear constraints

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