about linearization of nonlinear objective function

[覃岭]

I meet a nonlinear term in objective as following:

min x*y,

s.t.

  -1<=x<=1

  y>=0

  ....(other constraints) 

and I linearize it as following formulation：

min z

-y<=z<=y

-M*u<=z<=M*u

0<=u<=1

-u<=x<=u

where M is a positive real number large enough

could you give me some suggestion about this transformation?

thanks!

[Johan Löfberg]

Are both continuous, or which one is integer?

[覃岭]

both continuous

[Johan Löfberg]

You cannot create a MILP-representation of a product of continuous variables. I have no idea what your "linearization" models 

[覃岭]

I see.

so some other method should be considered such as outer approximation for the model with the product of continuous variables.

[Johan Löfberg]

Yes, or a PWA approximation of the product.

Here is a simple ay to approximate x*y. first use x*y = .25((x+y)^2-(x-y)^2), and then pwa of the univariates

sdpvar x y xplusysquared xminusysquared
N = 25;
d1 = binvar(N,1);
d2 = binvar(N,1);
range = linspace(-10,10,N)';
fval = range.^2;
xtimesy = .25*(xplusysquared-xminusysquared);
Model = [x+y == d1'*range,x-y == d2'*range, xplusysquared==d1'*fval, xminusysquared==d2'*fval,
         sum(d1)==1,sum(d2)==1];
 


or use sos2
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.SOS2

[覃岭]

thanks, I tried both methods and both are effective!

Piece wise approximation is more easy to code.