TY - JOUR

T1 - On solution of tropical discrete best approximation problems

AU - Кривулин, Николай Кимович

N1 - Krivulin N. On solution of tropical discrete best approximation problems // Soft Computing. 2024. Vol. 28, N20. P. 12097-12112. DOI: 10.1007/s00500-024-09940-4. URL: https://link.springer.com/article/10.1007/s00500-024-09940-4

PY - 2024/10/1

Y1 - 2024/10/1

N2 - We consider a discrete best approximation problem formulated in the framework of tropical algebra, which deals with the theory and applications of algebraic systems with idempotent operations. Given a set of samples of input and output of an unknown function, the problem is to construct a generalized tropical Puiseux polynomial that best approximates the function in the sense of a tropical distance function. The construction of an approximate polynomial involves the evaluation of both unknown coefficient and exponent of each monomial in the polynomial. To solve the approximation problem, we first reduce the problem to an equation in unknown vector of coefficients, which is given by a matrix with entries parameterized by unknown exponents. We derive a best approximate solution of the equation, which yields both vector of coefficients and approximation error parameterized by the exponents. Optimal values of exponents are found by minimization of the approximation error, which is transformed into minimization of a function of exponents over all partitions of a finite set. We solve this minimization problem in terms of max-plus algebra (where addition is defined as maximum and multiplication as arithmetic addition) by using a computational procedure based on the agglomerative clustering technique. This solution is extended to the minimization problem of finding optimal exponents in the polynomial in terms of max-algebra (where addition is defined as maximum). The results obtained are applied to develop new solutions for conventional problems of discrete best Chebyshev approximation of real functions by piecewise linear functions and piecewise Puiseux polynomials. We discuss computational complexity of the proposed solution and estimate upper bounds on the computational time. We demonstrate examples of approximation problems solved in terms of max-plus and max-algebra, and give graphical illustrations.

AB - We consider a discrete best approximation problem formulated in the framework of tropical algebra, which deals with the theory and applications of algebraic systems with idempotent operations. Given a set of samples of input and output of an unknown function, the problem is to construct a generalized tropical Puiseux polynomial that best approximates the function in the sense of a tropical distance function. The construction of an approximate polynomial involves the evaluation of both unknown coefficient and exponent of each monomial in the polynomial. To solve the approximation problem, we first reduce the problem to an equation in unknown vector of coefficients, which is given by a matrix with entries parameterized by unknown exponents. We derive a best approximate solution of the equation, which yields both vector of coefficients and approximation error parameterized by the exponents. Optimal values of exponents are found by minimization of the approximation error, which is transformed into minimization of a function of exponents over all partitions of a finite set. We solve this minimization problem in terms of max-plus algebra (where addition is defined as maximum and multiplication as arithmetic addition) by using a computational procedure based on the agglomerative clustering technique. This solution is extended to the minimization problem of finding optimal exponents in the polynomial in terms of max-algebra (where addition is defined as maximum). The results obtained are applied to develop new solutions for conventional problems of discrete best Chebyshev approximation of real functions by piecewise linear functions and piecewise Puiseux polynomials. We discuss computational complexity of the proposed solution and estimate upper bounds on the computational time. We demonstrate examples of approximation problems solved in terms of max-plus and max-algebra, and give graphical illustrations.

KW - tropical semifield

KW - tropical Puiseux polynomial

KW - best approximate solution

KW - discrete best approximation

KW - Chebyshev approximation

KW - Tropical Puiseux polynomial

KW - Best approximate solution

KW - Tropical semifield

KW - Discrete best approximation

UR - https://www.mendeley.com/catalogue/eb2cd00f-12bc-34e2-8200-3bff18f13e7f/

U2 - 10.1007/s00500-024-09940-4

DO - 10.1007/s00500-024-09940-4

M3 - Article

VL - 28

SP - 12097

EP - 12112

JO - Soft Computing

JF - Soft Computing

SN - 1432-7643

IS - 20

ER -