Newest papers

U-Examples: A Unified Family of Worst-Case Instances for Optimization Algorithms

Eghbal Hosseini · 2026 · arXiv

DOI: 10.48550/arXiv.2610.27909 · open-access PDF

Vietnamese

Các trường hợp tồi tệ nhất cho thấy những nơi mà các thuật toán tối ưu hóa thất bại: khối Klee-Minty cho phương pháp đơn giản, bát tồi tệ và rách cho sự xuống dốc, tối thiểu thoái hóa cho phương pháp Newton, khối Klee-Minty dư thừa cho các phương pháp điểm bên trong, cây không thể rách cho chi nhánh và ràng buộc, cảnh quan lừa đảo cho metaheuristics, và xe đạp thoái hóa cho các phương pháp tích cực. Những cấu trúc này đã được phát triển trong hơn bảy mươi năm trong các tài liệu riêng biệt, mỗi với công cụ riêng của nó. Cuộc khảo sát này xem xét chúng cùng nhau. Chúng tôi theo dõi lịch sử các trường hợp tồi tệ nhất cụ thể cho các quy tắc trên bảy đại diện

Machine translation (Meta M2M100); the English original follows.

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

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange