Perturbation theory for mathematical programming problems

V. A. Gaitsgory*, A. A. Pervozvanskii

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

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 practical usefulness of perturbation theory is demonstrated by considering the two LP problems. Decomposition and aggregation procedures are constructed on the base of general results to find suboptimal solutions of these problems.

Original languageEnglish
Pages (from-to)389-410
Number of pages22
JournalJournal of Optimization Theory and Applications
Volume49
Issue number3
DOIs
Publication statusPublished - Jun 1986
Externally publishedYes

    Fingerprint

Keywords

  • aggregation
  • decomposition
  • Mathematical programming
  • perturbation theory
  • singularities

Cite this