# Application of the Parabola Method in Nonconvex Optimization
## 2 Univariate Optimization: Parabola Method
### The Parabola Method  
Step 0. Choose the accuracy \(\varepsilon>0\). Choose points \(x_{1}^{0}<x_{2}^{0}<x_{3}^{0}\in[\alpha,\beta]\) such that  
\[f(x_{1}^{0})>f(x_{2}^{0})<f(x_{3}^{0}). \tag{2}\]  
Set \(z=x_{2}^{0},k=0\). Step 1. Find the minimum \(\overline{x}^{k}\) of the quadratic interpolation polynomial in the following way. \[\overline{x}^{k}=\frac{1}{2}\Bigg{(}x_{1}^{k}+x_{2}^{k}-\frac{a_{1}^{k}}{a_{2} ^{k}}\Bigg{)},\]  
\[a_{1}^{k}=\frac{f(x_{2}^{k})-f(x_{1}^{k})}{x_{2}^{k}-x_{1}^{k}},\ a_{2}^{k}= \frac{1}{x_{3}^{k}-x_{2}^{k}}\Bigg{(}\frac{f(x_{3}^{k})-f(x_{1}^{k})}{x_{3}^{ k}-x_{1}^{k}}-a_{1}^{k}\Bigg{)}.\]  
Step 2. Check stop criterion  
\[|\overline{x}^{k}-z|\leq\varepsilon. \tag{3}\]  
If (3) is held, then terminate the algorithm, and \(x^{*}=\overline{x}^{k}\) is \(\varepsilon\)-optimal point. Otherwise, go to Step 3. Step 3. Choose \(\hat{x}^{k}=\arg\min_{x=x_{1}^{k},x_{2}^{k}}f(x)\). Set \(z=\overline{x}^{k}\). Denote points \(\hat{x},x_{2}^{k},\overline{x}^{k}\) in ascending order as \(x_{1}^{k+1},\ x_{2}^{k+1},\ x_{3}^{k+1}\). Increase \(k\to k+1\), and go to Step 1. When \(f\) is a unimodal (semi-strictly quasiconvex [13]) over \(P\) function, both methods determine an approximate point of minimum in a finite number of iterations. In the case of the Golden Section Method the number of function evaluations is equal to the number of iterations plus two; in the case of the Parabola Method, the number of function evaluations is equal to the number of iterations plus three. It is well known that, in general, the Golden Section Method is more efficient than the Parabola Method. However, in the continuously differentiable case, the behavior of the Parabola Method can be improved. Consider the following two examples from [14]. **Example 1**. : _In problem (1), \(f(x)=-16(x^{2}-24x+5)e^{-x},\ P=[1.9,3.9]\). The Golden Section Method with \(\varepsilon=0.001\) finds the approximate solution \(x^{*}=2.867996734\) with \(f(x^{*})=-3.850450707\) in 16 iterations. The Parabola Method with the same \(\varepsilon\) finds the approximate solution \(x^{*}=2.868823736\) with \(f(x^{*})=-3.850448184\) in six iterations._  
**Example 2**. : _In problem (1), \(f(x)=2(x-3)^{2}+e^{\frac{x^{2}}{2}},\ P=[-3,3]\). The Golden Section Method with \(\varepsilon=0.001\) finds the approximate solution \(x^{*}=1.590558077\) with \(f(x^{*})=7.515924361\) in 19 iterations. The Parabola Method with the same \(\varepsilon\) finds the approximate solution \(x^{*}=1.584929941\) with \(f(x^{*})=7.516292947\) in 35 iterations._  
In both examples, the objective functions are unimodal. In the first example, the Parabola Method worked two times faster, and in the second example, the Parabola Method worked about two times slower than the Golden Section Method. From a geometrical point of view, the objective function in the first example is more like a parabola than in the second example, and we are going to show how the efficiency of the Parabola Method can be improved in cases similar to Example 2. We start from checking efficiency of the Golden Section Method on a number of multimodal functions. Tables 1 and 2 present the results of 17 test problems from [14].