[petsc-users] VI: RS vs SS

Fri Nov 1 10:18:59 CDT 2019

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?
> > >> 
> > > 
> > 
> 