Write sum of multi-variable polynomial function with CVX

#1

I want to optimize a binary integer programing problem. There is a vector variable z and a matrix variable x. All I want to do is to find out the optimal solution of z and x to get the minimal objective.

There is each value for each combination of x and z. The following is a simple version of my problem. While when I write

w = [1,2,3,4,5,6,7,8,9];
cvx_begin
    variable z(2) binary
    variable x(2) binary
    
    expression f

    f = z(1)*z(2)*(x(1)*x(2)*w(1)) + z(1)*(1-z(2))*(x(1)*x(2)*w(2)+x(1)*(1-x(2))*w(3)) + ... 
    z(2)*(1-z(1))*(x(1)*x(2)*w(4)+x(2)*(1-x(1))*w(5)) + ...
    (1-z(1))*(1-z(2))*( x(1)*x(2)*w(6)+x(1)*(1-x(2))*w(7)+x(2)*(1-x(1))*w(8)+(1-x(1))*(1-x(2))*w(9));
    minimize(f);
cvx_end

Then, error emerges shown as

Error using  .*  (line 262)
Disciplined convex programming error:
Invalid quadratic form(s): not a square.

It seems that the multiplication of x and z doesn’t follow the DCP rule, while I cannot find any way to write this correctly. Does anyone have any ideas about this?

(Mark L. Stone) #2

You have not followed CVX’s rules in the formula for f, hence the error message… Is f convex? If so, it would require a reformulation to follow CVX’s rules.

In any event, the products of binary variables can be linearized via “MIP” formulation, and made consistent with CVX’s rules. as shown in section 2,8 of https://www.fico.com/en/resource-download-file/3217 . Doing this reformulation will allow the problem to be entered in CVX.