Optimizing a equation with basis functions


(Mewan Wijemanne) #1

Hello,

I have the following equations;

Y = -2077.77932456644 +16.7872794266809BF1 +33.2218328714858BF2 +8.52627498031323BF3 +19.0514813801442BF4 -17.7108695638677BF5 +8.03819569742098BF6 -28.8378291473933BF7 -19.4689953875162BF8 -17.7390853424783BF9 +71.6404109074202BF10 +11.8387402541357BF11 -8.36665433654147BF12 +10.680112178894BF13 +22.8456570257402BF14 -89.5565023342891*BF15

Given that;

BF1 = max(0, x5 -5)
BF2 = max(0,5 -x5)
BF3 = max(0, x1 -3)
BF4 = max(0, x8 -3)
BF5 = max(0,7 -x10)
BF6 = max(0, x11 -2)
BF7 = max(0,2 -x11)
BF8 = max(0,7 -x6)
BF9 = max(0,7 -x2)
BF10 = max(0,3 -x3)
BF11 = max(0, x4 -3)
BF12 = max(0,6 -x9)
BF13 = max(0, x7 -2)
BF14 = max(0,2 -x7)
BF15 = max(0,1 -x1)

I entered this in to Matlab using the following code;

cvx_begin
cvx_solver gurobi
variable x1 integer;
variable x2 integer;
variable x3 integer;
variable x4 integer;
variable x5 integer;
variable x6 integer;
variable x7 integer;
variable x8 integer;
variable x9 integer;
variable x10 integer;
variable x11 integer;
variable BF1 integer;
variable BF2 integer;
variable BF3 integer;
variable BF4 integer;
variable BF5 integer;
variable BF6 integer;
variable BF7 integer;
variable BF8 integer;
variable BF9 integer;
variable BF10 integer;
variable BF11 integer;
variable BF12 integer;
variable BF13 integer;
variable BF14 integer;
variable BF15 integer;
BF1==max(0,x5-5);
BF2==max(0,5-x5);
BF3==max(0, x1 -3);
BF4==max(0, x8 -3);
BF5==max(0,7 -x10);
BF6==max(0, x11 -2);
BF7==max(0,2 -x11);
BF8==max(0,7 -x6);
BF9==max(0,7 -x2);
BF10==max(0,3 -x3);
BF11==max(0, x4 -3);
BF12==max(0,6 -x9);
BF13==max(0, x7 -2);
BF14==max(0,2 -x7);
BF15==max(0,1 -x1);
minimize (-2077.77932456644 +16.7872794266809BF1 +33.2218328714858BF2 +8.52627498031323BF3 +19.0514813801442BF4 -17.7108695638677BF5 +8.03819569742098BF6 -28.8378291473933BF7 -19.4689953875162BF8 -17.7390853424783BF9 +71.6404109074202BF10 +11.8387402541357BF11 -8.36665433654147BF12 +10.680112178894BF13 +22.8456570257402BF14 -89.5565023342891*BF15);
cvx_end

However it gave me the error saying;

"Error using cvxprob/newcnstr (line 192)
Disciplined convex programming error:
Invalid constraint: {real affine} == {convex}

Error in == (line 12)
b = newcnstr( evalin( ‘caller’, ‘cvx_problem’, ‘[]’ ), x, y, ‘==’ );

Error in TestOb (line 42)
BF1==max(0,x5-5);"

My objective is to minimize the equation to get the best possible x’s. I have all the cvx solvers. Any help would be appreciated. Thank you in advance!


(Mewan Wijemanne) #2

I updated the code as followed;

clc;
clear all;
%x1=0;
%x2=0;
%x3=5;
%x4=0;
%x5=4;
%x6=0;
%x7=3;
%x8=0;
%x9=1;
%x10=0;
%x11=0;
cvx_begin
cvx_solver gurobi
variable x1 integer;
variable x2 integer;
variable x3 integer;
variable x4 integer;
variable x5 integer;
variable x6 integer;
variable x7 integer;
variable x8 integer;
variable x9 integer;
variable x10 integer;
variable x11 integer;
variable BF1 integer;
variable BF2 integer;
variable BF3 integer;
variable BF4 integer;
variable BF5 integer;
variable BF6 integer;
variable BF7 integer;
variable BF8 integer;
variable BF9 integer;
variable BF10 integer;
variable BF11 integer;
variable BF12 integer;
variable BF13 integer;
variable BF14 integer;
variable BF15 integer;
x1>=0;
x1<=10;
x2>=0;
x2<=10;
x3>=0;
x3<=10;
x4>=0;
x4<=10;
x5>=0;
x5<=10;
x6>=0;
x6<=10;
x7>=0;
x7<=10;
x8>=0;
x8<=10;
x9>=0;
x9<=10;
x10>=0;
x10<=10;
x11>=0;
x11<=10;
BF1>=max(0,x5-5);
BF2>=max(0,5-x5);
BF3>=max(0,x1-3);
BF4>=max(0,x8-3);
BF5>=max(0,7-x10);
BF6>=max(0,x11-2);
BF7>=max(0,2-x11);
BF8>=max(0,7-x6);
BF9>=max(0,7-x2);
BF10>=max(0,3-x3);
BF11>=max(0,x4-3);
BF12>=max(0,6-x9);
BF13>=max(0,x7-2);
BF14>=max(0,2-x7);
BF15>=max(0,1 -x1);

minimize (-2077.77932456644 +16.7872794266809*BF1 +33.2218328714858*BF2 +8.52627498031323*BF3 +19.0514813801442*BF4 -17.7108695638677*BF5 +8.03819569742098*BF6 -28.8378291473933*BF7 -19.4689953875162*BF8 -17.7390853424783*BF9 +71.6404109074202*BF10 +11.8387402541357*BF11 -8.36665433654147*BF12 +10.680112178894*BF13 +22.8456570257402*BF14 -89.5565023342891*BF15);

cvx_end

Now it says no optimal solutions. Where as I know there exists one because I got it using a different software.


(Mark L. Stone) #3

I don’t know what problem you’re trying to solve or what problem you solved in the different software.

The problem in your original question is non-convex. CVX complains about the equality constraints, but that is easily remedied by using assignment, e.g., BF1 = max(0, x5 -5) rather than nonlinear equality constraint BF1 == max(0, x5 -5), and similarly for the others (and then there is no need to declare the BFi 's). However, the problem is non-convex because of the terms in the objective function which have negative coefficients. If all the terms in the objective function had non-negative coefficients, the problem would be accepted by CVX.

Now I will address the CVX problem provided in your 2nd post. Your 2nd formulation is solving a different problem (which is convex, other than the integer variables, which are MIDCP compliant) than what you provided in the first formulation (which is not convex). That 2nd formulation s correctly reported as being unbounded. Note that the only constraints on the BFi variables are that they are >= something. All of the “somethings” are indeed bounded. But that means there is no upper limit on the BFi variables. So the terms in the objective function which have a negative coefficient can be driven to negative value of unlimited magnitude by making the corresponding BFi large enough. Therefore the problem is unbounded.

By the way, I believe your original formulation, which is non-convex, is bounded, because all of the xi’s are bounded, and the BFI’s are equality constrained to (non-blowing up) functions of bounded variables. So perhaps you solved that non-convex formulation in the different software?

I think if you put the effort in, which leave to you, you can implement your first formulation (non-convex) as an MIDCP compliant program which CVX will accept, but you will have to introduce additional binary variables to handle the max terms (a Big M type approach) which have negative coefficients in the objective function.


(Mewan Wijemanne) #4

I understand what you mean. Thank you very much for your reply!