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

arXiv: https://arxiv.org/abs/2609.00471 · HTML: https://mlsanity.com/paper/2609.00471/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 59 references that are in the map.
- First posted on arXiv 31 Aug 2026.

## Builds on (most cited first, 6 of 6)

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems](https://mlsanity.com/paper/1410.1390/) (2014)
- [Global rates of convergence for nonconvex optimization on manifolds](https://mlsanity.com/paper/1605.08101/) (2016)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications](https://mlsanity.com/paper/1601.04059/) (2016)
- [Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems](https://mlsanity.com/paper/1302.0756/) (2013)

## Abstract (arXiv)

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.