Interior-point methods solve constrained optimization problems by following a smooth path through the inside of the feasible region toward the optimum. Each step solves a large linear system. That system becomes badly conditioned as the path nears the boundary: variables pinned at their bounds and variables far from them get scaled by factors that differ by many orders of magnitude. For problems with block structure, such as stochastic programs with many scenarios or network problems with many subnetworks, the natural way to parallelize is to hand each block to a worker that solves its piece iteratively. The coordinator then waits for all of them. Today every worker is held to the same accuracy target, measured as a plain residual. The coordinator therefore waits for the slowest worker to reach a precision that, for most of its variables, the method never needed.
We propose that "how accurately must this block be solved" has a precise answer tied to the boundary. An error in a step matters only through how it changes each variable relative to that variable's own distance from its bound, because that ratio decides how far the method can safely move. We will measure inner-solve error in this boundary-scaled way and give each block its own share of a total error budget. Each iteration's budget is set by how much room the current point has before it leaves the safe region around the path. Under a time deadline, the coordinator accepts slow blocks' partial solves whenever the budget allows. The result is one mechanism for three problems: it respects boundary ill-conditioning, it gives a principled inexact-solve criterion, and it turns stragglers from a synchronization stall into a bookkeeping question.
Core Claim
The fraction-to-boundary rule limits the step length $\alpha$ by the smallest ratio $x_i/|\Delta x_i|$ over components moving toward their bound. An error $\delta x_i$ in the computed direction therefore perturbs the step by roughly $\delta x_i / x_i$. A component with $x_i = 10^{-8}$ needs absolute error far below $10^{-8}$, while a component with $x_i = 1$ tolerates errors of $10^{-2}$. The standard Krylov stopping test $\|r\| \le \eta \|b\|$ ignores this distinction, so it over-solves most components and may under-solve the few that matter. (Krylov methods such as conjugate gradients solve a linear system by building up the answer from repeated matrix-vector products.) For block $j$ with primal iterate $x_j$, dual slack $s_j$, and direction error $(\delta x_j, \delta s_j)$, we define the boundary-scaled error
$$\rho_j = \|X_j^{-1}\delta x_j\|_2 + \|S_j^{-1}\delta s_j\|_2,$$
where $X_j, S_j$ are diagonal matrices of $x_j, s_j$. We accept a parallel step when
$$\sum_j \rho_j \le \eta_k = \gamma\,\big(1 - \|XSe/\mu_k - e\|/\beta\big),$$
with the following definitions. The term $\|XSe/\mu_k - e\|$ measures how far the current iterate sits from the central path at barrier parameter $\mu_k$. The constant $\beta$ is the width of the neighborhood the method must stay inside, so the parenthesis is the remaining margin. The constant $\gamma$ is a safety factor. The form follows from a standard neighborhood argument: if the scaled perturbation to the step is smaller than the remaining margin, the next iterate stays inside the neighborhood, so the iteration-count analysis carries over up to a constant.
The claim has three parts. First, this per-block scaled budget preserves long-step, predictor-corrector convergence behavior. Second, it lets blocks stop far earlier than a uniform residual test. Third, a deadline-driven coordinator that accepts partial solves under the budget removes most straggler stalls without the instability that asynchrony usually brings to second-order methods.
Relation to Prior Work
The obvious idea at this intersection is already done: interior-point dual decomposition with inexact subproblem solves. An Inexact Interior-Point Lagrangian Decomposition Algorithm with Inexact Oracles smooths a Lagrangian dual with self-concordant barriers, solves parallel subproblems inexactly, and proves short-step polynomial complexity. Its predecessor, An Interior-Point Lagrangian Decomposition Method for Separable Convex Optimization, requires exact subproblem solves. Both motivate this proposal, and both use a single tolerance and a synchronous coordinator. Our contribution differs in three ways. The tolerance is allocated per block in the boundary-scaled metric. It is tied to the neighborhood margin, so it works with long-step predictor-corrector methods rather than only short steps. And the coordinator accepts incomplete blocks under a deadline. IPLD's own finding is also a constraint on us: it was "relatively insensitive to error tolerances, provided they remained below a threshold (e.g., $10^{-4}$)". That suggests uniform tolerances may be good enough, so our experiments must show the gain rather than assume it.
Two papers supply the feasibility machinery and the unresolved tension we target. On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming adds an error-adjustment vector that absorbs linear-solve residuals, preventing "creeping infeasibility" in a centralized, full-rank setting. Faster Randomized Interior Point Methods for Tall/Wide Linear Programs reports that the correction was often unnecessary in practice. Stephen Wright's Stability of Linear Equations Solvers in Interior-Point Methods explains why direct solvers survive ill-conditioning: their errors concentrate in components where step sizes are already forced to be small. Our hypothesis is that the boundary-scaled error is the quantity that decides harm, and that preconditioned Krylov errors are often small in this metric even when raw residuals are not. If true, this explains the empirical robustness in a way we can test directly.
Two papers supply the parallel structure and preconditioning. Design and implementation of a modular interior-point solver for linear optimization (Tulip) exploits block-angular structure from Dantzig-Wolfe decomposition with exact factorizations and reports a tenfold speedup over commercial solvers on large dense instances, but its outer loop is single-threaded. A Scalable Interior-Point Gauss-Newton Method for PDE-Constrained Optimization with Bound Constraints shows that barrier-aware preconditioners can hold Krylov counts flat, at about 6.5 per step across four orders of magnitude of $\mu$. It still uses synchronous global reductions. We reuse regularized-IPM preconditioners from General-purpose preconditioning for regularized interior point methods inside each block, so that differences we observe come from the stopping rule and not the preconditioner.
Finally, Accelerated Dual Method for Distributed Optimization: An Inexact-Gradient View of Local Updates shows that stale or partial local work can be treated as inexactness in a first-order dual method. We carry that view to a second-order barrier method. There, inexactness is only safe when measured against the boundary.
Research Program
We will build a parallel block-angular interior-point solver on Tulip's modular linear-algebra interface. Each block's normal-equations system is solved by preconditioned conjugate gradients on its own worker. A small dense Schur complement over the linking constraints is solved exactly at the coordinator. Workers report current iterates together with an estimate of $\rho_j$.
The main technical problem is estimating true scaled error from inside conjugate gradients, not just the residual. We will use the energy-norm error estimates that CG provides from a few look-ahead iterations. We will then convert them to the $X_j^{-1}$-scaled norm through the block's diagonal scaling, and check the estimates against exact solves on small instances.
The coordinator sets $\eta_k$ from the neighborhood margin. It splits the budget across blocks in proportion to each block's recent cost per unit of error reduction, so that slow blocks get looser targets. It accepts the step at a wall-clock deadline if the reported $\sum_j \rho_j$ fits the budget. Otherwise it waits only for the blocks contributing most to the excess.
Infeasibility from partial solves is handled in the infeasible-interior-point style: residuals are allowed if they shrink in proportion to $\mu$. We will test whether block-local variants of Dexter et al.'s adjustment vector are ever needed.
On the theory side, we aim to prove that the budget condition keeps iterates in a wide neighborhood of the path, with iteration complexity matching the exact predictor-corrector method up to a constant. The proof will follow the neighborhood arguments of Dexter et al. and the local-norm arguments of IPLD. We will drop their full-rank assumption on the linking block and assume regularization instead.
Baselines
The do-nothing reference is single-threaded Tulip with exact block-angular factorization. Its tenfold speedup over CPLEX, Gurobi and Mosek on large Dantzig-Wolfe instances is the reported figure from Design and implementation of a modular interior-point solver for linear optimization. The file gives no absolute runtimes, so we rerun it.
The strongest direct competitor on our structured instances is the same solver with per-block exact factorizations run in parallel and a synchronous coordinator. This is the obvious engineering fix, and it inherits Wright's immunity to ill-conditioning. We run it on identical hardware and thread counts.
The strongest inexact competitor is synchronous parallel CG with a uniform relative-residual tolerance. We tune that tolerance on a grid ($10^{-2}$ to $10^{-8}$), giving it the same tuning budget as our $\gamma$. We run it with and without per-block error adjustment in the style of On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming.
On network utility maximization, the strongest existing method is IPLD. It solved instances with over 2 million variables in approximately 9 minutes, where SDPT3 ran out of memory, and reached $10^{-7}$ accuracy in far fewer iterations than Chambolle-Pock, as reported in An Inexact Interior-Point Lagrangian Decomposition Algorithm with Inexact Oracles. We reimplement it on our hardware rather than compare against the reported time. Chambolle-Pock and ADMM run with tuned step sizes as the first-order reference.
Two ablations isolate the key ingredients. The first uses the scaled budget with a synchronous coordinator, testing the metric alone. The second uses a deadline coordinator with a uniform residual budget, testing deadlines alone.
Beating the tuned uniform-tolerance baseline means reaching a $10^{-7}$ relative duality gap, with primal infeasibility at the level Dexter et al. report (around $10^{-10}$), in less wall-clock time. It also means doing so with fewer total inner iterations at matched outer iteration counts. Under injected straggler delays, the slowdown relative to the no-delay run must grow markedly more slowly than the synchronous baseline's.
Why not just…?
Why not just use one loose, uniform Krylov tolerance, since IPLD found it barely matters? This is the most serious threat. IPLD's reported insensitivity below $10^{-4}$ and the Tall/Wide paper's observation that correction was often unnecessary both suggest uniform tolerances are usually safe. Our answer is empirical. We will log, per block and per iteration, both the raw residual and the true scaled error $\rho_j$ computed from an exact reference solve. If the two are tightly correlated late in the solve, the scaled metric adds nothing. In that case the proposal reduces to its deadline component, and we will report that. The metric earns its place only if the uniform baseline either over-solves (measurably more inner iterations at equal accuracy) or occasionally loses long steps near the boundary.
Why not just parallelize exact per-block factorizations? Wright's analysis makes this numerically safe, and when blocks are small it will likely win. With a thousand small scenario blocks, per-block Cholesky is cheap and our mechanism has nothing to save. We therefore claim an advantage only when individual blocks are large enough that factorization fill-in dominates, the failure mode shown on FIT2P in General-purpose preconditioning for regularized interior point methods, or when worker latency varies. The block-size sweep below locates the crossover explicitly.
Why not just use a first-order splitting method such as ADMM, which parallelizes trivially? The file reports that Chambolle-Pock needed far more iterations than IPLD to reach $10^{-7}$ on the same network instances. It also reports that DIP was about ten times faster than an alternating-direction method on multicommodity flow, with the first-order method failing to reach accuracy within 24 hours on the largest cases (An Interior-Point Lagrangian Decomposition Method for Separable Convex Optimization). We rerun Chambolle-Pock at both $10^{-4}$ and $10^{-7}$ targets. We expect it to be competitive at low accuracy, and our claim concerns high accuracy.
Why not just apply Dexter et al.'s error-adjustment vector in each block? That construction guarantees feasibility, but it relies on full-rank, sketching-based preconditioners and does nothing for synchronization. We include it as a baseline variant. If it alone matches our wall-clock numbers without deadlines, the budget mechanism is redundant.
Proposed Experiments
The experiments use benchmarks from the file. The first is the Dantzig-Wolfe structured suite from the Tulip paper: two-stage stochastic programs with at least 1,000 scenarios, and distributed energy resource coordination instances. We scale per-block size to sweep from factorization-friendly to factorization-hostile. The second is the network utility maximization instances used by IPLD (tech-router-rf, tech-pgp, ADSL and VDSL). The third is Netlib and the Mittelmann barrier set, used as unstructured controls where we treat row partitions as blocks.
We will run on a shared-memory multicore node and on a small cluster. On the cluster we inject heavy-tailed latency into a random subset of workers, since the file offers no real straggler benchmark.
Metrics are wall-clock time to a $10^{-7}$ relative duality gap, total and per-block inner CG iterations, outer iteration counts, final primal and dual infeasibility, and the fraction of iterations accepted under deadline with incomplete blocks.
Three checks decide the question. The first is the correlation study between raw residual and scaled error described above, which directly tests the Gap 3 hypothesis. The second is an outer-iteration comparison: if the scaled budget is sound, outer iterations should stay within a small constant of the exact-solve method while inner work drops. A rise in outer iterations of the same size as the inner savings would falsify the claim. The third is a straggler sweep: synchronous baselines' time should grow with the injected tail delay, while ours should flatten until the budget can no longer absorb missing blocks. The point where that happens is itself a measurement of how much inexactness the boundary geometry permits.
References
- An Inexact Interior-Point Lagrangian Decomposition Algorithm with Inexact Oracles
- An Interior-Point Lagrangian Decomposition Method for Separable Convex Optimization
- On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming
- Faster Randomized Interior Point Methods for Tall/Wide Linear Programs
- Stability of Linear Equations Solvers in Interior-Point Methods
- Design and implementation of a modular interior-point solver for linear optimization
- A Scalable Interior‐Point Gauss–Newton Method for PDE‐Constrained Optimization With Bound Constraints
- General-purpose preconditioning for regularized interior point methods
- Accelerated Dual Method for Distributed Optimization: An Inexact-Gradient View of Local Updates