# Application of the Parabola Method in Nonconvex Optimization
## 2 Univariate Optimization: Parabola Method
### TPP Procedure  
1. Choose integer \(N>0\), and calculate \(\Delta=\frac{\beta-\alpha}{N^{*}}\). Set \(k=0,k_{p}=0\). 2. Calculate \(y_{1}^{k}=\alpha+k\Delta,y_{2}^{k}=\alpha+(k+1)\Delta,y_{3}^{k}=\alpha+(k+2)\Delta\). 3. If \(f(y_{1}^{k})>f(y_{2}^{k})<f(y_{3}^{k})\), then \(k_{p}=k_{p}+1,\
u_{1}^{k_{p}}=y_{1}^{k},\
u_{2}^{k_{p}}=y_{2}^{k},\
u_{3}^{k_{p }}=y_{3}^{k}\). 4. If \(y_{3}^{k_{p}}\leq\beta-\Delta\), then increase \(k\to k+1\), and go to Step 1. Otherwise, stop. When the TPP procedure stops, we have \(k_{p}\) three-point patterns, and in order to find the best solution, we can start the Parabola Method for all \(k_{p}\) patterns. In practice, we used the TPP procedure several times. We started from a small enough value of \(N\), say \(N=3\), and ran the TPP procedure. Then, we increased \(N\to 2N\) and ran the TPP procedure again. When the number of three-point patterns was the same in both runs, we stopped. In this case, we say that the TPP procedure stabilized. Otherwise, we increased \(N\) and ran the TPP procedure again, and so on. Since we assumed that the number of local minima of \(f\) over \(P\) is finite, such a repetition is also finite. Finally, we obtained \(k_{p}\) TPP subintervals \([\
u_{1}^{1},\
u_{3}^{1}]\)and the three-point corresponding patterns \(v_{1}^{i},v_{2}^{i},v_{3}^{i}\), \(i=1,\ldots,k_{p}\). We cannot guarantee that each subinterval contains exactly one local minimum; but, in practice, this property is true rather often. Then, we ran the Parabola Method for each subinterval, found the corresponding local minima, and selected the best ones as solutions. If \(k_{p}=0\), then no three-point patterns were detected. In this case, the Parabola Method is not applicable (it can be disconvergent), and we switch to the Golden Section Method. We call this strategy a two-stage local search approach (two-stage approach for short). Let us apply the two-stage approach to solving problems 11 (Figure 1) and 7 (Figure 2) from Table 1 for which the Golden Section Method did not find global minimum points and then run the Parabola Method over each obtained subinterval. **Example 3**. : _Problem 11: \(f(x)=-e^{-x}\sin(2\pi x),P=[0,4]\). Initial value \(N=3\). The TPP procedure was run four times. After the first run, one subinterval with one three-point pattern was obtained, after the second run, two subintervals with two three-point patterns were obtained, after the third run, four subintervals with four three-point patterns were obtained, and after the fourth run, four smaller subintervals with four three-point patterns were obtained again. The TPP procedure was stopped, and \(k_{p}=4\). The total number of function evaluations was equal to 24. Then, with the accuracy \(\varepsilon=0.001\), we ran the Parabola Method, which stopped after two additional function evaluations for each subinterval. The final subintervals, the three-point pattern (TPP), the corresponding starting parabolas, and additional function evaluations (\(k_{f}\)) of the Parabola Method over each subinterval are given in Table 3._  
Therefore, in total, after 32 function evaluations, all minima of the given function were determined. The geometrical interpretation of the results of the TPP procedure application corresponding to Table 3 is presented in Figure 3.  
In these tables, the Minima structure column shows how many local and global minima each problem has, the \(k_{f}^{TPP}\) column shows the number of performed function evaluations until the TPP procedure is stabilized, the TPP subintervals column shows the subintervals obtained from application of the TPP procedure, the \(k_{f}^{GSM}\) column shows the number of function evaluations of the Golden Section Method, the \(k_{f}^{PM}\) column shows the number of function evaluations of the Parabola Method, and the g/1 column shows the type of the calculated point: g--global minimum, I--local minimum. For example, for problem 2 with two local minima and one global minima, the TPP procedure found three subintervals after 12 function evaluations.