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

shami_cvx · November 2, 2017, 4:49am

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 · November 2, 2017, 6:39pm

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.

shami_cvx · November 3, 2017, 1:26am

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

shami_cvx · November 3, 2017, 12:30pm

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 · November 3, 2017, 1:06pm

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.

shami_cvx · November 3, 2017, 1:48pm

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 · November 3, 2017, 2:26pm

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.

shami_cvx · November 3, 2017, 3:15pm

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

shami_cvx · November 4, 2017, 8:08am

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 · November 4, 2017, 12:15pm

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.

shami_cvx · November 6, 2017, 1:19am

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

Mark_L_Stone · November 6, 2017, 1:48am

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

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

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.

shami_cvx · November 6, 2017, 3:14am

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 · November 6, 2017, 3:17am

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

shami_cvx · November 6, 2017, 3:33am

I have seen sir.

shami_cvx · November 6, 2017, 3:51am

I get your point thanks sir.