Optimize an objective function with absolute value function

If you just have linear constraints with this objective, you should solve this as a Linear Program (LP). Handling the abs objective is a common LP modeling trick. Here's one reference on how to do it.

There are many machine learning methods that computes absolute values in the objective function, be it in the loss (e.g. to implement a regression that is robust to outliers) or in the regularizer (L1 penalty such as the Lasso).

In both cases you can take an arbitrary sub-gradient e.g. 0 in your case, where the objective function is not derivable, in your case where x-x0 == 0. Furthermore, you should truncate the gradient when the update of the weights make your weight change sign. This allow for sparsity inducing regularizers to work as expected.

Edit: what I am describing here is not a Newton update but a regular stochastic gradient update that handles abs values without any problem if you apply the above tricks. I have no experience with second order methods + abs values in objective functions so I won't comment on the Newton part.

Newton's method will find something close to the optimum with any subgradient (and a nice subgradient of |x| is sign(x)). It won't, as other people said, however, find the exact optimum, and you can get better results with specialized optimizers for l1 regularized functions (since what you describe sounds like l1 regularization).

In machine learning there are some traditional methods for optimizing this sort of function, such as the lasso, coordinate ascent, truncated gradient (which might interact badly with newton's method), the method in this paper, the method in this other paper, and many others.

This problem also occurs a lot in compressive sensing, where people usually use linear programming to minimize such a regularized/constrained loss.

You can also solve a problem like this by showing that a sequence differentiable functions converges to your function in the limit and that the extrema also converges.

sqrt(x^2) is not differentiable at zero but sqrt(x^2 + 2^-n) is and you can show what happens to your extrema as n goes to infinity.

For slightly more information I asked about this problem here.

http://math.stackexchange.com/questions/1649/finding-the-extrema-non-differentialable-functions

Why not just optimize twice? Optimize f(x) and optimize -f(x), and use whichever answer you like better (i.e. whichever has the better abs(f(x)) ). That way you get rid of the absolute value and the resulting non-convexity.

A more complicated implementation might try to do both at once, spending more time one whichever side looks more promising at the moment.

I explain the whole idea by giving an example. Let's say that we would like to minimize the function f(x,y)=x-|y| subject to -3 <= x,y <= 3. Just introduce a new variable as t and rewrite the objective function as f(x,y,t) = x-t, then add the constraint -|y| <= t <= |y|. This way, the objective function is now derivative and the result of the optimizer is the same as being applied to the original problem definition.

You can write |x - x0| as the square root of a square. I.e. u = x - x0, then |u| = sqrt(u^2). You can then take the derivative of this.

If the derivative is difficult to calculate for other reasons you can calculate a derivative numerically, for example by using the secant method. In fact you can numerically calculate the derivative exactly at any point using automatic differentiation even if you cannot analytically calculate the derivative.