about nonlinear constraint and globle optimal solution

[katherine X]

Hello!Johan.

I have a nonlinear constraint like this:

z+(1/b)(1/N)sum (max[f_j,0]) _j=1-N <=0,

f_j = A-sum (u_iv_i,j(x_i+y_i)) _i=1-n,

where u x y are control variables, u=0 or 1, x and y are continuous. Z b A n are real values. N is sampling time. v_i,j is also a 0 or 1 variable which can be obtained by N-time sampling.

obviously the f_j function isn’t linear:ux+uy. the solve yalmip select is FMINCON. and the result isn't a globle optimal one.

i would like to ask that if there is any method that i can transform the constraint into linear that feasible in cplex?

if not, how can i get a globle optimal solution? 

thanks a lot!

here is the code.if helpful

Pmax=[455 455 130 130 162 80 85 55 55 55]; %
Pmin=[150 150 20 20 25 20 25 10 10 10];%

MTTF=[1100 1100 960 960 950 1960 1200 1980 1980 1980];
c=[1000 970 700 680 450 370 480 660 665 670];
b=[16.19 17.26 16.6 16.5 19.7 22.26 27.74 25.92 27.27 27.79];
a=[.00048 .00031 .002 .00211 .00398 .00712 .0079 .00413 .00222 .00173];
Pd=800;

Blo_max=0.1;
N=1000;
q=b*.1;
dt=24;

n=length(a);
ORR=ones(1,n)-exp(-dt./MTTF);

P=sdpvar(1,n);
R=sdpvar(1,n);
u=binvar(1,n);
z0=sdpvar(1,1);
R_tot=sdpvar(1,1);
 
constraints=[R>=0,Pmin<=P<=Pmax,R<=Pmax-P,sum(P)==Pd,sum(R)==R_tot];
for i=1:N
    v(i,:)=rand(1,n)>ORR;
end
z=max((Pd-sum(u.*v(1,:).*(P+R))-z0),0);
for i=2:N
    z=z+max((Pd-sum(u.*v(i,:).*(P+R))-z0),0);
end
constraints=[constraints,(z/N/Blo_max+z0)<=0];   
Cost=sum(a.*P.*P+b.*P+c+q.*R);
objective=Cost;
sol = solvesdp(constraints,objective)
    if sol.problem == 0
     u = double(u)
     P = double(P)
     R = double(R)
     cost=double(Cost)
     z0=double(z0)
    else
     display('Hmm, something went wrong!');
    end   

[Johan Löfberg]

Yes, it is trivially linearizable as it only involves product between binaries and continuous

if u == 0 then u*(P+R) = P+R

if u == 1 then u*(P+R) = 0

Hence, introduce a new variable to represent the product and use implies

product = sdpvar(1,10);

for i = 1:10

constraints = [constraints, implies(u(i), product(i) == P(i)+R(i))];

constraints = [constraints, implies(1-u(i), product(i) == 0)];

end

constraints = [constraints,R <= Pmax, 0 <= product <= 2*Pmax];

z=max((Pd-sum(product.*v(1,:))-z0),0);

for i=2:N

    z=z+max((Pd-sum(product.*v(i,:))-z0),0);

end

Note, implies is based on big-M, hence it needs explicit bounds on all involved variables, thus the trivially derived introduced bounds on the product variable and R

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Big-MAndConvexHulls

Problem is solved in root-node using gurobi, hence very simple.

[Johan Löfberg]

BTW, the implies operator should work vectorized, but there is a small bug. As long as you make sure the arguments are column vectors it works though

constraints = [constraints, implies(u(:),  product(:) == P(:)+R(:))];

constraints = [constraints, implies(1-u(:),  product(:) == 0)];

Fixed in next version.

[katherine X]

i can understand your explaination and tried the "implies" method.

whatever Pd's value is, the binary variable u always get 1. that is not right.

did you get the same results?

[Johan Löfberg]

And why is it not correct? IF it is not correct, then you must be missing some constraint in your model

[katherine X]

or change the Blo_max value. there should be changes in u. but i always get 1.

why?

[Johan Löfberg]

You haven't made any convincing argument *why* u=1 not could be optimal.

Here is a simple test to see what happens with the objective when you have zeros in the solution. 

for i = 1:10,
 sol = solvesdp([sum(u)<=i,constraints],objective,sdpsettings('verbose',0));
 if sol.problem == 0
   double(objective);
 end
end

ans =

   2.1327e+04

ans =

   2.1283e+04

ans =

   2.1237e+04

ans =

   2.1192e+04

ans =

   2.1149e+04

ans =

   2.1128e+04

ans =

   2.1106e+04

ans =

   2.1085e+04

The more ones, the better objective

[katherine X]

yes,you are right.

let me check the code carefully.

 

[katherine X]

and thanks!