Optimization-aided construction of multivariate Chebyshev polynomials (Q6651978)

This paper is on the construction of multivariate Chebyshev polynomials through a semi-programming procedure.\N\NUsing the equivalent characterizations of Chebyshev polynomials in dimension one, the paper first generalizes the definition of Chebyshev polynomials to the multivariate setting using\N\[\N\min_{p\in\mathcal{P}_n^d} \|p\|_\Omega, \mbox{ subject to \(p\) being monic},\N\]\Nwhere \(\|p\|_\Omega:=\max_{x\in\Omega} |p(x)|\) and \(\mathcal{P}_{n}^d\) is the space of \(d\)-variate polynomials of degree up to \(n\). With specific definition of monic polynomials, the above problem becomes\N\[\N\min_{p\in\mathcal{P}_{n-1}^d} \|m_k-p\|_\Omega,\N\]\Nwhere \(m_k = x_1^{k_1}\cdots x_d^{k_d}\) and \(|k| = k_1+\cdots+k_d=n\). Moreover, the paper mainly considers four types of domains for \(\Omega\): the simplex \(S\), the cross-polytope \(C\) (\(\ell_1\)-ball), the Euclidean ball (\(\ell_2\)-ball), and the hypercube \(H\) (\(\ell_\infty\) ball).\N\NThe paper then discusses the connection of multivariate Chebyshev polynomials with the solutions to the best approximation problem \(E_{\mathcal V}(f,\Omega) = \min_{v\in\mathcal V} \|f-v\|_\Omega = \|f-v^*\|_\Omega\), which can be expressed as its duality: \(E_{\mathcal V}(f,\Omega)=\max_{\lambda \in C(\Omega)^*} \lambda (f)\) subject to \(\lambda|_\mathcal{V} = 0\) and \(\|\lambda\|_{C(\Omega)^*} = 1\). The characterization of the best approximant \(v^*\) to \(f\in C(\Omega)\) is then given in terms of an extremal signature \(\sigma\) for \(\mathcal{V}\). To reduce the number of subproblems involved in solving the minimization problem, the paper discusses two reduction techniques. One is to discard zero indices \(k_i\), and the other is to utilize the group invariance property of the problem. Some known results of multivariate Chebyshev polynomials are then given for hypercube \(\Omega=H\), \(\Omega = B\), and \(\Omega = S\). More generally, the domain \(\Omega\) could be any compact basic semi-algebraic set determined by polynomials \(g_1,\ldots, g_H\) such that \(\Omega=\{x\in\mathbb{R}^d: g_1(x)\ge0,\ldots, g_H(x)\ge0\}\).\N\NThe paper next discusses the main computational procedure to solve for the multivariate polynomials through semi-definite programming. First, the primal minimization problem can be reformulated as\N\[\N\min_{c\in\mathbb{R}, p\in \mathcal{P}_{n-1}^d}c \quad \mbox{ subject to } \begin{cases}c+m_k-p\in \mathcal{P}_+^d(\Omega)\\\Nc-m_k+p\in \mathcal{P}_+^d(\Omega)\end{cases},\N\]\Nwhere \(\mathcal{P}_+^d(\Omega)\) is the cone of \(d\)-variate polynomials that are nonnegative on \(\Omega\). Its dual problem is then rewritten as\N\[\N\max_{\mu\in \mathcal{M}(\Omega)} \int_\Omega m_k d\mu \quad \mbox{ subject to } \int_\Omega pd \mu =0 \quad \forall p\in \mathcal{P}_{n-1}^d \mbox{ and } \int_\Omega d|\mu|=1,\N\]\Nwhere \(\mathcal{M}(\Omega)\) is the space of finite signed Borel measures on \(\Omega\). With \(\mathcal{M}_+(\Omega)\) denoting the cone of finite nonnegative Borel measures on \(\Omega\), the dual problem is equivalent to\N\[\N\max_{\mu^\pm\in \mathcal{M}_+(\Omega)} \int_\Omega m_k d(\mu^+-\mu^-) \quad \mbox{ subject to } \int_\Omega pd (\mu^+-\mu^-) =0 \quad \forall p\in \mathcal{P}_{n-1}^d \mbox{ and } \int_\Omega d(\mu^++\mu^-)=1.\N\]\NThen, using the duality relation \(\mathcal M_+(\Omega)^* = \mathcal{P}_+^d\) and the connection between the dual cone of \(\mathcal{Q}(g_1,\ldots, g_H):=\{p: p=\sigma_0+\sigma_1 g_1+\cdots+\sigma_H g_H\}\) and the positive semidefinite matrices, the dual problem can be linked to a sequence \(\{\mathrm{ub}_t'\): \(t\in\mathbb{N}_0\}\) of dual semidefinite programs:\N\begin{align*}\N&\mathrm{ub}_t':=\sup_{y^\pm\in\mathbb{R}^{\{0,\ldots, 2t\}^d}} \sum_{|\ell|\le N} \mathrm{coeff}_{m_\ell}(m_k)(y_\ell^+-y_\ell^-) \\\N\mbox{ subject to }\ &y_\ell^+-y_\ell^- =0 \quad \forall |\ell|\le n-1, y_0^+ +y_0^-=1, \\\N\mbox { and }\ &\mathrm{Hank}_t(y^\pm)\succeq 0, \mathrm{Hank}_{t-n_1'}(G_1y^\pm)\succeq 0,\ldots, \mathrm{Hank}_{t-n_H'}(G_H y^\pm) \succeq0,\N\end{align*}\Nwhere \(n_h':=\lceil \mathrm{deg}(g_h)/2\rceil\) for \(h=1,\ldots, H\), \(y_\ell^\pm:=\int_\Omega m_\ell d\mu^\pm\) are the moments with respect to \(\mu^\pm\), \(y^\pm = (y_\ell^\pm)_{\ell\in\mathbb{N}_0^d}\), and \(\mathrm{Hank}(y)\) is the Hankel matrix determined by the sequence \(y=(y_\ell)_{\ell\in\mathbb{N}_0^d}\) having entries \(y_{i+j}, i,j\in \mathbb{N}_0^d\), and \(G_h(y)_\ell:=\sum_{|\ell'|\le \mathrm{deg}(g_h)}\mathrm{coeff}_{m_{\ell'}}(g_h)y_{\ell+\ell'}\). More importantly, one has \(\lim_{t\rightarrow\infty} \mathrm{ub}_t' = E_{\mathcal{P}_{n-1}^d}(f,\Omega)\).\N\NWith the computational procedure, the paper demonstrates results of multivariate Chebyshev polynomials for \(d=3\) and \(n\) up to 6 in the cases of \(\Omega= C, B, S\). Especially, explicit Chebyshev polynomials are found and proved for the case \(m_{2,2,1}\) for \(\Omega=B\) and the case \(m_{2,1,1}\) for \(\Omega=S\).