Trust-region method got stuck at the maxcut problem.

[yuwenchen95]

Hi, I'm trying to use trust-region method to solve my maxcut problem but it seems to get stuck and converges quite slow compared to the Riemmanian gradient descent:

julia> include("test_manifolds.jl")
Initial  |  | F(x): 7240.556222
# 1      | Last Change: 51.691636 | F(x): 18.772602
# 2      | Last Change: 57.257111 | F(x): -28.735368
# 3      | Last Change: 33.131624 | F(x): -114.373536
# 4      | Last Change: 75.910744 | F(x): -134.610116
# 5      | Last Change: 21.069623 | F(x): -965.695033
# 6      | Last Change: 7.228024 | F(x): -1319.537624
# 7      | Last Change: 5.029343 | F(x): -1520.853110
# 8      | Last Change: 8.020609 | F(x): -1606.320624
# 9      | Last Change: 7.102618 | F(x): -1784.142436
# 10     | Last Change: 5.572008 | F(x): -1907.952948
# 11     | Last Change: 4.495797 | F(x): -1998.779608
# 12     | Last Change: 3.709804 | F(x): -2068.668458
# 13     | Last Change: 3.115326 | F(x): -2123.711060
# 14     | Last Change: 2.657788 | F(x): -2168.211414
# 15     | Last Change: 2.298452 | F(x): -2204.785086
# 16     | Last Change: 2.012513 | F(x): -2235.366959
# 17     | Last Change: 3.562753 | F(x): -2237.184007
# 18     | Last Change: 3.609978 | F(x): -2268.512122
# 19     | Last Change: 3.131794 | F(x): -2293.699280
# 20     | Last Change: 2.740499 | F(x): -2314.467586
# 21     | Last Change: 2.415960 | F(x): -2331.850003
# 22     | Last Change: 2.144424 | F(x): -2346.646443
# 23     | Last Change: 1.914799 | F(x): -2359.381925
# 24     | Last Change: 1.719148 | F(x): -2370.471276
# 25     | Last Change: 1.551028 | F(x): -2380.207159
# 26     | Last Change: 1.405658 | F(x): -2388.825053
# 27     | Last Change: 1.279122 | F(x): -2396.501057
# 28     | Last Change: 1.168422 | F(x): -2403.379266
# 29     | Last Change: 1.071073 | F(x): -2409.572491
# 30     | Last Change: 0.985114 | F(x): -2415.174485
# 31     | Last Change: 0.908902 | F(x): -2420.261269
# 32     | Last Change: 0.841103 | F(x): -2424.896917
# 33     | Last Change: 0.780589 | F(x): -2429.134776
# 34     | Last Change: 0.726422 | F(x): -2433.020381
# 35     | Last Change: 0.677801 | F(x): -2436.592408
# 36     | Last Change: 1.268092 | F(x): -2436.891466
# 37     | Last Change: 1.333426 | F(x): -2440.723743
# 38     | Last Change: 1.223546 | F(x): -2444.171927
# 39     | Last Change: 1.124441 | F(x): -2447.288259
# 40     | Last Change: 1.034921 | F(x): -2450.117246
# 41     | Last Change: 0.953933 | F(x): -2452.695186
# 42     | Last Change: 0.880576 | F(x): -2455.053179
# 43     | Last Change: 0.814049 | F(x): -2457.217084
# 44     | Last Change: 0.753658 | F(x): -2459.209189
# 45     | Last Change: 0.698784 | F(x): -2461.048331
# 46     | Last Change: 0.648883 | F(x): -2462.750852
# 47     | Last Change: 0.603469 | F(x): -2464.330750
# 48     | Last Change: 0.562113 | F(x): -2465.800256
# 49     | Last Change: 0.524426 | F(x): -2467.169969
# 50     | Last Change: 0.490066 | F(x): -2468.449212
# 51     | Last Change: 0.458721 | F(x): -2469.646149
# 52     | Last Change: 0.430112 | F(x): -2470.768009
# 53     | Last Change: 0.403986 | F(x): -2471.821178
# 54     | Last Change: 0.380117 | F(x): -2472.811349
# 55     | Last Change: 0.358298 | F(x): -2473.743593
# 56     | Last Change: 0.338341 | F(x): -2474.622453
# 57     | Last Change: 0.640151 | F(x): -2474.662099
# 58     | Last Change: 0.682292 | F(x): -2475.642484
# 59     | Last Change: 0.632425 | F(x): -2476.546959
# 60     | Last Change: 0.586691 | F(x): -2477.383992
# 61     | Last Change: 0.544741 | F(x): -2478.160850
# 62     | Last Change: 0.506259 | F(x): -2478.883853
# 63     | Last Change: 0.470956 | F(x): -2479.558468
# 64     | Last Change: 0.438571 | F(x): -2480.189470
# 65     | Last Change: 0.408864 | F(x): -2480.781020
# 66     | Last Change: 0.381615 | F(x): -2481.336775
# 67     | Last Change: 0.356624 | F(x): -2481.859942
# 68     | Last Change: 0.333706 | F(x): -2482.353353
# 69     | Last Change: 0.312694 | F(x): -2482.819511
# 70     | Last Change: 0.293431 | F(x): -2483.260638
# 71     | Last Change: 0.275776 | F(x): -2483.678710
# 72     | Last Change: 0.259596 | F(x): -2484.075494
# 73     | Last Change: 0.244770 | F(x): -2484.452569
# 74     | Last Change: 0.231187 | F(x): -2484.811355
# 75     | Last Change: 0.218742 | F(x): -2485.153130
# 76     | Last Change: 0.207339 | F(x): -2485.479050
# 77     | Last Change: 0.393784 | F(x): -2485.482937
# 78     | Last Change: 0.422638 | F(x): -2485.856288
# 79     | Last Change: 0.392830 | F(x): -2486.204291
# 80     | Last Change: 0.365401 | F(x): -2486.529622
# 81     | Last Change: 0.340167 | F(x): -2486.834604
# 82     | Last Change: 0.316958 | F(x): -2487.121259
# 83     | Last Change: 0.295618 | F(x): -2487.391353
# 84     | Last Change: 0.276004 | F(x): -2487.646428
# 85     | Last Change: 0.257981 | F(x): -2487.887838
# 86     | Last Change: 0.241428 | F(x): -2488.116773
# 87     | Last Change: 0.226231 | F(x): -2488.334280
# 88     | Last Change: 0.212284 | F(x): -2488.541287
# 89     | Last Change: 0.199491 | F(x): -2488.738614
# 90     | Last Change: 0.187761 | F(x): -2488.926991
# 91     | Last Change: 0.177011 | F(x): -2489.107070
# 92     | Last Change: 0.167162 | F(x): -2489.279430
# 93     | Last Change: 0.158143 | F(x): -2489.444596
# 94     | Last Change: 0.149887 | F(x): -2489.603035
# 95     | Last Change: 0.142330 | F(x): -2489.755171
# 96     | Last Change: 0.135414 | F(x): -2489.901389
# 97     | Last Change: 0.258170 | F(x): -2489.930760
# 98     | Last Change: 0.271652 | F(x): -2490.097161
# 99     | Last Change: 0.252973 | F(x): -2490.253632
# 100    | Last Change: 0.235779 | F(x): -2490.401178
The algorithm reached its maximal number of iterations (100).
  0.800338 seconds (264.57 k allocations: 416.860 MiB, 16.39% compilation time: 67% of which was recompilation)
Initial  |  | F(x): 7224.184508
# 1      | Last Change: 22.079402 | F(x): 406.268111
# 2      | Last Change: 29.141967 | F(x): -50.297494
# 3      | Last Change: 21.874585 | F(x): -982.377500
# 4      | Last Change: 20.877952 | F(x): -982.391475
# 5      | Last Change: 21.024332 | F(x): -1199.037568
# 6      | Last Change: 21.356842 | F(x): -1338.946474
# 7      | Last Change: 20.352880 | F(x): -1338.957055
# 8      | Last Change: 20.505273 | F(x): -1448.399253
# 9      | Last Change: 20.859076 | F(x): -1589.588929
# 10     | Last Change: 19.847726 | F(x): -1589.617018
# 11     | Last Change: 19.847361 | F(x): -1589.645105
# 12     | Last Change: 19.846996 | F(x): -1589.673190
# 13     | Last Change: 19.846631 | F(x): -1589.701272
# 14     | Last Change: 19.846266 | F(x): -1589.729351
# 15     | Last Change: 19.845901 | F(x): -1589.757429
# 16     | Last Change: 19.845536 | F(x): -1589.785504
# 17     | Last Change: 19.845171 | F(x): -1589.813576
# 18     | Last Change: 19.844806 | F(x): -1589.841647
# 19     | Last Change: 19.844441 | F(x): -1589.869715
# 20     | Last Change: 19.844076 | F(x): -1589.897780
# 21     | Last Change: 19.843711 | F(x): -1589.925844
# 22     | Last Change: 19.843346 | F(x): -1589.953905
# 23     | Last Change: 19.842981 | F(x): -1589.981963
# 24     | Last Change: 19.842617 | F(x): -1590.010020
# 25     | Last Change: 19.842252 | F(x): -1590.038074
# 26     | Last Change: 19.841887 | F(x): -1590.066125
# 27     | Last Change: 19.841522 | F(x): -1590.094175
# 28     | Last Change: 19.841157 | F(x): -1590.122222
# 29     | Last Change: 19.840792 | F(x): -1590.150266
# 30     | Last Change: 19.840427 | F(x): -1590.178309
# 31     | Last Change: 19.840062 | F(x): -1590.206349
# 32     | Last Change: 19.839697 | F(x): -1590.234386
# 33     | Last Change: 19.839332 | F(x): -1590.262422
# 34     | Last Change: 19.838967 | F(x): -1590.290455
# 35     | Last Change: 19.838602 | F(x): -1590.318486
# 36     | Last Change: 19.838237 | F(x): -1590.346514
# 37     | Last Change: 19.837872 | F(x): -1590.374540
# 38     | Last Change: 19.837507 | F(x): -1590.402564
# 39     | Last Change: 19.837142 | F(x): -1590.430585
# 40     | Last Change: 19.836777 | F(x): -1590.458605
# 41     | Last Change: 19.836413 | F(x): -1590.486621
# 42     | Last Change: 19.836048 | F(x): -1590.514636
# 43     | Last Change: 19.835683 | F(x): -1590.542648
# 44     | Last Change: 19.835318 | F(x): -1590.570658
# 45     | Last Change: 19.834953 | F(x): -1590.598666
# 46     | Last Change: 19.834588 | F(x): -1590.626671
# 47     | Last Change: 19.834223 | F(x): -1590.654674
# 48     | Last Change: 19.833858 | F(x): -1590.682674
# 49     | Last Change: 19.833493 | F(x): -1590.710673
# 50     | Last Change: 19.833128 | F(x): -1590.738669
# 51     | Last Change: 19.832763 | F(x): -1590.766662
# 52     | Last Change: 19.832398 | F(x): -1590.794654
# 53     | Last Change: 19.832034 | F(x): -1590.822643
# 54     | Last Change: 19.831669 | F(x): -1590.850629
# 55     | Last Change: 19.831304 | F(x): -1590.878614
# 56     | Last Change: 19.830939 | F(x): -1590.906596
# 57     | Last Change: 19.830574 | F(x): -1590.934576
# 58     | Last Change: 19.830209 | F(x): -1590.962553
# 59     | Last Change: 19.829844 | F(x): -1590.990529
# 60     | Last Change: 19.829479 | F(x): -1591.018502
# 61     | Last Change: 19.829114 | F(x): -1591.046472
# 62     | Last Change: 19.828749 | F(x): -1591.074441
# 63     | Last Change: 19.828385 | F(x): -1591.102407
# 64     | Last Change: 19.828020 | F(x): -1591.130370
# 65     | Last Change: 19.827655 | F(x): -1591.158332
# 66     | Last Change: 19.827290 | F(x): -1591.186291
# 67     | Last Change: 19.826925 | F(x): -1591.214248
# 68     | Last Change: 19.826560 | F(x): -1591.242202
# 69     | Last Change: 19.826195 | F(x): -1591.270154
# 70     | Last Change: 19.825830 | F(x): -1591.298104
# 71     | Last Change: 19.825465 | F(x): -1591.326052
# 72     | Last Change: 19.825101 | F(x): -1591.353997
# 73     | Last Change: 19.824736 | F(x): -1591.381940
# 74     | Last Change: 19.824371 | F(x): -1591.409881
# 75     | Last Change: 19.824006 | F(x): -1591.437820
# 76     | Last Change: 19.823641 | F(x): -1591.465756
# 77     | Last Change: 19.823276 | F(x): -1591.493690
# 78     | Last Change: 19.822911 | F(x): -1591.521621
# 79     | Last Change: 19.822546 | F(x): -1591.549550
# 80     | Last Change: 19.822182 | F(x): -1591.577477
# 81     | Last Change: 19.821817 | F(x): -1591.605402
# 82     | Last Change: 19.821452 | F(x): -1591.633325
# 83     | Last Change: 19.821087 | F(x): -1591.661245
# 84     | Last Change: 19.820722 | F(x): -1591.689163
# 85     | Last Change: 19.820357 | F(x): -1591.717078
# 86     | Last Change: 19.819992 | F(x): -1591.744992
# 87     | Last Change: 19.819627 | F(x): -1591.772903
# 88     | Last Change: 19.819263 | F(x): -1591.800811
# 89     | Last Change: 19.818898 | F(x): -1591.828718
# 90     | Last Change: 19.818533 | F(x): -1591.856622
# 91     | Last Change: 19.818168 | F(x): -1591.884524
# 92     | Last Change: 19.817803 | F(x): -1591.912423
# 93     | Last Change: 19.817438 | F(x): -1591.940321
# 94     | Last Change: 19.817074 | F(x): -1591.968216
# 95     | Last Change: 19.816709 | F(x): -1591.996108
# 96     | Last Change: 19.816344 | F(x): -1592.023999
# 97     | Last Change: 19.815979 | F(x): -1592.051887
# 98     | Last Change: 19.815614 | F(x): -1592.079773
# 99     | Last Change: 19.815249 | F(x): -1592.107657
# 100    | Last Change: 19.814884 | F(x): -1592.135538
The algorithm reached its maximal number of iterations (100).

If I increase the maximum radius, it could escape this suboptimal point but the convergence is still slow compared to the matlab manopt that converges superlinearly at the end.

Here is my source code and data. Glad if you can help to solve it!
maxcut_problem.zip

Btw, I'm testing various algorithms in Manopt.jl and wondering whether I can record time after each iteration via get_record() function, like what you have done for cost per iteration.

[kellertuer]

I do no Thale much experience with trust regions and what are its best parameters, so I can not help you on that much I fear. Can you maybe check a few papers on good parameters there? To be honest, the TR was a student project and was used for a few examples there but not much more until now.

The possibility to print and/or record time is on this PR
#146

where I was waiting for some feedback, but sure we could merge that somewhen next week.

edit: I changed you output to code so it looks a little nicer in your post, I hope that is ok.

[yuwenchen95]

Thanks! I would take a look at other papers. Looking forward to seeing a new release with record time!

[kellertuer]

Great. The new release will hopefully be in the next few days.

[kellertuer]

Time measurements are now available in Manopt 0.3.40