U-Examples: A Unified Family of Worst-Case Instances for Optimization Algorithms
Abstract
Worst-case instances show where optimization algorithms fail: the Klee-Minty cube for the simplex method, ill-conditioned and rippled bowls for gradient descent, degenerate minima for Newton's method, redundant Klee-Minty cubes for interior-point methods, unprunable trees for branch-and-bound, deceptive landscapes for metaheuristics, and degenerate cycling for active-set methods. These constructions were developed over seventy years in separate literatures, each with its own tools. This survey reviews them together. We trace the history of rule-specific worst cases across seven representative algorithm classes and organize them with one reading: in each, the optimum lies near the start, yet the algorithm's own update rule is misdirected onto a long trajectory or, at the boundary, into a non-terminating loop. We call such an instance a U-Example; the letter U stands both for the unification and for the U-shaped bowls around which descent methods are made to crawl. A common framework treats every algorithm as a rule on a state space with a progress potential, so that one definition of misdirection, and of the resulting blow-up in cost, covers pivoting, descent, interior-point, tree-search, and population methods. Each member is drawn in a common visual grammar and quantified in general dimension n. The blow-up is independent of the dimension for the two descent members and exponential in it for four search members, with degenerate cycling as a breakdown. We connect the constructions to neighbouring theories (oracle complexity, performance estimation, smoothed analysis, and the complexity of local search), each of which asks a different question of the same instances. We then map each worst case to the remedy that defeats it, examine how robust the instances are, and close with open challenges, in particular whether a worst case can be predicted from the update rule alone.
Related
- A family of spectral conjugate gradient algorithms derived by least-squares approximations based on a modified quasi--Newton update with application to a revised robust binary classification model
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- A unified family of multiblock ADMM schemes by means of graph splitting
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- Parallel Optimization: Theory, Algorithms, and Applications,
BibTeX
@misc{hosseini2026uexamples,
title = {{U-Examples: A Unified Family of Worst-Case Instances for Optimization Algorithms}},
author = {Eghbal Hosseini},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27909},
eprint = {2610.27909},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27909},
}
RIS
TY - UNPB
TI - U-Examples: A Unified Family of Worst-Case Instances for Optimization Algorithms
AU - Eghbal Hosseini
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.27909
UR - https://arxiv.org/abs/2610.27909
AB - Worst-case instances show where optimization algorithms fail: the Klee-Minty cube for the simplex method, ill-conditioned and rippled bowls for gradient descent, degenerate minima for Newton's method, redundant Klee-Minty cubes for interior-point methods, unprunable trees for branch-and-bound, deceptive landscapes for metaheuristics, and degenerate cycling for active-set methods. These constructions were developed over seventy years in separate literatures, each with its own tools. This survey reviews them together. We trace the history of rule-specific worst cases across seven representative algorithm classes and organize them with one reading: in each, the optimum lies near the start, yet the algorithm's own update rule is misdirected onto a long trajectory or, at the boundary, into a non-terminating loop. We call such an instance a U-Example; the letter U stands both for the unification and for the U-shaped bowls around which descent methods are made to crawl. A common framework treats every algorithm as a rule on a state space with a progress potential, so that one definition of misdirection, and of the resulting blow-up in cost, covers pivoting, descent, interior-point, tree-search, and population methods. Each member is drawn in a common visual grammar and quantified in general dimension n. The blow-up is independent of the dimension for the two descent members and exponential in it for four search members, with degenerate cycling as a breakdown. We connect the constructions to neighbouring theories (oracle complexity, performance estimation, smoothed analysis, and the complexity of local search), each of which asks a different question of the same instances. We then map each worst case to the remedy that defeats it, examine how robust the instances are, and close with open challenges, in particular whether a worst case can be predicted from the update rule alone.
ER -