0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Commented Nov 15, 2016 at 5:29
  • $\begingroup$ How large is $N$ and $K$ $\endgroup$
    – Johan Löfberg
    Commented Nov 16, 2016 at 14:05

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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