4
$\begingroup$

I am looking for an explicit description and discussion of the dual of the $\ell^1$-norm minimization problem $\lVert A x\rVert_1\to\min$, where $A$ is a matrix, and $x$ belongs to the $n$-simplex $\sum_{i=0}^n x_i =1, x_i\ge 0$.

EDIT Apparently those who voted for closing this question had hard time recognizing the "reference request" tag. I do know how to reformulate this as a linear programming problem and how to construct the dual problem. The question is about references to works where this was done in the particular situation described in the question.

$\endgroup$
6
  • $\begingroup$ I don't get the question. There are several possibilities to for a dual problem. One would be to add a constraint $Ax=y$, do the usual split into positive and negative part of $y$ and you have a linear problem. Apply linear duality. Another possibility is to apply Fenchel-Rockafellar duality. And what do you mean by "discussion" of the dual problem? $\endgroup$
    – Dirk
    Dec 23, 2017 at 22:37
  • 3
    $\begingroup$ If I am not mistaken it can be reformulated ad a linear program, and thus you can apply usual duality to that. $\endgroup$ Dec 23, 2017 at 22:45
  • 2
    $\begingroup$ Yes - I am aware of the general theory, and how this problem can be reduced to a linear programming one - which is why I put "linear programming" tag. However, I am pretty sure this particular situation must have been treated somewhere in the literature, so that - instead of reinventing the wheel - I was looking for appropriate references, and was not able to find any myself. I also invite those who put this question on hold to do that or to explain their reasons for thinking that this question does not qualify to be a "research" one. $\endgroup$
    – R W
    Dec 24, 2017 at 18:27
  • 1
    $\begingroup$ @Suvrit I am not asking for a general reference on duality in linear programming. I want to know whether the dual problem for the $\ell^1$-norm minimization problem has any special features not present in the general case, which is why I am asking for references to works where this situation was explicitly considered. Apparently our points of view on what research is and what it is not are different. However, what you have written does not provide an answer to my question. I do not find anything related to $\ell^1$-minimization in "Convex Analysis" - correct me if I am wrong. $\endgroup$
    – R W
    Dec 25, 2017 at 5:39
  • 1
    $\begingroup$ @RW we can choose to disagree here -- also, am surprised that you did not find anything related to $\ell_1$-norms in Rockafellar's book (that is one of the basic examples when talking Fenchel conjugates). Also, perhaps your question is missing information that would substantiate why you believe it to be a research question -- perhaps rather than by fiat, you could tell us what aspects are you wishing to explore? Otherwise, it seems to be a just an ultra-special case of a general well-established theory. Maybe I'm just not getting what's really the question! $\endgroup$
    – Suvrit
    Dec 25, 2017 at 16:23

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.