Descrizione: 

Seminario del prof. Bahman Kalantari (Department of Computer Science, Rutgers University; New Brunswich, NJ, USA).

Abstract
In this talk I will introduce a simple geometric algorithm, called the triangle algorithm for solving the convex hull membership problem: to test if a specific point p in the m-dimensional Euclidean space lies in the convex hull of a given set S of n points in the same Euclidean space. This is a fundamental problem in linear programming and finds applications in statistics, machine learning and computational geometry. I will describe the distance dualities that justify the validity of the triangle algorithm and give complexity bounds and theoretical performance. I will make comparisons with the simplex and the Frank-Wolfe methods for solving the convex hull membership problem. Numerical experiments suggest the triangle algorithm is quite competitive. Not only suitable formulation of the triangle algorithm can solve the general LP feasibility problem, even the more fundamental problem of solving a square linear system Ax=b, giving a new iterative method that is competitive with such classical methods as AOR, SOR and more. Finally, I will give an overview of a generalization that gives an algorithmic separating hyperplane theorem. Specifically, the general triangle algorithm tests if two compact convex sets intersect, otherwise it computes a separating hyperplane, or if desired, the optimal pair of supporting hyperplanes. In particular, it can solve the support vector machine (SVM) problem, offering an alternative algorithm to the popular sequential minimal optimization algorithm. The triangle algorithm also finds applications to NP-complete problems, as well as combinatorial and graph problems. Some of the above results are published and some are available online or work in progress.

Data: 
26-11-2015
Luogo: 
Dipartimento di Scienze Statistiche, p.le A. Moro 5, Roma. Aula 34 (4° p.), ore 11.