[petsc-dev] quasi-newton approximations

[Munson, Todd]

For the implementation in TAO, we have a QN matrix class that implements
a subset of the Mat operations.  We wrap the QN matrix in a PC Shell
when used as a preconditioner.

I imagine something similar could be a starting point for generic QN
matrices and preconditioners.

Todd.
 
> On Aug 30, 2016, at 9:26 PM, Oxberry, Geoffrey Malcolm <oxberry1 at llnl.gov> wrote:
> 
> 
> 
> On 8/30/16, 12:36 PM, "Munson, Todd" <tmunson at mcs.anl.gov> wrote:
> 
>> 
>> For preconditioners, I use them as a default for unconstrained and bound
>> constrained problems.  They can be overridden by someone who knows a
>> good preconditioner for their particular problem.
> 
> Makes sense to me. I agree that QN approaches are good for constructing
> preconditioners, and also readily lend themselves to cheaper computation
> of Hessian inverse approximations. Definitely for the unconstrained case,
> this use is apparent.
> 
>> 
>> For more general constrained problems, its harder.  But they could be
>> part of your saddle point problem preconditioner.
> 
> Absolutely. If you solve a KKT-like system, this preconditioner is good
> for the (0,0) block.
> 
>> 
>> Note: we already use QN methods in TAO for the some reduced space methods
>> where we use a QN approximation to the reduced Hessian matrix, primarily
>> because we never want to actually form the reduced Hessian matrix.  It
>> could still be used as a preconditioner in a flexible CG method using
>> the product form of the reduced Hessian.
> 
> Yes, that makes sense to me.
> 
> The issue I am thinking about ‹ and I still need to think about it more ‹
> is that there are two interfaces for QN approximations that are useful.
> One of them is as a preconditioner; the other interface is as a Hessian
> approximant. As a practitioner and method developer, I would want both
> interfaces, but maybe these two interfaces are two aspects of the same
> thing, or can be expressed using a common formalism.
> 
> There are cases where using it as a preconditioner does not currently make
> sense; for instance, one of these cases is trust-region STCG, because
> variable preconditioning will change the shape of the trust region from
> iteration to iteration. In this particular setting, it makes more sense to
> me to use QN approximations for the Hessian rather than as a
> preconditioner.
> 
> There have been some alternate methods that replace STCG ‹ GLTR is one,
> IP-SSM is another ‹ and I do not know of these methods suffer from the
> same drawbacks, so I will have to do more reading. I remember skimming a
> paper on IP-SSM that mentioned the variable preconditioning issue, so I
> will have to look that up and do some more reading.
> 
> Geoff
> 
>> 
>> Todd.
>> 
>>> On Aug 30, 2016, at 4:13 PM, Oxberry, Geoffrey Malcolm
>>> <oxberry1 at llnl.gov> wrote:
>>> 
>>> I think refactoring to enable use of QN approximations in more methods
>>> is a good idea. As I¹m sure you both are aware, some IPMs and SQP
>>> methods admit QN approximations, and it would be good to have this
>>> option on the command line for more methods (e.g., TAOIPM, the nascent
>>> SQP implementation), especially where attempting to form even the action
>>> of the Hessian is onerous.
>>> 
>>> For the optimization methods, it¹s not immediately clear that
>>> extracting them as a PC makes sense to me. I¹d have to think about it
>>> more. In many algorithms (e.g., in IPOPT), using the QN approximation
>>> also enables more efficient linear algebra via
>>> Sherman-Morrison-Woodbury, but it¹s not clear to me that this
>>> modification is really appropriate for some of the possible algorithm
>>> combinations in TAO. It makes sense for TAOIPM with KSPPREONLY and PCLU
>>> with SuperLU or another package capable of pivoting with zeroes on the
>>> diagonal, but if an actual Krylov subspace method is used, I¹m not sure
>>> it makes sense anymore.
>>> 
>>> Geoff 
>>> 
>>> From: <petsc-dev-bounces at mcs.anl.gov> on behalf of Matthew Knepley
>>> <knepley at gmail.com>
>>> Date: Tuesday, August 30, 2016 at 2:02 PM
>>> To: "Munson, Todd" <tmunson at mcs.anl.gov>
>>> Cc: petsc-dev <petsc-dev at mcs.anl.gov>
>>> Subject: Re: [petsc-dev] quasi-newton approximations
>>> 
>>> I think we should extract them the same way as SNESMFFD. Using them as
>>> a PC
>>> is a good idea.
>>> 
>>>   Matt
>>> 
>>> On Tue, Aug 30, 2016 at 1:18 PM, Munson, Todd <tmunson at mcs.anl.gov>
>>> wrote:
>>> 
>>> One of the common concepts for TAO and SNES is the quasi-Newton
>>> approximations.
>>> SNES seems to only use them in SNESQN (for non-symmetric matrices) and
>>> TAO uses
>>> them in TAOLMVM and TAOBLMVM (for symmetric matrices).  TOA also allows
>>> them to
>>> be used as a preconditioner for the Hessian-based line-search and
>>> trust-region
>>> methods.
>>> 
>>> Should we consider extracting some common class for these
>>> approximations and
>>> the associated operations or just leave them as separate things?
>>> 
>>> Todd.
>>> 
>>> 
>>> 
>>> 
>>> -- 
>>> What most experimenters take for granted before they begin their
>>> experiments is infinitely more interesting than any results to which
>>> their experiments lead.
>>> -- Norbert Wiener
>> 
>