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.
Accepté le :
DOI : 10.1051/ro/2016042
Mots-clés : Linear inequalities, least squares solutions, convex polyhedron, quadratic function, alternative theorem
@article{RO_2017__51_3_567_0,
author = {Contesse, Luis and Hiriart-Urruty, Jean-Baptiste and Penot, Jean-Paul},
title = {Least squares solutions of linear inequality systems: a pedestrian approach},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {567--575},
publisher = {EDP-Sciences},
volume = {51},
number = {3},
year = {2017},
doi = {10.1051/ro/2016042},
mrnumber = {3880512},
zbl = {1387.90185},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2016042/}
}
TY - JOUR AU - Contesse, Luis AU - Hiriart-Urruty, Jean-Baptiste AU - Penot, Jean-Paul TI - Least squares solutions of linear inequality systems: a pedestrian approach JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 567 EP - 575 VL - 51 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2016042/ DO - 10.1051/ro/2016042 LA - en ID - RO_2017__51_3_567_0 ER -
%0 Journal Article %A Contesse, Luis %A Hiriart-Urruty, Jean-Baptiste %A Penot, Jean-Paul %T Least squares solutions of linear inequality systems: a pedestrian approach %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 567-575 %V 51 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2016042/ %R 10.1051/ro/2016042 %G en %F RO_2017__51_3_567_0
Contesse, Luis; Hiriart-Urruty, Jean-Baptiste; Penot, Jean-Paul. Least squares solutions of linear inequality systems: a pedestrian approach. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 567-575. doi : 10.1051/ro/2016042. http://www.numdam.org/articles/10.1051/ro/2016042/
A. Björck, Numerical methods for least squares problems. SIAM Publ. (1996). | MR | Zbl
and , Solving linear inequalities in a least squares sense. SIAM J. Sci. Comput. 17 (1996) 275–286. | DOI | MR | Zbl
, Inconsistent signal feasibility problems: least squares solutions in a product space. IEEE Trans. Signal Process. 42 (1994) 2955–2966. | DOI
S.P. Han, Least-squares solution of linear inequalities. Technical Report TR-2141, Mathematics Research Center, University of Wisconsin-Madison (1980).
R.T. Rockafellar, Convex analysis. Princeton University Press, Second printing (1972). | MR | Zbl
J.H. Spoonamore, Least squares methods for solving systems of inequalities with application to an assignment problem. Technical Report TM FF-93/03, USACERL (1992). | MR
K. Yang, New iterative methods for linear inequalities. Technical Report 90-06, University of Michigan (1990). | MR
Cité par Sources :
