Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems
Empreu sempre aquest identificador per citar o enllaçar aquest ítem
http://hdl.handle.net/10045/75153
Títol: | Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems |
---|---|
Autors: | Cánovas Cánovas, María Josefa | López Cerdá, Marco A. | Parra López, Juan | Toledo, Francisco Javier |
Grups d'investigació o GITE: | Laboratorio de Optimización (LOPT) |
Centre, Departament o Servei: | Universidad de Alicante. Departamento de Matemáticas |
Paraules clau: | Stability | Well-posedness | Linear inequality systems | Distance to ill-posedness | Regularity |
Àrees de coneixement: | Estadística e Investigación Operativa |
Data de publicació: | de maig-2005 |
Editor: | Springer-Verlag |
Citació bibliogràfica: | Mathematical Programming. 2005, 103(1): 95-126. doi:10.1007/s10107-004-0519-6 |
Resum: | In this paper we consider the parameter space of all the linear inequality systems, in the n-dimensional Euclidean space, with a fixed and arbitrary (possibly infinite) index set. This parameter space is endowed with the topology of the uniform convergence of the coefficient vectors by means of an extended distance. Some authors, in a different context in which the index set is finite and, accordingly, the coefficients are bounded, consider the boundary of the set of consistent systems as the set of ill-posed systems. The distance from the nominal system to this boundary (‘distance to ill-posedness’), which constitutes itself a measure of the stability of the system, plays a decisive role in the complexity analysis of certain algorithms for finding a solution of the system. In our context, the presence of infinitely many constraints would lead us to consider separately two subsets of inconsistent systems, the so-called strongly inconsistent systems and the weakly inconsistent systems. Moreover, the possible unboundedness of the coefficient vectors of a system gives rise to a special subset formed by those systems whose distance to ill-posedness is infinite. Attending to these two facts, and according to the idea that a system is ill-posed when small changes in the system’s data yield different types of systems, now the boundary of the set of strongly inconsistent systems arises as the ‘generalized ill-posedness’ set. The paper characterizes this generalized ill-posedness of a system in terms of the so-called associated hypographical set, leading to an explicit formula for the ‘distance to generalized ill-posedness’. On the other hand, the consistency value of a system, also introduced in the paper, provides an alternative way to determine its distance to ill-posedness (in the original sense), and additionally allows us to distinguish the consistent well-posed systems from the inconsistent well-posed ones. The finite case is shown to be a meeting point of our linear semi-infinite approach to the distance to ill-posedness with certain results derived for conic linear systems. Applications to the analysis of the Lipschitz properties of the feasible set mapping, as well as to the complexity analysis of the ellipsoid algorithm, are also provided. |
Patrocinadors: | This research has been partially supported by grants BFM2002-04114-C02 (01-02) from MCYT (Spain) and FEDER (E.U.), and Bancaja-UMH (Spain). |
URI: | http://hdl.handle.net/10045/75153 |
ISSN: | 0025-5610 (Print) | 1436-4646 (Online) |
DOI: | 10.1007/s10107-004-0519-6 |
Idioma: | eng |
Tipus: | info:eu-repo/semantics/article |
Drets: | © Springer-Verlag Berlin Heidelberg 2004 |
Revisió científica: | si |
Versió de l'editor: | https://doi.org/10.1007/s10107-004-0519-6 |
Apareix a la col·lecció: | INV - LOPT - Artículos de Revistas |
Arxius per aquest ítem:
Arxiu | Descripció | Tamany | Format | |
---|---|---|---|---|
2005_Canovas_etal_MathProgramm_final.pdf | Versión final (acceso restringido) | 330,46 kB | Adobe PDF | Obrir Sol·licitar una còpia |
Tots els documents dipositats a RUA estan protegits per drets d'autors. Alguns drets reservats.