Constraint violated in linear programming

1

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?

2

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.

3

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
4

Thank you for your responses!

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
5

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.

6

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