CVX Failed with identical inputs

1

Hi,
As described in my previous post, I am trying to solve a problem with a product term constraint. Now I solve it by decomposing the problem and iteratively call CVX to reach the solution. However, I find that sometimes the cvx_status is FAILED, with identical input constants. According to here, Failed means the solver cannot make enough progress even with a relaxed tolerance, so I am wondering if I should change the precision to make it work.

Here is the brief and sample program I use, it is not identical to the one I am testing, but the concept is the same.

last_tot = 0;
while diff >= tolerance
res_s = allocS(r, u1, u2, res_p, res_s);
[tot, res_p] = allocP(r, u1, u2, res);
diff = abs(tot - last_tot);
last_tot = tot;
end

and the cvx model for allocP:

input: r, u1, u2, s
K = length®;
NUM_U1 = length(u1);
rpos = u2.getPosition();
cvx_begin
obj = 0;
expression sub_D(NUM_U1);
expression sub_E(K, NUM_U1);
expression sub_P(NUM_U1, NUM_SLOT);
variable p(K, NUM_U1)
for u = 1:NUM_U1
for k = 1:K
obj = obj + s(k, u) * p(k, u) * r(k).duration / 1000;
end
end
minimize (obj)
res_p=p;
subject to
for u = 1:NUM_U1
pos = u1(u).getPosition();
for k = 1:K
sinr = SINR2(p(k, u), r(k).bandwidth, pos.x, pos.y, pos.z, rpos.x, rpos.y, rpos.z);
bps = log(1 + sinr) / log(2);
sub_D(u) = sub_D(u) + s(k, u) *bps * r(k).duration;
end
end
for u = 1:NUM_U1
sub_D(u)>=U1(u).getRequirement();
end

    for k = 1:K
        for u = 1:NUM_U1
            sub_S(k) = sub_S(k) + s(k, u);
        end
    end
        for i = 1:K
            sub_S(i)<=1;
        end
        s>=0;
        s<=1;
    for u = 1:NUM_U1
        for k=1:K
            sub_E(u) = sub_E(u) + s(k, u) * p(k, u)* r(k).duration;
        end
    end
        for u = 1:NUM_U1
            sub_E(u)<=U1(u).getDirectE();
        end

    for u = 1:NUM_U1
        for k = 1:K
            for j = 1:length(r(k).tslot)
                t = r(k).tslot(j);
                sub_P(u, t) = sub_P(u, t) + s(k, u) * p(k, u);
            end
        end
    end
        for u = 1:NUM_U1
            for t = 1:NUM_SLOT
                sub_P(u, t) <= P_MAX;
            end
        end
cvx_end

finally, the model for allocS:

input: r, u1, u2, p, last_s
K = length(r);
NUM_U1 = length(u1);
rpos = u2.getPosition();
cvx_begin
    obj = 0;
    expression sub_D(NUM_U1);
    expression sub_E(K, NUM_U1);
    expression sub_P(NUM_U1, NUM_SLOT);
    expression sub_S(K);
    variable s(K, NUM_U1)
    for u = 1:NUM_U1
        for k = 1:K
            obj = obj + s(k, u) * p(k, u) * r(k).duration / 1000 - 6000000 * ((last_s(k, u)^2 - last_s(k, u)) + (last_s(k, u) * 2) * (s(k, u) - last_s(k, u)));
        end
    end
    minimize (obj)
    res_s=s;
    subject to
    for u = 1:NUM_U1
        pos = u1(u).getPosition();
        for k = 1:K
            sinr = SINR2(p(k, u), r(k).bandwidth, pos.x, pos.y, pos.z, rpos.x, rpos.y, rpos.z);
            sub_D(u) = sub_D(u) + s(k, u) * r(k).bandwidth * log(1 + sinr) / log(2) * r(k).duration;
        end
    end
        for u = 1:NUM_U1
            sub_D(u)>=U1(u).getRequirement();
        end

    for k = 1:K
        for u = 1:NUM_U1
            sub_S(k) = sub_S(k) + s(k, u);
        end
    end
        for i = 1:K
            sub_S(i)<=1;
        end
        s>=0;
        s<=1;
    for u = 1:NUM_U1
        for k=1:K
            sub_E(u) = sub_E(u) + s(k, u) * p(k, u)* r(k).duration;
        end
    end
        for u = 1:NUM_U1
            sub_E(u)<=U1(u).getDirectE();
        end

    for u = 1:NUM_U1
        for k = 1:K
            for j = 1:length(r(k).tslot)
                t = r(k).tslot(j);
                sub_P(u, t) = sub_P(u, t) + s(k, u) * p(k, u);
            end
        end
    end
        for u = 1:NUM_U1
            for t = 1:NUM_SLOT
                sub_P(u, t) <= P_MAX;
            end
        end
cvx_end

The CVX runs well until, for example, iteration-64, and shows failed when executing the model of allocP, with the input:
s(k, u) = [[1.00, 1.00, 1.00], [1.00, 1.00, 1.00], [1.00, 1.00, 1.00]];
Nevertheless, the identical input is executed by the allocP in the previous iteration and the result is success. Because it is once successfully executed(in iteration-63), I think it should not present failed, and that’s why I really have no idea why this happens.

Thanks for any help in advance!

2

I don’t understand what you are saying. Your programs are not the same, so why should you expect the same results

Using numbers in allocP such as 6e6 might cause difficulty for the solver. When CVX is called in a higher level iterative algorithm. CVX inputs at some iteration might become extreme, ill-conditioned, or whatever. This can easily happen when such algorithms are not safeguarded by line search or trust region. The algorithm can diverge or become very bad numerically. Such are the hazards of using your own crude non-convex optimizer rather than a high quality off the shelf non-convex optimizer.

3

Hi Mark,
Thank you for reply! I expect the same results since that the output from allocS is identical (at least it is identical when I use fprintf to print it out). Because the output from allocS is the same, and this output will be used as input to allocP, I believe they should reach the same result.

By the way, I found I should switch allocS and allocP. I am sorry that I misplaced the code:(

4

I still find it confusing what you’ve done. Please pay attention to my 2nd paragraph above.

5

Hi Mark,
After carefully reading the your second paragraph, I understand that CVX shows Failed because the large number such as 6e6 will make the solution become ill-conditioned. As a result, it may become difficult for CVX to make sufficient progress and therefore presents Failed. Is it correct?

By the way, is there anyway to prevent this? (I need the number to be very large to act as a penalty factor.)

Thanks!

6

It is the solver CVX calls, rather than CVX itself, which has difficulty.

I suggest you use an off the shelf non-convex optimizer, such as available under YALMIP, rather than trying to write your own optimizer, which as you have seen, may not be so easy.

7

OK. I will try. Thank you for the clarification and suggestion!