I am trying to define an optimization problem that minimizes the distance between $a(x)$ and $b(x)$, where I need to adjust $b(x)$ downwards using the cost function $c(x)$ (hence, the cost must always be positive). Given that I require a linear problem (since IP or MIP would explode the computation time because of the scale of the problem), and given that absolute value minimization can be linearized (see here), this problem can be written as follows:
$$ \begin{align} \min\ &|a(x)-b(x)-|c(x)|| \\\\ \text{such that} \quad &Ax \leq d \\\\ \end{align} $$
Given that the piece-wise linear objective $\min\ |X|$ can be represented using the linear objective $\min\ Z$ with the added restrictions $Z \geq X, Z \geq -X$, I can rewrite above problem as follows:
$$ \begin{align} \min z \\\\ \text{such that} \quad y &\geq +c(x) \\\\ y &\geq -c(x) \\\\ z &\geq +(a(x)-b(x)-y) \\\\ z &\geq -(a(x)-b(x)-y) \\\\ Ax &\leq d \\\\ \end{align} $$
Would such a transformation for nested absolute values work as expected? Or am I missing something?
What you proposed is almost correct, but it allows $y > |c|$ at optimality when you instead want $y = |c|$. Suppose $\underline{c} \le c \le \overline{c}$ for some constants $\underline{c}$ and $\overline{c}$. You can repair your formulation by introducing a binary variable $z$ and imposing two additional linear big-M constraints: \begin{align} y - c &\le (\overline{c} - \underline{c}) z \\ y + c &\le 2\overline{c}(1-z) \end{align} These enforce two logical implications: \begin{align} z = 0 &\implies y \le c \\ z = 1 &\implies y \le -c \end{align}