[petsc-users] VI: RS vs SS

[Alexander Lindsay]

I'm not too familiar with the M and q notation. However, I've attached A
and b for the unconstrained linear problem in PETSc binary format (don't
know if they'll go through on this list...). l and u are 0 and 10
respectively.

On Fri, Nov 1, 2019 at 10:19 AM Munson, Todd <tmunson at mcs.anl.gov> wrote:

>
> Yes, that looks weird.  Can you send me directly the linear problem (M, q,
> l, and u)?  I
> will take a look and run some other diagnostics with some of my other
> tools.
>
> Thanks, Todd.
>
> > On Nov 1, 2019, at 10:14 AM, Alexander Lindsay <alexlindsay239 at gmail.com>
> wrote:
> >
> > No, the matrix is not symmetric because of how we impose some Dirichlet
> conditions on the boundary. I could easily give you the Jacobian, for one
> of the "bad" problems. But at least in the case of RSLS, I don't know
> whether the algorithm is performing badly, or whether the slow convergence
> is simply a property of the algorithm. Here's a VI monitor history for a
> representative "bad" solve.
> >
> >   0 SNES VI Function norm 0.229489 Active lower constraints 0/1 upper
> constraints 0/1 Percent of total 0. Percent of bounded 0.
> >   1 SNES VI Function norm 0.365268 Active lower constraints 83/85 upper
> constraints 83/85 Percent of total 0.207241 Percent of bounded 0.
> >   2 SNES VI Function norm 0.495088 Active lower constraints 82/84 upper
> constraints 82/84 Percent of total 0.204744 Percent of bounded 0.
> >   3 SNES VI Function norm 0.478328 Active lower constraints 81/83 upper
> constraints 81/83 Percent of total 0.202247 Percent of bounded 0.
> >   4 SNES VI Function norm 0.46163 Active lower constraints 80/82 upper
> constraints 80/82 Percent of total 0.19975 Percent of bounded 0.
> >   5 SNES VI Function norm 0.444996 Active lower constraints 79/81 upper
> constraints 79/81 Percent of total 0.197253 Percent of bounded 0.
> >   6 SNES VI Function norm 0.428424 Active lower constraints 78/80 upper
> constraints 78/80 Percent of total 0.194757 Percent of bounded 0.
> >   7 SNES VI Function norm 0.411916 Active lower constraints 77/79 upper
> constraints 77/79 Percent of total 0.19226 Percent of bounded 0.
> >   8 SNES VI Function norm 0.395472 Active lower constraints 76/78 upper
> constraints 76/78 Percent of total 0.189763 Percent of bounded 0.
> >   9 SNES VI Function norm 0.379092 Active lower constraints 75/77 upper
> constraints 75/77 Percent of total 0.187266 Percent of bounded 0.
> >  10 SNES VI Function norm 0.362776 Active lower constraints 74/76 upper
> constraints 74/76 Percent of total 0.184769 Percent of bounded 0.
> >  11 SNES VI Function norm 0.346525 Active lower constraints 73/75 upper
> constraints 73/75 Percent of total 0.182272 Percent of bounded 0.
> >  12 SNES VI Function norm 0.330338 Active lower constraints 72/74 upper
> constraints 72/74 Percent of total 0.179775 Percent of bounded 0.
> >  13 SNES VI Function norm 0.314217 Active lower constraints 71/73 upper
> constraints 71/73 Percent of total 0.177278 Percent of bounded 0.
> >  14 SNES VI Function norm 0.298162 Active lower constraints 70/72 upper
> constraints 70/72 Percent of total 0.174782 Percent of bounded 0.
> >  15 SNES VI Function norm 0.282173 Active lower constraints 69/71 upper
> constraints 69/71 Percent of total 0.172285 Percent of bounded 0.
> >  16 SNES VI Function norm 0.26625 Active lower constraints 68/70 upper
> constraints 68/70 Percent of total 0.169788 Percent of bounded 0.
> >  17 SNES VI Function norm 0.250393 Active lower constraints 67/69 upper
> constraints 67/69 Percent of total 0.167291 Percent of bounded 0.
> >  18 SNES VI Function norm 0.234604 Active lower constraints 66/68 upper
> constraints 66/68 Percent of total 0.164794 Percent of bounded 0.
> >  19 SNES VI Function norm 0.218882 Active lower constraints 65/67 upper
> constraints 65/67 Percent of total 0.162297 Percent of bounded 0.
> >  20 SNES VI Function norm 0.203229 Active lower constraints 64/66 upper
> constraints 64/66 Percent of total 0.1598 Percent of bounded 0.
> >  21 SNES VI Function norm 0.187643 Active lower constraints 63/65 upper
> constraints 63/65 Percent of total 0.157303 Percent of bounded 0.
> >  22 SNES VI Function norm 0.172126 Active lower constraints 62/64 upper
> constraints 62/64 Percent of total 0.154806 Percent of bounded 0.
> >  23 SNES VI Function norm 0.156679 Active lower constraints 61/63 upper
> constraints 61/63 Percent of total 0.15231 Percent of bounded 0.
> >  24 SNES VI Function norm 0.141301 Active lower constraints 60/62 upper
> constraints 60/62 Percent of total 0.149813 Percent of bounded 0.
> >  25 SNES VI Function norm 0.125993 Active lower constraints 59/61 upper
> constraints 59/61 Percent of total 0.147316 Percent of bounded 0.
> >  26 SNES VI Function norm 0.110755 Active lower constraints 58/60 upper
> constraints 58/60 Percent of total 0.144819 Percent of bounded 0.
> >  27 SNES VI Function norm 0.0955886 Active lower constraints 57/59 upper
> constraints 57/59 Percent of total 0.142322 Percent of bounded 0.
> >  28 SNES VI Function norm 0.0804936 Active lower constraints 56/58 upper
> constraints 56/58 Percent of total 0.139825 Percent of bounded 0.
> >  29 SNES VI Function norm 0.0654705 Active lower constraints 55/57 upper
> constraints 55/57 Percent of total 0.137328 Percent of bounded 0.
> >  30 SNES VI Function norm 0.0505198 Active lower constraints 54/56 upper
> constraints 54/56 Percent of total 0.134831 Percent of bounded 0.
> >  31 SNES VI Function norm 0.0356422 Active lower constraints 53/55 upper
> constraints 53/55 Percent of total 0.132335 Percent of bounded 0.
> >  32 SNES VI Function norm 0.020838 Active lower constraints 52/54 upper
> constraints 52/54 Percent of total 0.129838 Percent of bounded 0.
> >  33 SNES VI Function norm 0.0061078 Active lower constraints 51/53 upper
> constraints 51/53 Percent of total 0.127341 Percent of bounded 0.
> >  34 SNES VI Function norm 2.2664e-12 Active lower constraints 51/52
> upper constraints 51/52 Percent of total 0.127341 Percent of bounded 0.
> >
> > I've read that in some cases the VI solver is simply unable to move the
> constraint set more than one grid cell per non-linear iteration. That looks
> like what I'm seeing here...
> >
> > On Tue, Oct 29, 2019 at 7:15 AM Munson, Todd <tmunson at mcs.anl.gov>
> wrote:
> >
> > Hi,
> >
> > Is the matrix for the linear PDE symmetric?  If so, then the VI is
> equivalent to
> > finding the stationary points of a bound-constrained quadratic program
> and you
> > may want to use the TAO Newton Trust-Region or Line-Search methods for
> > bound-constrained optimization problems.
> >
> > Alp: are there flags set when a problem is linear with a symmetric
> matrix?  Maybe
> > we can do an internal reformulation in those cases to use the
> optimization tools.
> >
> > Is there an easy way to get the matrix and the constant vector for one
> of the
> > problems that fails or does not perform well?  Typically, the TAO RSLS
> > methods will work well for the types of problems that you have and if
> > they are not, then I can go about finding out why and making some
> > improvements.
> >
> > Monotone in this case is that your matrix is positive semidefinite;
> x^TMx >= 0 for
> > all x.  For M symmetric, this is the same as M having all nonnegative
> eigenvalues.
> >
> > Todd.
> >
> > > On Oct 28, 2019, at 11:14 PM, Alexander Lindsay <
> alexlindsay239 at gmail.com> wrote:
> > >
> > > On Thu, Oct 24, 2019 at 4:52 AM Munson, Todd <tmunson at mcs.anl.gov>
> wrote:
> > >
> > > Hi,
> > >
> > > For these problems, how large are they?  And are they linear or
> nonlinear?
> > > What I can do is use some fancier tools to help with what is going on
> with
> > > the solvers in certain cases.
> > >
> > > For the results cited above:
> > >
> > > 100 elements -> 101 dofs
> > > 1,000 elements -> 1,001 dofs
> > > 10,000 elements -> 10,001 dofs
> > >
> > > The PDE is linear with simple bounds constraints on the variable: 0 <=
> u <= 10
> > >
> > >
> > > For Barry's question, the matrix in the SS solver is a diagonal matrix
> plus
> > > a column scaling of the Jacobian.
> > >
> > > Note: semismooth, reduced space and interior point methods mainly work
> for
> > > problems that are strictly monotone.
> > >
> > > Dumb question, but monotone in what way?
> > >
> > > Thanks for the replies!
> > >
> > > Alex
> > >
> > > Finding out what is going on with
> > > your problems with some additional diagnostics might yield some
> > > insights.
> > >
> > > Todd.
> > >
> > > > On Oct 24, 2019, at 3:36 AM, Smith, Barry F. <bsmith at mcs.anl.gov>
> wrote:
> > > >
> > > >
> > > > See bottom
> > > >
> > > >
> > > >> On Oct 14, 2019, at 1:12 PM, Justin Chang via petsc-users <
> petsc-users at mcs.anl.gov> wrote:
> > > >>
> > > >> It might depend on your application, but for my stuff on maximum
> principles for advection-diffusion, I found RS to be much better than SS.
> Here’s the paper I wrote documenting the performance numbers I came across
> > > >>
> > > >> https://www.sciencedirect.com/science/article/pii/S0045782516316176
> > > >>
> > > >> Or the arXiV version:
> > > >>
> > > >> https://arxiv.org/pdf/1611.08758.pdf
> > > >>
> > > >>
> > > >> On Mon, Oct 14, 2019 at 1:07 PM Alexander Lindsay via petsc-users <
> petsc-users at mcs.anl.gov> wrote:
> > > >> I've been working on mechanical contact in MOOSE for a while, and
> it's led to me to think about general inequality constraint enforcement.
> I've been playing around with both `vinewtonssls` and `vinewtonrsls`. In
> Benson's and Munson's Flexible Complementarity Solvers paper, they were
> able to solve 73.7% of their problems with SS and 65.5% with RS which led
> them to conclude that the SS method is generally more robust.  We have had
> at least one instance where a MOOSE user reported an order of magnitude
> reduction in non-linear iterations when switching from SS to RS. Moreover,
> when running the problem described in this issue, I get these results:
> > > >>
> > > >> num_elements = 100
> > > >> SS nl iterations = 53
> > > >> RS nl iterations = 22
> > > >>
> > > >> num_elements = 1000
> > > >> SS nl iterations = 123
> > > >> RS nl iterations = 140
> > > >>
> > > >> num_elements = 10000
> > > >> SS: fails to converge within 50 nl iterations during the second
> time step whether using a `basic` or `bt` line search
> > > >> RS: fails to converge within 50 nl iterations during the second
> time step whether using a `basic` or `bt` line search (although I believe
> `vinewtonrsls` performs a line-search that is guaranteed to keep the
> degrees of freedom within their bounds)
> > > >>
> > > >> So depending on the number of elements, it appears that either SS
> or RS may be more performant. I guess since I can get different relative
> performance with even the same PDE, it would be silly for me to ask for
> guidance on when to use which? In the conclusion of Benson's and Munson's
> paper, they mention using mesh sequencing for generating initial guesses on
> finer meshes. Does anyone know whether there have been any publications
> using PETSc/TAO and mesh sequencing for solving large VI problems?
> > > >>
> > > >> A related question: what needs to be done to allow SS to run with
> `-snes_mf_operator`? RS already appears to support the option.
> > > >
> > > >   This may not make sense. Is the operator used in the SS solution
> process derivable from the function that is being optimized with the
> constraints or some strange scaled beast?
> > > >>
> > > >
> > >
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20191104/be09b0c4/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: A.dat
Type: application/octet-stream
Size: 32032 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20191104/be09b0c4/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: b.dat
Type: application/octet-stream
Size: 6416 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20191104/be09b0c4/attachment-0003.obj>