"Numeric error" message when using a Taylor series iteration method

[gpb...@gmail.com]

I'm using AMPL & Gurobi for a continuous quadratic problem with mostly linear constraints, but also some ratio-type constraints: xy=z.

Gurobi doesn't directly support those constraints, so I have a work-around:

• Supply a rough estimate of the solution values
• Use this rough estimate to create a linear constraint that approximates the ratio constraint in the neighbourhood of the rough estimate (Taylor series method)
  
• Solve, using the linear constraint
• Use the solutions to update the rough estimates
• Repeat until solutions converge

Small code example:

prices.mod:

var volume; # the quantity sold for some commodity
var value; #the value sold for that commodity
var price; #the price of this commodity

param volume_first_estimate := 10; # our initial estimate for volume
param price_first_estimate := 150;
param value_first_estimate := 1000;

# note that these values are not consistent; we wish to adjust them so that the
# final values are consistent.

# The following constraint is what I want:
# subject to ExactPriceConstraint: value = price * volume;
# but since price and volume are both var, this would be quadratic. Instead:

param volume_best_estimate;
param price_best_estimate;
param value_best_estimate;
# Our working best estimate for each of these items

subject to LinearisedPriceConstraint: value = price*volume_best_estimate + price_best_estimate*volume - price_best_estimate*volume_best_estimate;

minimize OF: (price-price_first_estimate)^2+(value-value_first_estimate)^2+(volume-volume_first_estimate)^2;

prices.run:

reset;
option solver gurobi_ampl;
model prices.mod;
let price_best_estimate=price_first_estimate;
let volume_best_estimate=volume_first_estimate;
let value_best_estimate=value_first_estimate;

printf "\nPrice %s, volume %s, value %s: ratio PVo/Va = %s", price_best_estimate, volume_best_estimate, value_best_estimate, price_best_estimate*volume_best_estimate/value_best_estimate;

for {i in 1..10}{
solve;
let price_best_estimate := price;
let value_best_estimate := value; # don't actually end up using this, except
let volume_best_estimate := volume;
printf "\nIteration %s: Price %s, volume %s, value %s: ratio PVo/Va = %s", i, price, volume, value, price*volume/value;
}

For this small example, the method works as expected. After five iterations, price*volume = value to six significant figures, which is more than good enough for my purposes.

However, when I try to use this method as part of a larger system with many other variables, constraints, and terms in the objective function, I often get "suboptimal" and/or "numeric error" messages from the solver. Often the first couple of iterations go OK, with these messages only displaying at later iterations; despite the messages, the solver still returns a solution that appears reasonable.

The fact that it happens mostly in later iterations leads me to suspect that the error is associated with the case where the optimal solution is very close to the previous best estimate. Note that in this constraint:

value = price*volume_best_estimate + price_best_estimate*volume - price_best_estimate*volume_best_estimate;

if volume = volume_best_estimate and price = price_best_estimate then the RHS becomes: price*volume + price*volume - price*volume i.e. all three terms are equal, except for the sign.

I'm aware that subtracting two numbers that are almost equal can result in drastic loss of precision, and I suspect something of this sort might be going on.

As far as I can tell, Gurobi is still producing a good solution to the problem given, but I don't like ignoring warning messages. Any thoughts on what's happening here, and how it might be resolved?

Thanks in advance - Geoffrey

[Robert Fourer]

The first thing I would suggest is to set

option show_stats 1;
option gurobi_options 'outlev=1';

(or add outlev=1 to your existing gurobi_options string) and then post all of the output from one of the runs that produced the errors. Often there are some clues in that material as to what is happening in Gurobi.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of gpb...@gmail.com
Sent: Tuesday, December 19, 2017 6:31 AM
To: AMPL Modeling Language
Subject: [AMPL 15368] "Numeric error" message when using a Taylor series iteration method

I'm using AMPL & Gurobi for a continuous quadratic problem with mostly linear constraints, but also some ratio-type constraints: xy=z.

Gurobi doesn't directly support those constraints, so I have a work-around:
• Supply a rough estimate of the solution values
• Use this rough estimate to create a linear constraint that approximates the ratio constraint in the neighbourhood of the rough estimate (Taylor series method)
• Solve, using the linear constraint
• Use the solutions to update the rough estimates
• Repeat until solutions converge
Small code example:

...

[gpb...@gmail.com]

Example log attached. This includes one initial solve run followed by five iterations where the "rough estimate" values are updated and then the problem is rerun (no other changes to constraints etc.)

The first run shows:

" Matrix range     [8e-10, 2e+05]"

and warns about this large range of coefficients. It then gives "Sub-optimal termination".

In the second run ("Iteration 1") the lower end of the matrix range has decreased from 8e-10 to 1e-10, leading to the same warnings, and suboptimal termination.

In the third run ("Iteration 3", the lower end of the range is 2e-13 and I get "Numerical trouble encountered"/"Numeric error" messages. Subsequent runs give similar results.

Given that the matrix coefficients for the first two runs vary by a factor of ~ 10^15 and for later runs ~ 10^18, I assume this is a numeric precision issue. The fact that the lower range changes with successive iterations suggests to me that it's probably related to the case where "rough estimate" values are very close to solution values, possibly because in this case the constraint is defined in terms of the difference between several numbers of almost equal magnitude.

As previously noted, my constraints have forms like x = y*z_RE+y_RE*z-y_RE*z_RE where the "_RE" terms are parameters that will be very close to the solutions for corresponding vars - hence all three RHS terms will be very similar except for the minus sign on the third term. I can rearrange them to avoid subtraction, e.g. x+y_RE*z_RE = y_z*RE+y_RE*z, but I'm not sure if this makes any difference after presolve?

Cheers - Geoffrey

[ptiwari]

The problem might be due to matrix coefficient range. You can refer to http://files.gurobi.com/Numerics.pdf document about numerical issue in Gurobi.

[Robert Fourer]

Hi Geoffrey,

It is not surprising that the tiny matrix coefficients (and tiny right-hand side values) in your problems lead to failures in the optimization runs. Gurobi suggests setting the NumericFocus parameter, defined as

numericfocus how much to try detecting and managing numerical issues:
0 = automatic choice (default)
1-3 = increasing focus on more stable computations

So adding 'numericfocus 3' to your gurobi_options string might help matters, though the computations will likely be slower.

If NumericFocus doesn't help, then you can use AMPL's "expand" command to identify some particular constraints where the tiny values appear. This should shed some light on why the values are occurring, and will allow you to check whether they are what you expect or whether there is some error due to AMPL not evaluating things in the desired order.

In the end, you might have to conclude that your overall algorithm cannot be implemented in practice, at least not without some changes and perhaps a higher stopping tolerance.