1

First time poster...apologies for formatting.

I am trying to devise a solution to a familiar linear algebra equation, Ax=b, where all elements in A are non-negative and all the elements in b are positive. My constraint is that the difference between the L1 norm of Ax and L1 norm of b must be minimized (ie min (||Ax||_1 - ||b||_1)). In english, I want the coefficients that make the sum of the elements in b "closest" to the sum of the elements in Ax.

Hoping to find out whether there is an algorithmic solution to this problem, preferably in Python.

Jason
  • 11
  • 2
    Are you sure that is the objective? If it is, an optimal solution is $x=0$. If you meant to minimize $\left||Ax|_1 - |b|_1\right|$, just take any $y$ with $Ay \ne 0$ and let $x = \dfrac{|b|_1}{|Ay|_1 }y$ to make the objective value $0$. Or did you mean to minimize $|Ax - b |_1$? – Robert Israel Apr 18 '19 at 21:16
  • Thanks @RobertIsrael. I do want \begin{equation} |||Ax||_1 - ||b||_1|_1 \end{equation}. (the other would be l1 regression). The solution you proposed gives x as a scalar, correct? x is a vector, though. Rusty in my linear algebra, been quite a few years. Much appreciate the help – Jason Apr 18 '19 at 21:25
  • For more context...Suppose I'm in retail and I sell a number of SKUs that are oftentimes sold together. Each x is the cost of an individual SKU, but is unknown because of said bundling. The costs are a function of what's in A (which has M buyers of N SKUs), and b is the total dollars for each of my buyers. I want to find the average cost for each SKU. – Jason Apr 18 '19 at 21:33
  • 2
    No, $x$ is a vector, as is $y$. $y$ is any vector such that $Ay \ne 0$. Then you scale $y$, i.e. multiply it by a scalar, chosen to make $|Ax|_1$ equal to $|b|_1$. – Robert Israel Apr 18 '19 at 22:02
  • I don't understand the question. Perhaps what you mean is that for given $A$ and $b$, you want to find some $x$, such that $|Ax-b|_1$ becomes minimal? – Jan-Christoph Schlage-Puchta Apr 19 '19 at 09:28
  • @RobertIsrael provided the correct answer. And there is no unique solution to the problem as stated. Will need to reformulate more carefully based on the use case: Suppose I'm in retail and I sell a number of SKUs that are oftentimes sold together. Each x is the cost of an individual SKU, but is unknown because of said bundling. The costs are a function of what's in A (which has M buyers of N SKUs), and b is the total dollars for each of my buyers. I want to find the average cost for each SKU. – Jason Apr 19 '19 at 14:14

0 Answers0