Questa tesi di dottorato riguarda lo studio comparativo di stime per funzioni polinomiali su multi-intervalli reali nell’ambito della programmazione logica con vincoli polinomiali. La trattazione si apre con l’introduzione di stime per funzioni polinomiali reali definite su un intervallo reale limitato a valori non negativi. Le stime analizzate sono di tre tipologie: la prima si basa sul massimo e sul minimo dei coefficienti dei polinomi di Bernstein; la seconda si fonda sull’aritmetica degli intervalli; la terza comprende semplici stime ottenute considerando i valori assoluti ed i segni dei coefficienti della funzione polinomiale e l'estremo superiore dell’intervallo. L’obiettivo del lavoro è identificare, tra le stime studiate, quella che meglio approssima il comportamento della funzione polinomiale. Inizialmente si confrontano le stime semplici e quella ottenuta dall’aritmetica degli intervalli, la quale, su un intervallo a valori non negativi, risulta la più efficace perché tiene conto sia dell’estremo inferiore sia di quello superiore. Successivamente, si mette a confronto anche la stima basata sui polinomi di Bernstein. In quest’ultima fase emergono alcune difficoltà, poiché i polinomi di Bernstein sono espressi in una base specifica, mentre le altre stime utilizzano la base canonica. Questa differenza rende le espressioni difficilmente confrontabili. Tuttavia, sfruttando opportune maggiorazioni, in particolare basate sul binomio di Newton e sulle proprietà dei coefficienti binomiali, è possibile superare tali ostacoli. Si giunge così alla conclusione che la stima basata sui coefficienti del polinomio di Bernstein è la più precisa, sebbene risulti anche la più onerosa dal punto di vista computazionale. Una volta analizzato il problema in una dimensione, le tre tipologie di stime vengono estese a multi-intervalli in più variabili. Si effettua quindi un confronto tra le diverse approssimazioni nei multi-intervalli. Prestando particolare attenzione all’uso dei multi-indici, si dimostra che le stime basate sui polinomi di Bernstein offrono le migliori approssimazioni, ma presentano le peggiori prestazioni nei termini del tempo di calcolo. Un’ulteriore estensione trattata nella tesi riguarda lo studio delle stime associate al campionamento di funzioni polinomiali. L’analisi prende in considerazione dapprima l’intervallo unitario e successivamente un intervallo reale a valori non ne\-ga\-ti\-vi. Nel caso unidimensionale, adattando opportunamente i valori assoluti delle tre tipologie di stime alle derivate prime e seconde, è possibile definire e confrontare queste nuove approssimazioni. Lo studio viene poi esteso al caso multidimensionale, considerando prima il multi-intervallo unitario e poi multi-intervalli con valori non negativi. Mentre nel multi-intervallo unitario si ottengono risultati coerenti con il caso unidimensionale, nel caso di multi-intervalli non negativi la situazione diventa più delicata, poiché nelle maggiorazioni occorre prestare particolare attenzione agli estremi degli intervalli. Il quadro si è complicato, ma per multi-intervalli non negativi si è arrivati inizialmente a comprendere il comportamento in due casi specifici: il primo quando tutti gli estremi superiori sono maggiori o uguali di uno; il secondo quando tutti gli estremi superiori sono minori o uguali di uno. Si sono poi ottenuti risultati generali per qualsiasi multi-intervallo non negativo, anche grazie all'uso delle stime precedentemente ottenute. Il risultato principale di questa tesi consiste in un insieme di ordinamenti tra diverse stime per funzioni polinomiali, sia per intervalli reali non negativi, sia per multi-intervalli reali non negativi.
This Doctoral Thesis focuses on the comparative study of bounds for polynomial functions over real multi-intervals within the framework of logic programming with polynomial constraints. The Thesis begins by introducing bounds for real polynomial functions defined over a bounded real interval with non-negative values. Three types of bounds are analyzed: the first is based on the maximum and minimum of the Bernstein polynomial coefficients; the second relies on interval arithmetic; the third consists of simple bounds obtained by considering the absolute values and the signs of the polynomial function coefficients and the right bound of the interval. The aim of the research is to identify, among the proposed bounds, the one that best approximates the behavior of the polynomial function. The study first compares the simple bounds and the one derived from interval arithmetic, which is the most accurate on a non-negative interval, because it takes into account both the left and right bounds. Then, the bounds based on Bernstein polynomials are compared with the others. At this stage, several difficulties arise, as Bernstein polynomials are expressed in a specific basis, whereas the other bounds use the canonical basis. This difference makes the expressions difficult to compare. However, by employing appropriate upper bounds---specifically, Newton’s binomial formula and the properties of binomial coefficients---these difficulties can be overcome. It is thus shown that the bounds based on the Bernstein polynomial coefficients is the most accurate, although also the most computationally expensive. Once the problem has been addressed in one dimension, the three types of bounds are extended to multi-intervals. A comparison is then made among the various approximations over multi-intervals. By carefully handling the needed multi-indices, it is shown that the bounds based on Bernstein polynomials provide the best approximations, but the worst computational time. A further extension explored in the Thesis is the study of bounds related to the sampling of polynomial functions. The analysis begins with the unit interval and then considers a non-negative real interval. In the unidimensional case, by suitably adapting the absolute values of the three types of bounds to first and second derivatives, new approximations can be defined and compared. The study is then extended to higher dimensions, first to the unit multi-interval and then to a box with non-negative values. While in the unit multi-interval the results are consistent with the unidimensional case, the box scenario for non-negative multi-interval is more complex, since greater attention must be paid to the interval bounds when establishing upper limits. The situation has become more complicated, but for non-negative multi-intervals, we initially managed to understand the behavior in two specific cases: the first when all the right bounds are greater than or equal to one; the second when all the right bounds are less than or equal to one. We then achieved results for any non-negative multi-interval, also using the previously obtained bounds. The major result of this Thesis is a set of orderings among different bounds for polynomial functions, both for non-negative real intervals and for non-negative real multi-intervals.
A Comparative Study of Selected Bounds for Polynomial Constraints
SOLIANI, ERIDANO
2026
Abstract
Questa tesi di dottorato riguarda lo studio comparativo di stime per funzioni polinomiali su multi-intervalli reali nell’ambito della programmazione logica con vincoli polinomiali. La trattazione si apre con l’introduzione di stime per funzioni polinomiali reali definite su un intervallo reale limitato a valori non negativi. Le stime analizzate sono di tre tipologie: la prima si basa sul massimo e sul minimo dei coefficienti dei polinomi di Bernstein; la seconda si fonda sull’aritmetica degli intervalli; la terza comprende semplici stime ottenute considerando i valori assoluti ed i segni dei coefficienti della funzione polinomiale e l'estremo superiore dell’intervallo. L’obiettivo del lavoro è identificare, tra le stime studiate, quella che meglio approssima il comportamento della funzione polinomiale. Inizialmente si confrontano le stime semplici e quella ottenuta dall’aritmetica degli intervalli, la quale, su un intervallo a valori non negativi, risulta la più efficace perché tiene conto sia dell’estremo inferiore sia di quello superiore. Successivamente, si mette a confronto anche la stima basata sui polinomi di Bernstein. In quest’ultima fase emergono alcune difficoltà, poiché i polinomi di Bernstein sono espressi in una base specifica, mentre le altre stime utilizzano la base canonica. Questa differenza rende le espressioni difficilmente confrontabili. Tuttavia, sfruttando opportune maggiorazioni, in particolare basate sul binomio di Newton e sulle proprietà dei coefficienti binomiali, è possibile superare tali ostacoli. Si giunge così alla conclusione che la stima basata sui coefficienti del polinomio di Bernstein è la più precisa, sebbene risulti anche la più onerosa dal punto di vista computazionale. Una volta analizzato il problema in una dimensione, le tre tipologie di stime vengono estese a multi-intervalli in più variabili. Si effettua quindi un confronto tra le diverse approssimazioni nei multi-intervalli. Prestando particolare attenzione all’uso dei multi-indici, si dimostra che le stime basate sui polinomi di Bernstein offrono le migliori approssimazioni, ma presentano le peggiori prestazioni nei termini del tempo di calcolo. Un’ulteriore estensione trattata nella tesi riguarda lo studio delle stime associate al campionamento di funzioni polinomiali. L’analisi prende in considerazione dapprima l’intervallo unitario e successivamente un intervallo reale a valori non ne\-ga\-ti\-vi. Nel caso unidimensionale, adattando opportunamente i valori assoluti delle tre tipologie di stime alle derivate prime e seconde, è possibile definire e confrontare queste nuove approssimazioni. Lo studio viene poi esteso al caso multidimensionale, considerando prima il multi-intervallo unitario e poi multi-intervalli con valori non negativi. Mentre nel multi-intervallo unitario si ottengono risultati coerenti con il caso unidimensionale, nel caso di multi-intervalli non negativi la situazione diventa più delicata, poiché nelle maggiorazioni occorre prestare particolare attenzione agli estremi degli intervalli. Il quadro si è complicato, ma per multi-intervalli non negativi si è arrivati inizialmente a comprendere il comportamento in due casi specifici: il primo quando tutti gli estremi superiori sono maggiori o uguali di uno; il secondo quando tutti gli estremi superiori sono minori o uguali di uno. Si sono poi ottenuti risultati generali per qualsiasi multi-intervallo non negativo, anche grazie all'uso delle stime precedentemente ottenute. Il risultato principale di questa tesi consiste in un insieme di ordinamenti tra diverse stime per funzioni polinomiali, sia per intervalli reali non negativi, sia per multi-intervalli reali non negativi.I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
