Why is this LP hard?

Created by Zikai Xiong · Based on Xiong, arXiv:2410.04043

Restarted PDHG (rPDHG) is a first-order method for linear programs. Here it solves a tiny LP (4 variables, 2 constraints) and its dual at the same time. Start with the three steps below.

The LP

min c^⊤x s.t. Ax = b, x ≥ 0

Angle θ_p to the nearest tie –

Its dual

max b^⊤y s.t. A^⊤y ≤ c

Angle θ_d to the nearest tie –

Speed 1×

Iterations of rPDHG to reach ε = 10⁻⁶

–

What makes it hard: Φ

Φ = min{ , } = –

θ_p and θ_d are the angles marked in the two pictures (here ‖c‖ = ‖b‖ = 1). The iteration bound of [A] grows with Φ. Hover over a term for its meaning.

Every direction of the arrows

iterationsΦexact tie

After step 3, these charts show the iterations for every direction of each arrow.

Convergence of this run

errorrestart

The error of rPDHG’s average iterate; ticks mark restarts. Near a tie, each restart cycle takes longer.

The LP, its dual and the two pictures

The LP is $\min\, c^\top x$ subject to $Ax=b,\ x\ge 0$ with $A\in\mathbb{R}^{2\times 4}$; its dual is $\max\, b^\top y$ subject to $A^\top y+s=c,\ s\ge 0$.

Take a $4\times4$ orthogonal matrix $Q=[U\ W]$ with rows $(u_j^\top, w_j^\top)$, and let $A=W^\top$ and $c=U\gamma$. Then $AA^\top=I$ (so $\kappa=1$) and $Ac=0$, as [A] assumes. Here $\|c\|=\|b\|=1$.

The LP’s picture: $x=Wb+Uv$ with $v\in\mathbb{R}^2$. Edge $j$ is where $x_j=w_j^\top b+u_j^\top v=0$, and $c^\top x=\gamma^\top v$. The path shows $U^\top x$ for rPDHG’s iterates $x$, which are generally not on the plane $Ax=b$.
The dual’s picture: $y$ itself. Edge $j$ is where $s_j=u_j^\top\gamma-w_j^\top y=0$. The path shows rPDHG’s iterates $y$.

Both pictures are exact, with true distances and angles. Changing $c$ moves the dual’s edges, and changing $b$ moves the LP’s edges, so a tie in one picture is a degenerate vertex in the other. The LP is feasible only when $b$ lies in the cone of the columns of $A$, marked by the arc on the dial of $b$.

rPDHG (Algorithm 1 of [A])

Input: $z^{0,0}=(0,0)$, $\tau=\frac{1}{2\kappa}$, $\sigma=\frac{1}{2\lambda_{\max}\lambda_{\min}}$, $\beta=1/e$.

repeat (outer loop $\ell=0,1,\dots$)

repeat (inner loop $k=0,1,\dots$)

$x^{+}=\max\{0,\,x-\tau(c-A^\top y)\}$, $\ y^{+}=y+\sigma\,(b-A(2x^{+}-x))$

$\bar z^{\ell,k+1}=$ average of $z^{\ell,1},\dots,z^{\ell,k+1}$

until the $\beta$-restart condition holds

restart: $z^{\ell+1,0}\leftarrow \bar z^{\ell,k}$

until the average iterate is $\varepsilon$-optimal

Restart when the normalized duality gap of the average has dropped by the factor $\beta$ since the last restart. Stop when the average iterate has primal residual, dual infeasibility and duality gap all at most $\varepsilon=10^{-6}$.

The condition number Φ of [A]

With the optimal basis $B$, the other indices $N$ and $T=B^{-1}N$:

$\Phi=(\|x^\star\|_1+\|s^\star\|_1)/\min\{\zeta_p,\zeta_d\}$, where $\zeta_p=\min_j s^\star_{N_j}/\sqrt{\|T_{:,j}\|^2+1}$ is the smallest $\|\Delta c\|$ that changes the optimal basis, and $\zeta_d=\min_i x^\star_{B_i}/\sqrt{\|T_{i,:}\|^2+1}$ is the smallest $\|\Delta b\|_{(AA^\top)^{-1}}$ that does.
In the two pictures, $\zeta_p=\|c\|\sin\theta_p$ and $\zeta_d=\|b\|\sin\theta_d$, where $\theta_p$ and $\theta_d$ are the marked angles between the level line and the nearest edge at $x^\star$ and at $y^\star$.
As $\theta_p\to0$, the reduced cost $s^\star_k$ of a nonbasic variable tends to $0$, so edge $s_k$ passes closer and closer to $y^\star$. As $\theta_d\to0$, a basic variable $x^\star_l$ tends to $0$, so edge $x_l$ passes closer and closer to $x^\star$.

What [A] proves

With $Ac=0$, a unique optimum and the step sizes above, rPDHG reaches $\varepsilon$-optimality within $O\big(\kappa\Phi\ln(\kappa\Phi\|w^\star\|/\varepsilon)\big)$ iterations, where $w^\star=(x^\star,s^\star)$. This is an $O(\cdot)$ bound: the charts draw $\Phi$ next to the iteration counts without any fitted constant, and the page never treats it as a prediction of exact counts.

Source

[A] Z. Xiong. Accessible complexity bounds for restarted PDHG on linear programs with a unique optimizer. Mathematics of Operations Research, 2026. arXiv:2410.04043