Are there methods for inverting non-square matrices under constraints?

[Nikratio]

Hello,

I need to invert a non-square matrix A under the constraint that the absolute value of each component of the solution is less than some maximum. In other words, I want \vec{b} such that A . \vec b = \vec c and |b_i| < \alpha.

Are there any established methods for doing this?

My idea is to start with the pseudoinverse to compute the unconstrained solution, and to then add components \vec v_i from the null space of A to satisfy the constraint. If this doesn't help, I wanted to consecutively add more basis vectors from the singular value decomposition of A, starting with the basis corresponding to the smallest singular value.

However, I don't see how to pick the coefficients of the \vec v_i in such a way that the final solution is optimal in the sense that there is no other solution that satiesfies the constraints but has a smaller ||A.\vec b - \vec c||.

Anyone able to help? Pointers to appropriate literature would be appreciated as well, I am not quite sure what keywords I should be looking for.

 

[marcusl]

I see some confusion in your question, or at least nomenclature. You write b as a vector, in which case it certainly is not the pseudoinverse of A. It seems that you are asking for a constrained solution to a system of linear equations?

 

[Nikratio]

Yeah, you're right.

What I want is a constrained solution to the system of linear equations.

At the beginning I was thinking that maybe I can construct a matrix A^+ such that \vec b = A^+ . \vec c and \vec b satisfies the constraint. Construction of A^+ would then be a "constrained matrix inversion". But I no longer think that such a matrix can exist, so my problem is indeed to find a constrained solution to a system of linear equations.

 

[marcusl]

One possible approach is to couch it as a linear programming problem that can be solved by the simplex method. This method solves systems of linear equations subject to simple constraints.

In this case you would minimize Ix, where I is the identity matrix, subject to the constraint
Ax < b
where the vector b has components alpha. A web search should turn up dozens of sites on simplex method and linear programming, and it is also covered in texts on numerical analysis.

I expect there's also a variant available somewhere to deal with the absolute value I|x|, or some means to reset any value that goes negative.

 

[Nikratio]

Linear Programming was exactly the right keyword, thank you so much! I should be able to find my way from here on.