[petsc-dev] Question about linesearch

[Munson, Todd]

Hi,

I am not sure that this linesearch is implemented in PETSc itself.  To implement
it, you would need the ability to perform projections onto your feasible region,
which is what I am assuming you mean by undershoot or overshoot.

Once the projections are involved, however, there are lots of potential problems to
consider in the general case.

Here I am assuming that x_k is feasible with respect to your feasible region.  If
not, then there are even more options.  For the particular form of line search 
you have (sufficient decrease conditions) you will want the projection in 
two places:

  f(\Pi_C(x_k + \lambda d_k) < f(x_k) + \alpha grad f(x_k)^T (\Pi_C(x_k + \lambda d_k) - x_k)

where \Pi_C is the projection of the argument onto the feasible region C, a convex
set.

The last term makes sure you measure descent against the projected direction, rather 
than the full direction.  The projected direction may not be a descent direction,
so you need a fix when \alpha grad f(x_k)^T (\Pi_C(x_k + \lambda d_k) - x_k) >= 0.
I would need to dig out some papers for the appropriate fix, which if I recall
correctly involves the \min operation.

Unless your direction is the steepest descent direction for f(x_k), there is no
guarantee that you will satisfy the sufficient decrease condition for any value
of \lambda and you would need to impose a finite lower bound on \lambda and 
have a backup that uses the steepest descent direction.

I recall an alternative line search that uses a convex combination of the 
steepest descent direction and d_k, but would have to find the papers
on it.

Second order sufficiency (e.g., the equivalent of the strong Wolfe conditions)
is probably off the table for now when you have projections.

As you can see, there are lots of options (even before adding monotone versus
non monotone considerations); the PETSc developers would have to say which 
ones are relevant and whether or not the projected line searches are 
separate from the normal line searches.

Todd.

> On Sep 22, 2017, at 8:22 AM, Lulu Liu <lulu.liu at kaust.edu.sa> wrote:
> 
> Hi,
> 
> I am trying to find a lambda by the linesearch such that
> f([x_{k}+\lambda d_{k}])<f(x_{k})+\alpha\lambda grad f(x_{k})^{T}d_{k}
> where [x_{k}+lambda d_{k}] means the projection that cuts off the undershoot or overshoot of  x_{k}+lambda d_{k}.
> 
> How to add the above projection into the linesearch in PETSc?
> 
> Thanks!
> 
> This message and its contents, including attachments are intended solely for the original recipient. If you are not the intended recipient or have received this message in error, please notify me immediately and delete this message from your computer system. Any unauthorized use or distribution is prohibited. Please consider the environment before printing this email.