Minimizing a Sum of Absolute Values via Linear Programming

Reported in interviews at Radix Trading

Problem statement

How would you minimize a sum of absolute values when the objective has kinks at zero? The objective is $\sum_i |x_i|$, possibly with linear constraints such as $Cx=d$. Give an equivalent smooth formulation and name the class of optimization problem it becomes.

Show hint

Can a non-smooth term be moved out of the objective and into the constraints somehow?

Relevant roles: Applied Scientist, Research Scientist, ML Engineer and Data Scientist.

Related free problems