## 2 Background  
Unless otherwise stated, we use the standard notation found in [36]. We work in the finite-dimensional space \(\mathbb{R}^{n}\) with the inner product \(x^{\top}y=\sum_{i=1}^{n}x_{i}y_{i}\). The norm of a vector is denoted as \(\|x\|\) and is taken to be the \(\ell_{2}\) norm. Given a matrix \(A\in\mathbb{R}^{n\times m}\), the \(\ell_{2}\) induced matrix norm is used. We denote by \(B(x^{0};\Delta)\) the closed ball centered at \(x^{0}\) with radius \(\Delta\). The identity matrix in \(\mathbb{R}^{n\times n}\) is denoted by \(\mathrm{Id}_{n}\), and the vector of all ones in \(\mathbb{R}^{n}\) is denoted by \(\mathbf{1}_{n}\). The _Minkowski sum_ of two sets of vectors \(A\) and \(B\) is denoted by \(A\oplus B\). That is,  
\[A\oplus B=\{a+b:a\in A,b\in B\}.\]  
In the next sections, we will refer to a calculus-based approach and a non-calculus approach to approximate gradients and Hessians. Let us clarify the meanings of these two approaches. We begin with the non-calculus-based approach. Let \(F:\mathbb{R}^{n}\rightarrow\mathbb{R}\) and let \(Q_{F}(x^{k})\) be a quadratic interpolation of \(F\) at \(x^{k}\) using \((n+1)(n+2)/2\) distinct sample points poised for quadratic interpolation. An approximation of the gradient of \(F\) at \(x^{k}\), denoted by \(g^{k}\), is obtained by computing \(\
abla Q_{F}(x^{k})\), and an approximation of the Hessian of \(F\) at \(x^{k}\), denoted by \(H^{k}\), is obtained by computing \(\
abla^{2}Q_{F}(x^{k})\). We now explain the calculus-based approach. Let \(F:\mathbb{R}^{n}\rightarrow\mathbb{R}\) be constructed using \(f_{1}:\mathbb{R}^{n}\rightarrow\mathbb{R}\) and \(f_{2}:\mathbb{R}^{n}\rightarrow\mathbb{R}\). Let \(Q_{f_{1}}\) and \(Q_{f_{2}}\) be quadratic interpolation functions of \(f_{1}\) and \(f_{2}\), respectively. When a calculus-based approach is employed and the composite objective function \(F\) has the form \(F=f_{1}\cdot f_{2}\), then  
\[g^{k}=\
abla(Q_{f_{1}}\cdot Q_{f_{2}})(x^{k})=f_{1}(x^{k})\
abla Q_{f_{2}}(x^ {k})+f_{2}(x^{k})\
abla Q_{f_{1}}(x^{k}), \tag{1}\]  
and  
\[H^{k}=\
abla^{2}(Q_{f_{1}}\cdot Q_{f_{2}})(x^{k})=f_{2}(x^{k})\
abla^{2}Q_{f_ {1}}(x^{k})+\
abla Q_{f_{1}}(x^{k})\Big{(}\
abla Q_{f_{2}}(x^{k})\Big{)}^{\top }+\
abla Q_{f_{2}}(x^{k})\Big{(}\
abla Q_{f_{1}}(x^{k})\Big{)}^{\top}+f_{1}(x^ {k})\
abla^{2}Q_{f_{2}}(x^{k}). \tag{2}\]  
Similarly, when the composite objective function \(F\) has the form \(F=\frac{f_{1}}{f_{2}}\), then (assuming \(f_{2}(x^{k})\
eq 0\))  
\[g^{k}=\
abla\Bigg{(}\frac{Q_{f_{1}}}{Q_{f_{2}}}\Bigg{)}(x^{k})=\frac{f_{2}(x^ {k})\
abla Q_{f_{1}}(x^{k})-f_{1}(x^{k})\
abla Q_{f_{2}}(x^{k})}{[f_{2}(x^{k} )]^{2}}. \tag{3}\]  
and  
\[H^{k}=\
abla^{2}\Bigg{(}\frac{Q_{f_{1}}}{Q_{f_{2}}}\Bigg{)}(x^{k })=\frac{1}{[f_{2}(x^{k})]^{3}}\Big{[}[f_{2}(x^{k})]^{2}\
abla^{2}Q_{f_{1}}(x^ {k})-f_{1}(x^{k})f_{2}(x^{k})\
abla^{2}Q_{f_{2}}(x^{k})+2f_{1}(x^{k})\
abla Q_ {f_{2}}(x^{k})\
abla Q_{f_{2}}(x^{k})^{\top}\] \[-f_{2}(x^{k})\Big{(}\
abla Q_{f_{1}}(x^{k})\
abla Q_{f_{2}}(x^{k} )^{\top}+\
abla Q_{f_{2}}(x^{k})\
abla Q_{f_{1}}(x^{k})^{\top}\Big{)}\Big{]}, \tag{4}\]  
To compute \(H^{k}\), the technique called the (generalized) simplex Hessian is utilized [59]. When the two matrices involved in the computation of the simplex Hessian are square matrices that have been properly chosen, the simplex Hessian is equal to the Hessian of the quadratic interpolation function. The formula for computing simplex Hessians is based on simple matrix algebra. Hence, this technique is straightforward to implement in an algorithm. The formula for computing the simplex Hessian requires the computation of \(n+1\) simplex gradients. Definition 1 ([55]): _(Simplex gradient). Let \(f:\operatorname{dom}f\subseteq\mathbb{R}^{n}\to\mathbb{R}\). Let \(x^{0}\in\operatorname{dom}f\) be the point of interest. Let \(T= \begin{bmatrix}t^{1}&t^{2}&\cdots&t^{n}\end{bmatrix} \in\mathbb{R}^{n\times n}\) with \(x^{0}\oplus T\in\operatorname{dom}f\).