Perturbation theory for mathematical programming problems. (English) Zbl 0568.90089
Mathematical programming (MP) problems depending on a small parameter are investigated. Attention is paid to the cases where the solutions to the reduced program and/or the solutions to the dual reduced program are not unique. Conditions are given for the convergence of perturbed solutions to a point of the reduced problem solution set, if the small parameter tends to zero. It is shown how to find this point and how to construct an approximate solution to the perturbed program. A singular situation may appear if the dual solution set is unbounded. In this case, a gap between perturbed and reduced solutions may arise. However, it is shown that the perturbed solutions are close to the solutions of some modified reduced problem. The fractional usefulness of perturbation theory is demonstrated by considering two LP problems. Decomposition and aggregation procedures are constructed on the base of general results to find suboptimal solutions of these problems.
MSC:
| 90C31 | Sensitivity, stability, parametric optimization |
| 65K05 | Numerical mathematical programming methods |
| 90C05 | Linear programming |
Keywords:
perturbation; singularities; approximate solution; Decomposition; aggregation; suboptimal solutionsReferences:
| [1] | Mills, H.,Marginal Values of Matrix Games and Linear Programs, Linear Inequalities and Related Systems, Princeton University Press, Princeton, New Jersey, 1956. · Zbl 0072.37702 |
| [2] | Gol’stein, E. G., andYudin, D. B.,New Directions in Linear Programming, Nauka, Moscow, 1966 (in Russian). |
| [3] | Volkonsky, V. A.,Correctness and Marginal Values of Linear Programming Problem, Primenenie Matematiky v Issledovaijah, Vol. 3, Nauka, Moscow, 1965 (in Russian). |
| [4] | Dem’janov, V. F., andPevny, A. B.,Calculations of First and Second Marginal Values, Zadachi Matematicheskogo Programmirovania v Optimizacii, Novosibirsk, 1972 (in Russian). |
| [5] | Levitin, E. S.,Differentiability of Optimal Value of Mathematical Programming Problem with Respect to a Parameter, Kibernetika, Vol. 12, No. 1, 1976 (in Russian). |
| [6] | Lempio, F., andMaurer, H.,Differential Stability in Infinite-Dimensional Nonlinear Programming, Applied Mathematics and Optimization, Vol. 6, pp. 139-152, 1980. · Zbl 0426.90072 · doi:10.1007/BF01442889 |
| [7] | Gauvin, J., andDubeau, F.,Differential Properties of the Marginal Function in Mathematical Programming, Mathematical Programming Study, Vol. 19, pp. 101-119, 1982. · Zbl 0502.90072 |
| [8] | Gauvin, J., andTolle, J. W.,Differential Stability in Nonlinear Programming, SIAM Journal on Control and Optimization, Vol. 15, No. 2, 1977. |
| [9] | Karmanov, V. G.,Mathematical Programming, Nauka, Moscow, 1976 (in Russian). · Zbl 0967.90089 |
| [10] | Ashmanov, S. A.,Stability Conditions for Linear Programming Problems, Matematicheskie Metody Optimizacii i Primenenie, CEMI, AN USSR, Moscow, 1980 (in Russian). · Zbl 0485.90062 |
| [11] | Gol’stein, E. G., andMovshovich, S. M.,Continuous Dependence on a Parameter of Solution Set to Minimax Problem, Ekonomika i Matematicheskie Metody, Vol. 4, No. 4, 1968 (in Russian). |
| [12] | Fiacco, A. V., andMcCormick, G. P.,Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, New York, 1968. · Zbl 0193.18805 |
| [13] | Rockafellar, R. T.,Lagrange Multipliers in Optimization in Nonlinear Programming, SIAM-AMS Proceedings, Vol. 9, Providence, Rhode Island, 1976. · Zbl 0341.90046 |
| [14] | Geoffrion, A.,Objective Function Approximation in Mathematical Programming, Vol. 13, No. 1, 1977. · Zbl 0356.90062 |
| [15] | Mangasarian, O. L., andMerger, R. R.,Nonlinear Perturbations of Linear Programs, SIAM Journal on Control and Optimization, Vol. 17, No. 6, 1979. · Zbl 0432.90047 |
| [16] | Ben-Israel, A., Ben-Tal, A., andZlobec, S.,Optimality in Convex Programming: A Feasible Directions Approach, Mathematical Programming Study, Vol. 19, pp. 16-38, 1982. |
| [17] | Mangasarian, O. L., andFromovitz, S.,The Fritz John Necessary Optimality Conditions in the Presence of Equality and Inequality Constraints, Journal of Mathematical Analysis and Applications, Vol. 17, No. 1, 1967. · Zbl 0149.16701 |
| [18] | Pervozvansky, A. A.,Optimization of Systems with Weak Connections, System Science, Vol. 2, Nos. 1-2, 1976. |
| [19] | Gaitsgory, V. G.,Sequential Aggregation and Noncorrect Linear Programming Problems, Voprosy Planirovanija i Upravlenija, AN TSSR, Dushanbe, 1976 (in Russian). |
| [20] | Gaitsgory, V. G., andPervozvansky, A. A.,Small Nonlinear Perturbations in Optimization Problems, Ekonomika i Matematicheskie Metody, Vol. 13, No. 1, 1977 (in Russian). |
| [21] | Gaitsgory, V. G., andPervozvansky, A. A.,On the Approximate Solutions to the Optimal Weak Coupling Problems, Matematicheskie Metody Reshenija Ekonomicheskich Zadach, Nauka, Moscow, 1977 (in Russian). |
| [22] | Pervozvansky, A. A., andGaitsgory, V. G.,Operative Control of Industrial Activity as a Problem of Stochastic Programming, System Science, Vol. 3, No. 1, 1977. |
| [23] | Pervozvansky, A. A., andGaitsgory, V. G.,Sensitiveness of Mathematical Programming Problems, Teorija Invariantnosti i Ego Primenenija, Vol. 3, Naukova Dumka, Kiev, 1979 (in Russian). |
| [24] | Gaitsgory, V. G., andPervozvansky, A. A.,Perturbations Method in Optimization Problem, Dinamika System, Gorki, Vol. 14, pp. 3-32, 1978 (in Russian). |
| [25] | Pervozvansky, A. A., andGaitsgory, V. G.,Suboptimization, Decomposition, and Aggregation, Proceedings of 7th IFAC Congress, Vol. 2, pp. 1057-1062, 1978. |
| [26] | Pervozvansky, A. A., andGaitsgory, V. G.,Decomposition, Aggregation, and Suboptimization, Nauka, Moscow, 1979 (in Russian). |
| [27] | Gaitsgory, V. G., andPervozvansky, A. A.,Perturbation Method for the Problem of Mathematical Programming, Ekonomika i Matematicheskie Metody, Vol. 19, No. 4, 1983 (in Russian). |
| [28] | Gaitsgory, V. G., andPervozvansky, A. A.,Hierarchical Procedure for Optimization of Finite Markov Chains, Trudy 7 Zimney Shkoly po Matematicheskomy Programmirovaniju, Drogobych, CEMI, AN USSR, pp. 185-197, 1974 (in Russian). |
| [29] | Gaitsgory, V. G., andPervozvansky, A. A.,On the Optimization of Weakly Controlled Stochastic Systems, Soviet Mathematics Doklady, Vol. 21, No. 2, 1980. |
| [30] | Gaitsgory, V. G., andPervozvansky, A. A.,Aggregation of States in Markov Chains with Weak Interactions, Kibernetika, Vol. 11, No. 3, 1975 (in Russian). |
| [31] | Gaitsgory, V. G., andPervozvansky, A. A.,Movement Partition in Markov Systems, Dinamika System, Gorki, Vol. 6, pp. 14-45, 1975 (in Russian). |
| [32] | Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401 |
| [33] | Delebeque, F., andQuadrat, J. P.,Asymptomic Problems for Control of Markov Chains with Strong and Weak Interactions, Automatica, Vol. 16, No. 3, 1980. |
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.
