Convex optimization with convex constrained(Infeasible solution) I am confused constrained no.2 and 3


(EHTISHAM ASGHAR) #1

Objective function is s(t)^2

My code is
T = 16; s_min = 1; s_max = 6; jobs = 11;
A = [1,3,4,6,7,9,11,12,13,10,12];
D = [6,13,10,10,10,13,14,16,16,16,16];
S = randn(16,11);
W = ones(11,1);

cvx_begin quiet

obj = 0;
variable s(16,1)
for t = 1:T

obj = obj + s(t)*s(t);

end

minimize(obj)

%constraints
for t = 1:T
subject to
s_min <= s(t) <= s_max %constraint no.1
subb2 = 0;
subb3 = 0;

for i = 1:jobs
    subb2 = subb2 + S(t,i);
   
     if   t == A(i)
        for k = A(i):D(i)
            subb3 = subb3 + S(k,i);
        end
     end

      subb3 >= W(i)                %constraint no.3

end
s(t) == Subb2 %constraint no.2

end

cvx_end
disp(s);
disp(cvx_optval);
disp(cvx_status);


(Mark L. Stone) #2

There are many problems with your code.

“Constraint 3” doesn’t involve CVX variables or expressions at all. It is formulated only in terms of MATLAB variables, Therefore, it is not a CVX constraint, and will output 1 or 0 depending on whether or not the MATLAB variables subb3 and W happen to satisfy subb3 >=- W(i).

You may be confusing yourself by having identical variable names, differing only in lower vs. upper case 1st letter, between MATLAB and CVX variables (also note Subb2 which doesn’t even exist).

I recommend not using quiet until you have a well functioning program you are confident in.

You are using for loops in many places which are unnecessary. For instance, your objective can be written as minimize(sum(s.^2)) . The constraint s_min <= s(t) <= s_max can be written as s_min <= s <= s_max outside of any for loop.

I suggest you define the matrix S as your CVX variable as such
variable S(T,jobs)
then the s can be created as CVX expressions by using= involving S on the right hand side.
You should make as much use of sum as you can, rather than for loops.

I have not attempted to tell you everything you need to do to fix your code. I leave it to you to make a serious attempt to fix it. Perhaps you should re-read the CVX Users; Guide before you try.


(EHTISHAM ASGHAR) #3

I follow your kind instructions sir.
Thanks a lot for answering me.


(EHTISHAM ASGHAR) #4

Sir I could not get you about " I suggest you define the matrix S as your CVX variable as such
variable S(T,jobs), then the s can be created as CVX expressions by using = involving S on the right hand side." Because s is single dimension array as s(T) and S(T,Jobs), is it possible? Or if use S(T,jobs) as CVX variable and s(t) as expressions then what about objective function? I am not getting your point, I am still confused how to handle constraint no.3?
And now I have removed most of for loop, please have look.

% input data
T = 16; s_min = 1; s_max = 6; jobs = 12;
A = [1,3,4,6,7,9,11,12,13,13,10,12];
D = [6,13,10,10,10,13,14,15,15,16,16,16];
S = rand(16,12);
cvx_begin
variable s(16);
minimize(sum(s.^2))
subject to
s_min <= s <= s_max;
for t=1:T
s(t) == sum(S(t,:))
end
cvx_end
disp(s);
disp(cvx_optval);
disp(cvx_status);


(Mark L. Stone) #5

S shouldn’t be random data, it should be declared as a CVX variable, as I stated above.

Do not declare s as a variable. The for loop specifying s(t) should have s(t) = sum(S(t,:)). which makes s a CVX expression. And this must be placed before the minimize in which s is used. Then you need to add the constraints involving W.


(EHTISHAM ASGHAR) #6

Like this?
% input data
T = 16; s_min = 1; s_max = 6; jobs = 12;
A = [1,3,4,6,7,9,11,12,13,13,10,12];
D = [6,13,10,10,10,13,14,15,15,16,16,16];
W = rand(jobs);
cvx_begin
variable S(T,jobs);
expression s(16);
for t=1:T
s(t) = sum(S(t,:))
end
minimize(sum(s.^2))
subject to
s_min <= s <= s_max;
for t=1:T
s(t) == sum(S(t,:))
for i = 1:jobs
sub3 = 0;
if t == A(i)
for k = A(i):D(i)
sub3 = sub3 + S(k,i);
end
end

                sub3 >= W(i)                %constraint no.3
            end
   end

cvx_end
disp(s);
disp(cvx_optval);
disp(cvx_status);


(Mark L. Stone) #7

I haven’t checked this very carefully, but this code might model your problem. I leave you to check that it models what you want.

T = 16; s_min = 1; s_max = 6; jobs = 12;
A = [1,3,4,6,7,9,11,12,13,13,10,12];
D = [6,13,10,10,10,13,14,15,15,16,16,16];
W = rand(jobs,1);
cvx_begin
variable S(T,jobs);
expression s(16)
for t=1:T
s(t) = sum(S(t,:));
end
minimize(sum(s.^2))
subject to
s_min <= s <= s_max;
for i = 1:jobs
sum(S(A(i):D(i),i)) >= W(i)
end
cvx_end

Edit:expression s(16) should really be expression s(T) so that the code will still work if the value of T is changed to something other than 16.


(EHTISHAM ASGHAR) #8

Thank sir Mark i am very thank full to you. I see it.


(EHTISHAM ASGHAR) #9

Sir code is running but not according to model. Can you please have a look on constraint no.2 how it is applied in the code?


(Mark L. Stone) #10

What you called constraint 2 in your original post was messed up. Can you tell me which constraint number 2 is in the image in the first post?

I think my code includes all the constraints in the image, although the “constraint” s(t) = sum(S(t,:)) is implemented by use of a CVX expression rather than constraint. Is that what you are calling constraint 2? If so, the CVX expression is how it is applied in the code.


(EHTISHAM ASGHAR) #11

Yes, you are right it I wanted to confirm it. But its not modeling problem properly.


(Mark L. Stone) #12

You should add the constraint S >= 0 , which you didn’t previously tell us about, although it is always satisfied anyhow using the W you have provided. If you make W large enough, you may need the constraint. I added the constraint S >= 0 to my above program for the runs below.

With your input data and W (no matter which random values are chosen), s = vector of ones is achieved; it is feasible, and must be optimal. This must look very unsatisfying to you. This situation will occur.
unless at least some elements of W exceed s_min.

If W is larger, such as W = 10*rand(jobs,1);, the optimal s will not be all ones. Here are the optimal s and S values for 2 random instantiations of W

1st instantiation of W

Optimal s

1.8424
1.8424
3.7174
3.7174
3.7174
3.7174
4.4002
4.4002
4.4002
4.4002
4.4002
4.4002
4.4002
4.4002
4.4002
4.4002

cvx_optval = +255.68

Optimal S for above s
1.8424 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
1.8424 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 3.7174 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.8744 2.8430 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.8744 2.8430 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.7899 2.1163 0.8113 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0000 0.0000 0.0000 4.4002 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0000 0.0000 0.0000 4.4002 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0000 0.0000 0.0000 0.2538 4.1464 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0000 0.0000 0.0000 0.2397 2.0397 0.0000 0.0000 0.0000 0.0000 2.1207 0.0000
0.0000 0.0000 0.0000 0.0000 0.0000 0.7519 2.8950 0.0000 0.0000 0.0000 0.7533 0.0000
0.0000 0.0000 0.0000 0.0000 0.0000 0.4639 0.8478 1.6899 0.0000 0.0000 0.4595 0.9390
0.0000 0.0000 0.0000 0.0000 0.0000 0.3553 0.5462 0.8038 1.2593 0.5026 0.3520 0.5809
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.5789 0.8737 1.4347 0.5297 0.3654 0.6177
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.9912 1.7738 0.5728 0.3857 0.6767
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.4584 0.6484 2.2933

+++++++++++++++++++++++++++++++++++++
2nd instantiation of W

Optimal s

4.0881
4.0881
4.3822
4.3822
4.3822
4.3822
4.3822
4.3822
5.0201
5.0201
5.0201
5.9043
5.9043
5.9043
5.9043
5.9043

cvx_optval = +398.557

Optimal S for above s
4.0881 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
4.0881 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 4.3822 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 1.4881 2.8941 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 1.4881 2.8941 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.3943 0.4529 3.5351 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0978 0.1010 0.1255 4.0579 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0978 0.1010 0.1255 4.0579 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0000 0.0000 0.0000 0.0000 5.0201 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0000 0.0000 0.0000 0.0000 0.1593 0.0000 0.0000 0.0000 0.0000 4.8608 0.0000
0.0000 0.0000 0.0000 0.0000 0.0000 0.1489 3.5073 0.0000 0.0000 0.0000 1.3639 0.0000
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 4.8373 0.0000 0.0000 0.0000 1.0670
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.5174 2.9194 0.7524 0.0000 0.7151
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.5176 2.9199 0.7520 0.0000 0.7148
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.5178 2.9202 0.7518 0.0000 0.7146
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 3.2453 0.0000 2.6590

Note that in these two runs, S has zeros in locations in accordance with the sentence after equation 1.8. However, with your original W = rand(jobs,1);, I got optimal solutions which did not have zeros as indicated in that statement. In that case, the vector of ones was achieved for s, producing the smallest possible objective value, without those locations being forced to zero. So that statement after equation 1.8 is not necessarily true, although I believe it is true that there exists an optimal solution which does have zeros in locations so indicated (the optimal solution is not necessarily unique). So if you want to guarantee having zeros in those locations, you need to either explicitly add constraints, or perhaps do something else. TO explicitly add the constraints, add S(setdiff(1:T,A(i):D(i)),i) == 0 to the for loop in the constraints section.


(EHTISHAM ASGHAR) #13

Sir Mark I am thankful to you for giving me your time, your description is very helpful to me, everything is clear to me you described above. Yes you are right optimal solution is not unique to meet that statement I think about.
Once again thanks a lot sir.


(Mark L. Stone) #14

You may have missed it. Just before you posted, I edited my post above to show how to add the extra zero constraints.


(EHTISHAM ASGHAR) #15

I have seen sir.:grinning:


(EHTISHAM ASGHAR) #16

I get your point thanks sir.