Séminaire Modélisation, Optimisation, Dynamique

Solving linear inequalities in a least squares sense by successive projections

par Ngoc-Nguyen Tran (Université de Limoges)

Europe/Paris
XLIM Salle X.203

XLIM Salle X.203

FST-Université de Limoges, 123, Av. Albert Thomas.
Description
We consider the solution of a system of linear inequalities in a least squares sense. This problem arises in many applications: image reconstruction, linear programming, linear separability problem, etc. In this work, the dual form of least squares problem associated with the linear inequalities will be considered. We will see that the dual is the orthogonal projection of the right-hand side vector of the linear system, onto the intersection of a linear space and the nonnegative orthant. To numerically solve this problem, we apply a successive projection algorithm. The solution of the primal problem is then recovered by means of a least squares solution of linear inequalities. The global convergence of the algorithm is proved. Finally, we compare our approach to existing algorithms and show by means of numerical experiments that this new algorithm is very efficient when there is a large number of inequalities.