Hi, I want to formulate a minimization problem in CVX.
The objective function is sum((cumsum(reshape(sum(reshape(A.*X,6,3),2),3,2)).*Y)(:)), where Y=reshape(sum(reshape(X,6,3),2),3,2) is a 3-2 binary, A is a 3-2-3 double and X is a 3-2-3 nonnegative.
Disciplined convex programming error: Invalid quadratic form(s): not a square.
I can not use *, find(), unique(), isnan() and other functions due to B is binary. I have already tried my best for it. Could you please help me?
You have products of binary and continuous variables. You need to linearize them by introducing additional binary variables. See section 2.8 of https://www.fico.com/en/resource-download-file/3217 .
it might be easier if you start with a simpler formula and get that correct. then proceed to the formula you really want.
I don’t think cumsum will cause any extra difficulty, as all your terms, after linearization, will be affine.
help cvx\cumsum
Disciplined convex/geometric programming information for SUM:
cumsum(X) and cumsum(X,DIM) are vectorized forms of addition. So
when cumsum is used in a DCP or DGP, elements in each subvector
must satisfy the corresponding combination rules for addition (see
PLUS). For example, suppose that X looks like this:
X = [ convex concave affine ;
affine concave concave ]
Then cumsum(X,1) would be permittted, but cumsum(X,2) would not,
because the top row contains the sum of convex and concave terms, in
violation of the DCP ruleset. For DGPs, addition rules dictate that
the elements of X must be log-convex or log-affine.
clear;clc
A = ones(3,2,3);
L = ones(3,2);
U = ones(3,2) * 4;
cvx_begin quiet
cvx_solver gurobi
variable X(3,2,3) nonnegative
variable Z(3,2) nonnegative
Y = sum(X,3);
B = cumsum(sum(A .* X,3)).^2;
minimize sum(sum(Z))
subject to
sum(sum(X,2)) == 1;
Y <= 1;
X(:,:,1) == [0 1;0 0;0 0];
X(:,:,2) == [1 0;0 0;0 0];
X(:,:,3) == [0 0;1 0;0 0];
L .* Y <= Z <= U .* Y;
L .* (ones(3,2)-Y) <= B - Z <= U .* (ones(3,2)-Y);
cvx_end
Thanks for your answer.
I have tried this method following your advice to linearize variables, but I still have some problems that is my objective function and Y are both from binary X. For (objective function) .* (Y), I have to turn 3-2-3 double to 3-2 double with sum() and reshape(). I think this is why it do not work.
Could you please help me again? Thanks!
错误使用 cvxprob/newcnstr (line 192)
Disciplined convex programming error:
Invalid constraint: {real affine} <= {convex}
出错 <= (line 21)
b = newcnstr( evalin( ‘caller’, ‘cvx_problem’, ‘[]’ ), x, y, ‘<=’ );
You haven’t followed the instructions at all. You need to declare and use new binary variables and add constraints. Your new formulation will not have any products of variables. You are distracting yourself with cumsum and reshape. Figure out how to make the modifications for the elments inside them. Then applying cumsum and reshape should not cause any extra difficulty.
Thanks for your answer.
I have eliminated reshape and used cumsum only once to simplify the problem. Then I have added new cintinuous variable B and binary variable Y to linearized Z=B*Y as shown in the code：
clear;clc
A = ones(3,2,3);
L = ones(3,2);
U = ones(3,2) * 4;
cvx_begin quiet
cvx_solver gurobi
variable X(3,2,3) binary
variable Y(3,2) binary
variable B(3,2) nonnegative
variable Z(3,2) nonnegative
minimize sum(sum(Z))
subject to
sum(sum(X,2)) == 1;
Y == sum(X,3);
B == cumsum(sum(A.X,3)).^2;
L . Y <= Z <= U .* Y;
L .* (ones(3,2)-Y) <= B - Z <= U .* (ones(3,2)-Y);
cvx_end
But the question remain：b = newcnstr( evalin( ‘caller’, ‘cvx_problem’, ‘[]’ ), x, y, ‘==’ );
If % B == cumsum(sum(A. *X,3)).^2, then it won’t report mistakes, but the problem has not been sloved.
I am sorry to bother you with this question and looking forward to your suggestions.
Why are you squaring X? That results in affine <= convex, which is a non-convex constraint, and is disallowed by CVX.
The link does not tell you to square anything. You should only end up with affine (linear) expressions and constraints.
I have found that squaring lends to nonlinearity, but that is exactly what I need to get.
At present, I have two feasible results using cumsum from A=ones(3,2,3) under condision X(1,2,1)=0, X(1,1,2)=0, X(2,1,3)=0 and Y=[1 1; 1 0; 0 0]. One is Z=[1 1;4 1;1 1] after squaring, but it can not .* Y and not continue to linearize. The other is Z=[1 1;2 0;0 0] after linearizing [1 1;2 1;2 1] .* Y, but it can not .^2.
Both results are only one step away. Could you please advise me what I should do for the last step? Thank you very mach!
Your original problem involves a product of continuous and binary variables. That can be linearized (no squaring) by following the directions in the link. If you are trying to solve some other problem, you need to show us what that is.
Yes, my original problem involves a product of continuous and binary variables. It has been linearized to a new problem. I have simplified the code to:
clear;clc;
A = ones(3,2,3);
L = ones(3,2);
U = ones(3,2) * 4;
cvx_begin quiet
cvx_solver gurobi
variable X(3,2,3) binary
variable Y(3,2) binary
variable B(3,2) nonnegative
variable Z(3,2) nonnegative
minimize sum(sum(Z))
subject to
sum(sum(X,2)) == 1;
Y == sum(X,3);
B == cumsum(sum(A .* X ,3)).^2;
L . Y <= Z <= U .* Y;
L .* (ones(3,2)-Y) <= B - Z <= U .* (ones(3,2)-Y);
cvx_end
This will not work. Turning B == cumsum(sum(A.*X,3)).^2; to B == cumsum(sum(A.*X,3))； the code is feasible but do not achieve goal. Please tell me how can I modify it to minimize sum(sum(Z)) under condition B == cumsum(sum(A.*X,3)).^2;
Please write out what the CVX code would be (even though CVX will not accept it) if you had the product of continuous and binary variable, i.e., do not attempt linearization That way I can see what problem you want to solve is . As it is now, I am not sure what problem you are trying to solve.
Thanks for your answer.
This is my code that I want to solve it. I have removed the linearization process and simplified it. CVX do not accept it, but turning minimize sum(sum(Z.*Y)) to minimize sum(sum(Z)) is feasible. However, my goal is minimizing sum(sum(Z.*Y)).
clear;clc;
A = ones(3,2,3);
cvx_begin quiet
cvx_solver gurobi
variable X(3,2,3) nonnegative
variable Y(3,2) binary
Z = cumsum(sum(A .* X,3)).^2;
minimize sum(sum(Z.*Y))
subject to
sum(sum(X,2)) == 1;
Y == sum(X,3);
Y == sum(X,3);
Y( 2:end , : ) - Y( 1:end-1 , : ) <= 0;
cvx_end
Now I see clearly what was not evident in your first post.
I don’t believe your problem can be expressed as an MIDCP, and therefore can not be handled by CVX. That is because it has a product of a square of a continuous variable with a binary, rather than the product of a continuous variable with a binary. I’m happy for someone to prove me wrong, however.
OK. thank you for all your help!