search

ZIB-IOL / FrankWolfe.jl

Julia implementation for various Frank-Wolfe and Conditional Gradient variants
MIT License
95 stars 18 forks source link

SD steps in blended conditional gradients are not counted correctly anymore #362

Open pokutta opened 2 years ago

pokutta commented 2 years ago

The SD steps in blended conditional gradients are not counted correctly anymore in the iteration counter, i.e., they do not increase the iteration counter but the should do not call the lmo. 

seed = 0x646ca563610c1ad6
WARNING: redefinition of constant ws. This may fail, cause incorrect answers, or produce other errors.
WARNING: redefinition of constant Xs. This may fail, cause incorrect answers, or produce other errors.
WARNING: redefinition of constant ys. This may fail, cause incorrect answers, or produce other errors.

Blended Conditional Gradients Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Adaptive EPSILON: 1.0e-5 MAXITERATION: 100 TYPE: Float64
GRADIENTTYPE: Vector{Float64} lazy_tolerance: 2.0
[ Info: In memory_mode memory iterates are written back into x0!

-------------------------------------------------------------------------------------------------------------------------------
  Type     Iteration         Primal           Dual       Dual Gap           Time         It/sec     #ActiveSet   #non-simplex
-------------------------------------------------------------------------------------------------------------------------------
     I             1   9.574652e-01   8.448201e-01   1.126451e-01   0.000000e+00            Inf              1              0
    SD             2   9.146165e-01   8.019714e-01   1.126451e-01   3.479529e-01   5.747905e+00              1              1
    FW             3   9.146165e-01   8.019714e-01   1.126451e-01   3.473538e-01   8.636728e+00              1              1
    SD             4   8.769440e-01   7.642988e-01   1.126451e-01   4.129531e-01   9.686329e+00              2              2
    SD             4   8.714995e-01   7.588544e-01   1.126451e-01   4.132765e-01   9.678749e+00              2              2
    SD             4   8.691161e-01   7.564709e-01   1.126451e-01   4.135874e-01   9.671475e+00              2              2
    SD             4   8.682814e-01   7.556363e-01   1.126451e-01   4.139018e-01   9.664127e+00              2              2
    FW             8   8.682814e-01   7.556363e-01   1.126451e-01   4.125739e-01   1.939046e+01              2              2
    SD             9   8.568614e-01   7.442163e-01   1.126451e-01   4.155088e-01   2.166019e+01              2              3
    SD             9   8.537008e-01   7.410557e-01   1.126451e-01   4.158706e-01   2.164135e+01              2              3
    SD             9   8.513126e-01   7.386675e-01   1.126451e-01   4.161758e-01   2.162547e+01              2              3
    SD             9   8.495989e-01   7.369538e-01   1.126451e-01   4.164731e-01   2.161004e+01              2              3
    SD             9   8.484366e-01   7.357915e-01   1.126451e-01   4.167696e-01   2.159466e+01              2              3
    SD             9   8.476904e-01   7.350453e-01   1.126451e-01   4.170674e-01   2.157925e+01              2              3
    SD             9   8.472333e-01   7.345882e-01   1.126451e-01   4.173604e-01   2.156410e+01              2              3
    FW            16   8.472333e-01   7.345882e-01   1.126451e-01   4.154312e-01   3.851420e+01              2              3
    SD            17   8.449956e-01   7.323505e-01   1.126451e-01   4.191506e-01   4.055822e+01              3              4
    SD            17   8.446345e-01   7.319894e-01   1.126451e-01   4.194443e-01   4.052982e+01              3              4
    SD            17   8.443774e-01   7.317322e-01   1.126451e-01   4.197365e-01   4.050160e+01              3              4
    FW            20   8.443774e-01   7.317322e-01   1.126451e-01   4.189845e-01   4.773446e+01              3              4
    SD            21   8.430225e-01   7.303774e-01   1.126451e-01   4.215344e-01   4.981800e+01              4              5
    LD            22   8.430225e-01   7.303774e-01   1.126451e-01   4.213689e-01   5.221078e+01              4              5
    SD            23   8.428995e-01   8.195742e-01   2.332530e-02   4.231660e-01   5.435220e+01              4              6
    SD            23   8.428074e-01   8.194821e-01   2.332530e-02   4.235015e-01   5.430913e+01              4              6
    SD            23   8.427383e-01   8.194130e-01   2.332530e-02   4.238079e-01   5.426987e+01              4              6
    SD            23   8.426859e-01   8.193606e-01   2.332530e-02   4.241052e-01   5.423183e+01              4              6
    SD            23   8.426456e-01   8.193203e-01   2.332530e-02   4.244007e-01   5.419407e+01              4              6
    SD            23   8.426139e-01   8.192886e-01   2.332530e-02   4.246907e-01   5.415706e+01              4              6
    SD            23   8.425884e-01   8.192631e-01   2.332530e-02   4.249884e-01   5.411912e+01              4              6
    SD            23   8.425671e-01   8.192418e-01   2.332530e-02   4.252807e-01   5.408193e+01              4              6
    SD            23   8.425490e-01   8.192237e-01   2.332530e-02   4.255712e-01   5.404501e+01              4              6
    SD            23   8.425331e-01   8.192078e-01   2.332530e-02   4.258607e-01   5.400827e+01              4              6
    SD            23   8.425188e-01   8.191935e-01   2.332530e-02   4.261508e-01   5.397150e+01              4              6
    SD            23   8.425059e-01   8.191806e-01   2.332530e-02   4.264453e-01   5.393423e+01              4              6
    SD            23   8.424941e-01   8.191688e-01   2.332530e-02   4.267410e-01   5.389687e+01              4              6
    SD            23   8.424832e-01   8.191579e-01   2.332530e-02   4.270325e-01   5.386007e+01              4              6
    SD            23   8.424730e-01   8.191477e-01   2.332530e-02   4.273223e-01   5.382354e+01              4              6
    SD            23   8.424634e-01   8.191382e-01   2.332530e-02   4.276107e-01   5.378724e+01              4              6
    FW            39   8.424634e-01   8.191382e-01   2.332530e-02   4.229794e-01   9.220308e+01              4              6
    FW            40   8.423609e-01   8.190356e-01   2.332530e-02   4.281071e-01   9.343456e+01              4              7
    SD            41   8.417019e-01   8.183766e-01   2.332530e-02   4.295077e-01   9.545812e+01              5              8
    SD            41   8.416335e-01   8.183082e-01   2.332530e-02   4.298035e-01   9.539243e+01              5              8
    SD            41   8.415787e-01   8.182534e-01   2.332530e-02   4.300962e-01   9.532751e+01              5              8
    SD            41   8.415335e-01   8.182082e-01   2.332530e-02   4.303868e-01   9.526314e+01              5              8
    SD            41   8.414947e-01   8.181694e-01   2.332530e-02   4.306775e-01   9.519885e+01              5              8
    SD            41   8.413867e-01   8.180614e-01   2.332530e-02   4.309509e-01   9.513845e+01              4              8
    SD            41   8.413021e-01   8.179768e-01   2.332530e-02   4.312432e-01   9.507396e+01              4              8
    SD            41   8.412373e-01   8.179120e-01   2.332530e-02   4.315351e-01   9.500966e+01              4              8
    SD            41   8.411875e-01   8.178622e-01   2.332530e-02   4.318311e-01   9.494453e+01              4              8
    SD            41   8.411489e-01   8.178236e-01   2.332530e-02   4.321234e-01   9.488030e+01              4              8
    SD            41   8.411189e-01   8.177936e-01   2.332530e-02   4.324110e-01   9.481720e+01              4              8
    SD            41   8.410953e-01   8.177700e-01   2.332530e-02   4.327023e-01   9.475337e+01              4              8
    SD            41   8.410767e-01   8.177514e-01   2.332530e-02   4.329929e-01   9.468978e+01              4              8
    SD            41   8.410619e-01   8.177366e-01   2.332530e-02   4.332810e-01   9.462680e+01              4              8
    SD            41   8.410500e-01   8.177247e-01   2.332530e-02   4.335683e-01   9.456410e+01              4              8
    SD            41   8.410404e-01   8.177151e-01   2.332530e-02   4.338651e-01   9.449942e+01              4              8
    SD            41   8.410325e-01   8.177072e-01   2.332530e-02   4.341550e-01   9.443631e+01              4              8
    SD            41   8.410261e-01   8.177008e-01   2.332530e-02   4.344441e-01   9.437347e+01              4              8
    FW            59   8.410261e-01   8.177008e-01   2.332530e-02   4.293405e-01   1.374201e+02              4              8
    FW            60   8.409942e-01   8.176689e-01   2.332530e-02   4.349433e-01   1.379490e+02              4              9
    SD            61   8.407277e-01   8.174024e-01   2.332530e-02   4.367305e-01   1.396743e+02              5             10
    SD            61   8.407116e-01   8.173863e-01   2.332530e-02   4.370292e-01   1.395788e+02              5             10
    SD            61   8.406990e-01   8.173737e-01   2.332530e-02   4.373237e-01   1.394848e+02              5             10
    SD            61   8.406892e-01   8.173639e-01   2.332530e-02   4.376140e-01   1.393922e+02              5             10
    FW            65   8.406892e-01   8.173639e-01   2.332530e-02   4.365595e-01   1.488915e+02              5             10
    FW            66   8.405201e-01   8.171948e-01   2.332530e-02   4.395137e-01   1.501660e+02              6             11
    SD            67   8.404592e-01   8.171339e-01   2.332530e-02   4.409286e-01   1.519520e+02              7             12
    LD            68   8.404592e-01   8.171339e-01   2.332530e-02   4.407468e-01   1.542836e+02              7             12
    SD            69   8.404515e-01   8.348508e-01   5.600671e-03   4.427294e-01   1.558514e+02              7             13
    SD            69   8.404450e-01   8.348443e-01   5.600671e-03   4.430269e-01   1.557467e+02              7             13
    SD            69   8.404394e-01   8.348388e-01   5.600671e-03   4.433118e-01   1.556466e+02              7             13
    SD            69   8.404346e-01   8.348339e-01   5.600671e-03   4.436080e-01   1.555427e+02              7             13
    SD            69   8.404302e-01   8.348295e-01   5.600671e-03   4.439308e-01   1.554296e+02              7             13
    SD            69   8.404262e-01   8.348256e-01   5.600671e-03   4.442430e-01   1.553204e+02              7             13
    SD            69   8.404225e-01   8.348218e-01   5.600671e-03   4.445531e-01   1.552121e+02              7             13
    SD            69   8.404190e-01   8.348183e-01   5.600671e-03   4.448596e-01   1.551051e+02              7             13
    SD            69   8.404157e-01   8.348150e-01   5.600671e-03   4.451689e-01   1.549974e+02              7             13
    SD            69   8.404124e-01   8.348118e-01   5.600671e-03   4.454693e-01   1.548928e+02              7             13
    SD            69   8.404093e-01   8.348086e-01   5.600671e-03   4.457601e-01   1.547918e+02              7             13
    SD            69   8.404063e-01   8.348056e-01   5.600671e-03   4.460476e-01   1.546920e+02              7             13
    SD            69   8.404033e-01   8.348027e-01   5.600671e-03   4.463386e-01   1.545912e+02              7             13
    SD            69   8.404005e-01   8.347998e-01   5.600671e-03   4.466285e-01   1.544908e+02              7             13
    SD            69   8.403978e-01   8.347971e-01   5.600671e-03   4.469164e-01   1.543913e+02              7             13
    SD            69   8.403951e-01   8.347944e-01   5.600671e-03   4.472050e-01   1.542917e+02              7             13
    SD            69   8.403926e-01   8.347919e-01   5.600671e-03   4.474938e-01   1.541921e+02              7             13
    SD            69   8.403902e-01   8.347895e-01   5.600671e-03   4.477864e-01   1.540913e+02              7             13
    SD            69   8.403878e-01   8.347872e-01   5.600671e-03   4.480771e-01   1.539914e+02              7             13
    SD            69   8.403856e-01   8.347850e-01   5.600671e-03   4.483655e-01   1.538923e+02              7             13
    SD            69   8.403835e-01   8.347829e-01   5.600671e-03   4.486567e-01   1.537924e+02              7             13
    SD            69   8.403815e-01   8.347809e-01   5.600671e-03   4.489437e-01   1.536941e+02              7             13
    SD            69   8.403796e-01   8.347790e-01   5.600671e-03   4.492322e-01   1.535954e+02              7             13
    SD            69   8.403778e-01   8.347772e-01   5.600671e-03   4.495194e-01   1.534973e+02              7             13
    SD            69   8.403761e-01   8.347755e-01   5.600671e-03   4.498069e-01   1.533992e+02              7             13
    SD            69   8.403745e-01   8.347738e-01   5.600671e-03   4.500986e-01   1.532997e+02              7             13
    SD            69   8.403730e-01   8.347723e-01   5.600671e-03   4.503930e-01   1.531996e+02              7             13
    SD            69   8.403715e-01   8.347709e-01   5.600671e-03   4.506835e-01   1.531008e+02              7             13
    SD            69   8.403702e-01   8.347695e-01   5.600671e-03   4.509819e-01   1.529995e+02              7             13
    SD            69   8.403689e-01   8.347682e-01   5.600671e-03   4.512868e-01   1.528961e+02              7             13
    SD            69   8.403676e-01   8.347670e-01   5.600671e-03   4.515809e-01   1.527965e+02              7             13
    FW           100   8.403676e-01   8.347670e-01   5.600671e-03   4.425273e-01   2.259748e+02              7             13
    FW           101   8.403647e-01   8.347640e-01   5.600671e-03   4.521067e-01   2.233986e+02              7             14
  Last           101   8.403614e-01   8.241351e-01   1.622634e-02   4.537268e-01   2.226009e+02              7             15
-------------------------------------------------------------------------------------------------------------------------------
    PP           101   8.403614e-01   8.241351e-01   1.622634e-02   4.552840e-01   2.218395e+02              7             15
-------------------------------------------------------------------------------------------------------------------------------
pokutta commented 2 years ago

problem seems to be only with the SD counter -> when the next FW step is reached it jumps up. Also verify behavior for non-simplex steps (last column to the right)