A note of Lipschitz constants for solutions of linear inequalities and equations
type: Item
instance of: scholarly article
title: A note of Lipschitz constants for solutions of linear inequalities and equations
zbMATH Open document ID: 0860.15015
DOI: 10.1016/0024-3795(94)00349-1
author: Diethard Klatte
author: Gisbert Thiere
published in: Linear Algebra and its Applications
publication date: 1997-04-13T00:00:00Z
review text: This paper is concerned with Lipschitz constants for systems of the form \[ Ax\leq b,\quad Cx = d\tag{1} \] in which \(A\) and \(C\) are matrices of order \(m\times n\) and \(k \times n\), respectively, and \((b,d) \in R^m \times R^k\) is treated as a parameter vector. For a given parameter vector \(M(b,d)\) denotes the set of all \(x\) that satisfy the system (1). In 1952, \textit{A. J. Hoffman} [J. Res. Nat. Bur. Standards 49, 263-265 (1952; MR 14-455)] showed that the solution set mapping \((b,d) \mapsto M(b,d)\) of (1) is Lipschitzian on its effective domain, \(\text{dom} M: = \{(b,d) \mid M(b,d)\neq \emptyset\}\). This means that there exists a constant \(\rho= \rho_{\alpha \beta} (A,C)>0\) such that \[ h_\beta \bigl(M(b,d), M(b',d')\bigr) \leq\rho\left |\begin{matrix} b & - & b' \\ d & - & d' \end{matrix} \right|_\alpha \quad \forall (b,d),\;(b',d')\in \text{dom} M \tag{2} \] where \(|\cdot|_\alpha\) and \(|\cdot |_\beta\) are any two norms on \(R^{m+k}\) and \(R^n\), respectively, and \(h_\beta\) is the Hausdorff metric induced by \(|\cdot |_\beta\). This paper belongs to the literature dealing with estimates of the Lipschitz constant \(\rho\). Its principal contribution is a theorem to the effect that a sharp Lipschitz constant due to \textit{W. Li} [SIAM J. Control Optimization 32, No. 1, 140-153 (1994; Zbl 0792.90080)] is the same as the one used by \textit{S. M. Robinson} [Linear Algebra Appl. 6, 69-81 (1973; Zbl 0283.90028)] and that it agrees with one considered by the authors [Wiss. Z. PH Halle-Köthen XXVI(8), 13-17 (1988; MR 91f:65123)].
reviewed by: R. W. Cottle
Mathematics Subject Classification ID: 15A39
Mathematics Subject Classification ID: 15A06
Mathematics Subject Classification ID: 15A45
zbMATH DE Number: 931954
zbMATH Keywords: linear inequalities
zbMATH Keywords: linear equations
zbMATH Keywords: Lipschitz constants
MaRDI profile type: Publication
full work available at URL: 0024-3795(94)00349-1
OpenAlex ID: W2085154531
cites work: The distance to a polyhedron
cites work: Sensitivity theorems in integer linear programming
cites work: Well-posed optimization problems
cites work: Q3040944
cites work: Error bounds for solutions of linear equations and inequalities
cites work: The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program
cites work: Sharp Lipschitz Constants for Basic Optimal Solutions and Basic Feasible Solutions of Linear Programs
cites work: Perturbation Analysis of a Condition Number for Linear Systems
cites work: Q4742548
cites work: Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity Problems
cites work: Bounds for error in the solution set of a perturbed linear program
cites work: Q5603731
cites work: Q4001644
Recommended article: Error bounds for solutions of linear equations and inequalities
Recommended article: Solving systems of nonlinear matrix equations involving Lipschitzian mappings
Recommended article: Lipschitz modulus of linear and convex inequality systems with the Hausdorff metric
Recommended article: Relazioni di grandezza fra le soluzioni di due sistemi di equazioni alle derivate parziali, e fra le loro derivate.
Recommended article: Fixed point theorems for uniformly Lipschitzian mappings in LP spaces
Recommended article: Hoffman's error bounds and uniform Lipschitz continuity of best \(l_ p\)-approximations
Recommended article: Sharp Lipschitz Constants for Basic Optimal Solutions and Basic Feasible Solutions of Linear Programs
Recommended article: Calculation of a sharp Lipschitz constant for a system of linear inequalities
Recommended article: On sharp Lipschitz and Hoffman constants for a system of linear inequalities
Recommended article: Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity Problems
description: scientific article; zbMATH DE number 931954