Connecting optimization with spectral analysis of tri-diagonal matrices

Jean B Lasserre (1, 2)

1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
2 IMT - Institut de Mathématiques de Toulouse UMR5219

We show that the global minimum (resp. maximum) of a continuous function on a compact set can be approximated from above (resp. from below) by computing the smallest (rest. largest) eigenvalue of a hierarchy of (r × r) tri-diagonal univariate moment matrices of increasing size. Equivalently it reduces to computing the smallest (resp. largest) root of a certain univariate degree-r orthonormal polynomial. This provides a strong connection between the fields of optimization, orthogonal polynomials, numerical analysis and linear algebra, via asymptotic spectral analysis of tri-diagonal symmetric matrices.

Mots clés: tri-diagonal matrices; orthogonal polynomials; hierarchy of upper bounds; global optimization

Domaines: Optimisation et contrôle [math.OC]; Analyse numérique [math.NA]

Jean B Lasserre. Connecting optimization with spectral analysis of tri-diagonal matrices. Mathematical Programming, Series A, 2020, 190, pp.795--809. ⟨10.1007/s10107-020-01549-3⟩. ⟨hal-02190818v4⟩