Optimization-aided construction of multivariate Chebyshev polynomials
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\).
- Symmetric multivariate Chebyshev polynomials
- Chebyshev multivariate polynomial approximation and point reduction procedure
- Chebyshev-type extremal problems for multivariate polynomials on convex bodies.
- The multivariate integer Chebyshev problem
- Multivariate approximation by polynomial and generalized rational functions
- A Unified Approach to Certain Problems of Approximation and Minimization
- An explicit class of min-max polynomials on the ball and on the sphere
- Basc: constrained approximation by semidefinite programming
- Best approximation of monomials in several variables
- Best approximation to monomials on a cube
- Bivariate polynomials of least deviation from zero
- Chebyshev approximation to zero
- Chebyshev polynomials of several variables
- Chebyshev polynomials. From approximation theory to algebra and number theory
- Computation of Chebyshev polynomials for union of intervals
- Determining projection constants of univariate polynomial spaces
- Global optimization with polynomials and the problem of moments
- GloptiPoly 3: moments, optimization and semidefinite programming
- scientific article; zbMATH DE number 1688610 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- On multivariate polynomials of least deviation from zero on the unit ball
- On Polynomials of Least Deviation from Zero in Several Variables
- Parameterfreie Abschätzung und Realisierung von Erwartungswerten
- Polynomials of least deviation from zero and Chebyshev-type cubature formulas
- Positive polynomials in control.
- Semidefinite programming and integer programming
- Some Chebyshev approximations by polynomials in two variables
- Tchebycheff polynomials on a triangular region
- The moment problem
- The moment-SOS hierarchy
This page was built for publication: Optimization-aided construction of multivariate Chebyshev polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6651978)
