Finite time horizon sdp problem

(Moon) #1

I have the following sdp formulation in infinite time horizon

\begin{equation} \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} \end{equation}

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{equation} \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} \end{equation}

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.