CVX Code for Pairwise Ranking

Uncategorized
Aug 23, 2012
S
#1

Hi,
I want to know the CVX code for the following problem:
s & R are m-dimensional vector.

minimize (d) (d is a declared vector of dim m)
s.t
d>=0
s’=s+d
s’i>= 1+ s’j if Ri>Rj

Basically, i want to compare every element of s’ with every other element of s’, provided the condition on R holds.
Thanks

ADDED: Hi, There is no example as such in the CVX user guide. The problem is with the pairwise comparison part. I am trying to put the constraint that whenever Ri>Rj, the S’i>=1 +S’j. And this should happen for all i,j (i= 1…m, j=1…m). This constraint is extensively used in pairwise ranking algorithm. Is it possible to write this in CVX? Thanks

M
#2

What have you tried so far? This forum is not intended to be a substitute for trying out the software and reading the user guide.

S
#3

Hi,
There is no example as such in the CVX user guide. The problem is with the pairwise comparison part.
I am trying to put the constraint that whenever Ri>Rj, the S’i>=1 +S’j. And this should happen for all i,j (i= 1…m, j=1…m). This constraint is extensively used in pairwise ranking algorithm.
Is it possible to write this in CVX?
Thanks

M
#4

I’m going to move your “answer” (which is not an answer, of course :P) to your text above, where it belongs. As the name implies, answer posts are reserved for answers to the original question. Comments are reserved for discussions like these.

M
#5

Again, I need to ask, what have you tried? If Ri and Rj are constants then I see no reason why this would not work. If they are variables, then of course it will not work, as the model is not convex.

M
#6

Here is some simple CVX code that assumes that s and R are vectors of length m:

cvx_begin
    variable sp(m)
    minimize( sum(sp-s) )
    sp >= s
    for i = 1 : m
        for j = 1 : M
           if R(i) > R(j),
                sp(i) >= 1 + sp(j)
           end
       end
   end
cvx_end

This has not been tested, and the for loops are going to be slow for large m. This might fix it, but again, you’d better test it.

cvx_begin
    variable sp(m)
    minimize( sum(sp-s) )
    sp >= s
    [ii,jj] = find( bsxfun( @gt, R(:), R(:)' ) );
    sp(ii) >= sp(jj) + 1
cvx_end