Constraint violated in linear programming

Hi all,
I recently started using cvx, so I’m a beginner. I’m getting a constraint violated with the following feasibility problem:

``````clear all;
close all;
clc;

%% Prepare problem parameters

H = [
2 1 2;
1 2 1;
2 1 2;
];
c = [0; -2; 2];
n = length(c);
A = [eye(n); -1 * eye(n)];
b = -1 * ones(2*n, 1);

%% Verify if a point is optimal by using KKT conditions
% x* is optimal <=> there exists lambda satisfying the KKT conditions

x_star = [0; 1; -1];

cvx_begin
variable lambda(2*n);
minimize(0);
subject to
A * x_star - b >= 0;                % (i)
H * x_star + c - A'*lambda == 0;    % (ii)
lambda >= 0;                        % (iii)
lambda .* (A*x_star - b) == 0;      % (iv)
cvx_end

lambda .* (A*x_star - b)
assert(all(lambda .* (A*x_star - b) == 0));
``````

What am I doing wrong?

Solvers only satisfy constraints to within a feasibility tolerance, typically 1e-8 or maybe 1e-6. Testing equality constraints to be satisfied "exact;ly (to all double precision bits) is not a proper way of testing whether the solver has performed properly.

Moreover, you cannot even compute an inner product exactly on a computer using floating numbers. So it is actually weird to expect the solution should satisfy the constraints exactly.

Numerical analysis is an unappreciated topic.

1 Like

I understand that it is related to numerical computation, and indeed modifying it to:

``````cvx_begin
variable lambda(2*n);
minimize(0);
subject to
A * x_star - b >= 0;                % (i)
H * x_star + c - A' * lambda == 0;    % (ii)
lambda >= 0;                        % (iii)
lambda .* (A*x_star - b) <= eps;      % (iv)
cvx_end
``````

correctly yields:

``````Status: Infeasible
``````

However, now I’m trying to understand when the `==` works and when it does not. For example, why is it ok to use it in this example from the documetation?

``````cvx_begin
variable x(n);
minimize( norm(A*x-b) );
subject to
C*x == d;
norm(x,Inf) <= 1;
cvx_end
``````

Declare `slack` a variables, change the objective to `minimize(slack)` and change the RHS of last inequality to `slack` Is that feasible? What is the optimal value of `slack`? If it is larger than `eps`, that explains your infeasibility.

The original problem is obviously infeasible, Mosek will tell you that immediately. The reason you are getting a wrong answer form the default SCS is because it struggles, as you can see from the log (it gives up at 1st iteration and returns what it has) so its answer is simply wrong.

1 Like