Levenberg–Marquardt method and partial exact penalty parameter selection in bilevel optimization

We start here by acknowledging that it is very difficult to check that partial calmness (cf. Definition 2.1) holds in practice. Nevertheless, we would like to consider Theorem 2.2 as the base of our experimental analysis, and ask ourselves how large \(\lambda\) needs to be for Algorithm 2.6 to converge. Intuitively, one would think that taking \(\lambda\) as whatever large number should be fine. However, this is usually not the case in practice. One of the main reasons for this is that for too large values of \(\lambda\), Algorithm 2.6 does not behave well. In particular, if we run Algorithm 2.6 with varying \(\lambda\) for a very large number of iterations, the value of the Error blows up at some point and the values \(\left\Vert \Upsilon ^{\lambda }_\mu (z^k)\right\Vert\) stop decreasing. Recall that ill-conditioning (and possibly the ill-behaviour) refers to the fact that one eigenvalue of the Hessian involved in \(\nabla \Upsilon _\mu ^\lambda (z^k)\) being much larger than the other eigenvalues, which affects the curvature in the negative way for gradient methods (Press et al. 1992). To analyze this ill-behaviour in this section, we are going to run our algorithm for 1, 000 iterations with no stopping criteria and let \(\lambda\) vary indefinitely. We will subsequently look at which iteration the algorithm blows up and record the value of \(\lambda\) there. To proceed, we denote by \(\lambda _{ill}\) the first value of \(\lambda\) for which the ill-behaviour is observed for each example. The table below presents the number of BOLIB examples that are approximately within certain intervals of \(\lambda _{ill}\) (Table 1).

On average, the ill-behaviour seems to typically occur after about 500 iterations (where \(\lambda _{ill}\approx 10^{10}\)), as it can be seen in the table above. For 34 problems ill-behaviour was not observed under the scope of 1000 iterations. We also see that for most of the problems (72/124), the starting point for the ill-behaviour happens when \(10^9<\lambda <10^{11}\). We further observe that algorithm has shown to behave well for the values of penalty parameter \(\lambda <10^9\) with only 7/124 examples demonstrating ill-behaviour for such \(\lambda\). This makes the choice of very large values of \(\lambda\) not attractive at all, as the algorithm would diverge for a large majority of our examples. For instance, taking \(\lambda =10^{20}\), we observed that the ill-behaviour would occur for 90/124 tested examples. Mainly, the analysis shows that choosing \(\lambda >10^9\) could cause the algorithm to diverge. Hence, based on our method, selecting \(\lambda \le 10^7\) seems to be a very safe choice for our BOLIB test set. This is useful for the choice of fixed \(\lambda\) as we can choose values smaller than \(10^7\). For the case of varying \(\lambda\) the values are controlled by the stopping criteria proposed in the next section. The complete results on the values of \(\lambda _{ill}\) for each example will be presented in Table 2 below.

Interestingly, 34 out of the 124 test problems do not demonstrate any ill behaviour signs even if we run the algorithm for 1000 iterations with \(\lambda =0.5*1.05^{iter}\). A potential reason for this could just be that the parameter \(\lambda\) does not get sufficiently large after 1, 000 iterations to cause problems for these problems. It could also be that the eigenvalues of the Hessian are not affected by large values of \(\lambda\) for these examples. Also, there is a possibility that elements of the Hessian involved in (22) do not depend on \(\lambda\) at all, as for 20/34 problems where the function g is linear in (x, y) or not present in these problems. Next, we focus our attention on assessing what magnitudes of the penalty parameter \(\lambda\) to better evaluate the performance of our method.

It is clear from the previous subsection that to reduce the chances for Algorithm 2.6 to diverge or exhibit some ill-behaviour, we should approximately select \(\lambda < 10^7\). However, it is still unclear whether only large values of \(\lambda\) would be sensible to ensure a good behaviour of the algorithm. In other words, it is important to know whether relatively small values of \(\lambda\) can lead to a good behaviour for Algorithm 2.6. To assess this, we attempt here to identify inflection points, i.e., values of k where we have \(\left\Vert \Upsilon ^{\lambda _k}_\mu (z^k)\right\Vert <\epsilon\) as \(\lambda _k\) varies increasingly as described in the introduction of this section. We would then record the value of \(\lambda _k\) at these points.

Ideally, we want to get the threshold \(\bar{\lambda }\) such that solution is retained for all \(\lambda >{\bar{\lambda }}\) in the sense of Theorem 2.2. To proceed, we extract the information on the final \(Error^*:=\left\Vert \Upsilon ^\lambda (z^*)\right\Vert\) for each example from Tin and Zemkoho (2020) and then rerun the algorithm with varying penalty parameter \(\lambda _k:=0.5*1.05^k\) with new stopping criterion (i.e., \(Error \le 1.1 Error^*\)) while relaxing all of the stopping criteria (see details in Sect. 4). This way, we stop once we observe \(Error_k:=\left\Vert \Upsilon ^{\lambda _k}(z)\right\Vert\) close to the \(Error^*\) that we obtained in our experiments (Tin and Zemkoho 2020). It is worth noting that it would make sense to test only 72/117 (\(61.54\%\)) of examples, for which algorithm performed well and produced a good solution. This approach can be thought of as finding the inflection point. For instance, if we have an algorithm running as below, we want to stop at the inflection point after 125–130 iterations. The illustration of how we aim to stop at the inflection point is presented in Fig. 2a–b below, where we have \(\left\Vert \Upsilon ^\lambda (z)\right\Vert\) on the y-axis and iterations on the x-axis.

For some of the examples, we obtained a better Error than initial \(Error^*\). For these cases, we stopped very early as \(Error_k \le 1.1Error^*\) was typically met at an early iteration k (where \(\lambda\) was still small), as demonstrated in Fig. 2c–d above. This demonstrates the disadvantage of \(\lambda\) being an increasing sequence. If the algorithm makes many iterations, the parameter \(\lambda\) keeps increasing without possibility to go back to the smaller values. It turns out that for some examples the smaller value of \(\lambda\) was as good as large values, or even better to recover a solution. This further justifies the choice to start from the small value of \(\lambda\), that is \(\lambda _0<1\) and increase it slowly.

With the setting to stop whenever \(Error_k \le 1.1 Error^*\), we often stop very early. Hence, we do not always get \({\bar{\lambda }}\) that represents the inflection point, which we aimed to get; cf. Fig. 2c–d, where (c) has a scale of \(10^4\) on the y-axis. Although, we can clearly see from Fig. 2c that inflection point lies around 190–200 iterations, where the value of \(\lambda\) is much bigger. It is clear that we stopped earlier due to having small value of Error after 12–45 iterations. It was observed that such scenario is typical for the examples in the considered test set. For this reason, we want to introduce \(\lambda ^*\) as the large threshold of \(\lambda\). This value will be used to represent the value of the penalty parameter at the inflection point, where solution starts to be recovered for large values of \(\lambda\) (\(\lambda >6.02\)), while we also record \({\bar{\lambda }}\) as the first (smallest) value of \(\lambda\) for which good solution was obtained. For instance, with \(\lambda\) defined as \(\lambda := 0.5\times 1.05^k\) in Fig. 2c we have \({\bar{\lambda }} = 0.5\times 1.05^{12}\) and \(\lambda ^*=0.5\times 1.05^{190}\) as we obtain good solution for small \(\lambda\) after 12 iterations and for large \(\lambda\) after 190 iterations. We shall note that the value \(\lambda >6.02\) is the value of the penalty parameter after we make at least 50 iterations as for the case with varying \(\lambda\) we have \(\lambda = 0.5\times 1.05^{51}=6.02\).

The complete results of detecting \({\bar{\lambda }}\) and \(\lambda ^*\) is presented in Table 2 below. It was observed that the behaviour of the method follows the same pattern for the majority of the examples. Typically, we get a good solution, which is retained for some small values of \(\lambda\), and subsequently, the value of the Error blows up and takes some iterations to start decreasing, coming back to obtaining and retaining a good solution for large values of \(\lambda\). Such pattern is clearly demonstrated in Fig. 2c. Such a behaviour is interesting as usually, only large values of penalty parameters are used in practice (Burke 1991; Di Pillo and Grippo 1989), as intuitively suggested by Theorem 2.2. As mentioned in Fletcher (1975), some methods require penalty parameters to increase to infinity to obtain convergence.

We are now going to proceed with finding the threshold of \(\lambda\) for which we start getting a solution and retain the value for larger values of \(\lambda\). We are going to proceed with the technique of finding small threshold \({\bar{\lambda }}\) and large threshold \(\lambda ^*\), which was briefly discussed earlier. To find the threshold we first extract the value of the final \(Error^*\) for each example from Tin and Zemkoho (2020). To find \({\bar{\lambda }}\) we run the algorithm with \(\lambda\) being defined as \(\lambda :=0.5\times 1.05^k\), with the new stopping criteria:Of course, we also relax all of the aforementioned stopping criteria, as Error is the main measure here and we know that desired value of Error exists. We then define \({\bar{\lambda }} := 0.5 \times 1.05^{{\bar{k}}}\), where \({\bar{k}}\) is the number of iterations after stopping whenever we get \(Error<1.1Error^*\). For most of the cases we detect \({\bar{\lambda }}\) early due to a good solution after the first few iterations in the same manner as shown in Fig. 2c. Since for many examples we satisfy condition \(Error\le 1.1 Error^*\) for early iterations (before the inflection point is achieved), we further introduce \(\lambda ^*\), the large threshold \(\lambda\). The value of \(\lambda ^*\) will be used to represent the value of the penalty parameter at the inflection point, where solution starts to be recovered for large values of \(\lambda\). This will be obtained in the same way as \({\bar{\lambda }}\) with the only difference that we additionally impose the condition to stop after at least 50 iterations. To obtain \(\lambda ^*\) we run the algorithm with \(\lambda :=0.5\times 1.05^k\) and the following stopping criteria:Then the large threshold is defined as \(\lambda ^* := 0.5\times 1.05^{k^*}\), where \(k^*\) is the number of iterations after stopping whenever we get \(Error<1.1Error^*\) and \(k>50\). This way \(\bar{\lambda }\) represents the first (smallest) value of \(\lambda\) for which good solution was obtained, while \(\lambda ^*\) represent the actual threshold after which solution is retained for large values of \(\lambda\). The demonstration of stopping at the inflection point for large threshold \(\lambda ^*\) was shown in Fig. 2b and for small threshold \({\bar{\lambda }}\) in Fig. 2d.

It makes sense to test only the examples where algorithm performed well and produced a good solution. For the rest of the examples, the value of \(Error^*\) would not make sense as the measure to stop, and we do not obtain good solutions for these examples by the algorithm anyway. From the optimistic perspective we could consider recovered solutions to be the solutions for which the optimal value of upper-level objective was recovered with some prescribed tolerance. Taking the tolerance of \(20\%\), the total amount of recovered solutions by the method with varying \(\lambda\) is 72/117 (\(61.54\%\)) for the cases where solution was reported in BOLIB (Zhou et al. 2020). This result will be shown in more details in Sect. 4.2. Let us look at the thresholds \({\bar{\lambda }}\) and \(\lambda ^*\) for these examples in the figure below, where the value of \(\lambda\) is shown on \(y-axis\) and the example numbers on the \(x-axis\).

For 68/72 problems, we observe that large threshold of the penalty parameter has the value \(\lambda ^* \le 10^4\), which shows that we usually can obtain a good solution before 205 iterations. This further justifies stopping algorithm after 200 iterations (see next section) if there is no significant step to step improvement. As for the main outcome of Fig. 3, we observe that small threshold is smaller than large threshold (\({\bar{\lambda }} < \lambda ^*\)) for 59/72 (\(82 \%\)) problems. This clearly shows that for majority of the problems, for which we recover solution with \(\lambda :=0.5\times 1.05^k\), we obtain a good solution for small \(\lambda\) as well as for large \(\lambda\). This demonstrates that small \(\lambda\) could in principle be good for the method. For the rest \(18\%\) of the problems we have \({\bar{\lambda }} = \lambda ^*\), meaning that good solution was not obtained for \(\lambda <6\) for these examples. This also means that we typically obtain good solution for small values of \(\lambda\) and for large values of \(\lambda\), but not for the medium values (\(\bar{\lambda }<\lambda <\lambda ^*\)).

As for the general observations of Fig. 3, for 42/72 (\(58.33\%\)) examples we observed that the large threshold \(\lambda ^*\) is located somewhere in between \(90-176\) iterations with \(40<\lambda ^*<2680\). For 7/72 problems threshold is in the range \(6.02<\lambda ^* \le 40\), and for only 4/72 problems \(\lambda ^*>1.1\times 10^4\). Once again, this justifies that typically \(\lambda\) does not need to be large. It also suggests the optimal values of \(\lambda\) for the tested examples, at least for our solution method. We observe that for 19/72 problems we get \(\lambda ^*=51\), which should be treated carefully as this could mean that the inflection point could possibly be achieved before 50 for these examples. Nevertheless, \(\lambda ^*=6.02\) is still a good value of penalty parameter for these examples as solutions are retained for \(\lambda >\lambda ^*\).

As going to be observed in Sect. 4 we could actually argue that smaller values of \(\lambda\) work better for our method not only for varying \(\lambda\) but also for fixed \(\lambda\). Together with the fact that we often have the behaviour as demonstrated in Fig. 2c, it follows that small \(\lambda\) could be more attractive for the method we implement. We even get better values of Error and better solutions for small values of \(\lambda\) for some examples. Hence we draw the conclusion that small values of \(\lambda\) can generate good solutions. Since it is typical to use large values of \(\lambda\) for other penalization methods [e.g. in Bertsekas (1982), Burke (1991), Di Pillo and Grippo (1989)], it is interesting what could be the reasons that small \(\lambda\) worked better for our case. This could be due to the specific nature of the method, or due to the fact that we do not do full penalization in the usual sense. Other reason could come from the structure of the problems in the test set. The exact reason of why such behaviour was observed remains an open question. What is important is that this could possibly be the case that small values of \(\lambda\) would be good for some other penalty methods and optimization problems of different nature. This result contradicts typical choice of large penalty parameter for general penalization methods for optimization problems. As the conclusion for our framework, we can claim that for our method \(\lambda\) needs not to be large.

Intuitively, one would think that for partially calm examples, Algorithm 2.6 would behave well, in the sense that varying \(\lambda\) increasingly would lead to a good convergence behaviour. To show that it is not necessarily the case, we start by considering the following result identifying a class of bilevel program of the form (1) that is automatically partially calm.

Examples 8, 40, 43, 45, 46, 188, and 123 in the BOLIB library (see Table 2) are of the form described in this result. The expectation is that these examples will follow the pattern of retaining solution after some threshold, that is for \(\lambda >\lambda ^*\), as they fit the theoretical structure behind the penalty approach as described in Theorem 2.2. Note that all of these examples follow the pattern shown in Fig. 1a. However, if we relax the stopping criteria used to mitigate the effects of ill-conditioning, as discussed in the previous two subsections, varying \(\lambda\) for 1000 iterations for these seven partially calm examples leads to the 3 typical scenarios demonstrated in Fig. 4.

In the first case of Fig. 4, we can clearly see the algorithm is performing well, retaining the solution for the number of iterations, but then blows up at one point (after 500 iterations) and never goes back to reasonable solution values. Examples 40 and 46 also follow this pattern. Example 123 (second picture in Fig. 4) shows a slightly different picture, where the zig-zagging pattern is observed. Algorithm 2.6 blows up at some point and starts zig-zagging away from the solution after obtaining it for a smaller value of \(\lambda\). Zig-zagging is very common issue in penalty methods and often caused by ill-conditioning (Nocedal and Wright 1999). Note that Example 118 exhibits a similar behaviour. This is somewhat similar to scenario 1. However, we put this separately as zig-zagging issue is often referred to as the danger that could be caused by ill-conditioning of a penalty function. The last picture of Fig. 4 shows a case where Algorithm 2.6 runs very well without any ill-behaviour observed for all the 1000 iterations. It could be possible that the algorithm could blow up after more iterations if we keep increasing \(\lambda\). It could also be possible that ill-conditioning does not occur for this example at all, as the Hessian of \(\Upsilon ^\lambda\) (13) is not affected by \(\lambda\). Out of the seven BOLIB problems considered here, only examples 43 and 45 follows this pattern.

For Step 0 of Algorithm 2.6 we set the tolerance to \(\epsilon :=10^{-5}\) and the maximum number of iterations to be \(K:=1000\). We also choose \(\alpha _0 := \left\Vert \Upsilon ^\lambda (z^0)\right\Vert\) (if \(\lambda\) is varying, we set \(\lambda :=\lambda _0\) here), \(\gamma _0:= 1\), \(\rho =0.5\), and \(\sigma =10^{-2}\). The selection of \(\sigma\) is based on the overall performance of the algorithm while the other parameters are standard in the literature.

Here, we compare the values of the upper-level objective functions at points computed by the Levenberg–Marquardt algorithm with fixed \(\lambda\) and varying \(\lambda\). For the comparison purpose, we focus our attention only on 117 BOLIB examples (Zhou et al. 2020), as solutions are not known for the other seven problems. To proceed, let \(\bar{F}_A\) be the value of upper-level objective function at the point \((\bar{x},\bar{y})\) obtained by the algorithm and \(\bar{F}_K\) the value of this function at the known best solution point reported in the literature (see corresponding references in Zhou et al. 2020). We consider all fixed \(\lambda \in \{10^6,10^5,\ldots ,10^{-3}\}\) and varying \(\lambda\) in one graph and present the results in Figure 5 below, where we have the relative error \((\bar{F}_A - \bar{F}_K) / (1+|\bar{F}_K|)\) on the \(y-axis\) and number of examples on the x-axis, starting from 30th example. We further plot the results for the best fixed value of \(\lambda\). The graph is plotted in the order of increasing error. From Fig. 5 we can clearly see that many more solutions were recovered for the small values of fixed \(\lambda\) than for large ones. For instance with the allowable accuracy error of \(\le 20\%\) we recover solutions for \(78.63\%\) for fixed \(\lambda \in \{10^{-2},10^{-3}\}\), while for \(\lambda \in \{10^6,10^{5},10^4,10^3,10^2\}\) we recover at most \(40.17\%\) solutions. Interestingly, the worst performance is observed for fixed \(\lambda =100\). With the varying \(\lambda\), we observe that the algorithm performed averagely in comparisons made on the use of large and small fixed values of \(\lambda\), recovering \(59.83\%\) of the solutions with the accuracy error of \(\le 20\%\). It is worth saying that implementing Algorithm 2.6 with \(\lambda :=0.5\times 1.05^k\) still recovers over half of the solutions, which is not too bad. However, fixing \(\lambda\) to be small recovers way more solutions, which shows that varying \(\lambda\) is not the most efficient option for our case.

It was further observed that for some examples only \(\lambda \ge 10^3\) performed well, while for others small values (\(\lambda <1\)) showed good performance. If we were able to pick best fixed \(\lambda\) for each example, we would obtain negligible (less than \(10\%\)) error for upper-level objective function for \(85.47\%\) of the tested problems. With the accuracy error of \(\le 25\%\) our algorithm recovered solutions for \(88.9\%\) of the problems for the best fixed \(\lambda\) and for \(61.54\%\) with varying \(\lambda\). This means that if one can choose the best fixed \(\lambda\) from the set of different values, fixing \(\lambda\) is much more attractive for the algorithm. However, if one does not have a way to choose the best value or a set of potential values cannot be constructed efficiently for certain problems, varying \(\lambda\) could be a better option to choose. Nevertheless, for the test set of small problems from BOLIB (Zhou et al. 2020), fixing \(\lambda\) to be small performed much better than varying \(\lambda\) as increasing sequence. Further, if one could run the algorithm for all fixed \(\lambda\) and was able to choose the best one, the algorithm with fixed \(\lambda\) performs extremely well compared to varying \(\lambda\). In other words, algorithm almost always finds a good solution for at least one value of fixed \(\lambda \in \{10^6, 10^5, \ldots , 10^{-3}\}\).

Considering the structure of the feasible set of problem (2), it is critical to check whether the points computed by our algorithms satisfy the value function constraint \(f(x,y)\le \varphi (x)\), as it is not explicitly included in the expression of \(\Upsilon ^\lambda\) (13). If the lower-level problem is convex in y and a solution generated by our algorithms satisfies (8) and (11), then it will verify the value function constraint. Conversely, to guarantee that a point (x, y) such that \(y\in S(x)\) satisfies (8) and (11), a constraint qualification (CQ) is necessary. Note that conditions (8) and (11) are incorporated in the stopping criterion of Algorithm 2.6. To check whether the points obtained are feasible, we first identify the BOLIB examples, where the lower-level problem is convex w.r.t. y. As shown in Fliege et al. (2021) it turns out that a significant number of test examples have linear lower-level constraints. For these examples, the lower-level convexity is automatically satisfied. We detect 49 examples for which some of these assumptions are not satisfied, that is the problems having non-convex lower-level objective or some of the lower-level constraints being nonconvex. For these examples, we compare the obtained solutions with the known ones from the literature. Let \(f_A\) stand for \(f(\bar{x},\bar{y})\) obtained by one of the tested algorithms and \(f_K\) to be the known optimal value of lower-level objective function. In the graph below we have the lower-level relative error, \((f_A - f_K) / (1+|f_K|)\), on the y-axis, where the error is plotted in increasing order. In Fig. 6 below we present results for all fixed \(\lambda \in \{10^6,10^5,\ldots ,10^{-3}\}\) as well as varying \(\lambda\) defined as \(\lambda :=0.5\times 1.05^k\).

From the Fig. 6 below we can see that for 20 problems the relative error of lower-level objective is negligible (\(<5\%)\) for all values of fixed \(\lambda\) and varying \(\lambda\). We have seen that convexity and a CQ hold for the lower-level hold for 74 test examples. We consider solutions for these problems to be feasible for the lower-level problem. Taking satisfying feasibility error to be \(<20 \%\) and using information from the graph above, we claim that feasibility is satisfied for at most 100 (\(80.65\%\)) problems for fixed \(\lambda \in \{10^6,10^5,10^4,10^3\}\), for \(101-104\) (\(81.45-83.87\%\)) problems for \(\lambda \in \{10^3,10^2,10^1,10^0,10^{-1}\}\) and for 106 (\(85.48\%\)) problems for \(\lambda \in \{10^{-2},10^{-3}\}\). We further observe that feasibility is satisfied for 101 (81.4%) problems for varying \(\lambda\). Considering we could choose best fixed \(\lambda\) for each of the examples, we could also claim that feasibility is satisfied for 108 (87.1%) problems for best fixed \(\lambda\). From Fig. 6 we note that slightly better feasibility was observed for smaller values of fixed \(\lambda\) than for the big ones and that varying \(\lambda\) has shown average performance between these magnitudes in terms of the feasibility.

Recall that the experimental order of convergence (EOC) is defined bywhere K is the number of the last iteration (Fischer et al. 2021). If \(K=1\), no EOC will be calculated (EOC\(=\infty\)). EOC is important to estimate the local behaviour of the algorithm and to show whether this practical convergence reflects the theoretical convergence result stated earlier. Let us consider EOC for fixed \(\lambda \in \{10^6,\ldots ,10^{-3}\}\) and for varying \(\lambda\) (\(\lambda =0.5\times 1.05^k\)) in Fig. 7 below.

It is clear from this picture that for most of the examples our method has shown linear experimental convergence. This is slightly below the quadratic convergence established by Theorem 2.7. It is however important to note that the method always converges to a number, although sometimes the output might not be the optimal point for the problem. There are a few examples that shown better convergence for each value of \(\lambda\), with the best ones being \(\lambda \in \{10^{-3},10^{-2},10^{-1},10^6\}\) as seen in the figure above. These fixed values have shown slightly better EOC performance than varying \(\lambda\). Varying \(\lambda\) showed slightly better convergence than fixed \(\lambda \in \{10^0,10^1,10^2,10^3,10^4,10^5\}\). EOC bigger than 1.2 has been obtained for less than 5 (4.03 %) examples for fixed \(\lambda \in \{10^0,10^1,10^2,10^3,10^4,10^5\}\), while varying \(\lambda\) showed such EOC for 11 (8.87%) examples. Fixed \(\lambda =10^6\) has shown almost the same result as varying \(\lambda\) with rate of convergence greater than 1.2 for 12 (9.67%) examples, while \(\lambda =10^{-1}\) has demonstrated such EOC for 14 (11.29%) examples and \(\lambda \in \{10^{-2},10^{-3}\}\) for 17 (13.71 %) examples. Finally, in the graph above, we can see that for all values of \(\lambda\) only a few (\(\le 4/124\)) examples have worse than linear convergence.

Let us now look at the line search stepsize, \(\gamma _k\), at the last step of the algorithm for each example. Consider all fixed \(\lambda\) and varying \(\lambda\) in Fig. 8 below. This is quite important to know two things. Firstly, how often line search was used at the last iteration, that is how often implementation of line search was clearly important. Secondly, as main convergence results are for the pure method this would be demonstrative to note how often the pure (full) step was made at the last iteration. This can then be compared with the experimental convergence results in the previous subsection, namely with Fig. 7. In the figure above whenever stepsize on the y-axis is equal to 1 it means the full step was made at the last iteration. For these cases the convergence results shown in Theorem 2.7 could be considered valid. From the graphs above we observe that stepsize at the last iteration was rather \(\gamma _k=1\) or \(\gamma _k<0.05\). We observe that for varying \(\lambda\) algorithm would typically do a small step at the last iteration. It seems that algorithm with varying \(\lambda\) benefits more from line search technique than the algorithm with fixed \(\lambda\). Possibly, pure Levenberg–Marquardt method with varying \(\lambda\) would not converge for most of the problems. Interestingly, for fixed values of \(\lambda\) stepsize was \(\gamma _k<0.05\) at the last iteration much more often for the values of \(\lambda\) that showed worse performance in terms of recovering solutions (i.e. \(\lambda \in \{10^1, 10^2\}\)).

We also observe that for medium values of \(\lambda\) (\(\lambda \in \{10^4,10^3,10^2,10^1,10^0\}\)) full stepsize was made for less than half of the examples. For large values \(\lambda \in \{10^6,10^5\}\) full step was made for \(63.71\%\) and \(70.16\%\) of the problems respectively. Further on, small values of \(\lambda\) for which more solutions were recovered would do the full step at the last iteration for most of the examples. For instance, with \(\lambda =10^{-3}\) and \(\lambda =10^{-2}\) full step was made at the last iteration for \(73.39\%\) of the problems, while for \(\lambda =10^{-1}\) full step was made for \(75.81\%\) of the problems. In terms of the fixed \(\lambda _{best}\) it is interesting to observe that full step was used only for 82/124 (\(66.13 \%\)) of the problems, meaning that for a third of the problems linesearch was implemented in the last step for the best tested value of \(\lambda\). This also coincides with the results of Fig. 7 where with smaller values of \(\lambda\) the algorithm has shown faster than linear convergence for more examples than for big values of \(\lambda\). This is likely to be the case that small steps were made in the other instances due to the non-efficient direction of the method at the last iteration.

Let us firstly look at the level of accuracy of the algorithms in terms of recovering known optimal values of upper-level objective function for each example. We only consider 117 examples here, as these are the examples for which solutions were reported in Zhou et al. (2020). Let us combine two values of \(\lambda\) for each plot in Fig. 9 below. As in Fig. 5, the accuracy error is presented in increasing order from 0 to 1 over y-axis, while the x-axis represents the number of examples for which accuracy was smaller than given value on the y-axis. As can be seen from (a) and (b) in Fig. 9, all algorithms are not performing very well for large values of \(\lambda\). For \(\lambda \in \{10^6,10^5\}\), the best results are obtained by the Levenberg–Marquardt and semismooth Newton methods, having \(Accuracy\le 40\%\) for 57/117 examples. In terms of \(40\% \le Accuracy \le 100\%\), the Levenberg–Marquardt shows a better performance, obtaining \(Accuracy \le 90\%\) for 85/117 examples, while the other algorithms show this level of accuracy only for 65/117 examples.

The situation with \(\lambda \in \{10^4,10^3\}\) is very similar. Not that many solutions are recovered with high level of accuracy. Once again, the best results were shown by the Levenberg–Marquardt method here with \(Accuracy \le 90\%\) for 90/117 examples for \(\lambda =10^4\). It is further interesting that overall, the performance of fsolve is clearly worse than that of all the other three algorithms, with the line graphs being completely to the left of the line graphs representing the other algorithms throughout both (a) and (b) graphs. This demonstrates that algorithms specifically developed for bilevel framework perform better than standard solvers.

Looking at Fig. 9c, the situation is slightly different. We can clearly see that for \(\lambda \in \{ 10^2, 10^1 \}\), the semismooth Newton method outperformed the other algorithms. That said, it still does not recover very many solutions with a high level of accuracy. The \(Accuracy \le 30 \%\) is obtained by semismooth Newton method just for 80/117 examples for \(\lambda =10^1\), and only for 68/117 examples for \(\lambda =10^2\), which is on the same level with the other algorithms. We do not consider this level of accuracy to be high, but it is still interesting to see that some algorithms are better for some values of \(\lambda\) and worse for the other ones. Based on the performance of all tested algorithms, it seems that \(\lambda \in \{ 10^2, 10^1 \}\) is not the best choice of the penalty parameter for the given framework. Hence, the difference in performance for these values of \(\lambda\) is not so critical.

From Fig. 9d, we see that for \(\lambda \in \{10^0,10^{-1}\}\) Levenberg–Marquardt and Pseudo-Newton performed really well, having \(Accuracy\le 30\%\) for 99/117 examples, compared to only 89 examples for Semismooth Newton and fsolve. Further \(Accuracy \le 80\%\) is obtained by the Levenberg–Marquardt method for 110/117 examples, showing that Levenberg–Marquardt can almost always produce somewhat reasonable solutions for these values of \(\lambda\). Finally, in Fig. 9e we observe that for small values of \(\lambda\) Levenberg–Marquardt method performs the best and recovers many solutions, which is the critical point of the comparison. The level of accuracy for \(\lambda \in \{10^{-2},10^{-3}\}\) is similar to the one for \(\lambda \in \{10^0,10^{-1}\}\). Levenberg–Marquardt managed to have \(Accuracy\le 30\%\) for 98/117 examples and \(Accuracy\le 90\%\) for 111/117 examples for \(\lambda \in \{10^{-2},10^{-3}\}\). The pseudo-Newton method and fsolve show slightly worse performance here, while the semismooth Newton shows much worse performance for \(\lambda \in \{10^{-2},10^{-3}\}\) with \(Accuracy\le 90\%\) for only 80/117 examples. Summarizing, Fig. 9 clearly demonstrates that Levenberg–Marquardt algorithm for small values of \(\lambda\) was the most effective combination to solve the test set of bilevel problems from Zhou et al. (2020), in the sense of recovering optimal values of upper-level objective function.

In this section, we compare values of the lower-level objective functions obtained by the algorithms, in the case the true/known optimal values are reported in Zhou et al. (2020). Unlike Fig. 6, let us conduct comparison for all examples with true/known optimal solutions. The reason for this is that the system in Fischer et al. (2021) uses slightly different assumptions, required for feasibility of the system. Let us look at the values of \({\hat{f}}\) compared to known lower-level optimal values at the solution stated in Zhou et al. (2020). As before, we combine results for two values of \(\lambda\) for each plot. The plots are presented with the increasing order of the feasibility error. From Fig. 10a, we observe that for \(\lambda \in \{10^6,10^5\}\), the semismooth Newton method has smaller feasibility errors (\(\le 20\%\)) for a few more examples than the other algorithms. However, the Levenberg–Marquardt method was the best for \(20\% < Error \le 90\%\). In fact, this method has \(Error \le 90\%\) for 110/117 examples, while the next best result for the other algorithms is only 98/117 examples. Furthermore, the Levenberg–Marquardt method has \(Error \le 60\%\) for 101/117 examples, while the next best result for the other algorithms is only 82 examples. In other words, the other algorithms have very high feasibility errors for many examples in the cases where we have \(\lambda \in \{10^6,10^5\}\).

Looking at Fig. 10b, the Levenberg–Marquardt is even a clearer winner for \(\lambda \in \{10^4,10^3\}\). Once again, the semismooth Newton method has a negligible error (\(Error \le 20\%\)) for slightly more examples. However, the Levenberg–Marquardt feasibility error is much smaller on average with the line graph lying almost completely to the right of the other algorithms. Once again, the Levenberg–Marquardt error almost never goes beyond \(90\%\), and stays below \(60\%\) for majority of the examples, which cannot be said about the other algorithms.

Figure 10c demonstrates that the Levenberg–Marquardt is the clear leader for \(\lambda \in \{10^2,10^1\}\) in terms of recovering optimal values of the lower-level objective function (with the line graphs for LM being completely to the right). The semismooth Newton method was clearly second best out of the four tested algorithms. Surprisingly, Fig. 10d shows that for \(\lambda \in \{10^0,10^{-1}\}\) the semismooth Newton produces small error for more examples than the other algorithms. However, this is only true for \(Error \le 40\%\) for \(\lambda =10^0\). The gap between the Levenberg–Marquardt and semismooth Newton methods in this case remains small.

Finally, from Fig. 10e, we see that for small values of \(\lambda\), the Levenberg–Marquardt method performs slightly better than the other algorithms, having low feasibility error for more examples than other algorithms. It is interesting to see that fsolve is the only algorithm that performs bad for \(\lambda \in \{10^{-2},10^{-1}\}\). Since the Levenberg–Marquardt algorithm for small values of \(\lambda\) is the most effective to recover optimal values of upper-level objective function, this strengthens the view that it performs better than the other considered algorithms.

Now let us quickly look at the other parameters of the performance of the algorithms compared in this section. All tested algorithms have shown great computing time with less than 0.5 second to solve an example for a fixed value of \(\lambda\), which means that the difference in the CPU time is not significant. In terms of the Error (norm of the system being solved) at the last iteration, the semismooth Newton shows much better results than other algorithms, as one would expect. The reason for this is that it solves a different system, which is indeed square. Clearly, it is possible to solve a square system of equations more accurately in comparison to the case of an overdetermined system, which is much more challenging to solve to high accuracy. This is why for \(\lambda \in \{10^6,10^5,10^4,10^3,10^2,10^1\}\), the semismooth Newton method produces \(\left\Vert \Phi ^\lambda \right\Vert <10^0\) for 110-115 examples, while the other three tested methods perform worse, producing \(\left\Vert \Upsilon ^\lambda \right\Vert <10^0\) for only 70-80 examples. For \(\lambda \in \{10^0,10^{-1},10^{-2},10^{-3}\}\), the semismooth Newton produces \(Error<10^0\) for 122 examples, while the other methods show \(Error<10^0\) for only 100 examples. However, it is clearly not sensible to compare the methods on the measure of the Error as the two classes of method do not solve the same system of equations as indicated at the introduction of this section.

The advantage of the Levenberg–Marquardt method (Algorithm 2.6) is that it solves the optimality conditions (7)–(11) directly, while the semismooth Newton method solves a somewhat approximation of these optimality conditions, where the trick of introducing artificial variable z makes the system square. The main disadvantage here is that this trick requires condition \(y=z\) to recover points satisfying (7)–(11). The following table shows how often this condition is approximately satisfied for \(\Phi ^\lambda\) at the last iteration of semismooth Newton method in the context of solving the 124 test examples for a given value of the partial exact penalty \(\lambda\).

We can see that the condition \(y \approx z\) is not satisfied for a significant portion of the examples, especially for \(\lambda \in \{10^4, 10^3, 10^2, 10^1\}\) for which it is not satisfied for more than half of the problems. Interestingly, the condition was satisfied for majority of the examples for \(\lambda \in \{10^{-1}, 10^{-2}\}\). This is counter-intuitive as for these values of \(\lambda\), where the semismooth Newton shows worse performance in comparison to the other methods in terms of recovering optimal values of upper-level and lower-level objective functions. Nevertheless, we see that despite the fact that the Error parameter for semismooth Newton algorithm seems to be much better than for the other methods; this parameter is not very reliable as the crucial condition \(y^k \approx z^k\) is not satisfied in many cases.

Lastly, let us look at the experimental order of convergence (EOC) of the algorithms. The EOC is defined as in Sect. 4.4, with \(\Phi ^\lambda\) instead of \(\Upsilon ^\lambda\) for the semismooth Newton method (see Fischer et al. 2021 for the precise definition of \(\Phi ^\lambda\)). For all values of \(\lambda\), the semismooth Newton is the clear winner when talking about the EOC, as well as the Error. These results are expected, given that the reason for this is that the SN method is solving a square system, as already discussed above. As it can be seen in Fig. 11, the condition \(EOC>1.5\) is obtained when solving the square system for the majority of the tested examples, while the other methods demonstrate linear rate (\(EOC<1.1\)) for the majority of the examples for all values of \(\lambda\). This is easily explained by the fact that the latter methods try to solve the non-square system of optimality conditions (7)–(11), where it is often not possible to compute highly accurate solution. In fact, for most of the cases, we would expect that highly accurate solution does not exist even with some tolerance \(\Upsilon ^\lambda < \epsilon\) for some small \(\epsilon\). Furthermore, even the pseudo-Newton method has shown slightly better EOC for all values of \(\lambda\), which shows that Algorithm 2.6 generally has a linear convergence rate in the current framework.

As we have seen from Figs. 9 and 10, the Levenberg–Marquardt algorithm seems to be more attractive than the other tested algorithms based on the rate of recovering optimal values of upper-level and lower-level objective functions. All algorithms have shown similar speed, so there is no clear winner along this parameter. In terms of Error of the system at the last iteration and EOC, the semismooth Newton has shown the best performance. However, we have discussed that it would not be very accurate to compare these characteristics due to different systems being solved by the algorithms. Further, as we have seen from Table 3, there is some disadvantage of solving the system artificially constructed square system solved in Fischer et al. (2021) by means of a semismooth Newton method. Hence, despite the EOC measure, we believe that Algorithm 2.6 has shown the best performance along the main points of the comparison, namely accuracy and feasibility.