Abstract
Linear Chebyshev approximation, or the minimax problem, is a cornerstone of numerical analysis, traditionally solved via Lawson’s iteration. However, Lawson’s method suffers from linear convergence and difficulty in identifying the equioscillation points that characterize optimal solutions. This paper presents a modern optimization framework for the minimax problem by formulating it as an $L_q$-weighted dual programming problem. By applying a second-order interior-point method (IPM) to the $L_2$-weighted dual, we achieve superlinear convergence and precise identification of reference points. Experimental results on real and complex-valued functions demonstrate that the proposed method significantly outperforms traditional iterations, reducing the required steps from thousands to fewer than thirty.
Introduction
In numerical analysis and approximation theory, the linear Chebyshev approximation problem seeks to find a linear combination of basis functions that minimizes the maximum absolute error across a discrete set of points. This "minimax" objective is essential for creating optimal polynomial approximations where the error is distributed uniformly across the domain.
For decades, the standard approach has been Lawson’s iteration, an algorithm that solves a sequence of weighted least-squares problems. While elegant and simple to implement, Lawson’s iteration is a first-order method characterized by slow, linear convergence. In practical scenarios involving dense sampling or high-degree polynomials, the algorithm often stalls. Furthermore, it fails to clearly isolate the "reference points"—the specific nodes where the maximum error is attained—which are critical for verifying the optimality of the solution via the Alternation Theorem.
Methodology
1. Dual Programming Formulation
The authors reframe the primal minimax problem through the lens of Lagrange duality. By transforming the problem into an $L_q$-weighted dual, the focus shifts from the function coefficients to the weights assigned to each data node. This dual perspective is mathematically advantageous because the optimal solution to a minimax problem is inherently sparse; it is defined by a small subset of points where the error "equioscillates."
2. The Interior-Point Method (IPM)
To solve the dual problem, the paper introduces a Newton-type interior-point method. Unlike the first-order Lawson’s iteration, the IPM utilizes second-order information (the Hessian) to navigate the "central path" toward the optimal weights. This transition from first-order to second-order optimization allows the algorithm to achieve superlinear convergence.
3. Computational Stability and Efficiency
High-degree polynomial approximation often involves ill-conditioned Vandermonde matrices. To maintain numerical stability, the authors integrate the Arnoldi process into the solver. Additionally, they implement a "weight-filtering" mechanism. Since the dual solution is sparse, nodes with negligible weights can be pruned during the optimization process, significantly accelerating the final convergence stages without sacrificing accuracy.
Theoretical Contributions
Beyond the algorithmic improvements, the paper provides a fresh, self-contained proof of the Alternation Theorem. By using Linear Programming (LP) duality, the authors bridge the gap between classical approximation theory and modern convex optimization, making the theoretical foundations of minimax approximation more accessible to the optimization community.
Experimental Evaluation
The proposed method was evaluated against several challenging benchmarks:
- Real-valued functions: $f_1(x) = \sin(20|x|x)$ and the Runge function $f_2(x) = 1/(1+25x^2)$ on the interval $[-1, 1]$.
- Complex-valued functions: $g_1(z) = (2z + 1)^{-1/2}$ and $g_2(z) = (1 + z^4)^{1/2}$ sampled on a semi-disc.
- Sampling Density: Tests typically utilized 2,001 distinct nodes to simulate the dense conditions where Lawson’s iteration typically fails.
Key Results
- Convergence Speed: In real-valued tests, the IPM consistently converged within 18 to 27 iterations. In contrast, Lawson’s iteration frequently failed to reach the same tolerance even after 1,000 iterations.
- Reference Point Identification: The IPM successfully identified the exact number of equioscillation points required by theory (e.g., exactly 22 points for a degree-21 polynomial). Lawson’s method, however, tended to leave weights "scattered" across many adjacent nodes, obscuring the true reference set.
- Complex Domain Robustness: The dual formulation proved highly effective for complex-valued functions, maintaining efficiency where standard LP formulations would typically require a doubling of constraints.
Conclusion and Future Work
By applying modern interior-point techniques to the dual of the Chebyshev approximation problem, this research provides a robust and high-performance alternative to classical methods. The approach not only accelerates convergence but also provides a clearer numerical picture of the underlying approximation theory.
Future research directions include extending this dual framework to rational minimax approximation. Rational functions (ratios of polynomials) offer even greater approximation power but introduce significant non-linearities that challenge current optimization solvers.
Summary updated