A convex dual problem for the rational minimax approximation and Lawson's iteration

Lei-Hong Zhang, Linyi Yang, Wei Hong Yang, Ya-Nan Zhang

Introduction

In the field of approximation theory, the "minimax" problem seeks to find a function that minimizes the maximum possible error over a specific domain. While this is a well-understood task for simple polynomials, rational minimax approximation—where the approximating function is a ratio of two polynomials—presents a significant challenge. This problem is inherently non-convex, making it difficult to guarantee that a solution is the global optimum rather than a local minimum.

This paper introduces a novel approach to this problem by deriving a convex dual for the non-convex primal problem. By bridging the gap between classical approximation theory and modern optimization, the authors present "d-Lawson," a new iteration that guarantees global optimality under specific conditions and offers superior stability and precision compared to existing state-of-the-art methods.

The Challenge of Rational Approximation

Rational minimax approximation is often described as a "non-convex nightmare." Unlike polynomial approximation, which can be solved efficiently using the Remez algorithm, rational functions introduce two primary complications:

  1. Non-convexity: Traditional optimization methods frequently get trapped in local minima, failing to find the best possible fit.
  2. Complex Plane Complications: Computing these approximations in the complex plane is significantly more difficult than on a real interval. There are few "sufficient conditions" available to prove that a computed solution is truly the global best.

Existing fast methods, such as the Adaptive Antoulas-Anderson (AAA) algorithm or Rational Krylov Fitting (RKFIT), are excellent for finding high-quality fits quickly. However, they lack the theoretical framework to guarantee a true minimax solution. This research seeks a reliable path to that global optimum.

Methodology: The d-Lawson Algorithm

The authors' primary contribution is the transformation of the rational problem into a manageable optimization framework through several key steps:

Linearized Reformulation and Lagrange Duality

The process begins by transforming the rational problem into a linearized form. The authors then derive a convex dual problem for this linearization. This represents a significant breakthrough: while the original primal problem is non-convex, its dual is a concave maximization problem over a probability simplex. This dual problem is much easier to solve using standard optimization techniques.

The d-Lawson Framework

Building on this duality, the authors propose "d-Lawson," a refined version of Lawson’s iteration (an iteratively reweighted least-squares approach). In this new framework, the weights used to fit the data are revealed to be the dual variables of the optimization problem. This provides a rigorous mathematical foundation for the weight adjustments that were previously handled heuristically.

Numerical Robustness

To combat the numerical instability often associated with high-degree polynomials (the "Vandermonde blues"), the algorithm utilizes Arnoldi processes and QR factorizations. These techniques allow the computations to remain stable even as they approach machine precision.

Experimental Evaluation

The algorithm was evaluated using a suite of challenging mathematical test functions rather than standard datasets. These included:

  • Real-valued functions: The absolute value function $|x|$ (noted for its non-smoothness) and $\sqrt{x}$.
  • Singularities: Functions such as $f(x) = -1/\log|x|$ and various hyperbolic sines.
  • Complex-valued functions: Analytic functions like $\tan(z)$ and $\log(1+z/2)$ sampled on the unit disc, as well as functions containing poles and branch point singularities.

Key Insights and Results

Duality as an Optimality Test

The authors prove that "strong duality" (where the primal and dual solutions match) holds if and only if Ruttan’s sufficient condition is satisfied. This provides a practical, verifiable test for global optimality that was previously missing for many complex-plane problems.

Performance and Precision

  • Equioscillation: The d-Lawson algorithm successfully recovers the "equioscillation" property—a hallmark of true minimax solutions where the error curve hits its maximum value at multiple points with alternating signs. Methods like RKFIT often fail to capture this property.
  • High Precision: For analytic functions, the method consistently reaches errors as low as $10^{-15}$, effectively hitting the limits of machine precision.
  • Monotonicity and Filtering: The dual objective function in d-Lawson generally increases monotonically, providing a reliable monitor of progress. Additionally, a "filtering" technique allows the algorithm to ignore nodes with low error in later iterations, reducing computational costs without sacrificing accuracy.

Limitations and Future Directions

While d-Lawson is robust, it is generally slower than the AAA algorithm. The authors suggest a hybrid approach where AAA provides a "warm start" for d-Lawson to refine. Furthermore, while the algorithm performs excellently in practice, a formal theoretical proof of the convergence rate for the rational case remains an open challenge.

Future work may also explore alternative solvers for the dual problem, such as interior-point or projected gradient methods, to further enhance the efficiency of this convex programming approach to rational approximation.

Summary updated

BibTeX
@article{zhang2024convex,
  author = {Lei-Hong Zhang and Linyi Yang and Wei Hong Yang and Ya-Nan Zhang},
  title = {{A convex dual problem for the rational minimax approximation and Lawson's iteration}},
  journal = {Math. Comput.},
  year = {2024},
  doi = {10.1090/mcom/4021},
}
Figure