Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy

arXiv:2609.00471v1 Announce Type: cross Abstract: This paper introduces a structural taxonomy for constrained non-convex optimization based on the signature of Lagrange multipliers at KKT stationary points. Leveraging a unified game-theoretic interpretation of eight classical algorithm families--including block coordinate descent, ADMM, generalized Benders decomposition, successive convex approximation, interior-point methods, mirror descent, Frank-Wolfe, and Riemannian gradient descent--we show that the normalized multiplier vector carries an algorithm-independent structural fingerprint. Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid. We establish four structural theorems characterizing the partition: invariance under natural KKT symmetries, local stability under data perturbation with explicit Lipschitz margins from Robinson's strong regularity, codimension-one regime transitions, and the topological identification of the Hybrid regime as the Lebesgue-null boundary of the core regimes. A linear-time classifier is proposed with provable guarantees on correctness, iteration stabilization, sample complexity, and online tracking under data drift. Numerical experiments on 104 mixed-integer nonlinear programs and a downlink beamforming instance validate the theoretical predictions. The framework provides a foundational tool for regime-aware algorithm design and robustness analysis in non-convex optimization.

Abstract:This paper introduces a structural taxonomy for constrained non-convex optimization based on the signature of Lagrange multipliers at KKT stationary points. Leveraging a unified game-theoretic interpretation of eight classical algorithm families--including block coordinate descent, ADMM, generalized Benders decomposition, successive convex approximation, interior-point methods, mirror descent, Frank-Wolfe, and Riemannian gradient descent--we show that the normalized multiplier vector carries an algorithm-independent structural fingerprint. Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid. We establish four structural theorems characterizing the partition: invariance under natural KKT symmetries, local stability under data perturbation with explicit Lipschitz margins from Robinson's strong regularity, codimension-one regime transitions, and the topological identification of the Hybrid regime as the Lebesgue-null boundary of the core regimes. A linear-time classifier is proposed with provable guarantees on correctness, iteration stabilization, sample complexity, and online tracking under data drift. Numerical experiments on 104 mixed-integer nonlinear programs and a downlink beamforming instance validate the theoretical predictions. The framework provides a foundational tool for regime-aware algorithm design and robustness analysis in non-convex optimization.

Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Signal Processing (eess.SP)

arXiv:2609.00471 [math.OC]

(or arXiv:2609.00471v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2609.00471 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy

Subiecte conexe