0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rahul May 12 '14 at 2:36
  • $\begingroup$ 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. $\endgroup$ – Rahul May 12 '14 at 2:43
  • $\begingroup$ I see. Is there any downside to ditching the squares and going with a simple sum? $\endgroup$ – sebastian_k May 12 '14 at 2:46
  • $\begingroup$ 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. $\endgroup$ – Rahul May 12 '14 at 2:49
  • $\begingroup$ 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! $\endgroup$ – sebastian_k May 12 '14 at 3:03
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ That's an interesting approach, and I can picture why this is true, so I'll accept this. Is there a name for doing it like this, or some reference work where such tricks are listed? $\endgroup$ – sebastian_k May 12 '14 at 19:29
  • 1
    $\begingroup$ To my best knowledge, there is no special name for this technique but a quit similar strategy has been applied in "Quality of service and max-min fair transmit beamforming to multiple cochannel multicast groups" of Karipidis, Sidiropoulos. $\endgroup$ – The Pheromone Kid May 12 '14 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.