Regions of stability for ill-posed convex programs

Zlobec, Sanjo

Applications of Mathematics, Tome 27 (1982) no. 3, pp. 176-191

Abstract (VO)

Regions of stability are chunks of the space of parameters in which the optimal solution and the optimal value depend continuously on the data. In these regions the problem of solving an arbitrary convex program is a continuous process and Tihonov's regularization is possible. This paper introduces a new region we furnisch formulas for the marginal value. The importance of the regions of stability is demostrated on multicriteria decision making problems and in calculating the minimal index set of binding constraints in convex programming. These two nonlinear problems can be reduced to calculating a region of stability for a simple linear program. If Slater's condition holds, or for the rihgt hand side perurbations, the results reduce to the familiar ones.

Détail

DOI : 10.21136/AM.1982.103961

Classification : 90C25, 90C31
Keywords: ill-posed convex programs; regions of stability; Tihonov’s regularization; formulas for the marginal value; multicriteria decision making; minimal index set of binding constraints

Bibliographie

[1] R. Abrams L. Kerzner: A simplified test for optimality. Journal of Optimization Theory and Applications. 25 (1978), 161-170. | DOI | MR

[2] A. Ben-Israel A. Ben-Tal S. Zlobec: Optimality in Nonlinear Programming: A Feasible Directions Approach. Wiley-Interscience, New York 1981. | MR

[3] A. Ben-Israel A. Ben-Tal A. Charnes: Necessary and sufficient conditions for a Pareto-optimum in convex programming. Econometrica 45 (1977), 811 - 820. | DOI | MR

[4] A. Ben-Israel T. N. E. Greville: Generalized Inverses: Theory and Applications. Wiley-Interscience, New York 1974. | MR

[5] B. Brosowski: On parametric linear optimization. Optimization and Operations Research, Springer Verlag Lecture Notes in Economics and Mathematical Systems No. 157(R. Henn, B. Korte and W. Oettli, editors), Berlin, 1978, pp. 37-44. | MR | Zbl

[6] G. B. Dantzig J. Folkman N. Shapiro: On the continuity of the minimum set of a continuous function. Journal of Mathematical Analysis and Applications 17 (1967), 519-548. | DOI | MR

[7] I. I. Eremin N. N. Astafiev: Introduction to the Theory of Linear and Convex Programming. Nauka, Moscow, 1976. (In Russian.) | MR

[8] J. P. Evans F. J. Gould: Stability in nonlinear programming. Operations Research 18 (1970), 107-118. | DOI | MR

[9] A. V. Fiacco: Convergence properties of local solutions of sequences of mathematical programming problems in general spaces. Journal of Optimization Theory and Applications 13 (1974), 1-12. | DOI | MR | Zbl

[10] J. Gauvin J. W. Tolle: Differential stability in nonlinear programming. SlAM Journal on Control and Optimization 15 (1977), 294-311. | DOI | MR

[11] H. J. Greenberg W. P. Pierskalla: Extensions of the Evans-Gould stability theorems for mathematical programs. Operations Research 20 (1972), 143-153. | DOI | MR

[12] J. Guddat: Stability in convex quadratic parametric prcgramming. Mathematische Operationsforschung und Statistik 7 (1976), 223 - 245. | DOI | MR

[13] W. Krabs: Stetige Abänderung der Daten bei nichtlinearer Optimierung und ihre Konsequenzen. Operations Research Verfahren XXV 1 (1977), 93-113. | Zbl

[14] B. Kummer: Global stability of optimization problems. Mathematische Operationsforschung und Statistik, series Optimization (1977). | MR | Zbl

[15] O. Mangasarian: Nonlinear Programmirg. McGraw-Hill, New York, 1969. | MR

[16] D. H. Martin: On the continuity of the maximum in parametric linear programming. Journal of Optimization Theory and Applications 17 (1975), 205-210. | DOI | MR | Zbl

[17] V. D. Mazurov: The solution of an ill-posed linear optimization problem under contradictory conditions. Supplement to Ekonomika i Matematičeskii Metody, Collection No. 3 (1972), 17-23. (In Russian.) | MR

[18] M. Z. Nashed (editor): Generalized Inverses and Applications. Academic Press, New York, 1976.

[19] F. Nožička J. Guddat H. Hollatz B. Bank: Theorie der linearen parametrische Optimierung. Akademie - Verlag, Berlin, 1974.

[20] M. S. A. Osman: Qualitative analysis of basic notions in parametric convex programming, I. Aplikace Matematiky 22 (1977), 318-332. | MR | Zbl

[21] M. S. A. Osman: Qualitative analysis of basic notions in parametric convex programming, II. Aplikace Matematiky 22 (1977), 333-348. | MR | Zbl

[22] S. M. Robinson: A characterization of stability in linear programming. MRC Technical Report 1542, University of Wisconsin, Madison (1975).

[23] T. R. Rockafellar: Convex Analysis. Princeton University Press, 1970. | MR | Zbl

[24] A. N. Tihonov V. Y. Arsenin: Solutions of Ill-Posed Problems. Winston, Washington D. C., 1977. | MR

[25] A. C. Williams: Marginal values in linear programming. Journal of the Society of Industrial and Applied Mathematics 11 (1963), 82-94. | DOI | MR | Zbl

[26] H. Wolkowicz: Calculating the cone of directions of constacy. Journal of Optimization Theory and Applications 25 (1978), 451-457. | DOI | MR

[27] S. Zlobec: Marginal values for arbitrarily perturbed convex programs. Glasnik Matematički (1982, forthcoming). | MR

[28] S. Zlobec A. Ben-Israel: Perturbed convex programs: continuity of optimal solutions and optimal values. Operations Research Verfahren XXXI 1 (1979), 737-749.

[29] S. Zlobec A. Ben-Israel: Duality in convex programming: a linearization approach. Mathematische Operationsforschung und Statistik, series Optimization 10 (1979), 171 - 178. | DOI | MR

[30] S. Zlobec B. Craven: Stabilization and determination of the set of minimal binding constraints in convex programming. Mathematische Operationsforschung und Statistik, series Optimization 12 (1981), 203-220, | DOI | MR

[31] S. Zlobec R. Gardner A. Ben-Israel: Regions of stability for arbitrarily perturbed convex programs. In Mathematical Programming with Data Perturbations I (A. V. Fiacco, ed.), M. Dekker, New York, 1982, 69-89. | MR