Yet in my solver I want to add constraint that all elements of x must have the same sign.
Simple trick to do so is introduce a binary variable y and a constraint \forall i \; l \left( 1 - y \right) \leq {x}_{i} \leq y u where l and u are the lower and upper boundaries of the value.
Now, let’s say in practice I don’t want to have any boundaries? Than one can set u and l to have large values.
This is where the problem arise, for very very large values (Let’s say 1e12) MOSEK fails and returns the problem is infeasible while Gurobi just ignores the constraint and returns an answer with mixed signs.
Of course this is absurd case, but just wanted to know if it is a problem in the formulation of CVX or a bug in the solvers.
I know MOSEK people are hanging here so I thought it would be interesting for them.
My code:
clear('all');
% Parameters
solverString = 'CVX';
numRows = 8;
numCols = 6; %<! Half Positive, Half Negative
boundRadius = 1e12; %<! Set lower than 1e10 and it works
lowerBound = -boundRadius;
upperBound = boundRadius;
cvx_solver('Mosek');
% cvx_solver('Gurobi');
% Data (Model
mA = randn(numRows, numCols);
vXRef = randn(numCols, 1);
vXRef(1:floor(numCols / 2)) = abs(vXRef(1:floor(numCols / 2)));
vXRef(ceil(numCols / 2):numCols) = -abs(vXRef(ceil(numCols / 2):numCols));
vB = mA * vXRef;
hObjFun = @(vX) sum(((mA * vX) - vB) .^ 2);
% Solution
cvx_begin()
% cvx_precision('best');
variable vX(numCols, 1);
variable varY(1) binary;
minimize( norm(mA * vX - vB, 2) );
subject to
vX >= (1 - varY) * lowerBound;
vX <= varY * upperBound;
cvx_end
disp([' ']);
disp([solverString, ' Solution Summary']);
disp(['The ', solverString, ' Solver Status - ', cvx_status]);
disp(['The Optimal Value Is Given By - ', num2str(hObjFun(vX))]);
disp(['The Optimal Argument Is Given By - [ ', num2str(vX.'), ' ]']);
disp([' ']);
Didn’t you notice Mosek bitching like crazy about the large values of -1e12 and 1e12? Your first program above has the quiet option, which precludes the solver output, including warnings; although your second program should have shown you the Mosek warnings.
What you saw is not a “bug” in CVX or the solvers, but is a limitation or reality of double precision floating point optimizers.
If you really can;t impose “reasonable” bounds on the variables, one alternative for your problem is to separately solve two problems, one for each sign of x.
Mosek might still get the correct answer for some fairly large values. But for this problem, 1e12 is a little beyond its capability, and well beyond where it first starts warning you.
As far as Gurobi “ignoring” the constraints, that can be due to something called “trickle flow” (https://www.ibm.com/support/pages/why-does-binary-or-integer-variable-take-noninteger-value-solution), in which the integrality tolerance is not tight enough to ensure the intended constraint logic works as intended (i.e., the binary variable is noi exactly 0 or 1, and that difference, multiplied by a large magnitude number, is enough to trickle through. Your Big M is too big, and is too big relative to the integrality tolerance.
Of course I noticed.
Of course in real world I solved it by executing Non Negative Least Squares twice (See https://dsp.stackexchange.com/questions/52099 which I wrote the answer to long before this thread).
I just mentioned non optimal behavior. Gurobi is doing something unaccpetable (Marking infeasible solution as a solution).
Yet in my opinion, MOSEK should handle this better as well.
Big-M of order M=10^{12} is a no-go. One reason, like in this case, is that the formulation introduces auxiliary variables which will also take values also around M. A problem with only humongous solutions is hard to distinguish from infeasible. Another reason was given by @Mark_L_Stone, huge M eats up your integrality tolerance. And finally even for continuous problems you end up with huge numbers in strange places, like in the objective, assuming CVX dualized, which it most often does.
Just like the case with best accuracy, I totally understand the problem.
I don’t need 1e20 in practice, I was just surprised it caused failing.
My approach to things is prevent edge cases. For instance, it is better the program won’t run and give back answer the input is invalid than return answer the problem is infeasible.
Again, those are edge cases. In my opinion the answer to them isn’t technical explanation why the result is as it is (I figured out by my self before posting why) bu consistent message to the user - What’s defined isn’t good, refine it. As in this case it is easy for any knowledgeable user what is wrong. But what for cases it is more tricky?
At least this is the reasonable approach I’d take.
MOSEK warning 62: The A matrix contains a large value of -1.0e+12 in constraint ‘’ (8) at variable ‘’ (6).
MOSEK warning 62: The A matrix contains a large value of -1.0e+12 in constraint ‘’ (9) at variable ‘’ (6).
MOSEK warning 62: The A matrix contains a large value of -1.0e+12 in constraint ‘’ (10) at variable ‘’ (6).
MOSEK warning 62: The A matrix contains a large value of -1.0e+12 in constraint ‘’ (11) at variable ‘’ (6).
MOSEK warning 62: The A matrix contains a large value of -1.0e+12 in constraint ‘’ (12) at variable ‘’ (6).
MOSEK warning 62: The A matrix contains a large value of -1.0e+12 in constraint ‘’ (13) at variable ‘’ (6).
MOSEK warning 62: The A matrix contains a large value of 1.0e+12 in constraint ‘’ (14) at variable ‘’ (6).
MOSEK warning 62: The A matrix contains a large value of 1.0e+12 in constraint ‘’ (15) at variable ‘’ (6).
MOSEK warning 62: The A matrix contains a large value of 1.0e+12 in constraint ‘’ (16) at variable ‘’ (6).
MOSEK warning 62: The A matrix contains a large value of 1.0e+12 in constraint ‘’ (17) at variable ‘’ (6).
Warning number 62 is disabled.
MOSEK warning 52: A numerically large lower bound value -1.0e+12 is specified for constraint ‘’ (8).
MOSEK warning 53: A numerically large upper bound value -1.0e+12 is specified for constraint ‘’ (8).
MOSEK warning 52: A numerically large lower bound value -1.0e+12 is specified for constraint ‘’ (9).
MOSEK warning 53: A numerically large upper bound value -1.0e+12 is specified for constraint ‘’ (9).
MOSEK warning 52: A numerically large lower bound value -1.0e+12 is specified for constraint ‘’ (10).
MOSEK warning 53: A numerically large upper bound value -1.0e+12 is specified for constraint ‘’ (10).
MOSEK warning 52: A numerically large lower bound value -1.0e+12 is specified for constraint ‘’ (11).
MOSEK warning 53: A numerically large upper bound value -1.0e+12 is specified for constraint ‘’ (11).
MOSEK warning 52: A numerically large lower bound value -1.0e+12 is specified for constraint ‘’ (12).
MOSEK warning 53: A numerically large upper bound value -1.0e+12 is specified for constraint ‘’ (12).
MOSEK warning 52: A numerically large lower bound value -1.0e+12 is specified for constraint ‘’ (13).
MOSEK warning 53: A numerically large upper bound value -1.0e+12 is specified for constraint ‘’ (13).
But at the end is says problem infeasible.
So the user doesn’t know if it is because of the warning or the problem is really infeasible.
Moreover, Just as the logic I presented in the other case. If it works for boundary of 1e3 and find an answer which isn’t on the boundary of the set, I also expect it to do so on larger boundary.
This is consistency and it is important when dealing with user.
You may disagree, but I expect either to say the problem can not be solved due to the extreme constraints (Maybe the advanced user will have force option) or it should be consistent.