[Coin-ipopt] Limiting line search step

[Andreas Waechter]

Hi,

> Is there a way to enforce the "never-exceed" value of step size in line
> search (which would unfortunatelly depend on each search direction...)? Or
> at least a way to make it more conservative?
>
> The problem is that my objective function needs to deform an unstructured
> computational grid at one point, which is touchy, and too large a step
> crashes it. When the step was limited in a suitable fashion, it worked with
> simple BFGS/penalty algorithm.

There is no option in the Ipopt code that makes sure that the step you 
take is not exceeding a certain size.

If I understand correctly, you would like to have something like this:

Given the current iterate x_k, don't even try to evaluate any functions at 
a trial point x_k + alpha_k d_k (where d_k is the Newton-type step and 
alpha_k is the fraction of that step to be taken), if alpha_k*||d_k|| is 
larger than some tolerance you would provide.

One way to do this is that you could simply monitor in your implementation 
of the TNLP code how large the steps are that Ipopt wants to do (storing 
the previous request and computing the difference), and you could simply 
return 'false' when eval_f or other methods are called.  Then Ipopt will 
backtrack until your function no longer returns false.

Or you could try the following patch in your code (I haven't tested it):

In the file Ipopt/src/Algorithm/IpBacktrackingLineSearch.cpp in the method

bool BacktrackingLineSearch::DoBacktrackingLineSearch

look for the declaration of alpha_primal_max (l.635 in the current trunk 
version), and add a few lines after that as the following:

----- 8< -----------------------------
     // Compute primal fraction-to-the-boundary value
     Number alpha_primal_max =
       IpCq().primal_frac_to_the_bound(IpData().curr_tau(),
                                       *actual_delta->x(),
                                       *actual_delta->s());
     const Number dx_nrm2 = actual_delta->x()->Nrm2();
     if (dx_nrm2 > 0.) {
       const Number MaxDelta = 10.;
       alpha_primal_max = Min(alpha_primal_max, MaxDelta/dx_nrm2);
     }
----- 8< -----------------------------

In the above, you would need to change the number for MaxDelta according 
to what you want to specify as the maximum step size.

(The above assumes that you want to measure the step in the 2 norm. You 
can use Asum instead of Nrm2 for the 1-norm, or Amax instead of Nrm2 for 
the max-norm.)

There might be some other places still left where the step will actually 
be larger, but at least that gives you something to start, I hope.

Hope this helps,

Andreas