I have given an absorbing Markov chain $P_t$ dependent on the transition probabilities $t:V \times V \rightarrow [0,1]$ for $V$ the states of the chain. Given is also a initial vector $x$ and a vector $b$. The goal is then to find $$\min\limits_{t \in [0,1]^{E}} |N x -b|$$ for the fundamental matrix $N_t := (Id-P_t)^{-1}$. To complicate things even further, the transition probabilities are restricted through some functions $(f_i)_{i=1,\ldots, k},~f_i : [0,1]^{E} \rightarrow \mathbb{R}$. The restriction is then of the form $\forall i \in \{1,\ldots,k\}: f_i = 0$. The functions are multivariate rational functions over the transition probabilities and not convex. Given some transition probabilities $t \in [0,1]^E, t = (t_1, \ldots, t_{|E|})$ an example function would be $f(t) = -t_1t_2 + \frac{((-t_3 - t_1t_4)t_5)}{(-1 + t_6t_5 + t_7t_5)}$

As I am an algebraic topologist and do not know much about numerics. What kind of optimization algorithm would one use to solve this problem?

  • $\begingroup$ In optimization, it's convex versus nonconvex, not linear versus nonlinear. Are the nonlinear constraints quadratic? What is their structure? $\endgroup$ – Rodrigo de Azevedo Jan 5 '17 at 10:34
  • $\begingroup$ @RodrigodeAzevedo I added some infos to the question, thanks for the hint! $\endgroup$ – berndibus Jan 5 '17 at 14:02
  • $\begingroup$ Which vector norm are you minimizing? $\endgroup$ – Rodrigo de Azevedo Jan 5 '17 at 14:37
  • $\begingroup$ @RodrigodeAzevedo Does this make a difference? These are vectors in $\mathbb{R}^n$, and all norms are equivalent there. But I may be wrong, and in that case I mean Euclidean norm. $\endgroup$ – berndibus Jan 6 '17 at 0:16
  • $\begingroup$ Can you please explain what you want to do and where the $f_i$ functions come from? Also, you may want to take a look at Fastest Mixing Markov Chain on a Graph (2004). $\endgroup$ – Rodrigo de Azevedo Jan 6 '17 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.