[Coin-ipopt] New Termination Option: minimal progress?
Frank J. Iannarilli
franki at aerodyne.com
Fri May 20 21:52:43 EDT 2005
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
More information about the Coin-ipopt
mailing list