0
$\begingroup$

I am using cvx to solve linear programs with constraints of the form $Ax=b,x\ge0$. However the matrix $A$ is rank deficient and cvx returns a warning and finally displays status as 'Infeasible'. Rank deficient systems can have a solution and my guess is that my system does have a solution. Is there a way to make cvx solve this system without making the matrix full rank?

$\endgroup$
2
$\begingroup$

It's known that CVX itself, and to an extent the solvers it uses, have issues with rank deficiency in the equation matrix. (Hence the warnings.) But what is your aversion to doing some sort of LU factorization here? Also, have you tried all of the solvers, or just one?

Another approach is to solve a model that is guaranteed to be feasible. For instance:

cvx_begin
    variables x(n)
    minimize(norm(A*x-b))
    x >= 0
cvx_end

If your original problem is feasible, this should have an optimal value that is near zero (to within roundoff error). If it has a non-negligible, positive optimal value, then your original model was infeasible.

$\endgroup$
1
$\begingroup$

Depending on the particular $b$ vector that you have, it may be that the system of equations is infeasible or that there are solutions to $Ax=b$ but no solutions with $x \geq 0$. The solvers used with CVX are perfectly capable of detecting either type of LP infeasibility, so it's most likely the case that your guess is wrong and that the LP actually is infeasible.

Note that even if $A$ has full row rank and the system of equations $Ax=b$ is feasible, that doesn't mean that the LP including the constraints $x \geq 0$ must have a solution.

$\endgroup$
  • $\begingroup$ Is it possible that when the feasible region is very small (say only a point is feasible) then cvx can fail to detect it? $\endgroup$ – Pawan Aurora Jun 5 '14 at 4:03
  • $\begingroup$ CVX and its solvers use double precision floating point arithmetic, and round-off errors in this arithmetic can cause problems. If your system of equations and inequalities is very nearly infeasible in exact arithmetic, then round-off error could lead the solver to conclude that the LP is infeasible. $\endgroup$ – Brian Borchers Jun 5 '14 at 15:13
0
$\begingroup$

To expand on Brian's answer: You may think that if the matrix $A$ is rank deficient, then there needs to be a solution of $Ax=b$ with $x\ge 0$ because there is a whole subspace (actually an affine space) of solutions $x=x_0+y, y\in \text{ker}\;A$ that satisfy the equation and surely parts of this affine space must be non-negative in all components.

But that's not necessarily true. Imagine, for example $x_0=(0,-1)^T, \text{ker}\;A=\{y \in R^2: y=(y_1,0)^T\}$. For example, this would correspond to the linear system with $$ A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \qquad \qquad b = \begin{pmatrix} -1 \\ 0 \end{pmatrix}. $$ Even though $A$ is rank deficient, the linear system has no non-negative solutions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.