Wednesday, February 8, 2017

Failing to use optimal solution as initial point

In a somewhat complex non-linear programming model, I observed the following. I do here two solves in a row:

solve m2 minimizing zrf using dnlp;
solve
m2 minimizing zrf using dnlp;

We solve the model, and then in the second solve we use the optimal solution from the first solve as an initial point. This should make the second solve rather easy! But what I see is somewhat different.

The first solve has no problems. (I fed it a close to optimal initial point). The log looks like:

--- Generating DNLP model m2
--- testmodel6.gms(83981) 156 Mb  22 secs
--- testmodel6.gms(84048) 160 Mb
---   139,443 rows  139,450 columns  746,438 non-zeroes
---   8,504,043 nl-code  467,552 nl-non-zeroes
--- testmodel6.gms(84048) 116 Mb
--- Executing CONOPT: elapsed 0:01:44.102
CONOPT 3         24.7.3 r58181 Released Jul 11, 2016 WEI x86 64bit/MS Windows
 
 
    C O N O P T 3   version 3.17A
    Copyright (C)   ARKI Consulting and Development A/S
                    Bagsvaerdvej 246 A
                    DK-2880 Bagsvaerd, Denmark
 
 
   Iter Phase Ninf   Infeasibility   RGmax    NSB   Step InItr MX OK
      0   0        8.7137917110E-04 (Input point)
 
                   Pre-triangular equations:   9720
                   Post-triangular equations:  129722
 
      1   0        3.0000000000E-05 (After pre-processing)
      2   0        4.6875000000E-07 (After scaling)
      3   0     0  7.3256941462E-17               1.0E+00      F  T
 
** Feasible solution. Value of objective =   0.905233579345
 
   Iter Phase Ninf     Objective     RGmax    NSB   Step InItr MX OK
      4   3        9.0523357374E-01 1.9E-03     6 1.0E+00    3 T  T
      5   3        9.0523357341E-01 1.0E-03     3 1.0E+00    2 T  T
      6   3        9.0523357341E-01 1.3E-12     3
 
** Optimal solution. Reduced gradient less than tolerance.

We are hopeful the second solve should be even easier, but we see:

--- Generating DNLP model m2
--- testmodel6.gms(83981) 69 Mb
*** Error at line 83981: overflow in * operation (mulop)
--- testmodel6.gms(83981) 155 Mb 1 Error  22 secs
--- testmodel6.gms(84049) 116 Mb 1 Error
*** SOLVE aborted

How can an optimal solution be an invalid initial point?

My analysis is the following:

  • The equation we cannot generate is part of what Conopt calls “Post-triangular equations”. These equations are set aside by Conopt when solving the model, and are reintroduced just before reporting the solution because Conopt knows these equations will not change the solution. Typically “accounting rows” are such equations. These are constraints that could have been implemented as assignments in post-processing as they just calculate some additional information about the solution. In most cases these post-triangular equations do not require the evaluation of gradients.
  • When we generate the model again for the second time, GAMS will try to evaluate the gradients. It is here where we encounter the overflow. In this model things are way more complicated but think about the function \(f(x)=\sqrt{x}\) at \(x=0\). The function itself can be evaluated at \(x=0\), but the gradient can not. (Actually GAMS will patch the derivative of \(\sqrt{x}\) at \(x=0\) to fix this, but it is not smart enough to do this on my functions).
  • This also means that there is a architectural flaw here: we should do the presolve before evaluating gradients. Here GAMS will evaluate gradients, and subsequently CONOPT will presolve the model. This is exactly in the wrong order. Note that AMPL will do a presolve in the generation of the model opposed to GAMS which leaves it to the solver. I believe AMPL is doing the right thing here.

A work-around is:

solve m2 minimizing zrf using dnlp;
x.l(jd) = max(x.l(jd),1e-6);
solve
m2 minimizing zrf using dnlp;