Constrained Matrix Inversion

Main Question or Discussion Point

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.

Related Linear and Abstract Algebra News on Phys.org
marcusl
Gold Member
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?

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
Gold Member
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.

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