# Homogeneous non-negative least-squares

I would like to least-squares-"solve" a set of linear equations ($\underset{\mathbf{x}}{\mathrm{argmin}}\; \|\mathbf{Ax-b}\|_2$).

In my case, $\mathbf{b=0}$, e.g. the system is homogeneous. I also happen to know that all parameters must be positive, $\mathbf{x} \geq 0$. (The math works out because half of the coefficients are negative.)

• I am assuming that enforcing $\|\mathbf{x}\|_2=1$, e.g. constraining the solution to a hypersphere of constant radius, will take care of the homogeneneity (lest we simply get the trivial solution).

• I have found iterative methods (based on quadratic programming) to deal with the non-negativity constraint.

I have, however, not been able to find a way to combine the two constraints. When adding the fixed-norm constraint to the QP, the solver complains about non-convexity of the problem. Intuitively, I had assumed this was a convex problem. Am I wrong, and if yes, why? If not, how can I solve this problem in software?

• With the unit norm constraint, the problem is not convex because $(1,0,0,\ldots)$ and $(0,1,0,\ldots)$ are in the domain but the line segment joining them is not. – Rahul May 12 '14 at 2:36
• If you're willing to settle for enforcing $\|\mathbf x\|_1=1$ instead, then in conjunction with $\mathbf x\ge0$ this reduces to $\mathbf 1^T\mathbf x=1$ where $\mathbf 1$ is the vector of all ones, and you will obtain a quadratic programming problem that you can solve. – Rahul May 12 '14 at 2:43
• I see. Is there any downside to ditching the squares and going with a simple sum? – sebastian_k May 12 '14 at 2:46
• Yes: you will obtain a different answer with the one-norm than you would with the two-norm. But it is not clear to me that the answer you get from the two-norm is the only answer you want, anyway. – Rahul May 12 '14 at 2:49
• That isn't clear to me either. :) Is there any way to quantify the difference between the two? Are there other ways of "solving" homogeneous overconstrained systems? I appreciate your help! – sebastian_k May 12 '14 at 3:03

Following Rahuls comment, let us consider the convex optimization problem \begin{equation} \min_{\mathbf{x}} \|\mathbf{Ax}\|_2 ~~~\text{subject to } \mathbf{x} \geq 0, ~~\mathbf 1^T\mathbf x =\alpha. \end{equation} For some $\alpha^\star$, the solution $x^\star$ of the problem above will coincide with the solution of your original problem.
For any $\alpha_1 < \alpha^\star$, it follows $||x_1^\star|| < 1$. On the other hand, for $\alpha_2 > \alpha^\star$, it follows $||x_2^\star|| > 1$ (This is of course no rigorous proof). Therefore, one way to solve your optimization problem would be to search for the true $\alpha$ by solving the above stated problem combined with bi-section search:
Start with $\alpha_1=0$ and $\alpha_2$ great enough such that $||x_2||>1$.
Try $\alpha=(\alpha_1+\alpha_2)/2$. If the respective solution to the convex optimization problem has a norm greater than 1 set $\alpha_2:=\alpha$, otherwise $\alpha_1:=\alpha$. Then, repeat.