Engineering Commons^™

Theoretical Explanation Of Bernstein Polynomials' Efficiency: They Are Optimal Combination Of Optimal Endpoint-Related Functions, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

In many applications of interval computations, it turned out to be beneficial to represent polynomials on a given interval [x_-, x₊] as linear combinations of Bernstein polynomials (x- x _- )^k * (x₊ - x)^n-k. In this paper, we provide a theoretical explanation for this empirical success: namely, we show that under reasonable optimality criteria, Bernstein polynomials can be uniquely determined from the requirement that they are optimal combinations of optimal polynomials corresponding to the interval's endpoints.

Algorithms For Training Large-Scale Linear Programming Support Vector Regression And Classification, Pablo Rivas Perea

Open Access Theses & Dissertations

The main contribution of this dissertation is the development of a method to train a Support Vector Regression (SVR) model for the large-scale case where the number of training samples supersedes the computational resources. The proposed scheme consists of posing the SVR problem entirely as a Linear Programming (LP) problem and on the development of a sequential optimization method based on variables decomposition, constraints decomposition, and the use of primal-dual interior point methods. Experimental results demonstrate that the proposed approach has comparable performance with other SV-based classifiers. Particularly, experiments demonstrate that as the problem size increases, the sparser the solution …

M Solutions Good, M-1 Solutions Better, Luc Longpre, William Gasarch, G. W. Walster, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main objectives of theoretical research in computational complexity and feasibility is to explain experimentally observed difference in complexity.

Empirical evidence shows that the more solutions a system of equations has, the more difficult it is to solve it. Similarly, the more global maxima a continuous function has, the more difficult it is to locate them. Until now, these empirical facts have been only partially formalized: namely, it has been shown that problems with two or more solutions are more difficult to solve than problems with exactly one solution. In this paper, we extend this result and show …

Probabilities, Intervals, What Next? Optimization Problems Related To Extension Interval Computations To Situations With Partial Information About Probabilities, Vladik Kreinovich

Departmental Technical Reports (CS)

When we have only interval ranges [xi-,xi+] of sample values x1,...,xn, what is the interval [V-,V+] of possible values for the variance V of these values? We prove that the problem of computing the upper bound V+ is NP-hard. We provide a feasible (quadratic time) algorithm for computing the exact lower bound V- on the variance of interval data. We also provide feasible algorithms that computes V+ under reasonable easily verifiable conditions, in particular, in case interval uncertainty is introduced to maintain privacy in a statistical database.

We also extend the main formulas of interval arithmetic for different arithmetic operations …

Optimal Elimination Of Inconsistency In Expert Knowledge: Formulation Of The Problem, Fast Algorithms, Timothy J. Ross, Berlin Wu, Vladik Kreinovich

Departmental Technical Reports (CS)

Expert knowledge is sometimes inconsistent. In this paper, we describe the problem of eliminating this inconsistency as an optimization problem, and present fast algorithms for solving this problem.