Pith. sign in

REVIEW 3 major objections 5 minor 48 references

When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The primal interior point method can beat primal-dual near convergence by reusing one factorization as a preconditioner.

desk verdict A useful hybrid IPM idea with a real gap in the headline complexity theorem and an unverified non-degeneracy assumption. read the letter →

arxiv 2411.16015 v1 pith:NA6CNBPC submitted 2024-11-24 math.OC

Wenzhi Gao , Huikang Liu , Yinyu Ye , Madeleine Udell This is my paper · ORCID
classification math.OC MSC 90C0590C5165F08
keywords interiorpointmethodlinearprogrammingprimalnormalmatrixpreconditioningconjugategradientcentralpathsemidefinite
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that the classic primal interior point method, long overshadowed by the primal-dual variant, has a hidden advantage in the final phase of solving a linear program. As the iterate sequence converges, the primal normal matrix $M_X = AX^2A^T$ settles down and stops changing, so a single cached factorization can precondition every later linear solve. The central theorem bounds the preconditioned condition number by 9 once the barrier parameter is small enough, which turns the per-iteration cost of solving the normal equations from $O(n^3)$ to $O(n^2)$ with a Krylov solver. If this holds, a hybrid solver that starts with primal-dual and switches to primal IPM near convergence should be faster on a broad class of LPs; experiments on hundreds of benchmark instances and on semidefinite programs with many constraints support that expectation.

What carries the argument

The load-bearing object is the primal normal matrix $M_X = AX^2A^T$, the coefficient matrix of the normal equations whose solution produces the primal IPM search direction. Its stability is controlled by two proximity notions: Euclidean distance between iterates, which via Lemma 3.2 turns a close iterate into a good preconditioner, and the thresholded scaled distance of Definition 4, which handles coordinates that are large or tending to zero by mixing the Euclidean and scaled geometries. The delayed scaling matrix $W$ with $w_S = x_S$ and $w_L = z_L$ is the device that lets one cached factorization of $M_Z$ serve future iterates $x$ while the shifted scaling theorem keeps the surrogate direction accurate.

What would settle it

Solve a degenerate LP where an optimal solution has a zero coordinate in every optimal basis, so $\lambda_* = 0$, with the paper's preconditioned primal IPM and track $\kappa(M_{X_k}^{-1/2} M_{X_j} M_{X_k}^{-1/2})$; observing the bound exceed 9, or the conjugate-gradient iteration count failing to stay near $O(\log(1/\varepsilon))$ despite closeness in the thresholded distance, would overturn the stability claim.

Watch

Extended reading notes

Core claim

The central claim is that the primal normal matrix $M_{X_k} = AX_k^2A^T$ is stable under primal IPM convergence: Theorem 3.2 states that $\kappa(M_{X_k}^{-1/2} M_{X_j} M_{X_k}^{-1/2}) \le 9$ for all $j \ge k \ge k^*$, so after a threshold number of iterations one cached factorization of an earlier normal matrix serves as a uniformly good preconditioner for all later normal equations. The paper constructs a hybrid algorithm that uses primal-dual IPM until medium accuracy and then switches to the primal IPM with a delayed scaling matrix, which combines Euclidean proximity for preconditioning with scaled-distance proximity for an accurate search direction. The result is an $O(n^3 k^* + n^{2.5}\log^2(1/\varepsilon))$ complexity bound for primal non-degenerate LPs and a demonstrated speedup on benchmark LP instances and on SDPs with many constraints.

Load-bearing premise

The load-bearing premise is the paper's assumption A2: the primal problem is non-degenerate, so the optimal primal solution is unique and the smallest eigenvalue $\lambda_*$ of the limiting normal matrix is strictly positive.

Editorial extensions

If this is right

  • The per-iteration cost of the final IPM phase drops from $O(n^3)$ for a fresh factorization to $O(n^2)$ for a preconditioned Krylov solve, giving the hybrid algorithm its speedup.
  • A primal-dual solver can be modified to switch to primal IPM mid-run by caching one factorization and using iterative refinement; the paper's hybrid does this and reports a speedup on most of the 139 instances where both solvers pass.
  • For semidefinite programs with far more constraints than variables, the saving is larger because forming and factoring the normal matrix dominates the cost; the paper reports up to 10x speedup on such SDPs.
  • The complexity bound $O(n^3 k^* + n^{2.5}\log^2(1/\varepsilon))$ shows the iterative-solver phase has only logarithmic dependence on the accuracy target.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The stability argument should also hold when the barrier parameter is reduced adaptively rather than by a fixed schedule, so an adaptive step-size primal IPM might reach the preconditionable regime in fewer iterations.
  • The non-degeneracy assumption suggests the benefit of primal IPM is most pronounced on LPs with a unique primal optimum; on degenerate or badly scaled instances the condition number bound may degrade, and a practical solver would need a fallback to fresh factorizations.
  • A testable consequence: on instances where the primal-dual solver already converges superlinearly in one or two iterations, switching to primal IPM should give no speedup; a prospective study could quantify the optimal iteration at which to switch.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper revisits the primal barrier interior point method for linear optimization and argues that, near convergence, the primal normal matrices M_{X_k} = A X_k^2 A^T are stable: under assumptions A1 and A2 (nonempty relative interiors, full row rank A, and primal nondegeneracy with |B| = m), Theorem 3.2 states that the preconditioned condition number κ(M_{X_k}^{-1/2} M_{X_j} M_{X_k}^{-1/2}) ≤ 9 for all j ≥ k ≥ k^*. This motivates Algorithms 2 and 3, which cache a factorization of one normal matrix and use it as a preconditioner for iterative solves of later normal equations. The claimed payoff is a total arithmetic complexity O(n^3 k^* + n^{2.5} log^2(1/ε)) for the preconditioned primal IPM. Numerical experiments on 924 MIPLIB LP relaxations and on SDP benchmark instances show that a hybrid primal-dual/primal IPM speeds up a subset of instances, and Section 5.4 offers a qualitative taxonomy of IPM convergence patterns.

Significance. If the stability theorem is correct, it is a genuinely useful structural observation: it identifies a concrete reason why a primal scaling can outperform primal-dual scaling near convergence, and it gives a principled preconditioning strategy for normal-equation solves. The paper's experimental reporting is honest about the limited regime of benefit: 744 of 924 instances fall into cases C1/C2, and the reported speedups for the remaining instances are moderate and carefully qualified. The proofs in Appendix B are mostly self-contained and the dependence of the constants on λ^* and γ is explicit rather than fitted. However, two issues are load-bearing for the paper's central claim: the formal complexity theorem in Appendix C does not prove the initial-phase term in Theorem 3.3, and the experiments do not verify the nondegeneracy assumption A2 on which all the theoretical guarantees rest. These gaps do not destroy the empirical contribution, but they mean the paper currently overstates the connection between its provable stability regime and its numerical results.

major comments (3)
  1. [§C.4 / Theorem C.1] Theorem C.1 does not prove Theorem 3.3 as stated in the main text. The formal theorem assumes the iteration starts in the stable regime: μ1 below the threshold of Theorem 3.2, δ(x1, μ1) ≤ 1/2, and a cached factorization. Its proof invokes λ_min(A X^2 A^T) ≥ λ^*/4, which is only valid after the stable phase has begun. Consequently, the O(n^3 k^*) initial-phase cost in Theorem 3.3 is asserted, not derived: nothing in Appendix C bounds the number or cost of the iterations needed to reach the stable regime under Algorithm 2's inexact, cached-iterative solves. The standard primal IPM analysis cited for that phase assumes exact solves, so it cannot be applied directly to Algorithm 2. Please either prove the missing phase bound or restate Theorem 3.3 as a warm-start result with the initial-phase term removed.
  2. [§3.1 / §5.2] Assumption A2 is load-bearing for all of the stability and complexity results: Lemma 3.1, Theorems 3.1, 3.2, 3.3, and C.1 all rely on the maximal complementarity partition satisfying |B| = m so that λ^* = λ_min(M_{X^*}) > 0. For degenerate LPs, λ^* can be zero and the condition-number bound of Theorem 3.2 fails even in the warm-start regime. The experiments in Section 5.2 apply the hybrid solver to MIPLIB instances without checking nondegeneracy and without reporting the preconditioned condition numbers, so the observed speedups are not explicitly connected to the proved theoretical regime. To close this gap, the authors should at least report λ_min of the relevant normal matrices (or another degeneracy measure) for the instances on which primal IPM is invoked, or restrict the theoretical claims to the regime in which A2 is verified.
  3. [§3.2 / §5.2] The warm-start index k^* in Theorem 3.2 and the complexity bound in Theorem 3.3 depend on constants that are not available to a solver: λ^*, γ, ∥A_N∥/sqrt(λ_min(A_B^T A_B)), and ∥A∥. The practical algorithm instead switches heuristically on ∥x_k − x_{k−1}∥_{x_k,ν} ≤ 10^{-1} and a time-ratio threshold of 30. This is acceptable for an experimental paper, but the text should state explicitly that Theorem 3.3 is an existence-level result that does not translate into an implementable guarantee for the switching rule, and that the rule is validated only empirically.
minor comments (5)
  1. [§3.2] The sentence preceding Theorem 3.3 contains a typo: 'yeilds' should be 'yields'. Also, Theorem 3.3 is labeled 'Informal' but no formal statement is given in the main text; the formal statement appears only as Theorem C.1 in Appendix C, which makes the main-text claim hard to check.
  2. [§C.3 / Lemma C.3] In the proof of Lemma C.3, the displayed inequality after (26) reads 'δ(x_+, μ) ≤ √2 δ(x_+, μ)^2 + ...'; the first δ(x_+, μ) on the right should be δ(x, μ). As written, the line is self-referential and the square-root step is unclear.
  3. [§5.4 / Figures 2–4] The small-multiple plots in Figures 2–4 would be much easier to verify if they had axis labels, legends, and consistent scales; the current captions do not explain how the 'scaled' distance is computed for primal-dual iterates in the same way as Definition 4.
  4. [Definition 4 / Algorithm 3] The threshold ν in Definition 4, the update tolerance θ in Algorithm 3, and the switch parameters 0.1 and 30 in Section 5.2 are introduced without any sensitivity analysis; a brief study of how results depend on these parameters would strengthen the empirical claims.
  5. [§5.2 / Table 1] The text says 'Only six instances slow down when primal IPM is invoked and passes the test', but Table 1 contains several additional negative speedup entries (for example neos-885524, graph40-20-1rand, and supportcase29); the sentence should either quantify the criterion precisely or refer to the table for the exact count.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the stability and complexity results are derived from explicit assumptions and external IPM lemmas; the main caveat is a warm-start proof gap in Appendix C, not a circular reduction.

full rationale

The paper's core theoretical chain is self-contained rather than circular. Theorem 3.2's condition-number bound is derived from Lemma 3.1, whose proof (Appendix B.2) uses the central-path proximity bound of Lemma B.1, the coordinate bound x_mu,j <= gamma mu of Lemma B.2, and the non-degeneracy assumption A2; none of these lemmas assumes the conclusion. Lemma 3.2 is a standard spectral perturbation inequality, and Theorem 3.2 applies it to the explicit iterate bound (21) to obtain kappa(M_{X_k}^{-1/2} M_{X_j} M_{X_k}^{-1/2}) <= 9; the threshold k* is expressed in terms of problem constants (lambda*, gamma, A), not fitted to data. Theorem 3.4's per-iteration O(n^2 log(1/epsilon)) bound follows from the shifted scaling theorem (Lemma B.4, [21]) plus Lemma 3.2, with explicit hypotheses on the thresholded distance; the delayed scaling construction w = (x_S, z_L) is an algorithmic design, not a prediction equivalent to its conclusion. The numerical experiments are demonstrations on MIPLIB and SDP benchmarks; no parameter is fitted to force the reported speedups. Self-citations exist (HDSDP [16]; Guler-Ye [23] for maximal complementarity) but are not load-bearing: HDSDP is used as the software baseline and the maximal complementarity result is standard external theory. The one substantive caveat is that the formal statement in Appendix C (Theorem C.1) assumes a warm start with mu_1 below the threshold and delta(x_1,mu_1) <= 1/2, so the O(n^3 k*) initial-phase term asserted in Theorem 3.3 is not proven there; this is a proof-completeness issue, not a circularity, since the phase is asserted from standard primal IPM analysis rather than being assumed as the target result. Hence the circularity score is low.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central theory relies on two domain assumptions (A1, A2) and standard IPM lemmas. The free parameters are experimental switch thresholds and tolerances that are not reported or analyzed, which limits the reproducibility and strength of the empirical claims. No new entities (forces, particles, conserved quantities) are introduced.

free parameters (4)
  • threshold nu in Definition 4 = not reported (example uses nu=1)
    Splits coordinates into large and small for the thresholded scaled distance; affects the switch condition and the existence of the delayed scaling matrix w. The value used in experiments is not stated.
  • factorization update tolerance theta in Algorithm 3 = not reported
    Controls how often the preconditioner is refactorized. Larger theta means fewer factorizations but potentially worse preconditioning; the value used in experiments is not given.
  • switch distance threshold 0.1 in Section 5.2 = 10^{-1}
    The hybrid switches to primal IPM when ||x_k - x_{k-1}||_{x_k,nu} <= 10^{-1}. This is chosen by hand and directly controls which instances are classified as C4 and thus the reported speedup distribution.
  • switch time ratio 30 in Section 5.2 = >30
    The hybrid only switches if factorization time divided by forward/backward substitution time exceeds 30. This heuristic filters for instances where the iterative solver is likely to help; its value materially affects the fraction of instances showing speedup.
assumptions (5)
  • domain assumption A1: interior point condition (F_p^0 and F_d^0 nonempty, A full row rank)
    Standard in IPM literature; used throughout Section 2 and 3 to guarantee the central path exists and Algorithm 1 is well-defined.
  • domain assumption A2: primal non-degeneracy (|B| = m)
    Used in Lemma 3.1 to bound the diameter of the central path proximity set and in Theorem 3.2 to ensure lambda_star > 0. Without it, the condition number bound and O(n^2) per-iteration cost fail.
  • domain assumption Shifted scaling theorem (Lemma 3.3), cited to [21]
    Underlies the approximation of the search direction by a surrogate projection in Algorithm 3. The paper relies on this external lemma without proof.
  • domain assumption Lemma B.1 (central path proximity bound), cited to [33]
    Used in Lemma 3.1 and Lemma B.3 to relate Euclidean distance to scaled distance; standard IPM analysis tool adopted as a black box.
  • standard math Conjugate gradient convergence: O(n^2 log(1/eps)) per solve for bounded condition number
    Standard result for preconditioned CG; used to convert the condition number bound into per-iteration arithmetic complexity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?." pith.science (2026). https://pith.science/paper/NA6CNBPC

@misc{pith2026241116015,
  author       = {Pith},
  title        = {Pith review of: When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NA6CNBPC}},
  note         = {Machine review of arXiv:2411.16015}
}
read the original abstract

The primal-dual interior point method (IPM) is widely regarded as the most efficient IPM variant for linear optimization. In this paper, we demonstrate that the improved stability of the pure primal IPM can allow speedups relative to a primal-dual solver, particularly as the IPM approaches convergence. The stability of the primal scaling matrix makes it possible to accelerate each primal IPM step using fast preconditioned iterative solvers for the normal equations. Crucially, we identify properties of the central path that make it possible to stabilize the normal equations. Experiments on benchmark datasets demonstrate the efficiency of primal IPM and showcase its potential for practical applications in linear optimization and beyond.

Figures

Figures reproduced from arXiv: 2411.16015 by the authors.

Figure 1
Figure 1. Left: distribution of primal IPM speedup over 139 LPs. Right: Dual vs hybrid dual-primal IPM on [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Problems with convergence pattern: linear convergence [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Problems with convergence pattern: fast convergence at the end. For problems like the leftmost [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Problems with convergence pattern: no clear convergence. Often this pattern results when the [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 45 canonical work pages

  1. [1]

    An implementation of kar- markar’s algorithm for linear programming.Mathematical programming, 44:297–335, 1989

    Ilan Adler, Mauricio GC Resende, Geraldo Veiga, and Narendra Karmarkar. An implementation of kar- markar’s algorithm for linear programming.Mathematical programming, 44:297–335, 1989

    work page 1989

  2. [2]

    HEC/Université de Geneve, 1996

    Erling D Andersen, Jacek Gondzio, Csaba Mészáros, Xiaojie Xu, et al.Implementation of interior point methods for large scale linear programming. HEC/Université de Geneve, 1996

    work page 1996

  3. [3]

    Inexact interior-point method.Journal of Optimization Theory and Applications, 96:109– 121, 1998

    Stefania Bellavia. Inexact interior-point method.Journal of Optimization Theory and Applications, 96:109– 121, 1998. 14

    work page 1998

  4. [4]

    An inexact dual logarithmic barrier method for solving sparse semidefinite programs.Mathematical Programming, 178:109–143, 2019

    Stefania Bellavia, Jacek Gondzio, and Margherita Porcelli. An inexact dual logarithmic barrier method for solving sparse semidefinite programs.Mathematical Programming, 178:109–143, 2019

    work page 2019

  5. [5]

    Algorithm 875: Dsdp5-software for semidefinite programming

    Steven J Benson and Yinyu Ye. Algorithm 875: Dsdp5-software for semidefinite programming. ACM Transactions on Mathematical Software (TOMS), 34(3):1–20, 2008

    work page 2008

  6. [6]

    A new preconditioning approach for an interior point-proximal method of multipliers for linear and convex quadratic programming

    Luca Bergamaschi, Jacek Gondzio, Ángeles Martínez, John W Pearson, and Spyridon Pougkakiotis. A new preconditioning approach for an interior point-proximal method of multipliers for linear and convex quadratic programming. Numerical Linear Algebra with Applications, 28(4):e2361, 2021

    work page 2021

  7. [7]

    Inexact constraint preconditioners for linear systems arising in interior point methods.Computational Optimization and Applications, 36:137– 147, 2007

    Luca Bergamaschi, Jacek Gondzio, Manolo Venturin, and Giovanni Zilli. Inexact constraint preconditioners for linear systems arising in interior point methods.Computational Optimization and Applications, 36:137– 147, 2007

    work page 2007

  8. [8]

    Preconditioning indefinite systems in interior point methods for optimization.Computational Optimization and Applications, 28:149–171, 2004

    Luca Bergamaschi, Jacek Gondzio, and Giovanni Zilli. Preconditioning indefinite systems in interior point methods for optimization.Computational Optimization and Applications, 28:149–171, 2004

    work page 2004

Show all 48 references
  1. [9]

    Faster randomized infeasible interior point methods for tall/wide linear programs.Advances in Neural Information Processing Systems, 33:8704– 8715, 2020

    Agniva Chowdhury, Palma London, Haim Avron, and Petros Drineas. Faster randomized infeasible interior point methods for tall/wide linear programs.Advances in Neural Information Processing Systems, 33:8704– 8715, 2020

    2020

  2. [10]

    Randomized nystr\" om preconditioned interior point-proximal method of multipliers.arXiv preprint arXiv:2404.14524, 2024

    Ya-Chi Chu, Luiz-Rafael Santos, and Madeleine Udell. Randomized nystr\" om preconditioned interior point-proximal method of multipliers.arXiv preprint arXiv:2404.14524, 2024

    2024 arXiv

  3. [11]

    Proximal stabilized interior point methods and low-frequency-update preconditioning techniques

    Stefano Cipolla and Jacek Gondzio. Proximal stabilized interior point methods and low-frequency-update preconditioning techniques. Journal of Optimization Theory and Applications, 197(3):1061–1103, 2023

    2023

  4. [12]

    Solving linear programs in the current matrix multipli- cation time

    Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multipli- cation time. Journal of the ACM (JACM), 68(1):1–39, 2021

    2021

  5. [13]

    A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

    Daniel Dadush, Sophie Huiberts, Bento Natura, and László A Végh. A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 761–774, 2020

    2020

  6. [14]

    Iterative solution of problems of linear and quadratic programming

    II Dikin. Iterative solution of problems of linear and quadratic programming. InDoklady Akademii Nauk, volume 174, pages 747–748. Russian Academy of Sciences, 1967

    1967

  7. [15]

    Convergence of a class of inexact interior-point algorithms for linear programs.Mathematics of Operations Research, 24(1):50–71, 1999

    Roland W Freund, Florian Jarre, and Shinji Mizuno. Convergence of a class of inexact interior-point algorithms for linear programs.Mathematics of Operations Research, 24(1):50–71, 1999

    1999

  8. [16]

    Hdsdp: Software for semidefinite programming.arXiv preprint arXiv:2207.13862, 2022

    Wenzhi Gao, Dongdong Ge, and Yinyu Ye. Hdsdp: Software for semidefinite programming.arXiv preprint arXiv:2207.13862, 2022

    2022 arXiv

  9. [17]

    Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D

    AmbrosGleixner, GregorHendel, GeraldGamrath, TobiasAchterberg, MichaelBastubbe, TimoBerthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shinano. MIPLIB 2017: ...

    2017

  10. [18]

    Interior point methods 25 years later

    Jacek Gondzio. Interior point methods 25 years later. European Journal of Operational Research, 218(3):587–601, 2012

    2012

  11. [19]

    Matrix-free interior point method.Computational Optimization and Applications, 51:457– 480, 2012

    Jacek Gondzio. Matrix-free interior point method.Computational Optimization and Applications, 51:457– 480, 2012

    2012

  12. [20]

    General-purpose preconditioning for regu- larized interior point methods.Computational Optimization and Applications, 83(3):727–757, 2022

    Jacek Gondzio, Spyridon Pougkakiotis, and John W Pearson. General-purpose preconditioning for regu- larized interior point methods.Computational Optimization and Applications, 83(3):727–757, 2022. 15

    2022

  13. [21]

    Properties of the central points in linear programming problems

    Clovis C Gonzaga and Marli Cardia. Properties of the central points in linear programming problems. Numerical Algorithms, 35:185–204, 2004

    2004

  14. [22]

    Degeneracy in interior point methods for linear programming: a survey

    Osman Güler, Dick den Hertog, Cornelis Roos, Tamas Terlaky, and Takashi Tsuchiya. Degeneracy in interior point methods for linear programming: a survey. Annals of Operations Research, 46:107–138, 1993

    1993

  15. [23]

    Convergence behavior of interior-point algorithms.Mathematical Program- ming, 60(1-3):215–228, 1993

    Osman Güler and Yinyu Ye. Convergence behavior of interior-point algorithms.Mathematical Program- ming, 60(1-3):215–228, 1993

    1993

  16. [24]

    A new polynomial-time algorithm for linear programming

    Narendra Karmarkar. A new polynomial-time algorithm for linear programming. InProceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302–311, 1984

    1984

  17. [25]

    Computational results of an interior point algorithm for large scale linear programming.Mathematical Programming, 52:555–586, 1991

    NK Karmarkar and KG Ramakrishnan. Computational results of an interior point algorithm for large scale linear programming.Mathematical Programming, 52:555–586, 1991

    1991

  18. [26]

    Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow

    Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow. In2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424–433. IEEE, 2014

    2014

  19. [27]

    Springer, 1984

    David G Luenberger, Yinyu Ye, et al.Linear and nonlinear programming, volume 2. Springer, 1984

    1984

  20. [28]

    Interior point methods for linear programming: Computational state of the art.ORSA Journal on Computing, 6(1):1–14, 1994

    Irvin J Lustig, Roy E Marsten, and David F Shanno. Interior point methods for linear programming: Computational state of the art.ORSA Journal on Computing, 6(1):1–14, 1994

    1994

  21. [29]

    On the implementation of a primal-dual interior point method

    Sanjay Mehrotra. On the implementation of a primal-dual interior point method. SIAM Journal on optimization, 2(4):575–601, 1992

    1992

  22. [30]

    An independent benchmarking of sdp and socp solvers.Mathematical Programming, 95(2):407–430, 2003

    Hans D Mittelmann. An independent benchmarking of sdp and socp solvers.Mathematical Programming, 95(2):407–430, 2003

    2003

  23. [31]

    Benchmarking optimization software-a (hi) story

    Hans D Mittelmann. Benchmarking optimization software-a (hi) story. InSN operations research forum, volume 1, page 2. Springer, 2020

    2020

  24. [32]

    Interior point methods for linear optimization

    Cornelis Roos, Tamás Terlaky, and J-Ph Vial. Interior point methods for linear optimization. 2005

    2005

  25. [33]

    Wiley Chichester, 1997

    Cornelis Roos, Tamás Terlaky, and Jean-Philippe Vial.Theory and algorithms for linear optimization: an interior point approach. Wiley Chichester, 1997

    1997

  26. [34]

    A polynomial method of approximate centers for linear programming

    Cornelis Roos and J Ph Vial. A polynomial method of approximate centers for linear programming. Mathematical Programming, 54:295–305, 1992

    1992

  27. [35]

    SIAM, 2003

    Yousef Saad.Iterative methods for sparse linear systems. SIAM, 2003

    2003

  28. [36]

    Implementation of an interior point method with basis preconditioning

    Lukas Schork and Jacek Gondzio. Implementation of an interior point method with basis preconditioning. Mathematical Programming Computation, 12(4):603–635, 2020

    2020

  29. [37]

    Scaling, shifting and weighting in interior-point methods.Computational Optimization and Applications, 3(4):305–315, 1994

    Michael J Todd. Scaling, shifting and weighting in interior-point methods.Computational Optimization and Applications, 3(4):305–315, 1994

    1994

  30. [38]

    A deterministic linear program solver in current matrix multiplication time

    Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 259–278. SIAM, 2020

    2020

  31. [39]

    A primal-dual interior point method whose running time depends only on the constraint matrix.Mathematical Programming, 74(1):79–120, 1996

    Stephen A Vavasis and Yinyu Ye. A primal-dual interior point method whose running time depends only on the constraint matrix.Mathematical Programming, 74(1):79–120, 1996. 16

    1996

  32. [40]

    Anoteonhybridpreconditioners for large-scale normal equations arising from interior-point methods.Optimization Methods & Software, 25(2):321–332, 2010

    MartaInezVelazco, AurelioRLOliveira, andFredericoFerreiraCampos. Anoteonhybridpreconditioners for large-scale normal equations arising from interior-point methods.Optimization Methods & Software, 25(2):321–332, 2010

    2010

  33. [41]

    Adaptive use of iterative methods in predictor–corrector interior point methods for linear programming.Numerical Algorithms, 25:387–406, 2000

    Weichung Wang and Dianne P O’Leary. Adaptive use of iterative methods in predictor–corrector interior point methods for linear programming.Numerical Algorithms, 25:387–406, 2000

    2000

  34. [42]

    SIAM, 1997

    Stephen J Wright.Primal-dual interior-point methods. SIAM, 1997

    1997

  35. [43]

    Ano(n3l) potential reduction algorithm for linear programming.Mathematical programming, 50(1-3):239–258, 1991

    Yinyu Ye. Ano(n3l) potential reduction algorithm for linear programming.Mathematical programming, 50(1-3):239–258, 1991

    1991

  36. [44]

    John Wiley & Sons, 2011

    Yinyu Ye.Interior point algorithms: theory and analysis. John Wiley & Sons, 2011

    2011

  37. [45]

    A new stopping criterion for krylov solvers applied in interior point methods

    Filippo Zanetti and Jacek Gondzio. A new stopping criterion for krylov solvers applied in interior point methods. SIAM Journal on Scientific Computing, 45(2):A703–A728, 2023. 17 Appendix Table of Contents A Detailed statistics on MIPLIB instances 19 B Proof of Results in Secti...

    2023

  38. [46]

    Next consider solving(A W2A⊤)−1A W(WX−1)v

    Plugging in conditionθ ≤ ε 6δ(x,µ) gives ∥X−1(∆x − ∆˜x)∥ ≤ε 2. Next consider solving(A W2A⊤)−1A W(WX−1)v. We have∥w − z∥ = ∥wS − zS ∥ ≤θ and for θ ≤ √λz 2∥A∥, we invokeLemma 3.2with β = 1 2 to get A W2A⊤ ⪰ 1 4 AZ2A⊤ ⪰ λz 4 and κ((AZ2A⊤)−1/2A W2A⊤(AZ2A⊤)−1/2) ≤ 9, Finally, we a...

  39. [47]

    Lemma C.4

    This completes the proof. Lemma C.4. Suppose δ(x, µ) ≤ 1 2, then for allµ ≤ √ λ⋆τ 16γ · ( ∥AN ∥√ λmin(A⊤ B AB) + 1)−1 ∥ψx∥ ≤( 1 αµσmin(A) + 2√ λ⋆ ) 1 σmin(A) ∥ζx∥. Proof. Recall that ψx = XA⊤(AX2A⊤)−1ζx + X−1λx and we first considerλx. First note that ∥λx∥ = q ⟨ζx, (AA⊤)−1ζx⟩ ...

  40. [48]

    Therefore x+ ∈ F0 p

    We have∥z − e∥∞ ≤ ∥z − e∥ ≤1 2 and from (27) we deduce that 2e − z + ψx ≥ ( 1 2 − ∥ψx∥)e ≥ 0.1e. Therefore x+ ∈ F0 p. Next fix τ = 1/(10√n) and for n ≥ 100 δ(x+, µ+) ≤ 1 1−τ (δ(x+, µ) + τ √n) ≤ 1 1−τ ( √ 2δ(x, µ)2 + ( √ 2n + 1)∥ψx∥) + τ √n 1−τ = √ 2 1−τ δ(x, µ)2 + √ 2n+1 1−τ ∥...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.