Polyhedral, conical and convex least-squares problems

par Jean-Baptiste Hiriart-Urruty (Université Paul Sabatier de Toulouse)

vendredi 29 avr. 2016, 10:30 → 11:30 Europe/Paris

XLIM Salle X.203

"De tous les principes qu’on peut proposer pour cet objet, je pense qu’il n’en est pas de plus général, de plus exact, ni d’une application plus facile que celui qui consiste à rendre minimum la somme des carrés des erreurs” “Of all the principles that can be proposed, I think there is none more general, more exact, and more easy of application, than that which consists of minimizing the sum of the squares of the errors” A.-M.Legendre, Nouvelles méthodes pour la détermination des orbites des comètes, Paris (1805). ABSTRACT FIRST PART (based on the work [4]). With the help of elementary results and techniques from Real Analysis and Optimization at the undergraduate level, we study least squares solutions of linear inequality systems. We prove existence of solutions in various ways, provide a characterization of solutions in terms of nonlinear systems, and illustrate the applicability of results as a mathematical tool for checking the consistency of a system of linear inequalities and for proving “theorems of alternative” like the one by Gordan. Since a linear equality is the conjunction of two linear inequalities, the proposed results cover and extend what is known in the classical context of least squares solutions of linear equality systems. SECOND PART (ongoing work with J.C. GILBERT). We extend the results in the previous work to more general situations: when the system of linear inequalities Ax <= b is replaced by a conical system Ax − b ∈ K (where K is a closed convex cone), or when the goal is to realize at best the (possible infeasible) inclusion Ax ∈ C (where C is a nonempty closed convex set). The questions addressed are as the same as above: solution existence, uniqueness and boundedness; characterizations of solutions by optimality conditions; numerical computation via a semismooth Gauss-Newton method. In the two parts, the constant key-word is “least squares solutions”. REFERENCES [1] A.Björck, Numerical methods for least squares problems, SIAM Publications (1996). [2] R.Bramley and B.Winnincka, Solving linear inequalities in a least squares sense, SIAM Journal on Scientific Computation 17, 275-286 (1996). [3] P.L.Combettes, Inconsistent signal feasibility problems: least squares solutions in a product space, IEEE Transactions on Signal Processing, Vol. 42, n◦11, 2955-2966 (1994). [4] L.Contesse, J.-B.Hiriart-Urruty and J.-P.Penot, Least squares solutions of linear inequality systems: a pedestrian approach. Preprint (2015). [5] J.-C.Gilbert, Lecture notes in optimization (INRIA Rocquencourt and ENSTA Paris-Saclay). Book in progress. [6] S.P.Han, Least-squares solution of linear inequalities. Tech. Rep. TR-2141, Mathematics Research Center, University of Wisconsin-Madison (1980). [7] J.-B.Hiriart-Urruty and C.Lemaréchal, Convex analysis and minimization algorithms (2 volumes), Springer (new printing, 1996). [8] R.T.Rockafellar, Convex analysis, Princeton University Press (1972).