On the exponential circuit imbalance of the Ben-Tal Nemirovski approximation

Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\bar{\chi}_A^*$. Their work builds on Vavasis and Ye’s (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\bar{\chi}_A$. The optimal condition measure $\bar{\chi}_A^*$ is defined as the minimum $\bar{\chi}_{AD}$ achievable over all positive diagonal column rescalings $D$. Dadush et al.\ (2024) also introduced the optimal circuit imbalance measure $\kappa_W^*$, which serves as a lower bound for $\bar{\chi}^*_A$.

Instances with artificially large optimal circuit imbalance measures $\kappa_W^*$ can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure $\kappa_W^*$ grows exponentially in the number of approximation steps. Since $\kappa_W^*$ lower bounds $\bar{\chi}_A^*$, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.

Article

Download

View PDF