Error bounds for solutions of linear equations and inequalities. (English) Zbl 0823.65055
The authors propose a method for computing a special form of Hoffmann constants \(\lambda_{\alpha \beta}: \text{dist}_ \beta (x, M(b,d)) \leq \lambda_{\alpha \beta} \left \| \begin{smallmatrix} (Ax - b)_ +\\ (Cx - d)\end{smallmatrix} \right \|_ \alpha\) \(\forall x \in \mathbb{R}^ n\), \(\forall (b, d) \in \text{dom }M\), where \(M(b,d) := \{x \in \mathbb{R}^ n/Ax \leq b,\;Cx = d\}\), \((b,d) \in \mathbb{R}^ m \times \mathbb{R}^ k\), \(\| \cdot \|_ \alpha\) and \(\| \cdot \|_ \beta\) are arbitrary norms in \(\mathbb{R}^{k + m}\) and \(\mathbb{R}^ n\) respectively, \(\text{dist}_ \beta (x,Z) := \inf_{z \in Z} \| x - z\|_ \beta\).
The results are used in the analysis of Lipschitz continuity for the solution of parametric quadratic programs.
The results are used in the analysis of Lipschitz continuity for the solution of parametric quadratic programs.
Reviewer: H.Benker (Merseburg)
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C20 | Quadratic programming |
| 90C05 | Linear programming |
| 90C31 | Sensitivity, stability, parametric optimization |
References:
| [1] | Al-Sultan KS, Murty KG (1992) Exterior point algorithms for nearest points and convex quadratic programs. Math Programming 57:145-161 · Zbl 0787.90066 · doi:10.1007/BF01581078 |
| [2] | Beer K, Käschel J (1979) Column generation in quadratic programming. Math Operationsforsch Stat, Series Optimization 10:179-184 · Zbl 0424.90053 |
| [3] | Bergthaller C, Singer I (1992) The distance to a polyhedron. Linear Algebra Appl 169:111-129 · Zbl 0759.15008 · doi:10.1016/0024-3795(92)90174-9 |
| [4] | Cook W, Gerards MH, Schrijver A, Tardos E (1986) Sensitivity theorems in integer linear programming. Math Programming 34:251-264 · Zbl 0648.90055 · doi:10.1007/BF01582230 |
| [5] | Eaves BC (1971) On quadratic programming. Management Sci 17:698-711 · Zbl 0242.90040 · doi:10.1287/mnsc.17.11.698 |
| [6] | Fujishige S, Zhan P (1990) A dual algorithm for finding the minimum-norm point in a polytope. J Oper Res Soc Japan 33:188-195 · Zbl 0712.90055 |
| [7] | Guddat J (1976) Stability in convex quadratic programming. Math Operationsforsch Stat 7:223-245 · Zbl 0352.90045 |
| [8] | Hoffman AJ (1952) On approximate solutions of systems of linear inequalities. J Res Nat Bur Standards 49:263-265 |
| [9] | Jongen HT, Klatte D, Tammer K (1990) Implicit functions and sensitivity of stationary points. Math Programming 49:123-138 · Zbl 0715.65034 · doi:10.1007/BF01588782 |
| [10] | Kall P (1976) Stochastic linear programming. Springer Berlin Heidelberg New York · Zbl 0317.90042 |
| [11] | Klatte D (1983) Eine Bemerkung zur parametrischen quadratischen Optimierung. Seminarbericht 50:174-185. Sektion Mathematik Humboldt-Universität Berlin · Zbl 0526.90082 |
| [12] | Klatte D (1984) Beiträge zur Stabilitätsanalyse nichtlinearer Optimierungsprobleme. Dissertation B (Habilitationsschrift), Sektion Mathematik Humboldt-Universität Berlin |
| [13] | Klatte D (1985) On the Lipschitz behavior of optimal solutions in parametric problems of quadratic optimization and linear complementarity. Optimization 16:819-831 · Zbl 0594.90081 · doi:10.1080/02331938508843080 |
| [14] | Klatte D (1987) Lipschitz continuity of infima and optimal solutions in parametric optimization: The polyhedral case. In: Guddat J, Jongen HT, Kummer B, No?i?ka F (eds) Parametric Optimization and Related Topics 229-248. Akademie-Verlag Berlin |
| [15] | Klatte D, Kummer B (1985) Stability properties of infima and optimal solutions of parametric optimization problems. In: Demyanov V, Pallaschke D (eds) Nondifferentiable Optimization: Motivations and Applications 215-229. Springer Berlin · Zbl 0598.90083 |
| [16] | Klatte D, Thiere G (1988) Über Fehlerschranken für lineare Ungleichungssysteme. Wissenschaftliche Zeitschrift der PH Halle-Köthen XXVI 8:13-17 |
| [17] | Klatte D, Thiere G (1994) A note on Lipschitz constants for solutions of linear inequalities and equations. Manuscript Institut für Operations Research Universität Zürich |
| [18] | Kleinmann P (1978) Quantitative Sensitivitätsanalyse bei parametrischen Optimierungsaufgaben. Seminarbericht Nr. 9 Sektion Mathematik Humboldt-Universität Berlin · Zbl 0407.90080 |
| [19] | Künzi HP, Krelle W (1962) Nichtlineare Programmierung. Springer Berlin Göttingen Heidelberg · Zbl 0102.15502 |
| [20] | Li W (1993) The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program. Linear Algebra Appl 187:15-40 · Zbl 0809.65057 · doi:10.1016/0024-3795(93)90125-8 |
| [21] | Li W (1994) Sharp Lipschitz constants for basic optimal solutions and basic feasible solutions of linear programs. SIAM J Control Optim. 32:140-153 · Zbl 0792.90080 · doi:10.1137/S036301299222723X |
| [22] | Luo ZQ, Tseng P (1991) Perturbation analysis of a condition number of linear systems. Manuscript Dept of Mathematics Univ of Washington Seattle, Washington USA |
| [23] | Mangasarian OL (1981) A condition number of linear inequalities and equalities. Methods of Oper Res 43:3-15 · Zbl 0505.90042 |
| [24] | Mangasarian OL (1981a) A stable theorem of the alternative: An extension of the Gordan theorem. Linear Algebra and Appl 41:209-223 · Zbl 0488.90044 · doi:10.1016/0024-3795(81)90100-2 |
| [25] | Mangasarian OL (1990) Error bounds for nondegenerate monotone linear complementarity problems. Math Programming 48:437-445 · Zbl 0716.90094 · doi:10.1007/BF01582267 |
| [26] | Mangasarian OL, Shiau TH (1986) Error bounds for monotone linear complementarity problems. Math Programming 36:81-89 · Zbl 0613.90095 · doi:10.1007/BF02591991 |
| [27] | Mangasarian OL, Shiau TH (1987) Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. SIAM J Control Optim 25:583-595 · Zbl 0613.90066 · doi:10.1137/0325033 |
| [28] | Murty KG, Fathi Y (1982) A critical index algorithm for the nearest point problem on simplicial cones. Math Programming 23:206-215 · Zbl 0479.90077 · doi:10.1007/BF01583789 |
| [29] | No?i?ka F, Guddat J, Hollatz H (1972) Theorie der linearen Optimierung. Akademie-Verlag Berlin · Zbl 0246.90024 |
| [30] | Robinson SM (1973) Bounds for error in the solution set of a perturbed linear program. Linear Algebra Appl 6: 69-81 · Zbl 0283.90028 · doi:10.1016/0024-3795(73)90007-4 |
| [31] | Robinson SM (1981) Some continuity properties of polyhedral multifunctions. Math Programming Study 14:206-214 · Zbl 0449.90090 |
| [32] | Schwartz B, Käschel J (1981) Verfahren der zulässigen Richtungen für Optimierungsaufgaben mit nichtdifferenzierbaren Funktionen und Dekomposition. Wiss Schriftenreihe TH Karl-Marx-Stadt Nr 11 |
| [33] | Sekitani K, Yamamoto Y (1993) A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes. Math Programming 61:233-249 · Zbl 0791.90046 · doi:10.1007/BF01582149 |
| [34] | Stoer J, Witzgall C (1970) Convexity and Optimization in Finite Dimensions I. Springer Berlin · Zbl 0203.52203 |
| [35] | Thiere G (1989) Untersuchungen zum Vergleich und zur Berechnung von Fehlerschranken für lineare Ungleichungssysteme. Dissertation A (PhD Thesis) Pädagogische Hochschule Halle-Köthen · Zbl 0729.65045 |
| [36] | Walkup D, Wets RJ-B (1969) A Lipschitzian characterization of convex polyhedra. Proceed Amer Math Soc 23:167-173 · Zbl 0182.25003 · doi:10.1090/S0002-9939-1969-0246200-8 |
| [37] | Wolfe P (1976) Finding the nearest point in a polytope. Math Programming 2:126-149 · Zbl 0352.90046 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
