Partitioned quasi-Newton profiles

[paraynaud]

@dpo, I splitted my performance profiles about partitioned quasi-Newton methods as we discussed to clarify them.
The profiles consider partially separable problems where n=5000.
I made 3 pools:

• using exact derivatives (ADNLPModel, PSNLPModel) and usual quasi-Newton methods (TR LBFGSModel and SR1Model, and LBFGS linesearch);
  time_profile.pdf
  iter_profile.pdf
• partitioned quasi-Newton methods (PBFGSNLPModel, PSR1NLPModel, PCSNLPModel, PSENLPModel);
  iter_profile.pdf
  time_profile.pdf
• limited-memory partitioned quasi-Newton methods (PLBFGSNLPModel, PLSR1NLPModel, PLSENLPModel).
  iter_profile.pdf
  time_profile.pdf

Then, I gathered the best methods, in terms of iterations or time for a last batch of performance profiles.
I kept: a PSNLPModel, the LBFGS linesearch, PSENLPModel, PSR1NLPModel and PLSENLPModel.
iter_profile.pdf
time_profile.pdf

The conclusion remains unchanged, but are easier to deduce.

[dpo]

Thanks @paraynaud. I have a few questions:

• In the first set of profiles, I presume "LBFGS_F" and "LSR1_F" mean "forward approximations", but what is "PS" on that profile?
• Did you swap the profiles for the P and PL methods (i.e, are they in the wrong section above)?
• What is the "PCS" method?

The final profile seems to point to PSR1 as the best method. But surely, if the size of elements is sufficiently large, that method will not even be viable.

How many variables are in the element functions? How many element functions are there? Do they all have the same number of elements? Are some of them detected as convex? Do the "E" methods always use the (L)BFGS update on the convex elements?

Your conclusions will be different if all elements have very few variables or if some are quite large.

[paraynaud]

In the first set of profiles, I presume "LBFGS_F" and "LSR1_F" mean "forward approximations"

Correct! Should I change the name? (perhaps "LBFGS_TR")

but what is "PS" on that profile?

It is a PartiallySeparableNLPModel, hprod computes the exact Hessian-vector product.
First, it computes every element Hessian-vector product, and then it aggregates their results to form Hv.
The profile shows that an ADNLPModel struggles for large problems (not reaching the first order condition) while a PartiallySeparableNLPModel can make it.

Did you swap the profiles for the P and PL methods (i.e, are they in the wrong section above)?

My mistake, it was not intentional, I corrected it.

What is the "PCS" method? Are some of them detected as convex?

PCS applies BFGS on convex elements and SR1 on not convex elements.

Do the "E" methods always use the (L)BFGS update on the convex elements?

No, it is more about "SE", for Secant Equations.
These methods aim to best satisfy the secant equation, applying BFGS if the curvature condition holds or SR1 otherwise.
In the future, we could add other QN updates, but to keep it consistent with the limited-memory operators, P(L)SE supports only (L)BFGS and (L)SR1 element updates.

How many variables are in the element functions? How many element functions are there? Do they all have the same number of elements? Are some of them detected as convex?

I will produce a table (similar to this one) gathering info about the problems, including: the size, the number of elements, if it is convex or not and their type (linear, quadratic or general)

Your conclusions will be different if all elements have very few variables or if some are quite large.

The set of partially-separable problems considers problems with small elements, in the sense that storing them with dense matrices is not an issue.
That is why I want to have a second numerical result considering relatively large elements.

[paraynaud]

Here is the table (using PrettyTables) in both .md and .tex about the partially-separable problems considered.
In the vast majority of the problems, the elements remain small.
There are some problems where one element is big, but the mean of the size of the elements remains small.
You can note that constant and linear elements are not merged together, maybe I should do it before the submission.

name	n	N	M	constant	linear	quadratic	cubic	general	convex	concave	general	mininimal element dimension	mean element dimension	maximal element dimension	minimal elemental contribution (for 1 variables)	mean elemental contribution (for 1 variables)	maximal elemental contribution (for 1 variables)
arwhead5000	5000	9999	3	1	4999	0	0	4999	9999	5000	0	0	1.49985	2	2	2.9994	4999
bdqrtic5000	5000	9992	2	0	0	4996	0	4996	9992	0	0	1	3.0	5	1	5.9952	4996
brybnd5000	5000	5000	7	0	0	0	0	5000	0	0	5000	2	6.9968	7	2	6.9968	7
chnrosnb5000	5000	9998	5000	0	0	4999	0	4999	4999	0	4999	1	1.5	2	1	2.9994	3
clplatea5000	4900	19045	5	0	1	9522	0	9522	19045	1	0	1	1.9927	2	0	7.7451	8
clplateb4900	4900	19114	5	0	70	9522	0	9522	19114	70	0	1	1.98912	2	0	7.75918	8
clplatec4900	4900	19046	7	0	2	9522	0	9522	19046	2	0	1	1.99265	2	0	7.74531	8
cragglvy4900	4900	12245	5	0	0	2449	0	9796	7347	0	4898	1	1.6	2	2	3.99837	4
dixmaane4900	4899	9799	6534	1	0	6532	0	3266	4900	1	4899	0	1.49985	2	3	3.0	3
dixmaanf4899	4899	14697	6535	1	0	6532	0	8164	4900	1	9797	0	1.66653	2	4	4.99959	5
dixmaang4899	4899	14697	6535	1	0	6532	0	8164	4900	1	9797	0	1.66653	2	4	4.99959	5
dixmaanh4899	4899	14697	6535	1	0	6532	0	8164	4900	1	9797	0	1.66653	2	4	4.99959	5
dixmaani4899	4899	9799	6534	1	0	6532	0	3266	4900	1	4899	0	1.49985	2	3	3.0	3
dixmaanj4899	4899	14697	6535	1	0	6532	0	8164	4900	1	9797	0	1.66653	2	4	4.99959	5
dixmaank4899	4899	14697	6535	1	0	6532	0	8164	4900	1	9797	0	1.66653	2	4	4.99959	5
dixmaanl4899	4899	14697	6535	1	0	6532	0	8164	4900	1	9797	0	1.66653	2	4	4.99959	5
dixmaanm4899	4899	9799	9799	1	0	6532	0	3266	4900	1	4899	0	1.49985	2	3	3.0	3
dixmaann4899	4899	14697	14697	1	0	6532	0	8164	4900	1	9797	0	1.66653	2	4	4.99959	5
dixmaano4899	4899	14697	14697	1	0	6532	0	8164	4900	1	9797	0	1.66653	2	4	4.99959	5
dixmaanp4899	4899	14697	14697	1	0	6532	0	8164	4900	1	9797	0	1.66653	2	4	4.99959	5
dixon3dq4899	4899	4899	2	0	0	4899	0	0	4899	0	0	1	1.99959	2	1	1.99959	2
dqdrtic4899	4899	4899	5	0	0	4899	0	0	4899	0	0	1	1.0	1	1	1.0	1
dqrtic4899	4899	4899	4899	0	0	0	0	4899	4899	0	0	1	1.0	1	1	1.0	1
edensch4899	4899	14695	4	1	0	4898	0	9796	9797	1	4898	0	1.33324	2	2	3.99918	4
engval14899	4899	9797	3	1	4898	0	0	4898	9797	4899	0	0	1.49985	2	1	2.99939	3
errinros4899	4899	9796	4899	0	0	4898	0	4898	4898	0	4898	1	1.5	2	1	2.99939	3
extrosnb4899	4899	4899	2	0	0	1	0	4898	1	0	4898	1	1.9998	2	1	1.9998	2
fletcbv24899	4899	14698	5	0	4899	4900	0	4899	9799	4899	4899	1	1.33324	2	4	4.0	4
fletcbv34899	4899	14698	4	0	0	4900	0	9798	4900	0	9798	1	1.33324	2	4	4.0	4
freuroth4899	4899	9796	4	0	0	0	0	9796	0	0	9796	2	2.0	2	2	3.99918	4
genhumps4899	4899	9797	3	0	0	4899	0	4898	4899	0	4898	1	1.49995	2	2	2.99959	3
genrose4899	4899	9797	3	1	0	4898	0	4898	4899	1	4898	0	1.49985	2	1	2.99939	3
genrose_nash4899	4899	9797	3	1	0	4898	0	4898	4899	1	4898	0	1.49985	2	1	2.99939	3
morebv4899	4899	4899	4899	0	0	0	0	4899	0	0	4899	2	2.99959	3	2	2.99959	3
ncb204899	4899	14667	4893	1	4888	10	10	9758	9788	4889	4879	0	7.30872	20	1	21.8814	23
noncvxu24899	4899	9798	6	0	0	4899	0	4899	4899	0	4899	2	2.99959	3	4	5.99918	10
noncvxun4899	4899	9796	6	0	0	4898	0	4898	4898	0	4898	1	2.99959	3	2	5.99796	10
nondia4899	4899	4899	2	0	0	1	0	4898	1	0	4898	1	1.9998	2	1	1.9998	4899
nondquar4899	4899	4899	2	0	0	2	0	4897	4899	0	0	2	2.99959	3	2	2.99959	4898
penalty34899	4899	2454	6	1	0	2449	0	4	2450	1	4	0	8.98289	4899	3	4.49969	5
powellsg4899	4896	4896	4	0	0	2448	0	2448	4896	0	0	2	2.0	2	2	2.0	2
quartc4896	4896	4896	4896	0	0	0	0	4896	4896	0	0	1	1.0	1	1	1.0	1
sbrybnd4896	4896	4896	4896	0	0	0	0	4896	0	0	4896	2	6.99673	7	2	6.99673	7
schmvett4896	4896	14682	3	0	0	0	0	14682	0	0	14682	2	2.33333	3	2	6.99714	7
sinquad4896	4896	4896	3	0	0	0	0	4896	1	0	4895	1	2.99939	3	1	2.99939	4896
sparsine4896	4896	4896	4896	0	0	0	0	4896	0	0	4896	1	5.99285	6	4	5.99285	9
sparsqur4896	4896	4896	4896	0	0	0	0	4896	4896	0	0	1	5.99285	6	4	5.99285	9
spmsrtls4896	4897	9791	9791	0	0	0	0	9791	0	0	9791	1	2.16658	3	3	4.33184	5
srosenbr4897	4896	4896	2	0	0	2448	0	2448	2448	0	2448	1	1.5	2	1	1.5	2
tointgss4896	4896	4894	2	0	0	0	0	4894	0	0	4894	3	3.0	3	1	2.99877	3
tquartic4896	4896	4895	2	0	0	1	0	4894	1	0	4894	1	1.9998	2	0	1.99939	4895
tridia4896	4896	4896	4896	0	0	4896	0	0	4896	0	0	1	1.9998	2	1	1.9998	2
vardim4896	4896	4898	3	0	0	4897	0	1	4898	0	0	1	2.99878	4896	3	3.0	3
woods4896	4896	7344	5	0	0	4896	0	2448	4896	0	2448	1	1.66667	2	2	2.5	3

\begin{table}
  \begin{tabular}{rrrrrrrrrrrrrrrrrr}
    \hline\hline
    \textbf{name} & \textbf{n} & \textbf{N} & \textbf{M} & \textbf{constant} & \textbf{linear} & \textbf{quadratic} & \textbf{cubic} & \textbf{general} & \textbf{convex} & \textbf{concave} & \textbf{general} & \textbf{mininimal element dimension} & \textbf{mean element dimension} & \textbf{maximal element dimension} & \textbf{minimal elemental contribution (for 1 variables)} & \textbf{mean elemental contribution (for 1 variables)} & \textbf{maximal elemental contribution (for 1 variables)} \\\hline
    arwhead5000 & 5000 & 9999 & 3 & 1 & 4999 & 0 & 0 & 4999 & 9999 & 5000 & 0 & 0 & 1.49985 & 2 & 2 & 2.9994 & 4999 \\
    bdqrtic5000 & 5000 & 9992 & 2 & 0 & 0 & 4996 & 0 & 4996 & 9992 & 0 & 0 & 1 & 3.0 & 5 & 1 & 5.9952 & 4996 \\
    brybnd5000 & 5000 & 5000 & 7 & 0 & 0 & 0 & 0 & 5000 & 0 & 0 & 5000 & 2 & 6.9968 & 7 & 2 & 6.9968 & 7 \\
    chnrosnb5000 & 5000 & 9998 & 5000 & 0 & 0 & 4999 & 0 & 4999 & 4999 & 0 & 4999 & 1 & 1.5 & 2 & 1 & 2.9994 & 3 \\
    clplatea5000 & 4900 & 19045 & 5 & 0 & 1 & 9522 & 0 & 9522 & 19045 & 1 & 0 & 1 & 1.9927 & 2 & 0 & 7.7451 & 8 \\
    clplateb4900 & 4900 & 19114 & 5 & 0 & 70 & 9522 & 0 & 9522 & 19114 & 70 & 0 & 1 & 1.98912 & 2 & 0 & 7.75918 & 8 \\
    clplatec4900 & 4900 & 19046 & 7 & 0 & 2 & 9522 & 0 & 9522 & 19046 & 2 & 0 & 1 & 1.99265 & 2 & 0 & 7.74531 & 8 \\
    cragglvy4900 & 4900 & 12245 & 5 & 0 & 0 & 2449 & 0 & 9796 & 7347 & 0 & 4898 & 1 & 1.6 & 2 & 2 & 3.99837 & 4 \\
    dixmaane4900 & 4899 & 9799 & 6534 & 1 & 0 & 6532 & 0 & 3266 & 4900 & 1 & 4899 & 0 & 1.49985 & 2 & 3 & 3.0 & 3 \\
    dixmaanf4899 & 4899 & 14697 & 6535 & 1 & 0 & 6532 & 0 & 8164 & 4900 & 1 & 9797 & 0 & 1.66653 & 2 & 4 & 4.99959 & 5 \\
    dixmaang4899 & 4899 & 14697 & 6535 & 1 & 0 & 6532 & 0 & 8164 & 4900 & 1 & 9797 & 0 & 1.66653 & 2 & 4 & 4.99959 & 5 \\
    dixmaanh4899 & 4899 & 14697 & 6535 & 1 & 0 & 6532 & 0 & 8164 & 4900 & 1 & 9797 & 0 & 1.66653 & 2 & 4 & 4.99959 & 5 \\
    dixmaani4899 & 4899 & 9799 & 6534 & 1 & 0 & 6532 & 0 & 3266 & 4900 & 1 & 4899 & 0 & 1.49985 & 2 & 3 & 3.0 & 3 \\
    dixmaanj4899 & 4899 & 14697 & 6535 & 1 & 0 & 6532 & 0 & 8164 & 4900 & 1 & 9797 & 0 & 1.66653 & 2 & 4 & 4.99959 & 5 \\
    dixmaank4899 & 4899 & 14697 & 6535 & 1 & 0 & 6532 & 0 & 8164 & 4900 & 1 & 9797 & 0 & 1.66653 & 2 & 4 & 4.99959 & 5 \\
    dixmaanl4899 & 4899 & 14697 & 6535 & 1 & 0 & 6532 & 0 & 8164 & 4900 & 1 & 9797 & 0 & 1.66653 & 2 & 4 & 4.99959 & 5 \\
    dixmaanm4899 & 4899 & 9799 & 9799 & 1 & 0 & 6532 & 0 & 3266 & 4900 & 1 & 4899 & 0 & 1.49985 & 2 & 3 & 3.0 & 3 \\
    dixmaann4899 & 4899 & 14697 & 14697 & 1 & 0 & 6532 & 0 & 8164 & 4900 & 1 & 9797 & 0 & 1.66653 & 2 & 4 & 4.99959 & 5 \\
    dixmaano4899 & 4899 & 14697 & 14697 & 1 & 0 & 6532 & 0 & 8164 & 4900 & 1 & 9797 & 0 & 1.66653 & 2 & 4 & 4.99959 & 5 \\
    dixmaanp4899 & 4899 & 14697 & 14697 & 1 & 0 & 6532 & 0 & 8164 & 4900 & 1 & 9797 & 0 & 1.66653 & 2 & 4 & 4.99959 & 5 \\
    dixon3dq4899 & 4899 & 4899 & 2 & 0 & 0 & 4899 & 0 & 0 & 4899 & 0 & 0 & 1 & 1.99959 & 2 & 1 & 1.99959 & 2 \\
    dqdrtic4899 & 4899 & 4899 & 5 & 0 & 0 & 4899 & 0 & 0 & 4899 & 0 & 0 & 1 & 1.0 & 1 & 1 & 1.0 & 1 \\
    dqrtic4899 & 4899 & 4899 & 4899 & 0 & 0 & 0 & 0 & 4899 & 4899 & 0 & 0 & 1 & 1.0 & 1 & 1 & 1.0 & 1 \\
    edensch4899 & 4899 & 14695 & 4 & 1 & 0 & 4898 & 0 & 9796 & 9797 & 1 & 4898 & 0 & 1.33324 & 2 & 2 & 3.99918 & 4 \\
    engval14899 & 4899 & 9797 & 3 & 1 & 4898 & 0 & 0 & 4898 & 9797 & 4899 & 0 & 0 & 1.49985 & 2 & 1 & 2.99939 & 3 \\
    errinros4899 & 4899 & 9796 & 4899 & 0 & 0 & 4898 & 0 & 4898 & 4898 & 0 & 4898 & 1 & 1.5 & 2 & 1 & 2.99939 & 3 \\
    extrosnb4899 & 4899 & 4899 & 2 & 0 & 0 & 1 & 0 & 4898 & 1 & 0 & 4898 & 1 & 1.9998 & 2 & 1 & 1.9998 & 2 \\
    fletcbv24899 & 4899 & 14698 & 5 & 0 & 4899 & 4900 & 0 & 4899 & 9799 & 4899 & 4899 & 1 & 1.33324 & 2 & 4 & 4.0 & 4 \\
    fletcbv34899 & 4899 & 14698 & 4 & 0 & 0 & 4900 & 0 & 9798 & 4900 & 0 & 9798 & 1 & 1.33324 & 2 & 4 & 4.0 & 4 \\
    freuroth4899 & 4899 & 9796 & 4 & 0 & 0 & 0 & 0 & 9796 & 0 & 0 & 9796 & 2 & 2.0 & 2 & 2 & 3.99918 & 4 \\
    genhumps4899 & 4899 & 9797 & 3 & 0 & 0 & 4899 & 0 & 4898 & 4899 & 0 & 4898 & 1 & 1.49995 & 2 & 2 & 2.99959 & 3 \\
    genrose4899 & 4899 & 9797 & 3 & 1 & 0 & 4898 & 0 & 4898 & 4899 & 1 & 4898 & 0 & 1.49985 & 2 & 1 & 2.99939 & 3 \\
    genrose_nash4899 & 4899 & 9797 & 3 & 1 & 0 & 4898 & 0 & 4898 & 4899 & 1 & 4898 & 0 & 1.49985 & 2 & 1 & 2.99939 & 3 \\
    morebv4899 & 4899 & 4899 & 4899 & 0 & 0 & 0 & 0 & 4899 & 0 & 0 & 4899 & 2 & 2.99959 & 3 & 2 & 2.99959 & 3 \\
    ncb204899 & 4899 & 14667 & 4893 & 1 & 4888 & 10 & 10 & 9758 & 9788 & 4889 & 4879 & 0 & 7.30872 & 20 & 1 & 21.8814 & 23 \\
    noncvxu24899 & 4899 & 9798 & 6 & 0 & 0 & 4899 & 0 & 4899 & 4899 & 0 & 4899 & 2 & 2.99959 & 3 & 4 & 5.99918 & 10 \\
    noncvxun4899 & 4899 & 9796 & 6 & 0 & 0 & 4898 & 0 & 4898 & 4898 & 0 & 4898 & 1 & 2.99959 & 3 & 2 & 5.99796 & 10 \\
    nondia4899 & 4899 & 4899 & 2 & 0 & 0 & 1 & 0 & 4898 & 1 & 0 & 4898 & 1 & 1.9998 & 2 & 1 & 1.9998 & 4899 \\
    nondquar4899 & 4899 & 4899 & 2 & 0 & 0 & 2 & 0 & 4897 & 4899 & 0 & 0 & 2 & 2.99959 & 3 & 2 & 2.99959 & 4898 \\
    penalty34899 & 4899 & 2454 & 6 & 1 & 0 & 2449 & 0 & 4 & 2450 & 1 & 4 & 0 & 8.98289 & 4899 & 3 & 4.49969 & 5 \\
    powellsg4899 & 4896 & 4896 & 4 & 0 & 0 & 2448 & 0 & 2448 & 4896 & 0 & 0 & 2 & 2.0 & 2 & 2 & 2.0 & 2 \\
    quartc4896 & 4896 & 4896 & 4896 & 0 & 0 & 0 & 0 & 4896 & 4896 & 0 & 0 & 1 & 1.0 & 1 & 1 & 1.0 & 1 \\
    sbrybnd4896 & 4896 & 4896 & 4896 & 0 & 0 & 0 & 0 & 4896 & 0 & 0 & 4896 & 2 & 6.99673 & 7 & 2 & 6.99673 & 7 \\
    schmvett4896 & 4896 & 14682 & 3 & 0 & 0 & 0 & 0 & 14682 & 0 & 0 & 14682 & 2 & 2.33333 & 3 & 2 & 6.99714 & 7 \\
    sinquad4896 & 4896 & 4896 & 3 & 0 & 0 & 0 & 0 & 4896 & 1 & 0 & 4895 & 1 & 2.99939 & 3 & 1 & 2.99939 & 4896 \\
    sparsine4896 & 4896 & 4896 & 4896 & 0 & 0 & 0 & 0 & 4896 & 0 & 0 & 4896 & 1 & 5.99285 & 6 & 4 & 5.99285 & 9 \\
    sparsqur4896 & 4896 & 4896 & 4896 & 0 & 0 & 0 & 0 & 4896 & 4896 & 0 & 0 & 1 & 5.99285 & 6 & 4 & 5.99285 & 9 \\
    spmsrtls4896 & 4897 & 9791 & 9791 & 0 & 0 & 0 & 0 & 9791 & 0 & 0 & 9791 & 1 & 2.16658 & 3 & 3 & 4.33184 & 5 \\
    srosenbr4897 & 4896 & 4896 & 2 & 0 & 0 & 2448 & 0 & 2448 & 2448 & 0 & 2448 & 1 & 1.5 & 2 & 1 & 1.5 & 2 \\
    tointgss4896 & 4896 & 4894 & 2 & 0 & 0 & 0 & 0 & 4894 & 0 & 0 & 4894 & 3 & 3.0 & 3 & 1 & 2.99877 & 3 \\
    tquartic4896 & 4896 & 4895 & 2 & 0 & 0 & 1 & 0 & 4894 & 1 & 0 & 4894 & 1 & 1.9998 & 2 & 0 & 1.99939 & 4895 \\
    tridia4896 & 4896 & 4896 & 4896 & 0 & 0 & 4896 & 0 & 0 & 4896 & 0 & 0 & 1 & 1.9998 & 2 & 1 & 1.9998 & 2 \\
    vardim4896 & 4896 & 4898 & 3 & 0 & 0 & 4897 & 0 & 1 & 4898 & 0 & 0 & 1 & 2.99878 & 4896 & 3 & 3.0 & 3 \\
    woods4896 & 4896 & 7344 & 5 & 0 & 0 & 4896 & 0 & 2448 & 4896 & 0 & 2448 & 1 & 1.66667 & 2 & 2 & 2.5 & 3 \\\hline\hline
  \end{tabular}
\end{table}