Finding an interior point in the optimal face of linear programs (Q1319020): Difference between revisions
From MaRDI portal
Latest revision as of 13:28, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding an interior point in the optimal face of linear programs |
scientific article |
Statements
Finding an interior point in the optimal face of linear programs (English)
0 references
3 January 1995
0 references
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 \textit{R. M. Freund} et al. [Technical Report, Sloan W. P. No. 1674-85, MIT, Cambridge, MA (1985)] and \textit{E. Tardos} [Oper. Res. 34, 250-256 (1986; Zbl 0626.90053)].
0 references
interior point
0 references
optimal face
0 references
primal-dual methods
0 references
strict complementarity
0 references
optimal partition
0 references
0 references
0 references