# Finite time horizon sdp problem

(Moon) #1

I have the following sdp formulation in infinite time horizon

$$\begin{split} \min_{P,Z} &\ trace(SXP)+trace(Z)\\ \text{sbj to } & \\ &\begin{bmatrix} XP-I & YP\\ P^T Y^T & XP \end{bmatrix} \succeq 0\\ &\begin{bmatrix} Z & R^{1/2}UP\\ P^T U^T R^{1/2} & XP \end{bmatrix}\succeq 0 \end{split}$$

that is in cvx:

       cvx_begin sdp
variable Z(1,1)
variable P(T,n)
minimize( trace(S*X*P)+ trace(Z) )
subject to
[Z, R^{1/2}*U*P; P'*U'*R^{1/2}, X*P] >= 0
[X*P-eye(n), Y*P; P'*Y', X*P] >= 0
cvx_end
K_cvx = -U*P*inv(X*P)


Now, I want to re-write it in finite horizon. Assuming my formulation is correct, it is the following

$$\begin{split} \min_{\substack{P_k,Z_k \\k\in \{ 0,\dots, N-1\} }} &\ trace(S_f X P(N)) + \sum_{k=0}^{N-1} \Big(trace(SXP(k))+trace(Z_k)\Big) \\ \text{sbj to } & \\ &\begin{bmatrix} X P(k+1) -I & Y P(k)\\ (Y P(k))^T & X P(k) \end{bmatrix} \succeq 0\\ &\begin{bmatrix} Z_k & R^{1/2}U P(k)\\ P(k)^T U^T R^{1/2} & X P(k) \end{bmatrix}\succeq 0\\ & X P(0) \succeq I_n \end{split}$$

which in cvx is

for j = 1:N-1
cvx_begin sdp
variable Z(1,1,N)
variable P(T,n,N)
minimize( trace(S*X*P(:,:,j))+ trace(Z(:,:,j)) + trace(Sf*X*P(:,:,N)) );
subject to
[Z(:,:,j), R^(0.5)*U*P(:,:,j); P(:,:,j)'*U' *R^(0.5), X*P(:,:,j)] >= 0;
[X*P(:,:,j+1)-eye(n), Y*P(:,:,j); P(:,:,j)' *Y' , X*P(:,:,j)] >= 0;
X*P(:,:,1) >= eye(n);
cvx_end
K_cvx_fh{j} = -U*P(:,:,j)*inv(X*P(:,:,j));
end


however, for {N \rightarrow \infty}, the solution is not converging to the infinite horizon solution. Do you have any tips to correct it?

(Mark L. Stone) #2

I won’t address what should or shouldn’t converge to what.

However, are you sure you are even specifying semidefinite constraints? Specifically, what guarantees that X*P is symmetric? You haven;t declared P to be symmetric (recall your previous thread LMI formulation using Yalmip vs CVX ), and I have no idea what (the numerical value of ) X is. Did you get a warning about asymmetry?

You mkay be better off at a different forum for a discussion of what should converge to what.

(Moon) #3

I already know the value of K (which it is obtained with Yalmip) and I want to obtain the same value using cvx. Solving the problem for infinite horizon formulation, K_{cvx} gives indeed K. I want also to write the sdp formulation in finite time, and to see if it is correct, I have chosen a big N so that the final K_{cvx_{fh}} converges to K_{cvx}. Unfortunately, there is still something missing because K_{cvx_{fh}} \neq K_{cvx} for N\rightarrow \infty .

Is it because I haven’t written properly in the code the \sum_{k=0}^{N-1} in the trace of the second formulation?

(Mark L. Stone) #4

In each CVX invocation, the objective as you have written the code is the sum of 3 trace terms. You are solving N-1 separate CVX problems. if that is not what you want to do, you need to change your code. You can, for instance, use a for loop from 0 to N-1 inside one CVX invocation (cvx_begin … cvx_end) to build up an objective function summing over terms from 0 to N-1.

If you show successful YALMIP code, hopefully it will not be difficult to determine how to implement it using CVX.

(Moon) #5

you are right, I am solving N cvx problem, which should not be the case. I need to solve this objective function \min_{P(k), Z(k)} \ trace(S_f X P(N)) + \sum_{k=0}^{N-1} (trace(SX P(k)) + trace(Z(k))). So i need to move the loop inside cvx_begin and take the sum over k in the objective function. Do you have any tutorials to help me out with this formulation? How can I write something like

    minimize( sum(trace(SX P(k)) + trace(Z(k)) )


and also I believe that it is wrong to define Z and P as

     variable Z(1,1,N)
variable P(T,n,N)


since the loop is inside cvx and I need to solve just one objective function.

(Mark L. Stone) #6

Fix this up to be what you want.

    Objective = 0
for k=1:N
Objective = Objective + trace(S*X*P(:,:,k)) + trace(Z(:,:,k))
end
minimize(Objective)


Constraints can also go inside a for loop if needed.

(Moon) #7

So there should be

     cvx_begin sdp
variable Z(1,1,N)
variable P(T,n,N)
obj = 0;
for j = 1:N-1
obj = obj + trace(S*X*P(:,:,j))+ trace(Z(:,:,j) )
subject to
[Z(:,:,j), R^(0.5)*U*P(:,:,j); P(:,:,j)'*U' *R^(0.5), X*P(:,:,j)] >= 0;
[X*P(:,:,j+1)-eye(n), Y*P(:,:,j); P(:,:,j)' *Y' , X*P(:,:,j)] >= 0;
X*P(:,:,1) >= eye(n);
end
minimize(obj + + trace(Sf*X*P(:,:,N))  )
cvx_end

K_cvx_fh = -U*P(:,:,N)*inv(X*P(:,:,N));


Still,

    Status: Failed
Optimal value (cvx_optval): NaN
(Mark L. Stone) #8

Is this infeasible? Look at my first post of this thread and address that.

Hmm, well if n does not equal N, then P can not be symmetric. Nevertheless, if X*P(:,:,j) is not symmetric, those can not be valid SDPs.

(Moon) #9

yes this is the problem indeed, this is not clear to me how these 3D arrays work…
so that would be XP(k+1)-I_n where P(k+1) is size T\times n and X is a data vector of size n \times T and k=0, \dots ,N.

Considering the 3d array

X*P(:,:,j+1)-eye(n)

should I change the size of eye(n)?

(Mark L. Stone) #10

I have no idea what you are doing. It is necessary, but not sufficient, that dimensions be conformal (consistent, as required in pre-2016b MATLAB).

P(N,N,K) symmetric
declares that each of the K 2-D slices, P(:,:,k) for k from 1 to N is symmetric. However, you have P(T,n,N), so this can not be declared symmetric unless T = n.

If you can not construct a symmetric matrix, then you can not use it in an SDP. Maybe you need to go back to the origins of the problem and make sure you have proper a mathematical formulation for specifying SDPs. Try to get the single time period problem correct before you venture into the multi-period problem.

(Moon) #11

This is the single time (asymptotic behavior )problem

   cvx_begin sdp
variable Z(1,1)
variable P(T,n)
minimize( trace(S*X*P)+ trace(Z) )
subject to
[Z, R^{1/2}*U*P; P'*U'*R^{1/2}, X*P] >= 0
[X*P-eye(n), Y*P; P'*Y', X*P] >= 0
cvx_end
K_cvx = -U*P*inv(X*P)


also in this case I have P(T,n) where T\neq n but it returns the correct value for K_{cvx}. Here there is no terminal penalty trace(Sf*X*P(:,:,N)) in the cost function and no initial condition X*P(:,:,1) >= eye(n)

(Mark L. Stone) #12

Using the optimal X, is X*P symmetric psd? using optimal Z and X, are [Z, R^{1/2}*U*P; P'*U'*R^{1/2}, X*P] and [X*P-eye(n), Y*P; P'*Y', X*P] psd?

(Moon) #13

They are psd but not symmetric for both cases.

(Mark L. Stone) #14

CVX deals with symmetric matrices in SDP (LMI) constraints. If the matrix is not symmetric, then you have not implemented anything meaningful in CVX. Perhaps you happen to get a correct or reasonable answer in some cases.

You need to formulate structurally symmetric matrices to be constrained to be semidefinite. If you can not ot do that, I think you are playing around in nonsense, whether you use CVX or YALMIP.