# zbMATH — the first resource for mathematics

Finding an interior point in the optimal face of linear programs. (English) Zbl 0803.90089
Consider the problem (P): $$\min c^ T x$$ subject to $$Ax= b$$, $$x\geq 0$$, and its dual (D): $$\max b^ T y$$ subject to $$A^ T y+ s=c$$, $$s\geq 0$$. It is well-known that feasible solutions $$x^*$$ and $$(y^*,s^*)$$ are optimal for (P) and (D) respectively iff $$x^*_ j s^*_ j=0$$ $$(j=1,\dots,n)$$. Let $$\sigma(x^*)= \{i| x^*_ i>0\}$$. The pair $$(x^*,s^*)$$ is strictly complementary if $$\sigma(x^*)\cap \sigma(s^*)= \emptyset$$ and $$\sigma(x^*)\cup \sigma(s^*)= \{1,2,\dots,n\}$$. The partition $$\{\sigma^*,\bar\sigma^*\}$$ of $$\{1,2,\dots,n\}$$ is an optimal partition, where $$\sigma(x^*)= \sigma^*$$ and $$\bar\sigma^*=\{1,2,\dots,n\}\backslash \sigma^*$$ in view of the invariant character of $$\sigma(x^*)$$ and $$\sigma(s^*)$$ for every strictly; complementary solution $$(x^*,s^*)$$. The authors study the problem of finding the optimal partition and a pair of points in the interior of $$\theta_ p= \{x: Ax= b,\;x\geq 0,\;x_ j=0$$ for $$j\in \bar\sigma^*\}$$ and $$\theta_ d= \{(y,s): A^ T y+ s=c,\;s_ j=0$$ for $$j\in \sigma^*\}$$. The authors claim that the optimal partition can be identified in $$O(n^ 3 L)$$ arithmetic operations where the data in (P) are rational and $$L$$ is their input length. They also propose a practical and (column) scaling independent criterion for identifying the optimal partition. Finally, the authors report computational results on the problems in the NETLIB test set.
For related work the reader is referred to R. M. Freund et al. [Technical Report, Sloan W. P. No. 1674-85, MIT, Cambridge, MA (1985)] and E. Tardos [Oper. Res. 34, 250-256 (1986; Zbl 0626.90053)].
Reviewer: R.N.Kaul (Delhi)

##### MSC:
 90C05 Linear programming
##### Software:
NETLIB LP Test Set
Full Text:
##### References:
  I. Adler and R.C. Monteiro, ”A geometric view of parametric linear programming,” manuscript, Department of Industrial Engineering and Operations Research, University of California (Berkeley, CA, 1989). · Zbl 0767.90042  R. Bixby, ”Implementing the simplex method: the initial basis,”ORSA Journal on Computing 4 (1992) 267–284. · Zbl 0759.90063  G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).  A.S. El-Bakry, R.A. Tapia and Y. Zhang, ”A study of indicators for identifying zero variables in interiorpont methods,” TR 91-15, Department of Mathematical Sciences, Rice University (Houston, TX, 1991). · Zbl 0801.65056  R. Fourer and S. Mehrotra, ”Solving symmetric indefinite systems in an interior-point method for linear programming,”Mathematical Programming (Series B) 62 (1993) 15–39. · Zbl 0802.90069 · doi:10.1007/BF01585158  R.M. Freund, R. Roundy and M.J. Todd, ”Identifying the set of always active constraints in a system of linear inequalities by a single linear program,” Technical Report, Sloan W.P. No. 1674-85 (MIT, Cambridge, MA, 1985).  D.M. Gay, ”Stopping tests that compute optimal solutions for interior-point linear programming algorithms,” Numerical Analysis Manuscript 89-11, AT&T Bell Laboratories (Murray Hill, NJ, 1989).  D.M. Gay, ”Electronic mail distribution of linear programming test problems,”Mathematical Programming Society News Letter, 10–12.  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  C.C. Gonzaga, ”An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming – Interior Point and Related Methods (Springer, New York, 1989) pp. 1–28. · Zbl 0691.90053  O. Güler and Y. Ye, ”Convergence behavior of interior-point algorithms,”Mathematical Programming 60 (1993) 215–228. · Zbl 0803.90087 · doi:10.1007/BF01580610  M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1989) 1–26. · Zbl 0676.90087 · doi:10.1007/BF01587074  N. Megiddo, ”On finding primal- and dual-optimal bases,”ORSA Journal on Computing 3 (1991) 63–66. · Zbl 0755.90056  S. Mehrotra, ”Quadratic convergence in a primal–dual method,”Mathematics of Operations Research 18 (1993) 741–751. · Zbl 0794.90034 · doi:10.1287/moor.18.3.741  S. Mizuno, M.J. Todd and Y. Ye, ”On adaptive-step primal–dual interior-point algorithms for linear programming,” (1990), to appear in:Mathematics of Operations Research. · Zbl 0810.90091  R.C. Monteiro and I. Adler, ”Interior path following primal–dual algorithms. Part I: Linear programming,”Mathematical Programming 44 (1989) 27–41. · Zbl 0676.90038 · doi:10.1007/BF01587075  J. Renegar, ”A polynomial-time algorithm, based on Newton’s method, for linear programming,”Mathematical Programming 40 (1988) 59–93. · Zbl 0654.90050 · doi:10.1007/BF01580724  A. Schrijver,Theory of Linear and Integer Programming (Wiley, New York, 1986). · Zbl 0665.90063  É. Tardos, ”A strongly polynomial algorithm to solve combinatorial linear programs,”Operations Research 34 (1986) 250–256. · Zbl 0626.90053 · doi:10.1287/opre.34.2.250  M.J. Todd, ”A low complexity interior-point algorithm for linear programming,”SIAM Journal on Optimization 2 (1992) 198–219. · Zbl 0811.90070 · doi:10.1137/0802011  P.M. Vaidya, ”An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations,”Mathematical Programming 47 (1990) 175–202. · Zbl 0708.90047 · doi:10.1007/BF01580859  Y. Ye, ”On the finite convergence of interior-point algorithms for linear programming,”Mathematical Programming (Series B) 57 (1992) 325–335. · Zbl 0794.90036 · doi:10.1007/BF01581087  Y. Ye, O. Güler, R.A. Tapia and Y. Zhang, ”A quadratically convergent $$O\left( {\sqrt {nL} } \right)$$ -iteration algorithm for linear programming,”Mathematical Programming 59 (1993) 151–162. · Zbl 0778.90037 · doi:10.1007/BF01581242
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.