How hard is a random LP?

The random LPs

Standard form $\min\, c^\top x$ subject to $Ax=b,\ x\ge 0$, from the model used in the experiments of [A] and [H]:

• $A\in\mathbb{R}^{m\times n}$ has i.i.d. $N(0,1)$ entries (or $\pm1$ entries);
• $\hat x=(|u_1|,\dots,|u_m|,0,\dots,0)$ and $\hat s=(0,\dots,0,|u_{m+1}|,\dots,|u_n|)$ with $u\sim N(0,I)$;
• $b=A\hat x$, and $c=\hat s+A^\top\hat y$ with $\hat y$ chosen so that $Ac=0$.

Then $x^\star=\hat x$ and $s^\star=\hat s$ are known, so $\Phi$ comes from its closed form.

rPDHG

The method of the one-LP page (Algorithm 1 of [A] and [H]), started at $0$. An LP counts as solved when $\|(x,s)-(x^\star,s^\star)\|_2\le 10^{-4}$, as in the experiments of [A]. A run stops after $\min\{10^6,\max\{10^5,\ 4\cdot10^9/(mn)\}\}$ iterations; such LPs are hollow dots.

What the papers prove

• [H] With probability at least $1-\delta$, rPDHG finds the optimal basis within $\widetilde O(n^{2.5}m^{0.5}/\delta)$ iterations ($\widetilde O(n^{2.5}/\delta)$ for Gaussian $A$), and then an $\varepsilon$-optimal solution within $O\big(\frac{\sqrt{nm}}{\delta}\ln\frac1\varepsilon\big)$ more; this holds for sub-Gaussian $A$ with $n/(n-m+1)$ bounded and $\delta$ not exponentially small. The factor $1/\delta$ leaves room for a few slow LPs.
• [A] With a unique optimum, rPDHG needs at most $O\big(\kappa\Phi\ln(\kappa\Phi\|w^\star\|/\varepsilon)\big)$ iterations, where $\kappa$ is the condition number of $A$ and $\Phi=(\|x^\star\|_1+\|s^\star\|_1)\cdot\max\Big\{\max_j \frac{\sqrt{\|T_{:,j}\|^2+1}}{s^\star_{N_j}},\ \max_i \frac{\sqrt{\|T_{i,:}\|^2+1}}{x^\star_{B_i}}\Big\}$ with $T=B^{-1}N$.

Both are $O(\cdot)$ bounds; the dashed line in the chart has only their slope.

Sources

• [A] Z. Xiong. Accessible complexity bounds for restarted PDHG on linear programs with a unique optimizer. Mathematics of Operations Research, 2026. arXiv:2410.04043
• [H] Z. Xiong. High-probability polynomial-time complexity of restarted PDHG for linear programming. Mathematics of Operations Research, forthcoming. arXiv:2501.00728

Self-tests

Run self-tests