Hassane Sadok (univ. Littorale, France)
Approximation and convex programming approaches for solving a min-max problem
(Joint work with Mohammed Bellalij and Yousef Saad)
Krylov subspace methods are strongly related to polynomial spaces and their convergence analysis can naturally be deduced from approximation theory. Analyses of this type lead to discrete min-max approximation problems over the spectrum of the matrix, from which uppers bound of the relative Euclidean residual norm are derived. Recently, we have presented a new approach to analyze the convergence rate of the GMRES method or the Arnoldi iteration, which was based on an expression for the residual norm using determinants of Krylov matrices. An interesting feature of this treatment is that it allows to provide, among other things, an analysis of the convergence for normal matrices, using convex constrained optimization. The goal of this paper is to explore the relationship between these two approaches. Specifically, we show that for normal matrices, the Karush-Kuhn-Tucker (KKT) optimality conditions deduced from the convex maximization problem and the characterization properties of polynomial of best approximation on a finite set of points are identical. Therefore, these two approaches are mathematically equivalent.