L'algorithme Remez

14

L'algorithme de Remez est une routine itérative bien connue pour approximer une fonction par un polynôme dans la norme minimax. Mais, comme le dit Nick Trefethen [1]:

La plupart de ces [implémentations] remontent à plusieurs années et en fait, la plupart d'entre elles ne résolvent pas le problème général de meilleure approximation tel que posé ci-dessus mais des variantes impliquant des variables discrètes ou un filtrage numérique. On peut trouver quelques autres programmes informatiques en circulation, mais dans l'ensemble, il semble qu'il n'y ait actuellement aucun programme largement utilisé pour calculer les meilleures approximations.

On peut également calculer la solution minimax en appliquant une optimisation par moindres carrés ou convexe, par exemple en utilisant Matlab et la boîte à outils CVX gratuite appliquée à la fonction Runge sur [-1, 1]:

m = 101; n = 11;            % 101 points, polynomial of degree 10
xi = linspace(-1, 1, m);    % equidistant points in [-1, 1]
ri = 1 ./ (1+(5*xi).^2);    % Runge function

tic                         % p is the polynomial of degree (n-1)
cvx_begin                   % minimize the distance in all points
    variable p(n);
    minimize( max(abs(polyval(p, xi) - ri)) );
cvx_end
toc                         % 0.17 sec for Matlab, CVX and SeDuMi

L'approximation avec les polynômes de Chebyshev a une norme minimax 0.1090tandis que cette approche atteint ici un minimum de 0.0654, la même valeur qui est calculée avec l'algorithme Remez dans la chebfunboîte à outils Matlab .

Y a-t-il un avantage à appliquer l'algorithme Remez plus compliqué si vous pouvez calculer la solution minimax plus rapidement et plus précisément avec un solveur d'optimisation? Existe-t-il des rapports / articles comparant ces deux approches sur des problèmes difficiles ou des cas de test?

-
[1] R. Pachon et LN Trefethen. BIT Numerical Mathematics (2008) Vol. 46.

Hans W.
la source

Réponses:

4

La «bonne» réponse dépend fortement de ce dont vous avez besoin pour votre approximant. Avez-vous vraiment besoin de la meilleure approximation pour une erreur liée? Ou juste une bonne approximation? Ou juste une bonne approximation au sens minmax?

Nick Trefethen a récemment donné un bel exemple où l'approximation de Remez est une mauvaise idée car elle minimise l'erreur maximale indépendamment de l'erreur moyenne sur tout l'intervalle, ce qui n'est peut-être pas ce que vous voulez. Bien sûr, l'erreur maximale peut être importante, mais elle est limitée pour les fonctions fluides.

Mise à jour

Suite à la discussion dans les commentaires ci-dessous, j'ai téléchargé la boîte à outils CVX et fait une comparaison directe avec l'algorithme Chebfun Remez (avertissement: je fais partie de l'équipe de développement Chebfun):

% Do the convex optimization bit.
m = 101; n = 11;            % 101 points, polynomial of degree 10
xi = linspace(-1, 1, m);    % equidistant points in [-1, 1]
ri = 1 ./ (1+(5*xi).^2);    % Runge function

tic                         % p is the polynomial of degree (n-1)
cvx_begin                   % minimize the distance in all points
    variable p(n);
    minimize( max(abs(polyval(p, xi) - ri)) );
cvx_end
toc_or = toc                % 0.17 sec for Matlab, CVX and SeDuMi

% Extract a Chebfun from the result
x = chebfun( [-1,1] );
A = [ chebfun(1) , x ];
for k=3:n, A(:,k) = A(:,k-1).*x; end
or = A * flipud(p)

% Make a chebfun of Runge's function
f = chebfun( @(x) 1 ./ ( 1 + 25*x.^2 ) )

% Get the best approximation using Remez
tic, cr = remez( f , 10 ); toc_cr = toc

% Get the maximum error in each case
fprintf( 'maximum error of convex optimization: %e (%f s)\n' , norm( f - or , inf ) , toc_or );
fprintf( 'maximum error of chebfun remez: %e (%f s)\n' , norm( f - cr , inf ) , toc_cr );

% Plot the two error curves
plot( [ f - cr , f - or ] );
legend( 'chebfun remez' , 'convex optimization' );

Après beaucoup de sortie, j'obtiens, sur mon ordinateur portable avec Matlab 2012a, la version 1.22 de CVX et le dernier instantané SVN de Chebfun:

maximum error of convex optimization: 6.665479e-02 (0.138933 s)
maximum error of chebfun remez: 6.592293e-02 (0.309443 s)

Notez que le Chebfun futilisé pour mesurer l'erreur est précis à 15 chiffres. Donc, Remez de Chebfun prend deux fois plus de temps, mais obtient une erreur globale plus petite. Il convient de noter que CVX utilise du code compilé pour l'optimisation alors que Chebfun est 100% natif Matlab. L'erreur minimale de 0.00654est l'erreur minimale «sur la grille», hors de cette grille, l'erreur peut aller jusqu'à 0.00659. Augmenter la taille de la grille pour m = 1001obtenir

maximum error of convex optimization: 6.594361e-02 (0.272887 s)
maximum error of chebfun remez: 6.592293e-02 (0.319717 s)

c'est-à-dire presque à la même vitesse, mais l'optimisation discrète est encore pire à partir du quatrième chiffre décimal. Enfin, en augmentant encore la taille de la grille pour m = 10001obtenir

maximum error of convex optimization: 6.592300e-02 (5.177657 s)
maximum error of chebfun remez: 6.592293e-02 (0.312316 s)

c'est-à-dire que l'optimisation discrète est maintenant plus de dix fois plus lente et est encore pire à partir du sixième chiffre.

L'essentiel est que Remez vous obtiendra le résultat globalement optimal. Bien que l'analogique discret puisse être rapide sur de petites grilles, il ne donnera pas un résultat correct.

Pedro
la source
Et N. Trefethen a souligné la même chose et a donné un exemple similaire dans l'article que je citais. La question n'était pas de la meilleure approximation, mais: Quel est l'avantage de l'algorithme Remez (de nos jours) si vous pouvez obtenir le même résultat avec un solveur convexe raisonnable ?
Hans W.
1
@HansWerner, je suis désolé, j'ai mal lu votre question. Votre solveur convexe ne vous donne pas le même résultat, du moins pas à tous les chiffres. Si je comprends bien votre code convexe, vous minimisez l'erreur maximale sur un ensemble discret de points. Il s'agit d'une bonne approximation - mais pas la même chose que - de minimiser l'erreur maximale globale.
Pedro
Le solveur convexe dans ce cas a donné un meilleur résultat. Pensez-y, l'algorithme Remez est une procédure itérative, assez similaire à une routine d'optimisation, et ne retournera pas non plus un résultat exact. Dans le cas concret ci-dessus, la solution de l'optimisation était meilleure, c'est-à-dire avait une norme maximale globale plus petite, que le résultat de la meilleure implémentation de Remez que je connaisse. La question est toujours ouverte .
Hans W.
@HansWerner, comment avez-vous mesuré l'erreur maximale de la solution obtenue avec le solveur convexe? L'algorithme Remez chebfundoit itérer jusqu'à ce que le minimum soit atteint à la précision de la machine (dans un sens).
Pedro
Pas nécessairement; il existe des options comme «tol» (qui est une tolérance relative) ou «maxiter» pour chebfun/remez, mais il existe des options similaires pour tous les types de solveurs d'optimisation. D'une certaine façon, on pourrait dire que Remez est une routine d'optimisation spécialisée pour une certaine tâche. Et la question est: les solveurs à usage général ont-ils rattrapé leur retard et il n'y a plus besoin d'un tel solveur spécialisé? Bien sûr, je peux me tromper.
Hans W.