## 2 DQL Method
### Quadratic Step  
#### 2.3.1 Framework of Quadratic Step  
If the direct step fails to find an improvement, then the method proceeds to the quadratic step. Note that after a failed direct step, the best point remains at \(x_{0}^{k}\). In the quadratic step, the method first selects the points that have been previously evaluated within some radius \(q^{k}\geq\beta\delta^{k}\) of the point of centre \(x_{0}^{k}\) for some \(\beta\geq 1\). These points are used to construct a quadratic model of the objective function. The radius condition \(q^{k}\geq\beta\delta^{k}\) ensures that all the points from the direct search are taken into account. The method extracts the quadratic information from these calculated points using a least-squares quadratic model or Hessian approximation. The pseudocode of the quadratic step is shown in Algorithm 3. Note that in the third line of Algorithm 3, the methods of extracting and utilizing the quadratic information varies for different strategies. The idea of the quadratic step is to use these previously evaluated points \(\{x_{i}\}\) to predict a candidate by using quadratic approximations. ```
1:\(q^{k}\leftarrow\beta\delta^{k}\)
2: Determine the set of evaluated points within the trust region \(Q^{k}=\{x_{i}:\left\|x_{i}-x_{0}^{k}\right\|\leq q^{k}\}\)
3: Determine the quadratic search candidates \(\mathbb{Q}^{k}\) using the quadratic information from \(Q^{k}\)
4:Improvement_check(\(\mathbb{Q}^{k}\), \(x_{0}^{k}\), \(\beta^{k}\))
5: Update Quadratic_Flag accordingly
```  
**Algorithm 3**Quadratic_Step(\(x_{0}^{k}\), \(\beta\), \(\delta^{k}\), \(\{x_{i}\}\))  
Quadratic Step Strategies  
Our first option for the quadratic step begins by constructing a least-squares quadratic model. We use the quadprog and trust functions from Matlab[20] to find the least-squares quadratic model and its optimum within the trust region. We label this quadratic step strategy as quadratic step strategy 1. Our second option for the quadratic step is to take one iteration of an approximated [PERSON]'s method. Approximation techniques are introduced to obtain the required gradient and Hessian. Notice that at the end of the direct step, the centred simplex gradient approximation is performed, so we take  
\[\
abla f(x_{0}^{k})\approx\
abla_{c}f(x_{0}^{k};\delta^{k}D^{k}). \tag{17}\]  
To approximate the Hessian at \(x_{0}^{k}\), we need all the points within radius \(q^{k}\) that have a gradient approximation. Since the gradient approximations are performed in previous unsuccessful direct steps, we can reuse those approximation. First, the points that have gradient approximation and are within the radius \(q^{k}\) are determined. We denote these by \(x_{h}^{j}\)\((j=1,2,\cdots,m)\). The corresponding search directions and search step lengths are denotedby \(D_{h}^{j}\) and \(\delta_{h}^{j}\) (\(j=1,2,\cdots,m\)). We take \(D_{h}^{0}\) and \(\delta_{h}^{0}\) as the search direction and search step length in the direct step of the current iterate. We obtain  
\[S=\left[x_{h}^{1}-x_{0}^{k}\quad x_{h}^{1}-x_{0}^{k}\quad\cdots\quad x_{h}^{m}- x_{0}^{k}\right]. \tag{18}\]  
The Hessian at \(x_{0}^{k}\) can be approximated as,  
\[\
abla^{2}f(x_{0}^{k})\approx\
abla_{s}^{2}f(x_{0}^{k};S,\{\delta_{h}^{j}D_{ h}^{j}\})=(S^{\top})^{\dagger}\delta_{\
abla_{c}f}(x_{0}^{k};S,\{\delta_{h}^{j}D_{ h}^{j}\}), \tag{19}\]  
where \(\delta_{\
abla_{c}f}(x_{0}^{k};S,\{\delta_{h}^{j}D_{h}^{j}\})\) is defined in Definition 3. If the approximated Hessian is positive definite, then the search candidate is determined via  
\[x_{Q}=x_{0}^{k}-(\
abla_{s}^{2}f(x_{0}^{k};S,\{\delta_{h}^{j}D_{h}^{j}\}))^{- 1}\
abla_{c}f(x_{0}^{k};\delta^{k}D^{k}). \tag{20}\]  
If the approximate Hessian is not positive definite, we can perform a trust-region search by building a quadratic model with the approximate gradient and Hessian at \(x_{0}^{k}\). We label this quadratic step strategy as quadratic step strategy 2.