[Coin-ipopt] New Termination Option: minimal progress?

[Frank J. Iannarilli]

Hi,


Here is a use case that I believe indicates need for a new termination 
option. To frame things, I'll start with a problem with noise-free data, 
progress to known-noise, then for *unknown-noise*, argue the need for this 
new termination option.


   For concreteness, assume the problem is a least-absolute-deviations 
(LAD) type of fitting of model to data. For a perfect model and noise-free 
data, we'd expect a solution to possess negligible dual-infeasibility. 
Therefore, we might set the IPOPT termination parameters as so:

    dtol 1e-4

Now let's add a *known* amount of noise, say r.m.s.=sigma, to the data. 
Evaluated at the noise-free solution value, the expected r.m.s. value of 
each deviation variable in the objective is therefore sigma.  Therefore, 
anticipating noisy data with *known sigma*, we'd set  the IPOPT termination 
parameters as so:

    iscalerr 0    # lets us express termination criterion in unscaled units
    dtol 3*sigma  # max-norm of expected dual-infeasibility of a solution
    dcmaxtol 1e-4 # we STILL want negligible constraint violation; our
                  #  raising of dtol, w/o setting dcmaxtol, would otherwise
                  #  allow constraint-violating solutions to terminate


However, for an *unknown* amount of noise (true value: sigma_true), we 
might set dtol to a much higher value, e.g., sigma_guess.  But if:

    dtol=sigma_guess >> sigma_true

then IPOPT will terminate too early with a sub-optimal solution.


On the other hand, setting:

     dtol=sigma_guess << sigma_true

I observe IPOPT to "wander aimlessly" once it's made progress toward the 
expected levels of dual infeasibility.


So might it make sense to add a new termination option that somehow 
"detects" that the algorithm is making minimal further progress, and 
terminates?  This would enable the unknown-noise LAD problem to achieve 
optimality without trying to iteratively guess the appropriate dtol.

The issue I see (still as a NLP/IP neophyte!) in implementing such an 
option would be detecting that progress has stalled, even though the 
remaining error may "slosh" back and forth between dual and primal 
infeasibility (thus rendering the observation of *relative reduction* of 
each an impotent gauge).


Thoughts or reactions?


Frank J. Iannarilli, franki at aerodyne.com
Aerodyne Research, Inc., 45 Manning Rd., Billerica, MA 01821 USA
www.aerodyne.com/cosr/cosr.html