Func. Optimization for target localization

Hello everybody, I am reproducing this paper http://www.bigdatalab.ac.cn/~wouyang/pubs/Received%20Signal%20Strength-Based%20Wireless%20Localization%20via%20Semidefinite%20Programming%20Noncooperative%20and%20Cooperative%20Schemes.pdf.
To be exact, I am implementing the eq. 17. 17.
The first error is “Error using sym>tomupad (line 1251)
Unable to convert ‘cvx’ to ‘system’.” To avoid this error and see if the rest of the code works I set up X=eye(2) and I got another error: "Error using reshape
To RESHAPE the number of elements must not change.

Error in cvx/cat (line 88)
yb = reshape( yb, nz, psz );

Error in cvx/vertcat (line 6)
y = cat( 1, varargin{:} );".

Here, part of the code:

cvx_begin
variables theta(2) t(N); % theta= [x y] target loc. % N=number of anchors
X= thetatheta’; % X -> auxiliary variable
% X= eye(2);
minimize(norm(t, inf))
subject to
for i =1:N
trace(X) - 2
phi(i,:)*theta +Ki(i) <= Bi_sqr(i)t(i);
[ trace(X) - 2
phi(i,:)*theta +Ki(i), sqrt(Bi_sqr(i));
sqrt(Bi_sqr(i)), t(i)] >= 0;
[ X, theta;
theta’, 1 ]>= 0;
end

cvx_end

I am new with this tool, my apologies if my questions are so basic. Any help you can provide will be greatly appreciated.

You should never be forming X= theta*theta’. That is non-convex. Instead, this formulation relaxes that via Schur Complement into the LMI, [X, theta;theta’, 1 ] >= 0. Note that you need to use cvx_begin sdp if you want to enter it this way, otherwise use [X, theta;theta’, 1 ] == semidefinite(3)

So use variable X(2,2) symmetric .and get rid of X= theta*theta’;

I have not checked to see whether you have any other errors.

1 Like

Mark, thanks a lot for your kind reply.
I made changes in the code following your suggestion. Here is the new code:

cvx_begin
variables theta(2) t(N); % theta= [x y] target loc. % N=number of anchors
variable X(2,2) symmetric

minimize(norm(t, inf))

subject to
    for i =1:N

        trace(X) - 2*phi(i,:)*theta +Ki(i) <= Bi_sqr(i)*t(i);
        [ trace(X) - 2*phi(i,:)*theta +Ki(i), Bi(i) ;
          Bi(i), t(i)] >= 0; 

% trace(X) - 2*phi(i,:slight_smile:theta +Ki(i) >= Bi_sqr(i)(1/t(i));

    end
    [ X, theta ; theta', 1 ]>= 0;

cvx_end

The first error does not appear anymore, however, the second one is still present. This error is related to the second constraint(red box):17

Error using reshape
To RESHAPE the number of elements must not change.

Error in cvx/cat (line 88)
yb = reshape( yb, nz, psz );

Error in cvx/vertcat (line 6)
y = cat( 1, varargin{:} );

This error is for this line of code which is the LMI for the second constraint:


[ trace(X) - 2*phi(i,:)*theta +Ki(i), Bi(i) ;
Bi(i) , t(i) ] >= 0;

I also try to use its original form ( trace(X) - 2*phi(i,: )theta +Ki(i) >= Bi_sqr(i)(1/t(i)); ) then it appears the following error:

Error using ./ (line 42)
Disciplined convex programming error:
Invalid operation: {1} / {real affine}

Any suggestion to avoid this error will be kindly appreciated.
thank you very much for your time

For the 2nd form, you can use inv_pos. If you do so, CVX accomplishes behind the scenes what the LMI version of that is doing.

Your LMI has a reshape error because spaces before and after - and + are causing MATLAB to create additional elements, as would occur with comma, So remove all the spaces within an element of the matrix.

Also, given the >= 0 syntax you’ve used to specify LMIs (semidefinite constraints), you need to use cvx_begin sdp That was the point of the 3rd sentence of my previous post, but I somehow forgot to include sdp prior to editing it just now.

1 Like

Dear Mark,

Thank you very much for your time, I really appreciate it. Thanks to your advice, I could solve my problem.
Do you know a web or book where I can check CVX optimization codes, by any chance? I would like to practice more.

Once again, thank you very much.

You can look at http://cvxr.com/cvx/examples/ for CVX examples. I think there are some optimization books which have some CVX examples, but I have not read any of them,

If you read http://stanford.edu/~boyd/cvxbook/ and do some of the exercises, you can greatly improve your ability to formulate and transform convex optimization problems suitable for CVX. And you will probably get some insight to help you understand what CVX is doing under the hood (you can look at CVX source code for functions such as inv_pos to see what it does).

Re-read the CVX USer’s Guide, now that you’ve actually used CVX a bit.

You can also read old CVX forum postings - many will be boring and uninsightful, but several of them might prove interesting and informative. Unfortunately, the thread titles are often not very informative as to the contents.

1 Like

Once again, thanks a lot!

The MOSEK modeling cookbook https://docs.mosek.com/modeling-cookbook/index.html may also help you understand how to formulate and transform conic optimization problems in a way which will help you use CVX effectively, even though it has no CVX examples. It should help you understand papers such as the one you linked, and how to implement models described therein in CVX. http://stanford.edu/~boyd/cvxbook/ (previously linked) can do that as well.

1 Like

Dear Mark,
I am reproducing a paper entitled “Cooperative RSS-Based Localization in Wireless Sensor Networks Using Relative Error Estimation and Semidefinite Programming”. It seems that I can not upload the file.
I am implementing the following equation:eq17
In the paperUi where ‘a_i’ and ‘x’ are bidimensional vectors, and ‘v_i=1/u_i’.
Please find below my code for this equation:

cvx_begin sdp quiet
variables u_i(len_ANs) v_i(len_ANs) % ‘len_ANs’ is the length of the set ‘A’
variable Z(3,3) symmetric

        cost=0;
        for i=1:len_ANs
            cost=cost+(u_i(i)/(d_tilt(i)^2)+(d_tilt(i)^2)*v_i(i));
        end
        
        minimize(cost)

        subject to
            for i =1:len_ANs
                u_i(i)==[a_i(i,:) -1]*Z*[a_i(i,:)';-1];
                [v_i(i) 1; 1 u_i(i)]>=zeros(2,2);
            end
            Z(1:2,1:2)==eye(2);
            Z>=zeros(3,3);

cvx_end

In this occasion, I don’t have any error :slight_smile: however the results that I have obtained are quite different from what is shown in the paper. I have contacted the authors for this matter but unfortunately, I couldn’t get any response. I know that this difference can be for some simulations setups but I would like to discard any problem within the code. Please, could you let me know if you find any inconsistency with the code and the equation?
Additionally, I wonder if a problem is formulated using a second-order cone programming the way how I call the CVX package affects the result, for instance, what about if I use just " cvx_begin" instead of " cvx_begin sdp"?
Thank you very much.

I don’t see anything obviously wrong from a quick perusal, except that I have no idea how u_i = ||a_i - x||^2 is supposed to come into play.

You have not provided a reproducible problem, because you didn’t provide the input data. And you haven;t shown the output, and how it compares to the paper. Furthermore, you have used quiet, so we don’t know what the solver and CVX reported in terms of whether the problem was solved.

Dear Mark,
thank you very much for your kind reply. Well, the main idea is to retrieve de estimation of ‘x’ (which is related to u_i by Ui ) from ‘Z’ after solving (17). The input for (17) is ‘d_tilt’ and the output the estimation of ‘x’. Please find below a complete version of the code for one Monte Carlo simulation:
(By the way, I have uploaded the paper. Please follow this link if required https://drive.google.com/file/d/1qA-gU_rcgNOOI3u5RLFqjyto7TTDxzOe/view?usp=sharing)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Parameter setup    
a_i= [0 0; 100 0; 100 100; 0 100; 50 50];
len_ANs= length(a_i);

y=4;
do=1;
P0=-40; 
mean_ni=0;
sigma_ni=sqrt(6) ;

TN=[10 30] % 'x'

% Data generation
for i= 1: len_ANs
    n_i(i)= normrnd(mean_ni,sigma_ni); % noise generation
    P_i(i)= P0 - 10*y*log10(norm(TN-a_i(i,:),2))+ n_i(i); % RSS generation
    d_tilt(i)= 10^((P0-P_i(i))/(10*y)); % input to eq. (17)
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cvx_begin sdp %quiet
    variables u_i(len_ANs)  v_i(len_ANs) 
    variable Z(3,3) symmetric 
            
    cost=0;
    for i=1:len_ANs
        cost=cost+(u_i(i)/(d_tilt(i)^2)+(d_tilt(i)^2)*v_i(i));
    end
            
    minimize(cost)
 
    subject to
        for i =1:len_ANs
            u_i(i)==[a_i(i,:) -1]*Z*[a_i(i,:)';-1];
            [v_i(i) 1; 1 u_i(i)]>=zeros(2,2);
         end
         Z(1:2,1:2)==eye(2);
         Z>=zeros(3,3);
cvx_end
ui_SDP_wang=Z(1:2,3)'; % estimation of 'x'
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
RMSE_SDP_Wang=sqrt(norm(TN-ui_SDP_wang,2).^2) % Paper output

I have noticed that most of the time the status of the solver is Inaccurate/Solved. May I know why is it happening and how to solve it? Below what CVX reports:

Calling SDPT3 4.0: 21 variables, 8 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 8
dim. of sdp var = 3, num. of sdp blk = 1
dim. of socp var = 15, num. of socp blk = 5


SDPT3: Infeasible path-following algorithms


version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|4.0e+02|1.9e+00|1.6e+09| 4.149766e+08 0.000000e+00| 0:0:00| chol 1 1
1|0.680|0.966|1.3e+02|6.3e-02|5.6e+08| 1.449905e+08 -1.764069e+08| 0:0:00| chol 1 1
2|0.749|1.000|3.2e+01|2.0e-05|1.3e+08| 4.739923e+07 -3.048139e+07| 0:0:00| chol 1 1
3|0.983|0.988|5.4e-01|1.0e-05|4.0e+06| 9.274871e+05 -2.366880e+06| 0:0:00| chol 1 1
4|0.987|0.988|6.9e-03|5.1e-06|5.0e+04| 1.285241e+04 -2.851439e+04| 0:0:00| chol 1 1
5|0.989|0.988|7.9e-05|2.9e-06|6.5e+02| 1.529656e+02 1.041754e+02| 0:0:00| chol 1 1
6|0.938|0.986|4.8e-06|1.3e-06|3.3e+01| 1.095234e+01 2.151152e+02| 0:0:00| chol 1 1
7|1.000|1.000|6.4e-08|6.3e-07|5.9e+00| 8.691059e-01 1.084538e+02| 0:0:00| chol 1 1
8|0.814|1.000|1.3e-08|3.1e-07|9.2e-01|-1.799748e+00 5.383127e+01| 0:0:00| chol 1 1
9|0.978|0.923|1.0e-08|1.7e-07|8.3e-02|-2.385762e+00 2.794112e+01| 0:0:00| chol 1 1
10|1.000|0.941|5.1e-09|8.3e-08|1.1e-02|-2.416270e+00 1.264399e+01| 0:0:00| chol 1 1
11|0.925|0.906|1.5e-08|4.3e-08|1.2e-03|-2.420460e+00 5.389480e+00| 0:0:00| chol 1 1
12|1.000|0.934|1.7e-08|2.1e-08|1.1e-04|-2.420835e+00 1.388397e+00| 0:0:00| chol 1 2
13|0.965|0.970|2.3e-08|6.3e-10|3.9e-06|-2.421804e+00 -2.306499e+00| 0:0:00| chol 1 1
stop: primal infeas has deteriorated too much, 8.0e-07
14|1.000|1.000|2.3e-08|6.3e-10|3.9e-06|-2.421804e+00 -2.306499e+00| 0:0:00|

number of iterations = 14
primal objective value = -2.42180423e+00
dual objective value = -2.30649890e+00
gap := trace(XZ) = 3.93e-06
relative gap = 6.85e-07
actual relative gap = -2.01e-02
rel. primal infeas (scaled problem) = 2.33e-08
rel. dual " " " = 6.33e-10
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 1.1e+04, 1.1e+03, 2.3e+04
norm(A), norm(b), norm© = 6.0e+02, 1.6e+04, 3.5e+04
Total CPU time (secs) = 0.12
CPU time per iteration = 0.01
termination code = -7
DIMACS: 2.9e-08 0.0e+00 1.1e-09 0.0e+00 -2.0e-02 6.9e-07


Status: Inaccurate/Solved
Optimal value (cvx_optval): +9.89173

Using the input you have provided, the problem is solved to reported oiptimality by all three of SDPT3, SeDuMi, and Mosek, and all within agreement with each other within tolerance. The optimal u_i values go up to ~ 1e4, which is a little large, but doesn’t seem to present a problem (although perhaps it does in post-processing?)

I haven’t tried to figure out what you are doing with your post-CVX calculations, because that is not part of your CVX optimization problem, But perhaps you are doing something different from the paper there.

Dear Mark,
As I mentioned before the status of the solver, most of the time is “Status: Inaccurate/Solved”. To consider a proper solution the status shouldn’t be just “Status: Solved”?

You provided one problem instance (one set of input data), and I wrote what happened when I ran the problem. If Status is Inaccurate/Solved, the solver was not able to achieve the requested accuracy. That cold be because of a numerically challenging problem, or just because the solver isn’t that robust. It may happen that SDPT3 gets Inaccurate/Solved, but Mosek, which is more numerically robust can acheve solved. BTW, don’t assume that all the runs made by the paper’s authors were necessarily “clean”. For al we know, you may be the 2nd person in the world (and me, the 3rd) to ever attempt the method in the paper.

Dear Mark,
thanks a lot for kind reply. I see… Ccould you let me know your opinion about this remain question:

That shouldn’t make a difference, presuming you follow CVX’s syntax for specifying SDPs. CVX converts all 2 by 2 SDPs into (rotated) Second Order Cone constraints before providing the problem to the solver. You could instead do this yourself. The paper started with a rotated second order cone constraint and formulated it as a 2 by 2 SDP. CVX converts it back before calling the solver.

Dear Mark,
I see…!
Once again, thank you very much for time and attention. I really appreciate it.