Finding an interior point in the optimal face of linear programs (Q1319020): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(4 intermediate revisions by 3 users not shown)
Property / reviewed by
 
Property / reviewed by: R. N. Kaul / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: R. N. Kaul / rank
 
Normal rank
Property / describes a project that uses
 
Property / describes a project that uses: NETLIB LP Test Set / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: A geometric view of parametric linear programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: Implementing the Simplex Method: The Initial Basis / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Study of Indicators for Identifying Zero Variables in Interior-Point Methods / rank
 
Normal rank
Property / cites work
 
Property / cites work: Solving symmetric indefinite systems in an interior-point method for linear programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3236242 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3033554 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Convergence behavior of interior-point algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: A polynomial-time algorithm for a class of linear complementarity problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Finding Primal- and Dual-Optimal Bases / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quadratic Convergence in a Primal-Dual Method / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: Interior path following primal-dual algorithms. I: Linear programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: A polynomial-time algorithm, based on Newton's method, for linear programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3818127 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Low Complexity Interior-Point Algorithm for Linear Programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the finite convergence of interior-point algorithms for linear programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming / rank
 
Normal rank

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
    0 references
    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

    Identifiers