The Polynomial Fitting Problem


      The Polynomial Fitting Problem has its roots in electronic filter design [RG75], and challenges an optimization procedure by forcing it to find parameter values with grossly different magnitudes, something very common in technical systems. The first metaheuristic used to deal with this problem has been presented in [SP95] . The problem lies in finding the coefficients of the following polynomial in :

such that



where is a Chebychev polynomial of degree . The Chebychev Polynomials are defined recursively according to the difference equation and , with the initial conditions and .

The solution to the Polynomial Fitting Problem consists of the coefficients of . This polynomial oscillates between -1 and 1 when its argument is between -1 and 1. Outside this region, the polynomial rises steeply in the direction of high positive ordinate values.

If is a solution and

then the pseudocode algorithm shown below is used in order to transform the constraints of this problem into an objective function to be minimized, called [HL00,ALN03]. Each parameter of this function (coefficient of the polynomial to fit to) is in the range .

Click here to get this description in tex format and here to get the figure in eps format.


Instances and best known solutions for those instances:

      The instances of this problem depends on the Chebychev polynomial employed to fit to. Thus, if we use

, or

we have a nine-parameter problem and a seventeen-parameter problem, respectively. The objective function value of the optimum is , i.e., the solution and the Chebychev polynomial fit exactly.

Related Papers:

[ALN03] E. Alba, F. Luna, and A.J. Nebro.Parallel Heterogenous Genetic Algorithms for Continuous Optimization. NIDISC'03 (to appear), 2003.

[HL00] F. Herrera and M. Lozano. Gradual Distributed Real-Coded Genetic Algorithms. IEEE Transactions on Evolutionary Computation, 4(1): 43-63, 2000.

[RG75] L.R. Rabiner and B. Gold. Theory and Applications of Digital Signal Processing. Prentice-Hall, Englewood Cliffs, N.J.,1975.

[SP95] R. Storn and K. Price. Differential evolution - A simple efficient adaptive scheme for global optimization over continuous spaces. Technical Report 95-012, Int. Comp. Sci. Inst., Berkeley, CA, 1995.

Click here to get the bibliography in bibtex format.

Last Updated: 4/7/03                                                                                For any question or suggestion, click here to contact with us.