# Least squares solution of underdetermined system with constraints

With $$Ax=b$$, where $$A \in \mathbb{R}^{3 \times 8}, x \in \mathbb{R}^{8 \times 1}$$ I can find the least squares solution $$x$$ for a given $$b$$ such that I minimize $$\left\|x\right\|^2_2$$. The general least squares solution (According to my understanding) is given by $$A^+b$$ where $$A^+$$ is the Moore-Penrose pseudo inverse of $$A$$.

However I would like to find the least squares solution $$x$$ such that $$x \geq 0$$. And if it is possible, to find a general matrix $$A'$$ such that $$A'b = x \geq 0$$ ? Maybe the latter is impossible as the sign of $$A'b$$ depends on the sign of $$b$$ which in the problem I am considering is unconstrained.

## 1 Answer

If I understand correctly, the problem you're trying to solve is \begin{aligned} \min_{\mathbf{x}}\quad & \|A\mathbf{x}-\mathbf{b}\|^2 \\ s.t. \quad & x_i\geq 0 \end{aligned} This is known as Non negative least squares and can be solved using any convex optimization algorithm. In your case the problem is of small scale ($$n=8$$) so in general it's easy to solve. You can use a second order solver like quadprog or even a simple first order algorithm like Projected Gradient (with or without acceleration).

As for your last question, finding $$A\,:\, A^T\mathbf{b}=\mathbf{x}\geq\mathbf{0}$$, what is the reason for this requirement? I'm asking since it's different than the original question - where $$A, \mathbf{b}$$ are the given data (not a variables) and we look for $$\mathbf{x}$$ that best fits this data.

• I want to get a state space representation of a spacecraft thruster allocation algorithm. Here $b$ is the desired angular impulse and $x$ is the array of thruster firing times hence the constraint $x_i \ge0$. Sounds like the SS representation isn’t really possible with this constraint where only $b$ is a variable, right? Feb 9 at 16:46
• @ThomasKirven honestly I have no clue what you just said :) What are your variables? Can you formulate an explicit problem? Feb 10 at 9:43
• sorry! lol I am used to talking with ppl in aerospace and assume everyone knows what the thruster allocation problem is :). Basically you have (in this case) 8 thrusters arranged on a spacecraft that each produce a constant torque vector and force vector (thanks to newtons 3rd law) relative to the spacecraft frame of reference. Feb 11 at 23:56
• So the problem is how to optimally allocate thruster firing durations $x_i$ to impart the desired momentum $b$ to the whole spacecraft. The momentum achieved by a single thruster is it’s torque*firing duration. The columns of A describe the torque each thruster produces. Since $x_i$ is time it must be positive (you cant fire a thruster for -6 seconds :D) The only variable is $b$ (the desired momentum for the whole spacecraft). Feb 11 at 23:57
• I think I have answered the second question for myself that there is no constant $A’$ matrix that will always minimize firing times for any given $b$. But your answer to my first question was really helpful @iarbel84, thanks! Feb 11 at 23:58