Goldfarb-Idnani Revisited:Invariants, Certificates, and the Limits of Guessing
Abstract
The dual active-set method of Goldfarb and Idnani solves the strictly convex quadratic program by adding and dropping one constraint at a time, requiring no phase one. Primal--dual active set and block principal pivoting skip the walk altogether: they guess an entire active set at once and repair it from returning signs. For bound constraints the guess is safe. The system solved on a candidate set is a principal submatrix of G−1, positive definite regardless of the guess; this P-matrix property guarantees finite termination. For C⊤ x ≥ b that hypothesis fails, which is our central focus. The working-set system is C𝒜⊤ G−1 C𝒜, positive definite only when C𝒜 has full column rank, a property of the guess, not the data. The P-matrix property is lost and the structural obstruction invalidates the guarantee. Strict convexity keeps the method usable: KKT conditions make candidate sets certified rather than trusted. Over 600 random instances across four constraint families this failure never occurs. However, duplicating columns of C raises failure rates to 93\%, dropping certified fraction from 100\% to zero. On real long-only portfolio data, the active set reaches 442 of 494 + 1 constraints.
Related
- Strong failures of club guessing at the successor of a regular cardinal
- Limit Theorems for the Complete Feedback Card Guessing Game
- Optimal no-feedback card guessing after a fixed number of riffle shuffles
- An upper bound on the proper hat guessing number of graphs
- The Lovász Local Lemma Is Sharp for the Hat Guessing Number
BibTeX
@misc{schmelzer2026goldfarbidnani,
title = {{Goldfarb-Idnani Revisited:Invariants, Certificates, and the Limits of Guessing}},
author = {Thomas Schmelzer and Martin Stoll},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30933},
eprint = {2608.30933},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30933},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Goldfarb-Idnani Revisited:Invariants, Certificates, and the Limits of Guessing
AU - Thomas Schmelzer
AU - Martin Stoll
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.30933
UR - https://arxiv.org/abs/2608.30933
AB - The dual active-set method of Goldfarb and Idnani solves the strictly convex quadratic program by adding and dropping one constraint at a time, requiring no phase one. Primal--dual active set and block principal pivoting skip the walk altogether: they guess an entire active set at once and repair it from returning signs. For bound constraints the guess is safe. The system solved on a candidate set is a principal submatrix of G^−1, positive definite regardless of the guess; this P-matrix property guarantees finite termination. For C^⊤ x ≥ b that hypothesis fails, which is our central focus. The working-set system is C_𝒜^⊤ G^−1 C_𝒜, positive definite only when C_𝒜 has full column rank, a property of the guess, not the data. The P-matrix property is lost and the structural obstruction invalidates the guarantee. Strict convexity keeps the method usable: KKT conditions make candidate sets certified rather than trusted. Over 600 random instances across four constraint families this failure never occurs. However, duplicating columns of C raises failure rates to 93\%, dropping certified fraction from 100\% to zero. On real long-only portfolio data, the active set reaches 442 of 494 + 1 constraints.
ER -