In [1] the following simple problem is posed:
Given data
p = [50, 50.5, 52, 53, 55, 55.5, 56, 57,60, 61]
try to track this as close as possible by minimizing the largest deviation while obeying the restrictions:
\[\begin{align}&\color{darkred}x_1 = \color{darkblue}p_1\\ &\color{darkred}x_i - \color{darkred}x_{i-1}\le 1.5\end{align}\]
Non-differentiable NLP model
An obvious way to formulate this is: \[\begin{align} \min&\max_i |\color{darkred}x_i-\color{darkblue}p_i| \\ &\color{darkred}x_1 = \color{darkblue}p_1\\ &\color{darkred}x_i - \color{darkred}x_{i-1}\le 1.5\end{align}\]
This is a non-differentiable formulation, and we are asking for trouble when trying to solve this using a standard nonlinear NLP solver. For instance, when I solve this with CONOPT, we may see:
S O L V E S U M M A R Y
MODEL m1 OBJECTIVE z
TYPE DNLP DIRECTION MINIMIZE
SOLVER CONOPT FROM LINE 25
**** SOLVER STATUS 4 Terminated By Solver
**** MODEL STATUS 7 Feasible Solution
**** OBJECTIVE VALUE 1.2500
RESOURCE USAGE, LIMIT 0.062 10000000000.000
ITERATION COUNT, LIMIT 31 2147483647
EVALUATION ERRORS 0 0
CONOPT 3 33.2.0 r4f23b21 Released Dec 01, 2020 WEI x86 64bit/MS Window
C O N O P T 3 version 3.17L
Copyright (C) ARKI Consulting and Development A/S
Bagsvaerdvej 246 A
DK-2880 Bagsvaerd, Denmark
The model has 11 variables and 10 constraints
with 29 Jacobian elements, 10 of which are nonlinear.
The Hessian of the Lagrangian has 10 elements on the diagonal,
45 elements below the diagonal, and 10 nonlinear variables.
Pre-triangular equations: 0
Post-triangular equations: 10
** Feasible solution. Convergence too slow. The change in objective
has been less than 3.7500E-12 for 20 consecutive iterations
Conopt realizes it has some troubles and declares the solution as just feasible instead of optimal. Indeed, we can do better than an objective of 1.25. Other NLP solvers may not even know they are in trouble and just report a solution and declare it (locally) optimal.
There is a big problem with this model. Most NLP solvers assume the objective and non-linear constraints are smooth (i.e. differentiable). In this case, we don't have this, and this lack of smoothness is often a recipe for disaster. This is a nice example of this.
I often complain about non-differentiability in models I see on forums. Often the reaction is: "Who cares?". Indeed, often NLP solvers will deliver some solution without warning. This post is about a small problem, where we really can do much better.
Note that the initial point also plays a role here. With a different starting point, you may find different solutions.
A global NLP solver may help for this model. Some of the ones I tried, don't have support for the max() function, so we need to reformulate the model. When doing that, we can actually do a bit better and form a linear programming problem.
