×

zbMATH — the first resource for mathematics

A general parametric analysis approach and its implication to sensitivity analysis in interior point methods. (English) Zbl 0853.90083
Summary: I. Adler and R. D. C. Monteiro [Algorithmica 8, No. 2, 161-176 (1992; Zbl 0767.90042)] developed a parametric analysis approach that is naturally related to the geometry of the linear program. This approach is based on the availability of primal and dual optimal solutions satisfying strong complementarity. We develop an alternative geometric approach for parametric analysis which does not require the strong complementarity condition. This parametric analysis approach is used to develop range and marginal analysis techniques which are suitable for interior point methods. Two approaches are developed, namely the LU factorization approach and the affine scaling approach.

MSC:
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler and R.D.C. Monteiro, ”A geometric view of parametric linear programming,”Algorithmica 8 (1992) 161–176. · Zbl 0767.90042
[2] R. Fourer and S. Mehrotra, ”Solving symmetric indefinite systems in an interior-point method for linear programming,”Mathematical Programming 62 (1993) 15–39. · Zbl 0802.90069
[3] J. Gauvin, ”Quelques precisions sur les prix marginaux en programmation lineaire,”INFOR 18 (1980) 68–73 (in French). · Zbl 0432.90043
[4] A.J. Goldman and A.W. Tucker, ”Theory of linear programming,” in: H.W. Kuhn and A.W. Tucker eds.,Linear Inequalities and Related Systems (Princeton University Press, Princeton, NJ, 1956) pp. 53–97. · Zbl 0072.37601
[5] O. Güler and Y. Ye, ”Convergence behavior of interior-point algorithms,”Mathematical Programming 60 (1993) 215–228. · Zbl 0803.90087
[6] S.P. Bradley, A.C. Hax and T.L. Magnanti,Applied Mathematical Programming (Addison-Wesley, Reading, MA, 1977).
[7] B. Jansen, C. Roos and T. Terlaky, ”An interior point approach to postoptimal and parametric analysis in linear programming,” Technical Report 92-21, Faculty of Technical Mathematics and Informatics, TU Delft, Netherlands, 1992.
[8] N. Megiddo, ”On finding primal and dual optimal bases,”ORSA Journal on Computing 3 (1991) 63–65. · Zbl 0755.90056
[9] S. Mehrotra and Y. Ye, ”Finding an interior point in the optimal face of linear programs,”Mathematical Programming 62 (1993) 497–515. · Zbl 0803.90089
[10] K.G. Murty, ”Linear Programming,” (Wiley, New York, 1983). · Zbl 0521.90071
[11] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[12] J.F. Shapiro,Mathematical Programming: Structures and Algorithms (Wiley, New York, 1979). · Zbl 0502.90054
[13] R.J. Vanderbei, ”A brief description of ALPO,”Operations Research Letters 10 (1991) 531–534. · Zbl 0744.90056
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.