Let us assume I have a sequence of numbers $\{n_1,n_2\cdots, n_k\}$ which I want to approximate / represent like so:
$$\hat n_i = a_i x + b_i :,\\ a_i \in \mathbb Z^+,b_i\in \mathbb Z\\\text{so that}\\ \min_{x,a_i,b_i}\sum_{i}\|n_i - \hat n_i\| + \sum_i w_1(a_i) + w_2(b_i)$$
For weight functions $w_1,w_2$ for which $w_1$ is 0 at $1$ and monotonically increasing with $a_i$ and $w_2$ is $0$ at $0$ and monotonically increasing with $|b_i|$
How can I approach this problem?
I assume that your weight functions are nonlinear. If you can set a priori bounds on the magnitudes of the $a$ and $b$ variables, you can solve this as a mixed integer linear program.
Assume that $a_{i}\in\lbrace0,\dots,A_{i}\rbrace$ and $b_{i}\in\lbrace B_{i,0},\dots,B_{i,N_{i}}\rbrace.$ Create binary variables $y_{i,j},\,j=0,\dots,A_{i}$ and $z_{i,j},\,j=0,\dots,N_{i}$ to select the values of $a_{i}$ and $b_{j},$ along with auxiliary continuous variables $s_{i},$ $t_{i},$ $u_{i}$ and $v_{i}.$ Add the following constraints.
$$\hat{n}_{i}=t_i + b_i\quad\forall i$$
$$s_i\ge n_i - \hat{n}_i\quad\forall i$$ $$s_i\ge \hat{n}_i -n_i\quad\forall i$$
The objective function is $\sum_{i}\left(s_{i}+u_{i}+v_{i}\right).$
There are two things to note. First, the final set of constraints actually says $$s_i \ge \vert n_i - \hat{n}_i \vert .$$
We get equality because the objective function will prevent the solver from inflating the value of $s_i.$ Second, while many modern solvers support implication constraints, if necessary the implication constraint $$y_{i,j} = 1\implies t_{i}=j \cdot x$$ can be linearized using the "big M" approach, substituting for the implication the constraints $$t_i\ge j\cdot x-M_{i,j}(1-y_{i,j})$$ $$t_i\le j\cdot x+M_{i,j}(1-y_{i,j})$$ where $M_{i,j}$ is an upper bound on $\vert a_{i}x-j\cdot x\vert.$
