(Affine) matrix product of a variable Markov matrix with a positive variable vector

1

Hi Team

Firstly, awesome tool! Thanks for CVX, it is fantastic.

I have a Markov matrix (every entry is positive or zero, every column adds up to 1) and a state vector which has strictly positive entries.

I can prove that this is affine by using linearity, the positivity of every entry and the column sum condition.

Is there a clever way to let CVX know that the matrix product of my Variable Markov matrix and the Variable state vector is affine?

I am trying to minimise the nuclear norm of a Markov matrix with hidden state variables whose initial condition I know, as well as how long the matrix has been iterating for. I have known positive numerical outputs of the hidden states at each step in time as well, which are affine.

I searched for Markov matrix related posts and couldn’t find ones which covered my use case.

Any help is appreciated, I recognise that most of the time the active participants on this forum spend their time telling people that they need to read the modelling sticky post (which I’ve done).

Thanks!
Jacques

2

Why is the product of a matrix variable and vector variable affine? You can constrain the product to equal an affine vector and constrain column sums to 1, but that won’t make the products be affine. Perhaps you have some particular meaning in mind which enables you to “prove that this is is affine by using linearity, the positivity of every entry and the column sum condition.”,; but if so, I have no idea what you mean,

if you have some underlying convex optimization (or feasibility) problem, you need to make clear exactly what that mathematical problem is. I have no idea what problem you are trying to model or solve.

3

Dear Mark

Thanks! I should have been clear; it is a hidden Markov model problem.
I’m using CVXR; %*% is the matrix multiplication operator in R

T <- 10 #samples in time
n <- 5 #Markov states

x_init <- matrix(c(0,0,1,0,0),nrow=n) #initial state vector of Markov system
d  #data vector of Markov output for the known initial condition, x_init. All numbers are positive in this vector

P <- Variable(n,n) #Markov matrix
x <- Variable(n,T) #history of states, stored as rect matrix

C <- matrix(c(1,1,0,0,0),nrow=1) #output vector

ones <- matrix(1, nrow = 1, ncol = n) #used in column sum constraint

obj <- Minimize(norm_nuc(P)) #Goal is to find Markov matrix with smallest nuclear norm

constr_struc <- list(P >= 0, ones %*% P  == ones) #Structural constraints on Markov matrix
constr_absorb <- list(P[n,n] == 1) #absorbing state in matrix
constr_dyn <- list(x>=0, x[,1] == x_init) #dynamic constraints on states and initial condition

# Here are the dynamic constraints in the forward equation, with known outputs at time t determined by data d[t]
for (t in 1:(T-1)){
  constr_dyn <- c(constr_dyn,
                            x[,t]>=0,
                            x[,t+1]>=0,
                            x[,t+1] == P %*% x[,t], 
                            C %*% x[,t] == d[t])
}
prob <- Problem(obj, c(constr_struc, constr_absorb,constr_dyn))
result <- solve(prob)

The error I get is for the constraint x[,t+1] == P %*% x[,t]

What work do I need to do to assure the solver that P %*% x[,t] is affine please?

I’m imagining that I would need to write a function like Markov_step(P,x[,t]) but wanted to receive guidance or references that would make this useable for others with the same sort of problem.

Grateful for your patience and any help
Jacques

4

This is a CVX forum., not a CVXR forum (despite the URL being cvxr.com)

I don’t understand the question. if only one of P and x is a variable, the product is affine; otherwise it is not.