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

[Andreas Waechter]

Hi Frank,

I guess I'm not quite sure what you mean by noise...

There are several ways to understand what noise.  For one, it could mean
numerical noise in the computation of function values and gradients (for
example if the optimization algorithm is coupled with a simulation
packages that solves differential equation for each evaluation of the
objective and constraint function which are then computed only to some
limited accuracy).  In that case, the linear model that the optimization
method builds internally to compute search direction might not be very
good and cause numerical trouble for the optimization method, because the
function behaves somewhat unpredictable for small changes in the
variables.  However, since you are using AMPL, the function and
derivatives are computed accurate to machine precision.

The other meaning of noise (which I thought you had meant) is related to
trying to fit a model to data (e.g. in a least square approach).  For
example, you might have some model that describes the behavior of some
(e.g. physical) quantity, and you are trying to fit parameters in your
model so that the quantities predicted by the model match as closely as
possible with some (e.g. real-world) measurements.  Here, one can consider
as non-noisy case the "synthetic" one where the "measured data" are
actually computed using some chosen values of the parameters in the model
that is to be used for the data fitting.  In other words, in this case it
is clear that there are optimal values of the parameters (those chosen
ones) which are able to match the "measured data" perfectly.  In that
case, an objective function that measures the deviation of the measured
data and the data predicted by the model, can be optimized to zero.

However, in a real application the model is only an approximation of what
is going on in the real-world, and also measurements are only obtained
within certain accuracy.  Therefore, if one was trying to find the best
fitting parameters for a model, but uses real-word data, it is usually not
possible to find values of the model parameters so that the model would
perfectly predict the behavior for all data points.  In such a case the
objective function (if it measures deviation of predicted and actual data)
will not be able to be optimized to zero.

I had assumed that you mean by noise this second option.  If that is true,
Ipopt (with AMPL) should still be able to converge to a solution that
satisfies the optimality conditions for the nonlinear optimization problem
quite accurately.  It's just that at such a (accuracy) optimal point of
the NLP, the objective function is no zero, simply because the best data
fitting that can be done is not able to match all predicted and actual
data.

Of course, there is always the possibility that for a non-convex model
Ipopt might converge to a local solution that is not the global solution.
There might be tricks like starting from different initial points, or even
some smoothing heuristics that might be able to help out, but I don't
think I could help with that.

I hope this addresses your question regarding the noise...

Best,

Andreas


On Fri, 20 May 2005, Frank J. Iannarilli wrote:

> 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
> _______________________________________________
> Coin-ipopt mailing list
> Coin-ipopt at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-ipopt
>