For linear equalities $Ax=b$, the solution can be written as $x=(A^TA)^{-1}A^Tb$.

For linear inequalities system $Ax\ge b$, on what condition the solution is $x\ge (A^TA)^{-1}A^Tb$?

========== (update)

My problem is exactly a optimize problem with the given objective function: $\min{||w||_2}$.

If the constraints is $Ax=b$, then the solution is $x=(A^TA)^{-1}A^Tb$, as @Rahul mentioned.

But when the constraints is $Ax\ge b$, I want to transform the problem to the following one:


$s.t. w\ge 0$

where $w=x-(A^TA)^{-1}A^Tb$.

The reason I have to rewrite the problem is that I want to use scipy's nnls as a solver, and it requires the constraints be something like $w \ge 0$.

I believe that if each element $a_{ij}$ of $A=(a_{ij})_{m\times n}$ is non-negative, the two problem is equivalent. But is there a weaker condition on which the two problem is equivalent?

  • 3
    $\begingroup$ I think you have a slight misconception. The solution of $Ax=b$ is $x=A^{-1}b$, assuming $A$ is invertible. If $A$ is not invertible, $x=(A^TA)^{-1}A^Tb$ gives a least-squares solution that does not necessarily satisfy $Ax=b$. As for the inequality case, the solution set is identical to $x\succeq A^{-1}b$ or $x\succeq (A^TA)^{-1}A^Tb$ when $A$ is diagonal and positive definite, but probably not otherwise. $\endgroup$
    – user856
    Jan 2, 2015 at 17:25
  • $\begingroup$ Systems of linear inequalities can be "solved" by matrix manipulations, so in some sense it is "like" the way we solve systems of linear equations. The usual phrase is "linear program" for a system of linear inequalities combined with a linear objective function (to minimize/maximize), but without an objective function we may ask if there are any points that satisfy the inequalities (so called feasible points). When there are feasible points, the region of solutions to the inequalities is convex. The bounded regions of this kind are polytopes. $\endgroup$
    – hardmath
    Jan 3, 2015 at 1:11
  • $\begingroup$ OK, your edit is helpful. Unfortunately, it remains the case that you cannot do the transformation you are hoping for. You could use a solver/modeling framework like CVXPY, however. $\endgroup$ Jan 3, 2015 at 17:22


You must log in to answer this question.

Browse other questions tagged .