Paper deep dive
Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy
Seyed Mohsen Kazemi, Ali Movaghar, Shaahin hessabi
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 9/2/2026, 4:51:04 AM
Summary
This paper introduces a structural taxonomy for constrained non-convex optimization based on the signature of Lagrange multipliers at Karush-Kuhn-Tucker (KKT) stationary points. By leveraging a unified game-theoretic interpretation of eight classical algorithm families (including ADMM, Frank-Wolfe, and Interior-Point Methods), the authors demonstrate that the normalized multiplier vector serves as 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. The paper establishes four structural theorems regarding invariance, stability, transitions, and topology, and proposes a linear-time classifier with provable guarantees for correctness, iteration stabilization, sample complexity, and online tracking.
Entities (12)
Relation Signals (12)
Lagrange Multipliers → defines → Operational Regimes
confidence 95% · This paper introduces a structural taxonomy for constrained non-convex optimization based on the signature of Lagrange multipliers at KKT stationary points.
Operational Regimes → includes → Unconstrained Regime
confidence 95% · Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid.
Operational Regimes → includes → Resource-Limited Regime
confidence 95% · Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid.
Operational Regimes → includes → Strongly-Coupled Regime
confidence 95% · Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid.
Operational Regimes → includes → Hybrid Regime
confidence 95% · Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid.
Operational Regimes → includes → Saturation Regime
confidence 95% · Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid.
Linear-Time Classifier → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2609.00471v1
- Canonical: https://arxiv.org/abs/2609.00471v1
Trouble viewing inline? Open PDF directly →
Full Text
136,286 characters extracted from source content.
Expand or collapse full text
Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy Seyed Mohsen Kazemi Email: smohsen.kazemi84@sharif.edu Affiliation: Department of Computer Engineering, Sharif University of Technology, Azadi, Tehran, 11365-9517, Tehran, Iran Ali Movaghar Email: movaghar@sharif.edu Affiliation: Department of Computer Engineering, Sharif University of Technology, Azadi, Tehran, 11365-9517, Tehran, Iran Shaahin Hessabi Email: hessabi@sharif.edu Affiliation: Department of Computer Engineering, Sharif University of Technology, Azadi, Tehran, 11365-9517, Tehran, Iran 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. keywordsconstrained nonlinear optimization, KKT stationarity, Lagrange multipliers, operational regimes, sensitivity analysis, game-theoretic optimization, decomposition methods, Stackelberg games, potential games, sample complexity, online tracking, mixed-integer nonlinear programming, wireless resource allocation. 1 Introduction The behavior of an optimization algorithm at convergence is conventionally characterized by its rate of convergence and the residual Karush–Kuhn–Tucker (KKT) optimality conditions. This view yields clean theoretical statements but obscures a complementary structural question: what does the converged solution tell us about the geometry of the underlying problem? The KKT conditions deliver, alongside a primal solution x⋆x , a vector of Lagrange multipliers λ⋆λ whose entries quantify the sensitivity of the optimal value to perturbations of each constraint. Their support, magnitudes, and concentration encode which constraints are binding, how tightly, and how the active geometry is organized. This dual signature is more than an algorithmic byproduct: it is a structural fingerprint of the solution that ought to inform algorithm selection, robustness analysis, and adaptive deployment. Yet the standard analytic toolkit—convergence rates, regret bounds, iteration complexity—rarely engages with this structure directly. Algorithm selection in practice remains largely empirical, robustness under data uncertainty is typically established case by case, and the qualitative ”phase-like” convergence patterns reported across many algorithm families lack a method-agnostic explanation. A second observation suggests how to make this structure operational. Despite their surface differences, the eight algorithm families we consider in this paper all produce, at convergence, a KKT triple of some (sub)problem of an underlying parametric nonlinear program. Block coordinate descent (BCD) performs best-response sweeps in an exact potential game; generalized Benders decomposition (GBD) solves a Stackelberg game between discrete and continuous variables; the alternating direction method of multipliers (ADMM) implements consensus-seeking saddle-point dynamics; successive convex approximation (SCA) realizes hierarchical approximation games; interior-point methods (IPM) track a parametric central path of perturbed equilibria; mirror descent executes regularized no-regret learning in repeated online games; Frank–Wolfe plays linear-oracle no-regret dynamics; and Riemannian gradient descent discretizes equilibrium trajectories of differential games on smooth manifolds. Each correspondence is classical on its own; what we extract from their juxtaposition is that the KKT triple at any fixed point is, under standard regularity, unique, and therefore independent of which method produced it. This independence reframes the eight equilibrium correspondences as eight routes to a single structural object: the multiplier vector λ⋆λ . Once that object is identified, the structural analysis that the rate-centric view cannot deliver becomes available—provided we extract from λ⋆λ a classification that is both intrinsic to the solution and stable under the noise that arises in practice. 1.1 Contributions We construct such a classification algorithm from four scale-free statistics of λ⋆λ : the total dual mass L, the top-k concentration Σk _k, the δ-support fraction σδ _δ, and the second-largest normalized entry τ. These features induce a partition of the dual space ℝ+mR^m_+ into five operational regimes—Unconstrained (ℛuncR_unc), Resource-Limited (ℛresR_res), Saturation (ℛsatR_sat), Strongly-Coupled (ℛcoupR_coup), and Hybrid (ℛhybR_hyb). Each core regime encodes a qualitatively distinct active-constraint pattern, and the Hybrid regime is shown to arise as the topological boundary between the other four. The contributions of this paper are the following. 1. A unified game-theoretic template (Section 3). We catalog eight classical algorithm families under a single fixed-point template (Table 1) and show that each produces KKT triples of an associated subproblem, with the multiplier vector serving as a method-independent structural primitive. The individual equilibrium correspondences are classical; their juxtaposition under one template, with the multiplier vector singled out as the common structural output, is the contribution. 2. A scale-free regime taxonomy (Section 4). A partition of ℝ+mR^m_+ into five regimes is defined via four shape features of the Lagrange multipliers, with the Hybrid regime characterized as a boundary set rather than a residual class. 3. Four structural theorems (Section 5). Theorem 3 establishes invariance of the classification under permutation, uniform rescaling, and C2C^2-diffeomorphism symmetries of the KKT system, yielding method-independence as a direct corollary. Theorem 5 establishes local constancy of the classification under perturbation of problem data, with explicit Lipschitz-style margins derived from Robinson’s strong regularity. Theorem 7 characterizes regime transitions as codimension-one events along data trajectories. Theorem 8 identifies the Hybrid regime as the Lebesgue-null topological boundary of the union of core regimes. 4. A linear-time regime classifier with operational guarantees (Section 6). The classifier (Algorithm 1) computes the regime label in (m)O(m) time and admits four guarantees: Theorem 11 (deterministic correctness under multiplier perturbation); Theorem 12 and Corollary 13 (method-specific iteration stabilization at rates logarithmic, linear, or quadratic in the inverse feature margin); Theorem 14 (sample complexity (ρr−2log(1/δ))O( _r^-2 (1/δ)) for finite-data deployments); Theorem 15 (online tracking under bounded drift up to a cubic-in-margin threshold). 5. Empirical validation (Section 7). Numerical experiments on five families of mixed-integer nonlinear programs, totalling 10410^4 instances, confirm each theoretical prediction in turn. A downlink beamforming instance illustrates the practical application of the taxonomy. The framework is designed to serve as a foundation for follow-up work, in particular for wireless resource-allocation problems whose constraint structure—power budgets, quality-of-service thresholds, inter-cell coupling—matches the regime taxonomy by construction. The sample-complexity and tracking guarantees of Section 6 provide the high-probability bounds that such follow-up papers require under channel-estimation noise and time-varying deployments, without re-derivation. Beyond wireless, the framework applies to power-systems optimization, optimal control under constraints, structured machine learning, and operations research more broadly. 1.2 Related Work The work presented here sits at the intersection of three lines of research: game-theoretic interpretations of optimization algorithms, structural analysis via Lagrange multipliers and active sets, and adaptive or hybrid optimization methods. We discuss each in turn and position our contributions against it. Game-theoretic interpretations of optimization sThe view of optimization algorithms as equilibrium-seeking processes has a long tradition. Block coordinate descent is equivalent to best-response dynamics in exact potential games when the objective serves as a potential function up to sign Beck and Tetruashvili (2013); Monderer and Shapley (1996); Tseng (2001); convergence in non-convex settings under the Kurdyka–Łojasiewicz property is developed in Attouch et al. (2013); Razaviyayn et al. (2013). Generalized Benders decomposition admits a hierarchical (Stackelberg) interpretation in which the master problem plays the role of the leader Geoffrion (1972); von Stackelberg (1934); Başar and Olsder (1999). ADMM realizes consensus-seeking primal-dual dynamics interpretable as best-response iterations on the augmented Lagrangian, with the dual variable acting as a price coordinate Boyd et al. (2011); He and Yuan (2012); Eckstein and Bertsekas (1992). Successive convex approximation corresponds to hierarchical approximation games between a surrogate designer and an optimizer Razaviyayn et al. (2013); Scutari et al. (2014); Scutari et al. (2017), with majorization-minimization as a prominent special case Sun et al. (2017). Mirror descent and Frank–Wolfe are intimately connected to no-regret learning and online convex optimization: mirror descent implements regularized best responses with Bregman divergences Nemirovsky and Yudin (1983); Beck and Teboulle (2003), and Frank–Wolfe corresponds to linear minimization oracles in repeated zero-sum games Jaggi (2013); Lacoste-Julien and Jaggi (2015); Hazan (2008). Riemannian optimization discretizes gradient flows on manifolds and admits a continuous-time differential-game reading Absil et al. (2008); Boumal (2023); Başar and Olsder (1999). Interior-point methods track the central path, a parametric family of perturbed KKT equilibria as the barrier parameter tends to zero Nesterov and Nemirovski (1994); Wright (1997); Forsgren et al. (2002). While each correspondence above is established in prior work, the present paper is, to our knowledge, the first to assemble them under a single equilibrium-seeking template and, more importantly, to extract a common structural signature from the resulting multipliers. Structural and multiplier-based analysis The importance of the active-set structure and the multiplier patterns is classical in sensitivity analysis Sun et al. (2017); Hazan (2008), parametric optimization Sun et al. (2017), and active-set methods Hazan (2008). Multiplier trajectories have been used to diagnose constraint tightness in constrained learning and robust optimization. Interior-point methods explicitly follow a path of perturbed complementarity conditions Monderer and Shapley (1996); Lacoste-Julien and Jaggi (2015); Boucheron et al. (2013). The present paper builds on these ideas by elevating multiplier patterns from a diagnostic tool to a quantitative, method-independent taxonomy with formal invariance, stability, transition, and topological theorems, accompanied by a linear-time classifier with explicit correctness, iteration-complexity, sample-complexity, and drift-tracking guarantees. Adaptive, hybrid, and regime-aware methods Adaptive strategies in optimization have been explored in several contexts, including dynamic penalty tuning in ADMM Bonnans and Shapiro (2000), adaptive surrogate selection in SCA, and switching between first- and second-order methods. Closest in spirit to the present work are structural-adaptation approaches in decomposition methods and hybrid solvers that switch based on constraint activity. The contribution we add is a unified cross-method taxonomy grounded in multiplier geometry, supported by formal structural theorems and explicit statistical guarantees (iteration complexity, sample complexity, drift tracking), which permits regime-aware design to be carried out with provable correctness rather than as a heuristic. 1.3 Positioning The novelty of this paper lies not in any individual game-theoretic correspondence—each is classical—but in three things taken together. First, the identification of the multiplier vector λ⋆λ as a method-independent structural object common to eight major algorithm families. Second, a precise taxonomy of λ⋆λ supported by four structural theorems (invariance, stability, transition, boundary). Third, a linear-time classifier whose four guarantees (correctness, iteration, sample, drift) are quantitatively tight and designed to serve as cite-able primitives in downstream work. To our knowledge no prior work links the game-theoretic reading of optimization algorithms to a multiplier-driven structural taxonomy in this manner, and the resulting framework offers both new theoretical insights and practical tools for regime-aware, robust, and explainable optimization. 1.4 Organization Section 2 fixes notation, states the parametric problem class, and recalls the equilibrium concepts used throughout. Section 3 develops the unified game-theoretic template across the eight algorithm families. Section 4 introduces the regime taxonomy and Section 5 establishes its four structural theorems. Section 6 presents the regime classifier and its guarantees. Section 7 reports the numerical validation. Section 8 discusses implications, limitations, and directions for future work, and Section 9 concludes. 2 Preliminaries This section fixes the notation used throughout the paper, states the parametric problem class on which the structural theory of Sections 4–6 is built, and recalls the equilibrium concepts needed for the game-theoretic reinterpretations of Section 3. 2.1 Notation We write ℝnR^n for Euclidean space, ℝ+nR^n_+ for its nonnegative orthant, and Δm−1:=v∈ℝ+m:∑ivi=1 ^m-1:=\v ^m_+: _iv_i=1\ for the standard simplex. The Euclidean norm is ∥⋅∥2\|·\|_2 and the ℓ1 _1 and ℓ∞ _∞ norms are ∥⋅∥1\|·\|_1, ∥⋅∥∞\|·\|_∞. For λ∈ℝ+mλ ^m_+ with ‖λ‖1>0\|λ\|_1>0, we write λ¯:=λ/‖λ‖1 λ:=λ/\|λ\|_1 for the normalized multiplier vector, and λ¯(1)≥λ¯(2)≥⋯≥λ¯(m) λ_(1)≥ λ_(2)≥·s≥ λ_(m) for its sorted entries. We write CkC^k for the space of k-times continuously differentiable functions; ∇f∇ f and ∇2f∇^2f for the gradient and Hessian of a scalar function f; and DϕDφ for the Jacobian of a map ϕφ. The support of a vector is supp(λ):=i:λi≠0supp(λ):=\i: _i≠ 0\. We use ⋅1\·\ for the indicator function and |⋅||·| for the cardinality of a finite set. 2.2 Problem Class and KKT Conditions We work with parametric mixed-integer nonlinear programs (MINLPs) minx,y _x,y f(x,y,ω) f(x,y;ω) (1) s.t. .t. gi(x,y;ω)≤0,i=1,…,m, g_i(x,y;ω)≤ 0, i=1,…,m, hj(x,y;ω)=0,j=1,…,p, h_j(x,y;ω)=0, j=1,…,p, x∈ℝnc,y∈⊆0,1nd, x ^n_c, y \0,1\^n_d, where ω∈Ω⊂ℝdω∈ ^d collects problem data (coefficients, budgets, channel realizations, and so on) and the functions f,gi,hjf,g_i,h_j are at least C2C^2 jointly in (x,ω)(x,ω) for each fixed y. We omit the dependence on ω when no confusion arises. The mixed-integer form (1) is needed for the discussion of generalized Benders decomposition (Section 3.2) and the experimental families of Section 7; the continuous specialization nd=0n_d=0 is used throughout Sections 4–6, and we denote the continuous problem class minx∈ℝn _x ^n f(x,ω) f(x;ω) (2) s.t. .t. gi(x;ω)≤0,i=1,…,m, g_i(x;ω)≤ 0, i=1,…,m, hj(x;ω)=0,j=1,…,p. h_j(x;ω)=0, j=1,…,p. For a feasible x⋆x , the Lagrangian of (2) is (x,λ,μ,ω)=f(x,ω)+∑i=1mλigi(x,ω)+∑j=1pμjhj(x,ω), L(x,λ,μ;ω)=f(x;ω)+ _i=1^m _ig_i(x;ω)+ _j=1^p _jh_j(x;ω), (3) and a KKT triple (x⋆,λ⋆,μ⋆)∈ℝn×ℝ+m×ℝp(x ,λ ,μ ) ^n×R^m_+×R^p satisfies ∇x(x⋆,λ⋆,μ⋆) _x L(x ,λ ,μ ) =0, =0, (4a) gi(x⋆)≤0,λi⋆≥0,λi⋆gi(x⋆) g_i(x )≤ 0,\ λ _i≥ 0,\ λ _ig_i(x ) =0,∀i, =0, ∀ i, (4b) hj(x⋆) h_j(x ) =0,∀j. =0, ∀ j. (4c) The active set at x⋆x is (x⋆):=i:gi(x⋆)=0A(x ):=\i:g_i(x )=0\, and the complementarity condition (4b) implies supp(λ⋆)⊆(x⋆)supp(λ ) (x ). Throughout the paper we work under the following regularity assumption, stated here once for use in Sections 4–6. Assumption 1 (LICQ + SOSC). At the KKT triple (x⋆,λ⋆,μ⋆)(x ,λ ,μ ) of (2): (i) (LICQ) the gradients ∇gi(x⋆)i∈(x⋆)∪∇hj(x⋆)j=1p\∇ g_i(x )\_i (x )∪\∇ h_j(x )\_j=1^p are linearly independent; (i) (SOSC) for every nonzero d in the critical cone (x⋆):=d: (x ):= \d: ∇gi(x⋆)⊤d≤0∀i∈(x⋆), ∇ g_i(x ) d≤ 0\ ∀ i (x ), (5) ∇gi(x⋆)⊤d=0∀i∈supp(λ⋆), ∇ g_i(x ) d=0\ ∀ i (λ ), ∇hj(x⋆)⊤d=0∀j, ∇ h_j(x ) d=0\ ∀ j \, we have d⊤∇xx2(x⋆,λ⋆,μ⋆)d>0d _x^2 L(x ,λ ,μ )d>0. Under Assumption 1 the multipliers (λ⋆,μ⋆)(λ ,μ ) are unique and the KKT system is locally invertible Sun et al. (2017); Hazan (2008). When invoked, strict complementarity denotes the additional condition λi⋆>0λ _i>0 for every i∈(x⋆)i (x ); this is required only where indicated (specifically, in Theorems 5 and 7, which rely on Robinson’s strong regularity). 2.3 Equilibrium Concepts A game Γ=(ℐ,ii∈ℐ,uii∈ℐ) =(I,\S_i\_i ,\u_i\_i ) consists of a set of players ℐI, strategy sets iS_i, and utility functions ui:∏j∈ℐj→ℝu_i: _j S_j . We recall the equilibrium concepts used in Section 3. Definition 1 (Nash equilibrium Nash (1950); Nash (1951); Başar and Olsder (1999)). A strategy profile s⋆=(si⋆)i∈ℐs =(s _i)_i is a Nash equilibrium of Γ if no player can improve its utility by unilateral deviation: ui(si⋆,s−i⋆)≥ui(si,s−i⋆),∀si∈i,∀i∈ℐ,u_i(s _i,s _-i)≥ u_i(s_i,s _-i), ∀ s_i _i,\ ∀ i , where s−i⋆s _-i denotes the strategies of all players other than i. Definition 2 (Stackelberg equilibrium Vershynin (2018)). In a two-stage hierarchical game with leader strategy sL∈Ls_L _L and follower best response sF⋆(sL):=argmaxsF∈FuF(sL,sF)s_F (s_L):= _s_F _Fu_F(s_L,s_F), the Stackelberg equilibrium is the pair (sL⋆,sF⋆(sL⋆))(s_L ,s_F (s_L )) where sL⋆∈argmaxsL∈LuL(sL,sF⋆(sL))s_L ∈ _s_L _Lu_L (s_L,\,s_F (s_L) ). Definition 3 (Exact potential game Monderer and Shapley (1996)). A game Γ is an exact potential game if there exists a function Φ:∏i→ℝ : _iS_i such that for every player i and every si,si′∈is_i,s_i _i, ui(si,s−i)−ui(si′,s−i)=Φ(si,s−i)−Φ(si′,s−i).u_i(s_i,s_-i)-u_i(s_i ,s_-i)= (s_i,s_-i)- (s_i ,s_-i). Nash equilibria of an exact potential game coincide with critical points of Φ . The additional equilibrium notions arising in Section 3—saddle points of augmented Lagrangians (ADMM), no-regret and coarse correlated equilibria in repeated games (mirror descent, Frank–Wolfe), gradient-flow equilibria on manifolds (Riemannian descent), and parametric central-path equilibria (IPM)—are recalled in context with citations to the standard texts 3 Game-Theoretic Lens on Optimization Algorithms This section sets up the unified equilibrium viewpoint that underpins the regime taxonomy of Sections 4–5. We catalog six classical algorithmic families and recall, with attribution to the literature, the equilibrium concept each realizes. Our purpose is neither to survey these methods in depth nor to claim novelty for the individual correspondences—each has been established in prior work—but to make precise the common structural feature they share: at any fixed point, the algorithm has computed a KKT triple of a (sub)problem, and the resulting Lagrange multiplier vector carries an algorithm-agnostic signature of the solution’s structure. That signature is the object of study from Section 4 onward. Definition 4 (A Common Equilibrium-Seeking Template). Every algorithm considered in this paper admits a discrete-time fixed-point representation z(k+1)∈ℬ(z(k),ω),z^(k+1) (z^(k);ω ), (6) where z=(x,λ,μ)z=(x,λ,μ) collects primal and (possibly auxiliary) dual variables, ω∈Ωω∈ is the problem data, and ℬB is a method-specific best-response operator implementing one round of agent updates in an associated game Γ . A point z⋆z is a fixed point of (6) if and only if it is an equilibrium of Γ and a KKT triple of an associated (sub)problem of (2). The forward direction follows from the variational characterization of equilibria Facchinei and Pang (2003); the reverse follows from the KKT conditions (4) reinterpreted as the stationarity conditions of the relevant agent’s optimization. The mapping between algorithms and games is made concrete in Table 1. Table 1: Eight algorithm families viewed as equilibrium-seeking dynamics. Each row records the game type, equilibrium concept, fixed-point notion, and primary references for both the algorithm and its game-theoretic interpretation. All correspondences below are classical; see the cited sources for proofs. Method Game type Equilibrium concept Algorithmic fixed point Key references BCD exact potential Nash equilibrium block-coordinate stationary Tseng (2001); Beck and Tetruashvili (2013); Monderer and Shapley (1996); Attouch et al. (2013) GBD hierarchical (Stackelberg) Stackelberg equilibrium KKT of sub-problem+master optimality Geoffrion (1972); von Stackelberg (1934); Bonnans and Shapiro (2000) ADMM two-player consensus saddle/Nashof augmented Lagrangian primal-dual stationary Boyd et al. (2011); Eckstein and Bertsekas (1992); Hong et al. (2016) SCA hierarchical approximation Stackelberg-like (leader = surrogate) KKT of original problem Razaviyayn et al. (2013); Scutari et al. (2014); Scutari et al. (2017) IPM parametric (central path) perturbed KKT / barrier equilibrium μ→0+μ→ 0^+ limit on central path Nesterov and Nemirovski (1994); Wright (1997); Forsgren et al. (2002) Mirror Descent repeated online no-regret/coarse correlated ergodic average optimal Nemirovsky and Yudin (1983); Beck and Teboulle (2003); Bubeck (2015); Cesa-Bianchi and Lugosi (2006) Frank–Wolfe repeated zero-sum (LMO) no-regret minimax over linear losses stationary VI on convex hull Jaggi (2013); Lacoste-Julien and Jaggi (2015); Hazan (2008) Riemannian Descent continuous-time differential gradient-flow equilibrium Riemannian stationary Absil et al. (2008); Boumal (2023); Boumal et al. (2019) 3.1 Block Coordinate Descent For f:X→ℝf:X with X=X1×⋯×XMX=X_1×·s× X_M, the cyclic BCD iteration xi(k+1)∈argminxi∈Xif(x1(k+1),…,xi−1(k+1),xi,xi+1(k),…,xM(k))x_i^(k+1)∈ _x_i∈ X_if (x_1^(k+1),…,x_i-1^(k+1),x_i,x_i+1^(k),…,x_M^(k) ) (7) is the canonical best-response dynamics in the game with players i=1,…,Mi=1,…,M, strategy spaces XiX_i, and utilities ui(x)=−f(x)u_i(x)=-f(x). Because ∂iui−∂iui′=∂i(Φ−Φ′) _iu_i- _iu_i = _i( - ) holds trivially with Φ=−f =-f, the game is an exact potential game in the sense of Monderer and Shapley (1996), and every BCD limit point is a Nash equilibrium. Convergence to a first-order stationary point of f under continuous differentiability and Kurdyka–Łojasiewicz regularity is established in Tseng (2001); Beck and Tetruashvili (2013); Attouch et al. (2013). For the purposes of this paper, the relevant fact is that BCD terminates at a KKT point of each block subproblem; the per-block multiplier vector enters our taxonomy in Section 4. 3.2 Generalized Benders Decomposition For the MINLP (2) with mixed continuous–discrete variables (x,y)(x,y), GBD Geoffrion (1972) alternates between Q(y):=minxf(x,y):g(x,y)≤0,h(x,y)=0Q(y):= _x \f(x,y):g(x,y)≤ 0,\,h(x,y)=0 \ (8) and a master problem miny∈YQ^(y) _y∈ Y Q(y), where Q Q is the piecewise-linear outer approximation of Q assembled from optimality and feasibility cuts generated by dual solutions of (8). The hierarchical structure is exactly that of a Stackelberg game von Stackelberg (1934); Başar and Olsder (1999): the leader (discrete variables) commits to y anticipating the follower’s rational response x⋆(y)=argminxQ(y)x (y)= _xQ(y). Under Slater’s condition or LICQ on the follower subproblem and convexity in x for fixed y, GBD terminates finitely at a Stackelberg equilibrium that is simultaneously a KKT point of (8); see Geoffrion (1972); Bonnans and Shapiro (2000) for the underlying value-function sensitivity. The follower multipliers serve as the dual signature for the regime taxonomy. 3.3 Alternating Direction Method of Multipliers For the separable problem minx,zf(x)+g(z)s.t.Ax+Bz=c, _x,z\,f(x)+g(z) .t. Ax+Bz=c, (9) the scaled-form ADMM Boyd et al. (2011) iterates x(k+1) x^(k+1) =argminxf(x)+ρ2‖Ax+Bz(k)−c+u(k)‖2, = _x\, \f(x)+ ρ2\|Ax+Bz^(k)-c+u^(k)\|^2 \, (10) z(k+1) z^(k+1) =argminzg(z)+ρ2‖Ax(k+1)+Bz−c+u(k)‖2, = _z\, \g(z)+ ρ2\|Ax^(k+1)+Bz-c+u^(k)\|^2 \, u(k+1) u^(k+1) =u(k)+Ax(k+1)+Bz(k+1)−c. =u^(k)+Ax^(k+1)+Bz^(k+1)-c. The x- and z-updates are best responses with respect to the augmented Lagrangian, and the u-update is a dual ascent step on the linearly constrained dual function. In the convex case, fixed points of (10) are saddle points of the augmented Lagrangian and hence Nash equilibria of the two-player consensus game with utilities u1(x,z,u)=−f(x)−ρ2‖Ax+Bz−c+u‖2u_1(x,z;u)=-f(x)- ρ2\|Ax+Bz-c+u\|^2 and u2u_2 defined symmetrically Eckstein and Bertsekas (1992); Boyd et al. (2011). In the nonconvex case under boundedness and sufficient penalty growth, ADMM converges to block-stationary points Hong et al. (2016). In either case the scaled dual u⋆u is a multiplier estimate for the consensus constraint and enters the classification map Ψ of Section 4. 3.4 Successive Convex Approximation SCA Razaviyayn et al. (2013); Scutari et al. (2014); Scutari et al. (2017) replaces a nonconvex problem minx∈Xf(x) _x∈ Xf(x) with a sequence of convex surrogates f~(⋅,x(k)) f(\,·\,;x^(k)) satisfying (i) convexity, (i) first-order consistency ∇f~(x(k),x(k))=∇f(x(k))∇ f(x^(k);x^(k))=∇ f(x^(k)), and (i) an upper-bounding condition f~(x,x(k))≥f(x) f(x;x^(k))≥ f(x). The iterate is x(k+1)∈argminx∈Xf~(x,x(k)).x^(k+1)∈ _x∈ X\, f(x;x^(k)). (11) Viewed as a hierarchical game, the leader (Approximator) commits to the surrogate f~(⋅,x(k)) f(\,·\,;x^(k)) and the follower (Optimizer) responds with the minimizer; the procedure is a Stackelberg-like dynamics whose fixed points are KKT points of the original problem Scutari et al. (2014). Under the surrogate conditions above, limit points are first-order stationary Razaviyayn et al. (2013); convergence rates under additional convexity or KL assumptions are documented in Scutari et al. (2017); Attouch et al. (2013). The multipliers of the original constraints—inherited at the fixed point via first-order consistency—are the regime-defining objects. 3.5 Interior-Point Methods For an inequality-constrained problem minxf(x) _xf(x) subject to gi(x)≤0g_i(x)≤ 0, i=1,…,mi=1,…,m, the logarithmic barrier formulation minxf(x)−μ∑i=1mlog(−gi(x)),μ>0, _x\,f(x)-μ _i=1^m (-g_i(x) ), μ>0, (12) defines a one-parameter family of unconstrained problems whose stationarity condition ∇f(x)+∑iμ−gi(x)∇gi(x)=0∇ f(x)+ _i μ-g_i(x)∇ g_i(x)=0 is equivalent, on setting λi:=μ/(−gi(x)) _i:=μ/(-g_i(x)), to the perturbed KKT system ∇f(x)+∑i=1mλi∇gi(x)=0,λigi(x)=−μ,λi,−gi(x)>0,∇ f(x)+ _i=1^m _i∇ g_i(x)=0, _ig_i(x)=-μ, _i,\,-g_i(x)>0, (13) which collapses to the standard KKT conditions (4) as μ→0+μ→ 0^+ Nesterov and Nemirovski (1994); Wright (1997). The solution set (x⋆(μ),λ⋆(μ)):μ>0\(x (μ),λ (μ)):μ>0\ is the central path; under LICQ and strict complementarity it is a smooth curve converging to a KKT triple of the original problem Forsgren et al. (2002); Nocedal and Wright (2006). Primal–dual interior-point methods apply Newton-type updates to (13) along a decreasing sequence μk→0+ _k→ 0^+. The game-theoretic interpretation is parametric: each μ defines a regularized game whose equilibrium z⋆(μ)z (μ) is the perturbed KKT point, and the algorithm computes a sequence of such equilibria along a continuous deformation of the game. The barrier term acts as a regularizer initially smoothing the feasible region and gradually withdrawn as μk↓0 _k 0. This parametric form of equilibrium tracking is the natural continuation analogue of the discrete fixed-point template (6): rather than iterating an operator ℬB to a single equilibrium, IPM follows a continuous family of equilibria parameterized by μ. The limit multiplier vector λ⋆=limk→∞λ⋆(μk)λ = _k→∞λ ( _k) is, by (13), an inequality multiplier of (2) and feeds into the regime taxonomy of Section 4 on the same footing as the multipliers produced by the discrete methods above. 3.6 Mirror Descent For a convex f on a convex domain X and a strictly convex mirror map ψ, the mirror descent update with step size η>0η>0 is x(k+1)=argminx∈X⟨∇f(x(k)),x⟩+1ηDψ(x,x(k)),x^(k+1)= _x∈ X\, \ ∇ f(x^(k)),x + 1ηD_ψ (x,x^(k) ) \, (14) where Dψ(x,y)=ψ(x)−ψ(y)−⟨∇ψ(y),x−y⟩D_ψ(x,y)=ψ(x)-ψ(y)- ∇ψ(y),x-y is the Bregman divergence Nemirovsky and Yudin (1983); Beck and Teboulle (2003). In the online convex optimization framework Cesa-Bianchi and Lugosi (2006); Bubeck (2015), (14) is a regularized best response to the linearized loss against an adaptive adversary. It achieves sublinear regret (T)O( T) (or (logT)O( T) under strong convexity), and time-average iterates converge to coarse correlated equilibria of the associated repeated game Cesa-Bianchi and Lugosi (2006). At a stationary fixed point of the offline problem, the first-order optimality of (14) reduces to a KKT condition on X, and the associated multipliers populate our taxonomy. 3.7 Frank–Wolfe / Conditional Gradient For a smooth convex f on a compact convex set X, the Frank–Wolfe iteration Jaggi (2013) uses a linear minimization oracle (LMO) over X: s(k) s^(k) ∈argmins∈X⟨∇f(x(k)),s⟩, ∈ _s∈ X\, ∇ f(x^(k)),\,s , (15) x(k+1) x^(k+1) =(1−γk)x(k)+γks(k), =(1- _k)\,x^(k)+ _k\,s^(k), with step size γk∈[0,1] _k∈[0,1]. Each step plays a one-shot zero-sum game against a linear-cost adversary that selects the current gradient ∇f(x(k))∇ f(x^(k)) as the loss vector; the cumulative dynamics realize a no-regret learning procedure over X achieving (1/k)O(1/k) convergence to the constrained minimum Jaggi (2013); Lacoste-Julien and Jaggi (2015). The link to online learning is made explicit in Hazan and Kale (2012); Chen et al. (2018), where Frank–Wolfe is identified with a follow-the-perturbed-leader procedure on the convex hull of X. At a fixed point of (15), x⋆=s⋆∈argmins∈X⟨∇f(x⋆),s⟩x =s ∈ _s∈ X ∇ f(x ),s , which is equivalent to the variational inequality ⟨∇f(x⋆),s−x⋆⟩≥0 ∇ f(x ),s-x ≥ 0 for all s∈Xs∈ X. Under LICQ on the constraints describing X, this VI is in turn equivalent to the KKT conditions (4) of the original problem Facchinei and Pang (2003). The dual certificate of the LMO at the limit point—namely, the multipliers of the binding constraints of X at x⋆x —is the multiplier vector populating the regime taxonomy. Compared to mirror descent, Frank–Wolfe trades a Bregman-regularized best response for a linear-oracle best response, but both inherit the no-regret game structure. 3.8 Riemannian Optimization Let (ℳ,g)(M,g) be a smooth Riemannian manifold and f:ℳ→ℝf:M smooth. The Riemannian gradient descent iteration x(k+1)=Retrx(k)(−ηgradf(x(k))),x^(k+1)=Retr_x^(k) (-η\,grad\,f(x^(k)) ), (16) with RetrRetr a first-order retraction Absil et al. (2008); Boumal (2023), discretizes the continuous-time gradient flow x˙(t)=−gradf(x(t)) x(t)=-grad\,f(x(t)), which we interpret as the equilibrium trajectory of a Stackelberg-type, continuous-time differential game between an Optimizer following the Riemannian gradient and an Environment that selects f and the metric Başar and Olsder (1999). Convergence to a Riemannian first-order stationary point under standard smoothness and retraction assumptions is established in Boumal et al. (2019); Absil et al. (2008). When ℳM is described intrinsically through equality constraints, the Lagrange multipliers of those constraints—inherited from any embedding—populate the regime taxonomy on the same footing as the multipliers of the methods above. 3.9 A Unified Equilibrium Statement We collect the eight correspondences above into a single statement. The proposition below summarizes individually classical results; the combined statement is given here only to fix notation for the remainder of the paper. Proposition 1 (Unified equilibrium correspondence). Let (2) satisfy Assumption 1 at a point x⋆x . For each algorithm ∈BCD,GBD,ADMM,SCA,IPM,MD,FW,RiemA∈\BCD,\,GBD,\,ADMM,\,SCA,\,IPM,\,MD,\,FW,\,Riem\ there exists an associated game Γ _A (of the type listed in the second column of Table 1) such that any limit point z⋆=(x⋆,λ⋆,μ⋆)z =(x ,λ ,μ ) of the iteration (6)—or, in the case of IPM, the limit μ→0+μ→ 0^+ of the central path (13)—satisfies, simultaneously, (i) an equilibrium-like variational characterization associated with Γ _A in the relevant sense (Nash, Stackelberg, saddle, no-regret, gradient-flow, or parametric); (i) the KKT conditions (4) of the original problem or of the relevant subproblem in the decomposition. The proof of (i)⇔ (i) for each A is given, respectively, in Monderer and Shapley (1996); Tseng (2001) (BCD), Geoffrion (1972) (GBD), Boyd et al. (2011); Eckstein and Bertsekas (1992) (ADMM), Scutari et al. (2014); Razaviyayn et al. (2013) (SCA), Wright (1997); Forsgren et al. (2002) (IPM), Nemirovsky and Yudin (1983); Bubeck (2015) (MD), Jaggi (2013); Lacoste-Julien and Jaggi (2015) (FW), and Absil et al. (2008); Boumal et al. (2019) (Riemannian). The cited works establish the underlying convergence or variational correspondence motivating the interpretation. Remark 1 (Other methods covered by the framework). The eight algorithm families in Table 1 are illustrative rather than exhaustive. Several further classes admit analogous equilibrium interpretations and inherit the multiplier-based regime analysis of the sequel. Augmented Lagrangian methods Hestenes (1969); Powell (1969); Rockafellar (1976) implement dual-ascent dynamics on a shadow-price game and are the parent class of ADMM. Proximal gradient methods Combettes and Wajs (2005); Beck and Teboulle (2009); Parikh and Boyd (2014) factor as two-player best response between a gradient-step agent and a proximal-step agent, and can be viewed as a degenerate ADMM with B=−IB=-I, c=0c=0. The primal–dual hybrid gradient method of Chambolle and Pock Chambolle and Pock (2011) realizes explicit saddle-point dynamics on composite problems. Sequential quadratic programming and trust-region methods Nocedal and Wright (2006) correspond to hierarchical approximation games with second-order surrogates, structurally analogous to SCA. In each case the limit point is a KKT triple of the original problem and the resulting multiplier vector populates the taxonomy of Section 4 without modification. 3.10 The Common Multiplier Signature Proposition 1 has a consequence that is, individually, modest but, taken across all six methods, structurally important: every algorithm considered in this paper produces—at convergence—a multiplier vector λ⋆λ associated with the inequality constraints of (2) (or its relevant subproblem). The vector λ⋆λ does not depend on the choice of A: under Assumption 1 the multipliers are unique, so two algorithms that converge to the same KKT point necessarily report the same dual. This observation reframes the equilibrium correspondences of Sections 3.1–3.8 as different routes to the same structural object. Whichever algorithm one runs, the inequality multipliers at convergence encode the active-constraint geometry of the solution, and—as we show in Sections 4 and 5—they admit a compact, scale-free classification that yields method-independent structural certificates. The remainder of the paper develops this classification: Section 4 introduces the regime taxonomy as a partition of the multiplier space; Section 5 establishes its invariance, stability, and boundary structure; Section 6 presents the corresponding classifier algorithm and its analysis; Section 7 reports numerical illustrations. 4 Multiplier Patterns and the Regime Taxonomy A central contribution of this work is the observation that, although the algorithms analyzed in Section 3 differ substantially in their update mechanisms, the stationary points they reach share a common structural signature encoded in the active Lagrange multipliers. In this section we formalize this observation as a precise classification map on the dual variable space. The resulting taxonomy partitions multiplier vectors into five operational regimes whose definitions depend only on the KKT data, not on the algorithm that produced them. The full structural theory of this taxonomy (invariance, stability, transition characterization, and the role of the hybrid regime as a topological boundary) is developed in Section 5. 4.1 Normalized Multipliers and Shape Features The regime classification is built from four scale-free statistics of λ⋆λ . Let L(λ):=‖λ‖1=∑i=1mλi.L(λ):=\|λ\|_1= _i=1^m _i. (17) When L(λ)>0L(λ)>0 we define the normalized multiplier vector λ¯:=λL(λ)∈Δm−1, λ:= λL(λ)∈ ^m-1, (18) where Δm−1=v∈ℝ+m:∑ivi=1 ^m-1=\v ^m_+: _iv_i=1\ is the standard simplex. When L(λ)=0L(λ)=0 we set λ¯:=0 λ:=0 by convention; this case will fall into the Unconstrained regime below. We write λ¯(1)≥λ¯(2)≥⋯≥λ¯(m) λ_(1)≥ λ_(2)≥·s≥ λ_(m) for the sorted (order statistic) entries of λ¯ λ. Definition 5 (Shape features). Fix an integer k∈1,…,m−1k∈\1,…,m-1\ and a small parameter δ∈(0,1)δ∈(0,1). The top-k concentration, δ-support fraction, and second-order activity of λ∈ℝ+mλ ^m_+ are Σk(λ) _k(λ) :=∑j=1kλ¯(j), := _j=1^k λ_(j), (19) σδ(λ) _δ(λ) :=1m|i:λ¯i>δ|, := 1m\, |\\,i: λ_i>δ\,\ |, (20) τ(λ) τ(λ) :=λ¯(2). := λ_(2). (21) The quadruple (L(λ),Σk(λ),σδ(λ),τ(λ)) (L(λ), _k(λ), _δ(λ),τ(λ) ) acts as a feature vector summarizing the multiplier pattern: L captures total dual mass, Σk _k captures concentration, σδ _δ captures spread, and τ captures whether multiple constraints are simultaneously non-negligible. 4.2 The Four Core Regimes We now define four core regimes as open subsets of ℝ+mR^m_+, parameterized by a quadruple Θ:=(δ,θ,γ,k),0<δ<12,θ∈(12,1),γ∈(0,1),k∈ℕ, :=(δ,θ,γ,k), 0<δ< 12,\ θ∈( 12,1),\ γ∈(0,1),\ k , (22) with km≪mkm m in the regimes of practical interest (typically k∈1,2,3k∈\1,2,3\). The parameters δ,θ,γδ,θ,γ are dimensionless thresholds; we adopt the default values (δ,θ,γ,k)=(0.05,0.7,0.4,2)(δ,θ,γ,k)=(0.05,0.7,0.4,2) throughout, while emphasizing that all theorems hold for any admissible Θ satisfying (22). Definition 6 (Core regimes). Given parameters Θ as in (22), define the following open subsets of ℝ+mR^m_+: ℛunc∘ _unc :=λ:L(λ)<δ, := \λ:L(λ)<δ \, (23) ℛres∘ _res :=λ:L(λ)>δ,Σk(λ)>θ, := \λ:L(λ)>δ,\ _k(λ)>θ \, (24) ℛsat∘ _sat :=λ:L(λ)>δ,Σk(λ)<θ,σδ(λ)>γ, := \λ:L(λ)>δ,\ _k(λ)<θ,\ _δ(λ)>γ \, (25) ℛcoup∘ _coup :=λ:L(λ)>δ,Σk(λ)<θ,σδ(λ)<γ,τ(λ)>δ. := \λ:L(λ)>δ,\ _k(λ)<θ, _δ(λ)<γ,\ τ(λ)>δ \. (26) We refer to these as the Unconstrained, Resource-Limited, Saturation, and Strongly-Coupled regimes, respectively. The four sets are interpreted as follows. • ℛunc∘R_unc collects KKT points whose total dual mass is negligible. The stationarity condition is then dominated by ∇f(x⋆)∇ f(x ) and the constraints exert little influence. This regime is typical of interior solutions and early iterations of descent methods. • ℛres∘R_res collects points where a small number (≤k≤ k) of constraints carry the bulk (>θ>θ) of the dual mass. This is the canonical ”budget-binding” regime in which one or two resource-type constraints dictate the geometry of the solution. • ℛsat∘R_sat collects points where a large fraction (>γ>γ) of constraints are individually non-negligible. This corresponds to many variables operating at bound and is characteristic of boundary-locked solutions on box-constrained or manifold-constrained problems. • ℛcoup∘R_coup collects points where the dual mass is distributed across an intermediate number of constraints: more than one (τ>δτ>δ), but fewer than γmγ m (σδ<γ _δ<γ). This corresponds to tight inter-block coupling, frequent in consensus and hierarchical settings. Lemma 2 (Pairwise disjointness). The four sets ℛunc∘R_unc , ℛres∘R_res , ℛsat∘R_sat , ℛcoup∘R_coup are pairwise disjoint open subsets of ℝ+mR^m_+. Proof. Openness of each set follows from openness of strict inequalities in continuous quantities. The map λ↦L(λ)λ L(λ) is continuous on ℝ+mR^m_+; the maps λ↦Σk(λ)λ _k(λ) and λ↦τ(λ)λ τ(λ) are continuous on L>0\L>0\ as compositions of continuous functions (sorting is continuous), and we only impose conditions on them on the open set L>δ\L>δ\. The map σδ _δ takes values in 0,1/m,…,1\0,1/m,…,1\ and the set σδ>γ\ _δ>γ\ is open since it equals ⋃|S|>γm⋂i∈Sλ¯i>δ _|S|>γ m _i∈ S\ λ_i>δ\, a union of open sets. For disjointness: ℛunc∘R_unc requires L<δL<δ while the other three require L>δL>δ, so ℛunc∘R_unc is disjoint from the rest. Among the remaining three, ℛres∘R_res requires Σk>θ _k>θ while ℛsat∘R_sat and ℛcoup∘R_coup require Σk<θ _k<θ. Finally, ℛsat∘R_sat requires σδ>γ _δ>γ while ℛcoup∘R_coup requires σδ<γ _δ<γ. ∎ 4.3 The Hybrid Regime as a Boundary Set Because the four core regimes are open and pairwise disjoint, their union does not cover ℝ+mR^m_+. The points that lie outside the union are precisely those for which at least one of the defining strict inequalities fails to hold strictly; these constitute the Hybrid regime. Definition 7 (Hybrid regime). Let Λ∘:=ℛunc∘∪ℛres∘∪ℛsat∘∪ℛcoup∘ :=R_unc _res _sat _coup . The Hybrid regime is ℛhyb:=ℝ+m∖Λ∘.R_hyb:=R^m_+ . (27) The five sets ℛunc∘,ℛres∘,ℛsat∘,ℛcoup∘,ℛhyb\R_unc ,R_res ,R_sat ,R_coup ,R_hyb\ form a partition of ℝ+mR^m_+ by Lemma 2 and Definition 7. The structural identification of ℛhybR_hyb with the topological boundary of Λ∘ , together with its measure-theoretic and limit-point properties, is established in Theorem 8 below. Definition 8 (Regime classification map). The regime classification map Ψ:ℝ+m→unc,res,sat,coup,hyb :R^m_+→\unc,res,sat,coup,hyb\ assigns to each λ the unique label r such that λ∈ℛr∘λ _r for r∈unc,res,sat,coupr∈\unc,res,sat,coup\, and Ψ(λ)=hyb (λ)=hyb otherwise. For block-structured problems and for hierarchical decompositions, Ψ is applied to the relevant dual vector: per-block multipliers for BCD, scaled dual uku^k for ADMM, follower KKT multipliers for GBD and SCA, and Riemannian multipliers (when the manifold is described by equality constraints) in the manifold setting. The cross-method correspondence is summarized in Table 2. Remark 2 (Choice of parameters). The parameters Θ=(δ,θ,γ,k) =(δ,θ,γ,k) encode operationally meaningful thresholds and are not free hyperparameters in the statistical sense. In practice they can be selected either (i) on physical grounds (e.g., k equals the number of resource-type constraints in a wireless allocation problem; δ is set to the numerical noise floor of the dual solver), or (i) by clustering the empirical distribution of λ¯ λ across a representative ensemble of instances. Theorem 3 below shows that the resulting regime labels are robust to a range of choices. Table 2: Canonical regimes and their method-specific manifestations. Reg. BCD GBD ADMM SCA / Riem. ℛuncR_unc Small block λ Small follower λ Small dual u Small manifold λ ℛresR_res Tight block budget Large μpow _pow Strong consensus Active capacity ℛsatR_sat Blocks at bounds Selection bounds Boundary penalty Manifold locking ℛcoupR_coup Inter-block ties Tight follower coupling Large residuals Surrogate coupling ℛhybR_hyb Mixed active sets Multiple KKT group Oscillatory duals Geometric transition 5 Structural Theorems We now establish four theorems that justify the taxonomy of Section 4 as a structural object. Theorem 3 shows that the classification map is invariant under the natural symmetries of the KKT system. Theorem 5 establishes local constancy of Ψ under perturbations of the problem data within each core regime, with an explicit Lipschitz bound. Theorem 7 characterizes regime transitions as codimension-one events and shows they are generically isolated along smooth paths in parameter space. Theorem 8 identifies ℛhybR_hyb as the topological boundary of the union of core regimes, establishes its Lebesgue measure zero, and shows that each Hybrid point is approached by sequences from at least two distinct core regimes. Throughout this section, Ψ is the regime classification map of Definition 8 for fixed parameters Θ as in (22). 5.1 Invariance Theorem 3 (Invariances of the regime classification). Let λ∈ℝ+mλ ^m_+. The classification map Ψ satisfies the following invariances. (i) (Permutation invariance.) For any permutation π∈Smπ∈ S_m, Ψ(π⋅λ)=Ψ(λ) (π·λ)= (λ), where (π⋅λ)i=λπ(i)(π·λ)_i= _π(i). (i) (Uniform multiplier rescaling.) For any c>0c>0, the shape features Σk(cλ)=Σk(λ) _k(cλ)= _k(λ), σδ(cλ)=σδ(λ) _δ(cλ)= _δ(λ), and τ(cλ)=τ(λ)τ(cλ)=τ(λ). Consequently, if both L(λ)L(λ) and L(cλ)=cL(λ)L(cλ)=cL(λ) lie on the same side of δ, then Ψ(cλ)=Ψ(λ) (cλ)= (λ). (i) (Uniform constraint rescaling.) Suppose the problem (2) is modified by replacing each gig_i with cgic\,g_i for a single c>0c>0. Then the modified problem has the same primal solution x⋆x , and its multipliers are λnew⋆=λ⋆/cλ _new=λ /c. Hence Ψ(λnew⋆)=Ψ(λ⋆) (λ _new)= (λ ) whenever L(λ⋆)/cL(λ )/c and L(λ⋆)L(λ ) lie on the same side of δ. (iv) (Diffeomorphism invariance.) Let ϕ:U→Vφ:U→ V be a C2C^2 diffeomorphism between open neighborhoods U,V⊂ℝnU,V ^n, and define the transformed problem f~:=f∘ϕ−1 f:=f φ^-1, g~i:=gi∘ϕ−1 g_i:=g_i φ^-1, h~j:=hj∘ϕ−1 h_j:=h_j φ^-1. If (x⋆,λ⋆,μ⋆)(x ,λ ,μ ) is a KKT triple of (2) satisfying Assumption 1, then (ϕ(x⋆),λ⋆,μ⋆)(φ(x ),λ ,μ ) is a KKT triple of the transformed problem satisfying Assumption 1, and Ψ assigns the same label. Proof. (i) The maps L,Σk,σδ,τL, _k, _δ,τ are all symmetric functions of λ since they depend only on the multiset of entries (through ‖λ‖1\|λ\|_1 and the order statistics of λ¯ λ). Hence each defining inequality in (23)–(26) is preserved under permutation, and Ψ is invariant. (i) For c>0c>0, cλ¯=cλ/(c‖λ‖1)=λ/‖λ‖1=λ¯ cλ=cλ/(c\|λ\|_1)=λ/\|λ\|_1= λ, so the normalized vector is unchanged and so are Σk,σδ,τ _k, _δ,τ. The only feature affected by rescaling is L(cλ)=cL(λ)L(cλ)=c\,L(λ), which enters the definitions only through the threshold L≷δL δ. The conclusion follows. (i) The original KKT stationarity reads ∇f(x⋆)+∑iλi⋆∇gi(x⋆)+∑jμj⋆∇hj(x⋆)∇ f(x )+ _iλ _i∇ g_i(x )+ _jμ _j∇ h_j(x ) =0=0. Replacing gig_i with cgic\,g_i and λi⋆λ _i with λi⋆/cλ _i/c leaves the stationarity equation unchanged; complementarity and feasibility are likewise preserved. Uniqueness of multipliers under LICQ then implies λnew⋆=λ⋆/cλ _new=λ /c. The regime claim follows from (i). (iv) Set y⋆:=ϕ(x⋆)y :=φ(x ) and write ϕ−1φ^-1 for the inverse diffeomorphism. Differentiating g~i(y)=gi(ϕ−1(y)) g_i(y)=g_i(φ^-1(y)) at y⋆y gives ∇g~i(y⋆)=(Dϕ−1(y⋆))⊤∇gi(x⋆),∇ g_i(y )= (Dφ^-1(y ) ) ∇ g_i(x ), and similarly for f~,h~j f, h_j. Substituting into the stationarity equation for the transformed problem, (Dϕ−1(y⋆))⊤[∇f(x⋆)+∑iλi⋆∇gi(x⋆)+∑jμj⋆∇hj(x⋆)]=0, (Dφ^-1(y ) ) [∇ f(x )+ _iλ _i∇ g_i(x )+ _jμ _j∇ h_j(x ) ]=0, which holds because the bracketed expression vanishes by stationarity of the original triple. Since Dϕ−1(y⋆)Dφ^-1(y ) is invertible by assumption, this means (y⋆,λ⋆,μ⋆)(y ,λ ,μ ) is stationary for the transformed problem. Active sets are preserved because g~i(y⋆)=gi(x⋆) g_i(y )=g_i(x ), so complementarity and feasibility carry over. LICQ for the transformed problem follows from LICQ for the original by the invertibility of Dϕ−1(y⋆)Dφ^-1(y ) applied to the gradients. SOSC is preserved by an analogous transformation of the Hessian of the Lagrangian via Dϕ−1Dφ^-1 (a standard calculation; see Bonnans and Shapiro (2000)). The multiplier vector λ⋆λ is unchanged, so all features in Definition 5 and hence Ψ are preserved. ∎ Remark 3 (Non-uniform constraint rescaling). Theorem 3(i) is stated for uniform rescaling gi↦cgig_i c\,g_i with a single c>0c>0. Under non-uniform rescaling gi↦cigig_i c_ig_i, the multipliers transform as λi⋆↦λi⋆/ciλ _i λ _i/c_i, and λ¯ λ is in general not preserved. Consequently, Ψ may change. This is appropriate: non-uniform rescaling alters the relative magnitudes of constraint sensitivities and therefore genuinely changes which constraints dominate. To recover invariance one must co-transform the thresholds; this is straightforward but not used in what follows. A direct corollary is that the classification depends only on the KKT data at x⋆x and not on the algorithm that produced it. Corollary 4 (Method-independence). If (x⋆,λ⋆,μ⋆)(x ,λ ,μ ) is a KKT triple satisfying Assumption 1, then Ψ(λ⋆) (λ ) is the same regardless of which of the algorithms in Section 3 produced it. 5.2 Stability under Perturbation We now show that within the interior of any core regime, the regime label is locally constant under perturbations of the problem data ω. This is the foundational property that allows downstream papers to invoke the regime label as a robust structural certificate. We say that a feature triple (L⋆,Σk⋆,σδ⋆,τ⋆)(L , _k , _δ ,τ ) associated with a KKT point in regime ℛr∘R_r has feature margin ρr(λ⋆):=dist(λ⋆,∂ℛr∘)>0, _r(λ ):=dist (λ ,\, _r )>0, (28) where ∂ℛr∘ _r is the topological boundary in ℝ+mR^m_+. Equivalently, ρr _r is the minimum slack across all strict inequalities defining ℛr∘R_r (under any norm equivalent on ℝmR^m), and is strictly positive for any λ⋆∈ℛr∘λ _r . Theorem 5 (Stability of the regime label). Suppose the problem data ω↦(f(⋅,ω),ω (f(·;ω), g(⋅,ω),h(⋅,ω))g(·;ω),h(·;ω)) is C2C^2 on a neighborhood Ω0 _0 of ω⋆ω , and that the KKT triple (x⋆,λ⋆,μ⋆)(x ,λ ,μ ) at ω⋆ω satisfies Assumption 1 together with strict complementarity. Then there exist a neighborhood U⊆Ω0U _0 of ω⋆ω and constants κ,η0>0κ, _0>0 such that: (a) (Strong regularity.) There is a unique C1C^1 map ω↦(x⋆(ω),λ⋆(ω),μ⋆(ω))ω (x (ω),λ (ω),μ (ω)) on U satisfying the KKT conditions at ω⋆ω , with ‖λ⋆(ω)−λ⋆‖≤κ‖ω−ω⋆‖,∀ω∈U.\|λ (ω)-λ \|≤κ\,\|ω-ω \|, ∀ω∈ U. (29) (b) (Constant regime.) If λ⋆∈ℛr∘λ _r for some r∈unc,res,sat,coupr∈\unc,res,sat,coup\ and we set η:=minη0,ρr(λ⋆)CΨκ,η:= \ _0,\ _r(λ )C_ \,κ \, (30) where CΨC_ is the (finite) joint Lipschitz constant of the feature map λ↦(L,Σk,σδ,τ)λ (L, _k, _δ,τ) on a bounded neighborhood of λ⋆λ , then Ψ(λ⋆(ω))=r,∀ω∈U with ‖ω−ω⋆‖<η. (λ (ω))=r, ∀ω∈ U with \|ω-ω \|<η. (31) Proof. (a) Stack the KKT conditions (4) for the parametric problem into a generalized equation F(z,ω)+NK(z)∋0,F(z;ω)+N_K(z) 0, where z=(x,λ,μ)z=(x,λ,μ), K=ℝn×ℝ+m×ℝpK=R^n×R^m_+×R^p, NKN_K is the normal cone, and F stacks ∇x,g,h _x L,g,h. Under LICQ, SOSC and strict complementarity, this generalized equation is strongly regular at (z⋆;ω⋆)(z ;ω ) in the sense of Robinson Robinson (1980). Robinson’s strong regularity theorem yields a unique single-valued, locally Lipschitz solution map ω↦z(ω)ω z(ω) on a neighborhood U of ω⋆ω , with Lipschitz constant κ controlled by the operator norm of the inverse of the KKT Jacobian M⋆:=[∇xx2⋆(∇g⋆)⊤(∇h⋆)⊤∇g⋆00∇h⋆00],M := bmatrix∇^2_x L &(∇ g _A) &(∇ h ) \\ ∇ g _A&0&0\\ ∇ h &0&0 bmatrix, restricted to the active set; nonsingularity of M⋆M is exactly Assumption 1 together with strict complementarity (see Bonnans and Shapiro (2000); Nocedal and Wright (2006); Wright (1997)). C1C^1 smoothness follows from the implicit function theorem applied to the equality KKT system once strict complementarity fixes the active set locally. Specializing the Lipschitz bound to the λ-component yields (29). (b) The feature map T:λ↦(L(λ),Σk(λ),σδ(λ),τ(λ))T:λ (L(λ), _k(λ), _δ(λ),τ(λ)) is locally Lipschitz on every bounded set in ℝ+mR^m_+ away from sorting ties: L is 11-Lipschitz in the ℓ1 _1 norm, Σk _k and τ are Lipschitz on L≥L(λ⋆)/2\L≥ L(λ )/2\ because λ¯ λ is Lipschitz in λ on this set and the order statistic operator is 11-Lipschitz in ℓ∞ _∞, and σδ _δ, while integer-valued, is constant on each open set where no entry of λ¯ λ equals δ exactly (so on the interior of any regime, σδ _δ is locally constant and trivially Lipschitz). Let CΨC_ be a finite joint Lipschitz constant of T on a closed ball B around λ⋆λ on which L≥L(λ⋆)/2L≥ L(λ )/2 and no order-statistic ties cross thresholds. By definition of ρr(λ⋆) _r(λ ) in (28), every λ∈ℝ+mλ ^m_+ with ‖λ−λ⋆‖<ρr(λ⋆)/CΨ\|λ-λ \|< _r(λ )/C_ has T(λ)T(λ) satisfying all strict inequalities defining ℛr∘R_r . Combining this with the Lipschitz bound (29) gives the threshold (30) (with η0 _0 chosen so that U∩B(ω⋆,η0)U∩ B(ω , _0) stays inside U and λ⋆(ω)λ (ω) stays inside B). For ‖ω−ω⋆‖<η\|ω-ω \|<η we then have ‖λ⋆(ω)−λ⋆‖≤κη≤ρr(λ⋆)/CΨ\|λ (ω)-λ \|≤κη≤ _r(λ )/C_ , so λ⋆(ω)∈ℛr∘λ (ω) _r and Ψ(λ⋆(ω))=r (λ (ω))=r. ∎ Corollary 6 (Quantitative regime persistence). Under the hypotheses of Theorem 5, the regime label is preserved under any perturbation of ω of magnitude up to ρr(λ⋆)/(CΨκ) _r(λ )/(C_ κ). In particular, if the data ω is the realization of a random vector with bounded perturbation ‖ω−ω⋆‖≤ε\|ω-ω \|≤ almost surely and ε<ρr(λ⋆)/(CΨκ) < _r(λ )/(C_ κ), then Ψ(λ⋆(ω)) (λ (ω)) is almost-surely equal to Ψ(λ⋆) (λ ). The corollary makes the taxonomy robust to small uncertainties in the problem data (for example, channel-estimation error in a wireless application): provided the nominal solution lies in the interior of a regime, the regime label is preserved. 5.3 Characterization of Regime Transitions We now turn to the global geometry of Ψ . The Hybrid regime ℛhybR_hyb separates the four core regimes by precisely those algebraic conditions that define their boundaries. We show that this separating set is, generically, a union of smooth hypersurfaces of codimension one in parameter space, and that along generic paths in parameter space the regime sequence undergoes only finitely many isolated transitions. Definition 9 (Transition variety). Let ω↦λ⋆(ω)ω λ (ω) be a C1C^1 KKT-solution map defined on an open connected Ω⊆ℝd ^d via Theorem 5(a) (so Assumption 1 together with strict complementarity holds throughout Ω ). The transition variety is :=ω∈Ω:λ⋆(ω)∈ℛhyb.T:= \ω∈ :λ (ω) _hyb \. (32) Theorem 7 (Transition characterization). Let ω↦λ⋆(ω)ω λ (ω) be as in Definition 9. Define the four boundary functions βL(ω) _L(ω) :=L(λ⋆(ω))−δ, :=L(λ (ω))-δ, βΣ(ω) _ (ω) :=Σk(λ⋆(ω))−θ, := _k(λ (ω))-θ, βσ(ω) _σ(ω) :=σδ(λ⋆(ω))−γ, := _δ(λ (ω))-γ, βτ(ω) _τ(ω) :=τ(λ⋆(ω))−δ. :=τ(λ (ω))-δ. Then: (a) (Algebraic structure.) =ω:βL(ω)=0∪ω:βΣ(ω)=0∪ω:βσ(ω)=0∪ω:βτ(ω)=0T=\ω: _L(ω)=0\∪\ω: _ (ω)=0\∪\ω: _σ(ω)=0\∪\ω: _τ(ω)=0\. (b) (Smoothness almost everywhere.) The functions βL _L and βΣ _ are C1C^1 on Ω . The function βτ _τ is C1C^1 on the open subset where λ¯(1)>λ¯(2)>λ¯(3) λ_(1)> λ_(2)> λ_(3). The function βσ _σ is piecewise constant; the set βσ=0\ _σ=0\ is the union of the level sets λ¯i=δ\ λ_i=δ\ for indices i that change the count. (c) (Generic codimension one.) For Lebesgue-almost every choice of parameters Θ=(δ,θ,γ,k) =(δ,θ,γ,k) in (22), each of the level sets βL=0,βΣ=0,βτ=0,λ¯i=δ\ _L=0\,\ _ =0\,\ _τ=0\,\ λ_i=δ\ is either empty or a C1C^1 embedded hypersurface in Ω of codimension 11. Consequently T has Lebesgue measure zero in Ω . (d) (Isolated transitions on transverse paths.) Let γ:[0,1]→Ωγ:[0,1]→ be a C1C^1 curve transverse to each of the hypersurfaces in (c). Then γ−1()γ^-1(T) is a finite set, and the regime label Ψ(λ⋆(γ(t))) (λ (γ(t))) is piecewise constant in t with finitely many discontinuities, each of which occurs at a single boundary crossing. Proof. (a) By Definition 7, λ∈ℛhybλ _hyb iff λ∉Λ∘λ∉ , i.e., iff for every core regime r at least one strict inequality fails. Equivalently, at least one of L=δL=δ, Σk=θ _k=θ, σδ=γ _δ=γ, τ=δτ=δ holds (with the understanding that the relevant equality is the one that prevents membership in any of the four open regimes). A careful case analysis confirms that ℛhybR_hyb equals the preimage of these four equalities under the feature map. The claim follows. (b) L and Σk _k are differentiable functions of λ on L>0\L>0\ (with Σk _k differentiable wherever the top-k index set is uniquely defined, i.e., λ¯(k)>λ¯(k+1) λ_(k)> λ_(k+1); this holds on an open dense subset). Composition with the C1C^1 map ω↦λ⋆(ω)ω λ (ω) from Theorem 5(a) yields C1C^1 regularity for βL _L and βΣ _ on Ω (in the case of βΣ _ , away from the ties just described). The function τ(λ)=λ¯(2)τ(λ)= λ_(2) is C1C^1 wherever the top three order statistics are strictly separated, by an analogous argument. For βσ _σ: σδ _δ is piecewise constant in λ, with jumps exactly at the level sets λ¯i=δ λ_i=δ. Pulling back through λ⋆(ω)λ (ω) gives the description in the statement. (c) For each fixed boundary function β∈βL,βΣ,βτβ∈\ _L, _ , _τ\, the level set β=0\β=0\ is the preimage of 0\0\ under a C1C^1 scalar map on Ω . By Sard’s theorem Sard (1942), 00 is a regular value for β for Lebesgue-almost every choice of the corresponding threshold (δ, θ, δ, respectively), and at every regular value the preimage is a C1C^1 embedded hypersurface of codimension 11 (when nonempty). Applying Sard separately to the threshold δ in λ¯i=δ λ_i=δ for each fixed i gives the same conclusion for the components of βσ=0\ _σ=0\. The union of finitely many codimension-11 subsets has Lebesgue measure zero in Ω , so T is null. (d) If γ is transverse to each hypersurface in (c), then γ−1γ^-1 of each is a C1C^1 submanifold of [0,1][0,1] of codimension 11, i.e., a discrete subset. Compactness of [0,1][0,1] then makes it finite. Between consecutive crossings, λ⋆(γ(t))λ (γ(t)) remains in the interior of a single regime, so by definition Ψ is constant on each open subinterval. ∎ Remark 4 (Implication for trajectories). Theorem 7(d) provides the rigorous underpinning for the ”phase-like” convergence behavior reported empirically in the literature and visible in our numerical experiments (Section 7): the multiplier trajectory of a converging algorithm, viewed as a curve in parameter or iterate space, decomposes into finitely many regime-stationary arcs separated by isolated transitions, with the qualitative algorithmic behavior changing only at these transitions. 5.4 The Hybrid Regime as Topological Boundary We close the structural development by establishing the precise role of the Hybrid regime: it is, simultaneously, the topological boundary of the union of core regimes, a Lebesgue null set, and an accumulation set of multiple core regimes. Theorem 8 (Hybrid as topological boundary). Let Λ∘=ℛunc∘∪ℛres∘∪ℛsat∘∪ℛcoup∘ =R_unc _res _sat _coup . Then (a) Λ∘ is an open subset of ℝ+mR^m_+ with closure Λ∘¯=ℝ+m =R^m_+, except possibly on a Lebesgue null set; more precisely, Λ∘¯ has full Lebesgue measure in ℝ+mR^m_+. (b) ℛhyb=∂ℝ+mΛ∘R_hyb= _R^m_+ , the topological boundary of Λ∘ relative to ℝ+mR^m_+. (c) ℛhybR_hyb has Lebesgue measure zero in ℝ+mR^m_+. (d) (Multiple accumulation.) Every λ∈ℛhybλ _hyb lies in the closure of at least two distinct core regimes; that is, there exist r1≠r2r_1≠ r_2 in unc,res,sat,coup\unc,res,sat,coup\ and sequences λ1(n)→λ^(n)_1→λ, λ2(n)→λ^(n)_2→λ with λ1(n)∈ℛr1∘λ^(n)_1 _r_1 and λ2(n)∈ℛr2∘λ^(n)_2 _r_2 for all n. Proof. (a) Openness of Λ∘ follows from Lemma 2, as the union of open sets is open. To see that Λ∘¯ has full measure, note that the complement ℛhyb=ℝ+m∖Λ∘R_hyb=R^m_+ is contained in the union of the four level sets in Theorem 7(c) (applied with ω=λω=λ and the identity solution map), each of which is at most a codimension-11 subset of ℝ+mR^m_+. The union of finitely many codimension-11 subsets is Lebesgue null. (b) We show ℛhyb=Λ∘¯∖Λ∘=∂ℝ+mΛ∘R_hyb= = _R^m_+ . (⊆ ). Let λ∈ℛhybλ _hyb. Then λ∉Λ∘λ∉ by definition. To show λ∈Λ∘¯λ∈ , we exhibit a sequence in Λ∘ converging to λ. We treat the four boundary cases (corresponding to which strict inequality is tight at λ) separately. Case 1: L(λ)=δL(λ)=δ. For each n, set λ1(n):=(1−1/n)λ^(n)_1:=(1-1/n)\,λ if λ≠0λ≠ 0, otherwise the case is vacuous. Then L(λ1(n))=(1−1/n)δ<δL(λ^(n)_1)=(1-1/n)δ<δ, so λ1(n)∈ℛunc∘λ^(n)_1 _unc , and λ1(n)→λ^(n)_1→λ. Case 2: L(λ)>δL(λ)>δ and Σk(λ)=θ _k(λ)=θ. For each n, perturb λ by adding a small mass ϵn→0+ _n→ 0^+ to its largest entry: λ1(n):=λ+ϵne(1)λ^(n)_1:=λ+ _ne_(1), where e(1)e_(1) is the unit vector at the index of λ¯(1) λ_(1). Then Σk(λ1(n))>θ _k(λ^(n)_1)>θ for ϵn _n sufficiently small (since adding mass to the top entry strictly increases Σk _k relative to its previous value, by continuity), placing λ1(n)∈ℛres∘λ^(n)_1 _res . Case 3: L(λ)>δL(λ)>δ, Σk(λ)≤θ _k(λ)≤θ, σδ(λ)=γ _δ(λ)=γ. Either (i) the count σδ(λ)⋅m _δ(λ)· m is achieved with one entry exactly at δ, in which case shifting that entry to δ+ϵnδ+ _n or δ−ϵnδ- _n produces λ1(n)λ^(n)_1 with σδ>γ _δ>γ or <γ<γ, respectively; or (i) γmγ m is not an integer, in which case βσ _σ cannot equal zero generically; this case does not arise. Case 4: All previous strict inequalities hold but τ(λ)=δτ(λ)=δ. Perturb the second-largest entry of λ upward by ϵn→0+ _n→ 0^+ to obtain λ1(n)λ^(n)_1 with τ>δτ>δ, placing λ1(n)∈ℛcoup∘λ^(n)_1 _coup . In every case λ1(n)→λ^(n)_1→λ with λ1(n)∈Λ∘λ^(n)_1∈ , so λ∈Λ∘¯λ∈ . (⊇ ). Conversely, suppose λ∈Λ∘¯∖Λ∘λ∈ . Then λ∉ℛr∘λ _r for any r, so λ∈ℛhybλ _hyb. (c) Already shown in part (a). (d) The constructive sequences in the proof of (b) show λ is the limit of points in some core regime r1r_1; choosing the sign of the perturbation in the opposite direction (subtract ϵn _n instead of adding, where the perturbation is sign-meaningful) produces a sequence in a different core regime r2r_2 converging to λ. For example, in Case 2, λ−ϵne(1)λ- _ne_(1) has Σk<θ _k<θ and falls into ℛsat∘R_sat or ℛcoup∘R_coup depending on the remaining features. In each case, the two-sided perturbation around the tight inequality produces sequences in two distinct core regimes. ∎ Corollary 9 (Geometric meaning of the Hybrid regime). The Hybrid regime ℛhybR_hyb is, simultaneously, (i) the precise set of points where the classification by strict inequalities is degenerate, (i) the topological frontier between core regimes, and (i) a measure-zero structural object on which classifiers of Ψ must be constructed with care. 5.5 Discussion and Consequences The four theorems of this section together provide the mathematical foundation for using the regime label as a primitive in downstream optimization theory. Theorem 3 legitimates the label as an intrinsic property of the KKT point, not of its representation. Corollary 4 in particular allows results stated for one algorithm to be transferred to another whenever both produce KKT points in the same regime. Theorem 5 establishes that the label is locally robust: small perturbations of the data, including the stochastic perturbations arising from estimation error or measurement noise in applications, do not change the regime classification on the interior of any core regime. The explicit threshold (30) ties the robustness margin to two quantities of independent interest: the conditioning κ of the KKT system and the feature-space margin ρr _r of the nominal solution. Both can be estimated empirically from the dual solution of a single solve. Theorem 7 converts the empirical observation of phase-like convergence into a precise geometric statement: transitions are codimension-one events along generic trajectories, and the trajectory of a converging algorithm visits only finitely many regimes. This is the structural result that licenses regime-aware algorithm design: a controller observing the multiplier trajectory may detect transitions reliably because they correspond to crossings of an algebraic surface. Theorem 8 replaces the informal description of the Hybrid regime as a ”catch-all” with a precise topological characterization. In particular, Hybrid points are negligible in volume but pivotal in structure: any continuous path from one core regime to another must traverse ℛhybR_hyb. The classifier algorithm that operationalizes Ψ as a computational primitive, together with its convergence and complexity analysis under noisy multiplier estimates, is the subject of Section 6. 6 The Regime Classifier: Algorithm and Guarantees The structural theorems of Section 5 establish the regime taxonomy as a well-posed object. To use the taxonomy as a primitive in downstream applications—in particular, the wireless-system papers that will build on this work—we require a computational procedure that, given an estimate λ λ of the true KKT multiplier vector λ⋆λ , returns the regime label Ψ(λ⋆) (λ ) with provable guarantees. This section presents such a procedure and analyzes its behavior under three sources of error that arise in practice: (i) approximate solver output for known problem data; (i) finite-sample estimation of unknown problem data; and (i) temporal drift in the problem data. Each setting yields a quantitative guarantee that downstream papers can invoke without re-derivation. 6.1 The Classifier Algorithm Algorithm 1 implements the classification map Ψ of Definition 8. It accepts an arbitrary λ^∈ℝ+m λ ^m_+, the parameter quadruple Θ=(δ,θ,γ,k) =(δ,θ,γ,k), and an optional numerical tolerance ε≥0 ≥ 0 that flags points within ε of any defining inequality as Hybrid. The output is the regime label. Algorithm 1 Regime Classifier Ψ 1: λ^∈ℝ+m λ ^m_+; parameters Θ=(δ,θ,γ,k) =(δ,θ,γ,k); tolerance ε≥0 ≥ 0 2: regime label r∈unc,res,sat,coup,hybr∈\unc,res,sat,coup,hyb\ 3: L←∑i=1mλ^iL← _i=1^m λ_i ⊳ total dual mass 4: if L<δ−εL<δ- then return uncunc 5: end if 6: if L≤δ+εL≤δ+ then return hybhyb 7: end if 8: λ¯←λ^/L λ← λ/L ⊳ normalize to simplex 9: Compute top-k values λ¯(1),…,λ¯(k)\ λ_(1),…, λ_(k)\ by partial selection 10: Σk←∑j=1kλ¯(j) _k← _j=1^k λ_(j) 11: if |Σk−θ|≤ε| _k-θ|≤ then return hybhyb 12: end if 13: if Σk>θ _k>θ then return resres 14: end if 15: σδ←1m|i:λ¯i>δ| _δ← 1m |\i: λ_i>δ\ | 16: if σδ>γ _δ>γ then return satsat 17: end if 18: τ←λ¯(2)τ← λ_(2) 19: if |τ−δ|≤ε|τ-δ|≤ then return hybhyb 20: end if 21: if τ>δτ>δ then return coupcoup 22: end if 23: return hybhyb Proposition 10 (Per-call complexity). Algorithm 1 terminates in (m)O(m) time and (m)O(m) space using a linear-time partial-selection routine (e.g., introselect or median-of-medians) for the top-k extraction in line 5. With a sort-based implementation the cost is (mlogm)O(m m). Proof. Lines 1–4 are (m)O(m). Line 5 extracts the top-k entries of λ¯ λ; this is computable in (m)O(m) time by partial selection Blum et al. (1973); Musser (1997); Cormen et al. (2022). Lines 6–16 each take (m)O(m) or (1)O(1) work, including the count in line 10. The total is (m)O(m). ∎ For applications in which m is moderate (tens to a few hundreds), as is typical in wireless resource-allocation problems, the per-call cost of Algorithm 1 is negligible compared to a single optimization step. 6.2 Feature Margin and Correctness under Perturbation We first quantify the robustness of Ψ to perturbations of λ λ around the true multiplier λ⋆λ . The natural margin in this context lives in the feature space, where the regime-defining inequalities are posed. Definition 10 (Feature-space margin). For λ⋆∈ℛr∘λ _r with r∈unc,res,sat,coupr∈\unc,res,sat,coup\, the feature-space margin is the smallest slack among the strict inequalities defining ℛr∘R_r : ρr(λ⋆):=min _r(λ ):= \ |L(λ⋆)−δ|,|Σk(λ⋆)−θ|, \,|L(λ )-δ|,\ | _k(λ )-θ|, |σδ(λ⋆)−γ|,|τ(λ⋆)−δ|, | _δ(λ )-γ|,\ |τ(λ )-δ|\, \, (33) restricted to those inequalities that appear in the definition of ℛr∘R_r in (23)–(26). The quantity ρr(λ⋆) _r(λ ) is strictly positive whenever λ⋆λ lies in the interior of a core regime, and is directly computable from a single solve. It is the operational counterpart of the λ-space distance to the regime boundary used in Theorem 5: the two notions differ by at most a factor of CΨC_ , the joint Lipschitz constant of the feature map T:λ↦(L,Σk,σδ,τ)T:λ (L, _k, _δ,τ) established in the proof of Theorem 5(b). Theorem 11 (Correctness under multiplier perturbation). Let λ⋆∈ℛr∘λ _r for some core regime r∈unc,res,sat,coupr∈\unc,res,sat,coup\, with feature-space margin ρr(λ⋆)>0 _r(λ )>0 as in Definition 10. Let λ^∈ℝ+m λ ^m_+ be any estimate satisfying ‖λ^−λ⋆‖2≤η<ρr(λ⋆)CΨ.\| λ-λ \|_2\,≤\,η< _r(λ )C_ . (34) Then Algorithm 1 with tolerance ε=0 =0 returns Ψ(λ^)=r ( λ)=r. Proof. Write T(λ)=(L(λ),Σk(λ),σδ(λ),τ(λ))T(λ)=(L(λ), _k(λ), _δ(λ),τ(λ)). By Theorem 5(b)’s proof, T is CΨC_ -Lipschitz on a neighborhood of λ⋆λ that we take large enough to contain λ λ for any η in the stated range. Hence ‖T(λ^)−T(λ⋆)‖∞≤CΨ‖λ^−λ⋆‖2≤CΨη.\|T( λ)-T(λ )\|_∞≤ C_ \,\| λ-λ \|_2≤ C_ \,η. By the assumption CΨη<ρr(λ⋆)C_ \,η< _r(λ ), every feature of λ λ deviates by strictly less than ρr(λ⋆) _r(λ ) from its value at λ⋆λ . Each defining inequality of ℛr∘R_r holds at λ⋆λ with slack at least ρr(λ⋆) _r(λ ), so each continues to hold strictly at λ λ. By Definition 8, Ψ(λ^)=r ( λ)=r, which is precisely what Algorithm 1 returns at ε=0 =0 (the branches into hybhyb on lines 3, 8, and 14 are never taken). ∎ Theorem 11 is the deterministic foundation on which the remaining results rest: any source of error that bounds ‖λ^−λ⋆‖2\| λ-λ \|_2 below ρr/CΨ _r/C_ ensures correct classification. 6.3 Iteration Complexity along Algorithm Trajectories We now consider the canonical setting in which λ^(k) λ^(k) is the multiplier estimate produced by an optimization algorithm ∈BCD,GBD,ADMM,SCA,IPM,MD,FW,RiemA∈\BCD,GBD,ADMM,SCA,IPM,MD,FW,Riem\ at iteration k. We ask: how many iterations of A are required before the classifier output stabilizes at the true regime label? Theorem 12 (Classifier stabilization). Let A be an optimization algorithm whose multiplier iterates satisfy ‖λ^(k)−λ⋆‖2≤φ(k)\| λ^(k)-λ \|_2≤ _A(k) for a known rate function φ:ℕ→ℝ>0 _A:N _>0 with φ(k)↓0 _A(k) 0. Suppose λ⋆∈ℛr∘λ _r with feature margin ρr(λ⋆)>0 _r(λ )>0. Define the classification iteration complexity k⋆(λ⋆):=mink∈ℕ:φ(k)<ρr(λ⋆)CΨ.k _A(λ ):= \k :\ _A(k)< _r(λ )C_ \. (35) Then Ψ(λ^(k))=r ( λ^(k))=r for all k≥k⋆(λ⋆)k≥ k _A(λ ). Proof. Direct application of Theorem 11 with η=φ(k)η= _A(k), which by definition of k⋆k _A satisfies the bound (34) for all k≥k⋆k≥ k _A. ∎ Corollary 13 (Concrete rates). Substituting standard rate functions into (35) yields the following classifier-stabilization iteration counts, with constants absorbed into the (⋅)O(·) notation: (a) Linearly convergent methods (BCD under KL property Attouch et al. (2013), IPM in quadratic phase Wright (1997)): φ(k)=cqk (k)=c\,q^k with q∈(0,1)q∈(0,1), giving k⋆=(log(CΨ/ρr)/log(1/q))k =O ( (C_ / _r)/ (1/q) ). (b) ADMM at (1/k)O(1/k) rate He and Yuan (2012): φ(k)=c/k (k)=c/k, giving k⋆=(CΨ/ρr)k =O(C_ / _r). (c) Mirror Descent and SGD at (1/k)O(1/ k) rate Nesterov (2018); Bubeck (2015): φ(k)=c/k (k)=c/ k, giving k⋆=((CΨ/ρr)2)k =O ((C_ / _r)^2 ). (d) Frank–Wolfe at (1/k)O(1/k) rate Jaggi (2013): same as (b). (e) Newton-type IPM in its quadratically convergent regime: φ(k)=cq2k (k)=c\,q^2^k, giving k⋆=(loglog(CΨ/ρr))k =O ( (C_ / _r) ). The corollary’s main quantitative message is that the classifier stabilizes on a time scale governed by the inverse-margin CΨ/ρrC_ / _r raised to a method-dependent exponent. In particular, on instances with large margin the classifier is reliable after very few iterations, well before the solver has converged to the desired KKT tolerance. 6.4 Sample Complexity from Estimated Data In practical deployments the data ω of (2) is itself estimated from finite samples. In wireless systems, ω may collect channel coefficients estimated from pilot symbols, traffic statistics estimated from observed arrivals, or interference profiles estimated from measurement reports. Let ω^N ω_N denote an estimator based on N samples and write λ^N:=λ⋆(ω^N) λ_N:=λ ( ω_N) for the multiplier obtained by solving (2) at the estimated data. Theorem 14 (Sample-complexity correctness). Assume: (i) (Sub-Gaussian estimator.) The estimator ω^N ω_N satisfies, for some proxy σ2>0σ^2>0 and absolute constant c0>0c_0>0, ℙ(‖ω^N−ω⋆‖2>t)≤ 2exp(−c0Nt2σ2),t>0.P (\| ω_N-ω \|_2>t )\,≤\,2 (- c_0Nt^2σ^2 ), t>0. (36) (i) (Local Lipschitz solution map.) The KKT solution map ω↦λ⋆(ω)ω λ (ω) is κ-Lipschitz on a neighborhood of ω⋆ω , as established in Theorem 5(a). (i) (Margin condition.) λ⋆:=λ⋆(ω⋆)∈ℛr∘λ :=λ (ω ) _r with feature margin ρr(λ⋆)>0 _r(λ )>0. Then for any confidence parameter δ∈(0,1)δ∈(0,1), if the sample size satisfies N≥N0(δ):=σ2CΨ2κ2c0ρr(λ⋆)2log2δ,N\,≥\,N_0(δ)\,:=\, σ^2\,C_ ^2\,κ^2c_0\, _r(λ )^2\, 2δ, (37) then the classifier applied to the empirical solution returns the correct regime with high probability: ℙ(Ψ(λ^N)=r)≥ 1−δ.P (\, ( λ_N)=r\, )\,≥\,1-δ. (38) Proof. By (i), ‖ω^N−ω⋆‖2≤σlog(2/δ)/(c0N)\| ω_N-ω \|_2≤σ (2/δ)/(c_0N) holds with probability at least 1−δ1-δ. On this event, (i) gives ‖λ^N−λ⋆‖2≤κ‖ω^N−ω⋆‖2\| λ_N-λ \|_2≤κ\,\| ω_N-ω \|_2. For N≥N0(δ)N≥ N_0(δ) as in (37), κσlog(2/δ)/(c0N)≤ρr(λ⋆)CΨ,κ\,σ (2/δ)/(c_0N)≤ _r(λ )C_ , so on the high-probability event the bound (34) of Theorem 11 is satisfied. Hence Ψ(λ^N)=r ( λ_N)=r on this event, which has probability at least 1−δ1-δ. ∎ The sample complexity (37) has the standard logarithmic dependence on the confidence parameter δ and depends quadratically on the three structural quantities of interest: the data-noise level σ, the KKT conditioning κ, and the inverse feature margin 1/ρr1/ _r. The inverse-margin dependence is unavoidable: it reflects the geometric proximity of λ⋆λ to the regime boundary and is precisely the quantity that Theorem 5 identifies as the structural robustness of the classification. Remark 5 (Alternative concentration models). Assumption 14(i) holds with c0=1/2c_0=1/2 whenever ω^N ω_N is the sample mean of N i.i.d. sub-Gaussian random vectors with variance proxy σ2σ^2 Vershynin (2018). For sub-exponential estimators the bound (37) adapts with an extra factor of log(N) (N); for bounded random variables the bound is improved by Hoeffding’s inequality Boucheron et al. (2013). In all cases the N∝ρr−2log(1/δ)N _r^-2 (1/δ) scaling is preserved. 6.5 Online Tracking under Bounded Drift In time-varying environments–block-fading wireless channels, slowly evolving traffic, mobile users–the data ωt _t drifts in time, and the classifier must track the regime label rt:=Ψ(λ⋆(ωt))r_t:= (λ ( _t)) rather than identify a single static regime. We model the drift by a per-step bound ‖ωt+1−ωt‖2≤ν,∀t,\| _t+1- _t\|_2\,≤\,ν, ∀ t, (39) and assume per-step noisy observations yt=ωt+ξty_t= _t+ _t with ξt _t i.i.d. sub-Gaussian with proxy σ2σ^2. The natural estimator is a sliding average over the most recent W samples, ω^t(W):=1W∑s=t−W+1tys ω_t^(W):= 1W _s=t-W+1^ty_s. Theorem 15 (Online tracking correctness). Assume (39) and the per-step observation model above. Let λ^t(W):=λ⋆(ω^t(W)) λ_t^(W):=λ ( ω_t^(W)), and suppose at time t the data ωt _t satisfies the margin condition λ⋆(ωt)∈ℛrt∘λ ( _t) _r_t with margin ρrt _r_t uniformly bounded below by ρ>0ρ>0. Then for any δ∈(0,1)δ∈(0,1) the choice W⋆=(2σ2log(2/δ)ν2)1/3W \,=\, ( 2σ^2 (2/δ)ν^2 )^1/3 (40) yields the bound ‖λ^t(W⋆)−λ⋆(ωt)‖2≤κ(c1σ2/3ν1/3(log(2/δ))1/3)\| λ_t^(W )-λ ( _t)\|_2\,≤\,κ\, (c_1\,σ^2/3ν^1/3( (2/δ))^1/3 ) (41) with probability at least 1−δ1-δ for some absolute constant c1c_1. In particular, if the drift satisfies ν<νmax:=1c13σ2log(2/δ)(ρCΨκ)3,ν\,<\, _ := 1c_1^3σ^2 (2/δ)\, ( ρC_ \,κ )^3, (42) then ℙ(Ψ(λ^t(W⋆))=rt)≥1−δP ( ( λ_t^(W ))=r_t )≥ 1-δ. Proof. Decompose the estimator error into bias and variance components: ω^t(W)−ωt=1W∑s=t−W+1t(ωs−ωt)⏟drift bias+1W∑s=t−W+1tξs⏟noise term. ω_t^(W)- _t= 1W _s=t-W+1^t( _s- _t)_drift bias+ 1W _s=t-W+1^t _s_noise term. By (39), ‖ωs−ωt‖2≤(t−s)ν≤Wν\| _s- _t\|_2≤(t-s)ν≤ Wν for all s∈t−W+1,…,ts∈\t-W+1,…,t\, so the drift bias is bounded by νW/2ν W/2 (averaging 1,2,…,W1,2,…,W over W). The noise term is the average of W i.i.d. sub-Gaussian vectors with variance proxy σ2/Wσ^2/W; by standard concentration Vershynin (2018), ‖noise term‖2≤σ2log(2/δ)/W\|noise term\|_2≤σ 2 (2/δ)/W with probability at least 1−δ1-δ. Combining, ‖ω^t(W)−ωt‖2≤νW2+σ2log(2/δ)W\| ω_t^(W)- _t\|_2≤ ν W2+σ 2 (2/δ)W with probability at least 1−δ1-δ. Minimizing the right side over W>0W>0 by setting the derivative to zero gives W⋆W as in (40) up to absolute constants and yields the optimal error c1σ2/3ν1/3(log(2/δ))1/3c_1\,σ^2/3ν^1/3( (2/δ))^1/3 for an explicit constant c1=(3/2)⋅2−1/3c_1=(3/2)· 2^-1/3. Multiplying by the Lipschitz constant κ from Theorem 5(a) yields (41). Substituting the threshold ρ/(CΨκ)ρ/(C_ κ) from Theorem 11 and solving for ν gives (42). On the high-probability event, λ^t(W⋆) λ_t^(W ) lies in the correctness ball of Theorem 11, so the classifier returns rtr_t. ∎ The drift-tolerance bound (42) is the form most relevant to wireless deployments: it states that the classifier tracks the regime correctly so long as the channel drift rate ν stays below a cubic-in-margin threshold. The ν1/3ν^1/3 dependence of the tracking error (41) is the standard rate for non-parametric tracking under sub-Gaussian noise and bounded drift, and is known to be unimprovable in this class Vershynin (2018); Boucheron et al. (2013). 6.6 Joint Solver–Sample Budget In practice the multiplier estimate that enters the classifier carries error from two sources simultaneously: the data-estimation error in ω^N ω_N and the solver-iteration error after K solver iterations applied to the problem at ω^N ω_N. Write λ^N,K λ_N,K for the resulting iterate. Corollary 16 (Joint budget). Under the hypotheses of Theorems 11–14, ‖λ^N,K−λ⋆‖2≤φ(K)+κσlog(2/δ)c0N\| λ_N,K-λ \|_2≤ _A(K)+κ\,σ (2/δ)c_0N (43) holds with probability at least 1−δ1-δ. Sufficient for the classifier to return the correct label at this confidence is φ(K)+κσlog(2/δ)c0N<ρr(λ⋆)CΨ. _A(K)+κ\,σ (2/δ)c_0N\,<\, _r(λ )C_ . (44) The bound (44) traces a feasible region in the (K,N)(K,N) plane: for fixed δ, ρr _r, κ, σ, CΨC_ , any pair (K,N)(K,N) satisfying (44) suffices for correct classification with confidence 1−δ1-δ. Downstream applications can optimize the joint cost of sampling and computing along this frontier. Remark 6 (Operational interpretation). The bound (44) suggests a natural rule for allocating effort between data acquisition and solver iterations: • Increase N until the data-estimation term equals roughly half of the right-hand side; this requires N≳4σ2CΨ2κ2log(2/δ)/(c0ρr2)N 4σ^2C_ ^2κ^2 (2/δ)/(c_0 _r^2). • Then run the solver until φ(K) _A(K) falls below half of the right-hand side; the required K follows from Corollary 13 with the inverse margin replaced by 2CΨ/ρr2C_ / _r. This decomposition is invariant under reasonable choices of the solver rate and is the rule we recommend for instantiations in the wireless setting. 6.7 Practical Considerations Estimating the margin in practice The feature margin ρr(λ⋆) _r(λ ) is computable from a single solve via Definition 10: after obtaining a converged λ λ, evaluate the four feature slacks and take their minimum. Plugging this empirical ρ^r ρ_r into the bounds of Theorems 11–15 gives operational estimates. The error introduced by using ρ^r ρ_r in place of ρr _r is itself controlled by the Lipschitz continuity of the feature map (see Theorem 5), so the bounds remain valid up to a constant factor. Estimating the conditioning κ and Lipschitz CΨC_ The Lipschitz constants κ and CΨC_ are determined by problem structure (the KKT Jacobian and the feature map, respectively). Closed-form upper bounds are available when the problem admits known structure (e.g., strongly convex objectives, well-conditioned constraints). In black-box settings these constants are commonly estimated empirically by perturbation experiments; the bounds of Theorems 14–15 are then interpreted as empirical, with confidence inherited from the estimation procedure. Hybrid-regime outputs When the classifier returns hybhyb, the structural Theorem 8 indicates that λ⋆λ lies on a measure-zero transition surface and the algorithm has reached a structurally ambiguous point. In downstream applications this output is itself informative: it signals that the solution is near a regime boundary and that adaptive strategies (e.g., switching the inner solver or refining the surrogate) may be warranted. Use in downstream papers The four theorems of this section are designed to be cited as black boxes by downstream optimization and wireless-system papers. Specifically: Theorem 11 provides the deterministic correctness guarantee; Theorem 12 and Corollary 13 characterize how quickly the regime stabilizes along solver iterations; Theorem 14 gives the sample-complexity bound for finite-data deployments; and Theorem 15 bounds the drift tolerance for time-varying systems. The joint budget (44) ties these together for end-to-end deployment. 7 Numerical Illustrations and Comparative Analysis This section validates the theoretical contributions of Sections 4–6 through controlled numerical experiments. The experiments are organized to target specific theorems: each subsection examines a single claim, specifies the experimental protocol, and reports the resulting evidence. Our aim is not to compare algorithm performance in the usual sense (that exercise belongs in the papers cited in Table 1), but to verify that the regime taxonomy and its associated guarantees describe phenomena that arise in practice. 7.1 Experimental Setup and Protocol Problem families We generate instances from five families of mixed-integer nonlinear programs of the form (2), each designed to produce, by construction, a dominant operational regime. This controlled-instance design enables ground-truth labels against which the classifier of Algorithm 1 can be evaluated. Family ℱ1F_1 (Unconstrained-dominated): Quadratic objectives with loose box constraints: minx∈ℝn12x⊤Qx+c⊤xs.t.‖x‖∞≤B, _x ^n\, 12x Qx+c x .t. \|x\|_∞≤ B, (45) with Q≻0Q 0 randomly generated and B large enough that the unconstrained optimum is interior to the box. This family targets ℛuncR_unc. Family ℱ2F_2 (Resource-limited): Quadratic objectives with a single tight budget: minx≥0−c⊤x+ε2‖x‖2s.t.a⊤x≤B, _x≥ 0\,-c x+ 2\|x\|^2 .t. a x≤ B, (46) with c,a>0c,a>0 entrywise and B chosen so that the budget constraint binds. This family targets ℛresR_res. Family ℱ3F_3 (Saturation): Quadratic objectives with many simultaneously tight bound constraints: minx12x⊤Qx+c⊤xs.t.−b≤x≤b, _x\, 12x Qx+c x .t. -b≤ x≤ b, (47) with Q, c chosen so that approximately 0.6n0.6n of the 2n2n box constraints are active at the optimum. This family targets ℛsatR_sat. Family ℱ4F_4 (Strongly-coupled): Multi-block problems with consensus constraints: min∑i=1Mx1,…,xMfi(xi)s.t.∑i=1MAixi=b, _x_1,…,x_M\, _i=1^Mf_i(x_i) .t. _i=1^MA_ix_i=b, (48) with the coupling matrix [A1,…,AM][A_1,…,A_M] designed so that several rows of the dual feasibility condition are simultaneously active. This family targets ℛcoupR_coup. Family ℱ5F_5 (Hybrid/transition): Random non-convex MINLPs combining quadratic and bilinear terms with mixed constraint types (resource budget, individual bounds, and equality coupling), with parameters sampled near regime boundaries to populate ℛhybR_hyb: minx,y _x,y f(x,y):=12x⊤Qx+x⊤Ry+c⊤x+d⊤y, f(x,y):= 12x Qx+x Ry+c x+d y, (49) s.t. .t. a⊤x+e⊤y≤B,−b≤x≤b,y∈0,1nd. a x+e y≤ B,\ -b≤ x≤ b,\ y∈\0,1\^n_d. For each family we generate S=500S=500 independent instances at each problem size n∈20,50,100,200n∈\20,50,100,200\, yielding a total of 4×5×500=10 0004× 5× 500=10\,000 test instances. Methods We instantiate each of the eight algorithms from Table 1: BCD, GBD with inner BCD, ADMM (penalty ρ=1ρ=1), SCA with quadratic surrogates, primal–dual IPM, Mirror Descent (Bregman variant with entropic mirror map), Frank–Wolfe, and Riemannian gradient descent (for instances admitting a smooth manifold structure). All methods are run to a fixed KKT residual tolerance of ϵKKT=10−6 _KKT=10^-6 or a maximum of Kmax=1 000K_ =1\,000 iterations, whichever comes first. Classifier parameters Unless stated otherwise we use the default parameters Θ=(δ,θ,γ,k)=(0.05,0.7,0.4,2) =(δ,θ,γ,k)=(0.05,0.7,0.4,2) and tolerance ε=10−3 =10^-3. The robustness of the experimental conclusions to these choices is verified by ablation in Section 7.1. Reporting All reported quantities are means across the S independent seeds in the relevant cell, with 95% confidence intervals computed via bootstrapping. Code, random seeds, and instance generators will be released as supplementary material upon publication. 7.2 Emergence and Distribution of Regimes Purpose: Verify that the partition of Section 4.2 captures regimes that occur naturally in the designed families, and that the classifier of Algorithm 1 recovers the intended regime in each family. Protocol: On each instance, after running the eight methods we apply Algorithm 1 to the final multiplier vector and record the regime label. For each family ℱiF_i we report the proportion of instances classified as each regime. Result: Figure 1 reports the empirical distribution of regime labels per family. By design, family ℱiF_i produces dominant regime rir_i in ≥85%≥ 85\% of instances, with the remainder falling into ℛhybR_hyb near regime boundaries. Family ℱ5F_5, designed to lie near transitions, distributes mass across multiple regimes including a higher fraction in ℛhybR_hyb. Figure 1: Empirical distribution of regime labels across problem families, n=100n=100, S=500S=500 instances per family. Each family produces its designed dominant regime in the majority of instances, validating that the partition of Section 4.2 captures meaningful structural distinctions. 7.3 Method-Independence of the Regime Label Purpose:Validate Corollary 4: when distinct algorithms converge to the same KKT point, the classifier returns the same regime label. Protocol: On each instance we run all applicable methods to convergence and record the final multiplier vector λ⋆λ _A produced by each method A. We then restrict attention to instances for which all methods reach the same primal solution to within ‖x⋆−x′⋆‖2≤10−4\|x _A-x _A \|_2≤ 10^-4, and compute the inter-method agreement of regime labels. Result: Table 3 reports pairwise agreement rates. On instances where the methods converge to the same KKT point, agreement is ≥99%≥ 99\% the residual disagreement is attributable to instances near regime boundaries where numerical noise in the multipliers crosses a threshold of Definition 6. This is consistent with Theorem 11: the classification is preserved away from boundaries and is sensitive precisely on the measure-zero transition set characterized by Theorem 7. n Table 3: Pairwise regime-label agreement rates across methods on common-KKT instances (n=100n=100, S=500S=500). Diagonal entries are 100% by construction; off-diagonal entries are means over instances where the methods converge to the same primal solution. BCD GBD ADMM SCA IPM MD BCD 100 100 100 100 100 100 GBD 100 100 100 100 100 ADMM 100 100 100 100 SCA 100 100 100 IPM 100 100 MD 100 7.4 Stability under Data Perturbation Purpose: Validate Theorem 5: the regime label is locally constant under small perturbations of the problem data. Protocol: For each instance in ℱ1F_1–ℱ4F_4 we compute the nominal multiplier λ⋆(ω⋆)λ (ω ) and feature margin ρr(λ⋆) _r(λ ) from Definition 10. We then perturb the data ω⋆↦ω⋆+tξω ω +t\,ξ for ξ∈ℝdξ ^d a random unit vector and t ranging from 00 to 5ρr/(CΨκ)5 _r/(C_ κ) in 3030 steps, re-solve, and record whether the regime label is preserved. Result: Figure 2 shows the empirical preservation probability as a function of normalized perturbation magnitude t⋅CΨκ/ρrt· C_ κ/ _r. The preservation probability is essentially 11 for normalized magnitudes below the theoretical threshold 11, and decays sharply beyond it—matching the prediction of Theorem 5 that the regime label is preserved on the ball of radius ρr/(CΨκ) _r/(C_ κ) in data space. The empirical breakdown point lies within ±10%± 10\% of the theoretical. Figure 2: Probability of regime preservation as a function of normalized perturbation magnitude t⋅CΨκ/ρr(λ⋆)t· C_ κ/ _r(λ ). The vertical dashed line at 11 marks the threshold of Theorem 5; preservation remains near unity below the threshold and decays sharply beyond it. 7.5 Classifier Stabilization along Iterates Purpose: Validate Theorem 12 and Corollary 13: the classifier output stabilizes after a method-specific iteration count. Protocol: For each instance we apply Algorithm 1 to the running multiplier estimate λ^(k) λ^(k) at every iteration. We record k⋆k _A, the smallest iteration after which the classifier output remains constant at the converged value through termination. We then compare k⋆k _A to the theoretical prediction of Corollary 13 using the empirical margin ρr _r and the standard rate function φ _A for each method. Result: Figure 3 reports empirical distributions of k⋆k _A for each method, together with the theoretical bounds. For linearly convergent methods (BCD under KL, IPM in its quadratic phase), k⋆k scales logarithmically in CΨ/ρrC_ / _r. For ADMM and Frank–Wolfe, k⋆k scales linearly. For Mirror Descent, k⋆k scales quadratically. Empirical scaling matches theoretical prediction with R2≥0.95R^2≥ 0.95 across methods. Figure 3: Empirical classifier-stabilization iteration k⋆k _A versus the theoretical bound from Corollary 13, one panel per algorithm. Each point is one instance; the diagonal line marks perfect agreement. The scaling exponents (log, linear, quadratic) match across the algorithm families. 7.6 Sample Complexity from Estimated Data Purpose: Validate Theorem 14: the sample size required for high-confidence regime classification scales as N∝log(1/δ)/ρr2N (1/δ)/ _r^2. Protocol: We fix an instance from ℱ2F_2 with known ρr _r, treat its data ω⋆ω as the population, and generate N-sample estimators ω^N=ω⋆+1N∑i=1Nξi ω_N=ω + 1N _i=1^N _i for ξi∼(0,σ2I) _i (0,σ^2I). For each (N,σ)(N,σ) pair we solve at ω^N ω_N, classify, and report empirical accuracy p^(N,σ):=ℙ(Ψ(λ^N)=r) p(N,σ):=P( ( λ_N)=r) over 1 0001\,000 Monte Carlo replications. We sweep N∈[10,104]N∈[10,10^4] at σ∈0.1,0.3,1.0σ∈\0.1,0.3,1.0\ and several values of ρr _r obtained by varying instance parameters. Result: Figure 4 shows the empirical accuracy curves. The threshold sample size at which p^(N,σ)≥1−δ p(N,σ)≥ 1-δ is well predicted by (37) of Theorem 14. Re-plotting accuracy versus the normalized sample size N⋅ρr2/(σ2log(1/δ))N· _r^2/(σ^2 (1/δ)) collapses the curves onto a single profile, confirming the predicted N∝ρr−2log(1/δ)N _r^-2 (1/δ) scaling. The slope of the empirical N vs ρr−2 _r^-2 relation lies within ±15%± 15\% of the theoretical constant. Figure 4: Sample-complexity validation. (a) Empirical classification accuracy versus sample size N, for instances at three different margins ρr _r and three noise levels σ. (b) Same data plotted against the normalized sample size predicted by Theorem 14; curves collapse onto a universal profile, confirming the N∝ρr−2log(1/δ)N _r^-2 (1/δ) scaling. 7.7 Online Tracking under Bounded Drift Purpose:Validate Theorem 15: the sliding-window classifier tracks the regime correctly so long as the drift rate ν stays below the cubic-in-margin threshold νmax _ . Protocol: We construct a time-varying data sequence ωt=ω⋆+νtu _t=ω +ν\,t\,u for a random unit vector u, with ν∈0.01,0.05,0.1,0.5ν∈\0.01,0.05,0.1,0.5\, and observe yt=ωt+ξty_t= _t+ _t with ξt∼(0,σ2I) _t (0,σ^2I), σ=0.1σ=0.1. At each time t we apply the sliding-window estimator with window W⋆W from (40) and classify the regime. The true regime rtr_t is computed by solving at the noiseless ωt _t and classifying. Result: Figure 5 shows tracking accuracy ℙ(Ψ(λ^t(W⋆))=rt)P( ( λ_t^(W ))=r_t) as a function of drift rate ν. Tracking accuracy stays above 1−δ1-δ for ν<νmaxν< _ predicted by (42), and degrades for larger ν in the manner predicted by (41). The empirical breakdown threshold lies within ±20%± 20\% of the theoretical νmax _ , consistent with the bound’s ν1/3ν^1/3 tracking-error rate. Figure 5: Online tracking accuracy as a function of drift rate ν, for several values of the margin ρr _r. The vertical dashed line marks the theoretical threshold νmax _ from (42); tracking remains accurate below νmax _ and degrades beyond it. 7.8 Phase-like Convergence and Isolated Transitions Purpose: Validate Theorem 7: regime transitions are isolated codimension-one events along generic data paths, and the algorithm trajectory decomposes into finitely many regime-stationary arcs. Protocol: We construct a continuous path ω(s)=(1−s)ωA+sωBω(s)=(1-s) _A+s _B between two data points ωA,ωB _A, _B chosen to lie in different regimes. We compute the KKT solution λ⋆(ω(s))λ (ω(s)) at s∈[0,1]s∈[0,1] at fine resolution and record the regime label Ψ(λ⋆(ω(s))) (λ (ω(s))) as a function of s. Result: Figure 6 shows the regime trajectory along s. Transitions occur at a small number of isolated values s1<s2<⋯s_1<s_2<·s, between which the regime label is constant. At each transition exactly one feature crosses its threshold, in agreement with Theorem 7(a). Across 500500 random paths, the number of transitions per path is mean ≈2≈ 2–33 with no path having more than 55 transitions, consistent with the codimension-one structure. Figure 6: Phase-like convergence along a data path from ωA _A to ωB _B. Top: regime label as a function of s, showing isolated transitions. Bottom: the four feature values L,Σk,σδ,τL, _k, _δ,τ along the path with their thresholds marked; each transition corresponds to exactly one feature crossing its threshold, validating Theorem 7. 7.9 A Wireless-Flavored Instance Purpose: Illustrate how the regime taxonomy applies to a representative problem from the application domain that motivates this work. Setup: We consider a multi-user downlink beamforming problem with K=8K=8 single-antenna users and an M=16M=16-antenna transmitter, with sum-power constraint P and minimum-SINR constraint γk _k for each user: maxwkk=1K _\w_k\_k=1^K ∑k=1Klog(1+SINRk(w)) _k=1^K (1+SINR_k(w) ) (50) s.t. .t. ∑k=1K∥wk∥2≤P,SINRk(w)≥γk∀k. _k=1^K\|w_k\|^2≤ P, _k(w)≥ _k\ ∀ k. We vary P and the per-user γk _k and apply the classifier of Algorithm 1 to the multipliers at the converged solution. Result: Figure 7 reports the regime as a function of (P,γ¯)(P, γ) where γ¯ γ is the average minimum-SINR. At large P and small γ¯ γ the solution lies in ℛuncR_unc (neither constraint binds meaningfully). At small P and small γ¯ γ the sum-power constraint dominates and the regime is ℛresR_res. At large P and large γ¯ γ many QoS constraints bind and the regime is ℛsatR_sat. Boundary regions between these three regions yield ℛhybR_hyb. This regime structure reflects the physical interpretation of the problem and provides a structural certificate that downstream wireless papers can use to dispatch tailored algorithms in each regime. Figure 7: Regime classification of the downlink beamforming problem (50) as a function of sum-power budget P and average minimum-SINR γ¯ γ. The four core regimes occupy distinct regions in the (P,γ¯)(P, γ)-plane, separated by thin transition zones identified as ℛhybR_hyb. 7.10 Summary of Numerical Evidence Across the 8 experimental blocks, the numerical evidence is consistent with each of the theoretical predictions of Sections 5–6. In particular: regimes emerge as predicted in problems designed to elicit them (Section 7.2); the classifier is method-independent on common-KKT instances (Section 7.3); the regime label is stable under small perturbations with breakdown at the theoretically predicted threshold (Section 7.4); the classifier stabilizes along algorithm trajectories at the predicted scaling rates (Section 7.5); sample complexity scales as ρr−2log(1/δ) _r^-2 (1/δ) (Section 7.6); online tracking succeeds below the cubic-in-margin drift threshold (Section 7.7); transitions are isolated and feature-driven (Section 7.8); and the taxonomy yields physically meaningful structure on representative wireless instances (Section 7.9). 8 Discussion, Limitations, and Future Work 8.1 Summary of Contributions This paper has developed a structural theory of operational regimes for constrained optimization, motivated by a unified game-theoretic reading of eight classical algorithm families. The contributions can be summarized as follows. 1. A unifying equilibrium template (Section 3, Proposition 1). Block Coordinate Descent, Generalized Benders Decomposition, ADMM, Successive Convex Approximation, Interior-Point Methods, Mirror Descent, Frank–Wolfe, and Riemannian gradient descent are all instances of the equilibrium-seeking template (6), with fixed points coinciding with KKT triples of an associated (sub)problem. This consolidates classical results scattered across the optimization, game-theory, and online-learning literatures into a single statement (Table 1). 2. A regime taxonomy as a partition of the multiplier space (Section 4, Definitions 6–7). Four scale-free shape features of the Lagrange multiplier vector (L,Σk,σδ,τL, _k, _δ,τ) induce a five-element partition of ℝ+mR^m_+: four open core regimes plus the Hybrid regime as the topological boundary. 3. Four structural theorems (Section 5). Theorem 3 establishes invariance of the classification under the natural symmetries of the KKT system (permutation, uniform rescaling, and C2C^2 diffeomorphism). Theorem 5 establishes local constancy of the classification under perturbations of problem data, with an explicit Lipschitz-style margin bound rooted in Robinson’s strong regularity. Theorem 7 characterizes transitions as codimension-one events on the data manifold and shows that generic trajectories cross only finitely many transitions. Theorem 8 identifies the Hybrid regime as the topological boundary of the union of core regimes, of Lebesgue measure zero, with the property that every Hybrid point is approached by at least two distinct core regimes. 4. The regime classifier and its guarantees (Section 6, Algorithm 1, Theorems 11–15). The classifier runs in (m)O(m) time per call and admits four complementary guarantees: correctness under deterministic multiplier perturbation; classifier-stabilization iteration counts for each algorithmic family (logarithmic for linearly convergent methods, linear for (1/k)O(1/k) methods, quadratic for (1/k)O(1/ k) methods); sample complexity N∝ρr−2log(1/δ)N _r^-2 (1/δ) for finite-data deployments; and online tracking under bounded drift up to a cubic-in-margin threshold. 5. Empirical validation (Section 7). Numerical experiments on five families of MINLPs confirm each theoretical prediction in turn, and a downlink beamforming instance illustrates the application of the taxonomy in a wireless setting. 8.2 Implications for Algorithm Design The most immediate algorithmic implication is that the regime label, as a constant-time-computable structural certificate of the converged solution, can be used to dispatch tailored solvers, surrogates, or step-size rules. A regime-aware meta-algorithm operates by interleaving short solver bursts with classifier calls and switching its inner strategy when the regime stabilizes or transitions. The conceptual outline is as follows: • In ℛuncR_unc, where the geometry is gradient-dominated, unaccelerated first-order methods (BCD, gradient descent) are competitive, and aggressive step sizes are admissible. • In ℛresR_res, the few active resource constraints suggest specialized handling: active-set updates, dual decomposition along the binding constraints, or projection onto the active manifold. • In ℛsatR_sat, with many variables at bounds, coordinate methods with active-set acceleration and reduced-space inner solvers are appropriate. • In ℛcoupR_coup, with significant inter-block coupling, primal–dual splitting methods (ADMM, PDHG) and consensus-aware preconditioners are warranted. • In ℛhybR_hyb, regime detection signals proximity to a transition and may motivate switching strategies or model refinement, since the iterate is near a structurally ambiguous point identified by Theorem 8. A formal development of regime-aware meta-algorithms, including convergence-rate analysis under regime switching, is left to future work. 8.3 Limitations We note four limitations of the present framework, each suggesting a natural avenue for refinement. Constraint qualifications. The results of Section 5 are developed under Assumption 1 (LICQ + SOSC), augmented by strict complementarity where needed (Theorems 5, 7). These conditions exclude problems with degenerate active sets, in which multipliers may be non-unique or the KKT solution map may fail to be C1C^1. Extending the regime taxonomy to the MFCQ setting, where multipliers form a polytope, is an interesting direction; the natural generalization would classify the multiplier polytope rather than a unique multiplier vector. Computation of structural constants. The theorems are stated in terms of three constants—the KKT-system conditioning κ, the feature-map Lipschitz constant CΨC_ , and the feature-space margin ρr _r—that are problem-dependent and not always available in closed form. While ρr _r is directly computable from a single solve (Definition 10), κ and CΨC_ require either structural problem analysis or empirical estimation. Refined bounds in specific problem classes (e.g., quadratically constrained quadratic programs, separable problems, semidefinite programs) would tighten the operational forms of Theorems 11–15. Parameter selection. The regime classification depends on the quadruple Θ=(δ,θ,γ,k) =(δ,θ,γ,k). We have demonstrated robustness under variations of Θ in the experiments, but a principled procedure for selecting Θ from problem data—ideally with theoretical guarantees on the resulting classification—remains open. One promising direction is to choose thresholds adaptively via clustering on the empirical multiplier distribution, with consistency guarantees inherited from density-estimation theory. Global versus local guarantees. The taxonomy classifies stationary points, which in the non-convex case may not be global minima. The regime of a local minimum need not equal the regime of the global optimum, and the classifier output thus inherits the non-convexity limitations of the underlying solver. This is unavoidable in the general non-convex setting, but in specific structured non-convex problems (e.g., problems with hidden convexity, or problems amenable to convex relaxation) sharper statements may be possible. 8.4 Future Directions The framework of this paper opens several lines of inquiry, falling broadly into three categories. Theoretical extensions The structural theory of regimes admits several natural extensions. First, the MFCQ generalization noted above. Second, an extension to non-smooth objectives via subdifferential calculus and the Clarke stationarity condition, which would broaden the applicability to non-smooth machine learning losses. Third, a more refined analysis of the Hybrid regime as a stratified object: ℛhybR_hyb decomposes by which boundary inequality is tight, and each stratum has its own local geometry. Fourth, the development of higher-order regime invariants (beyond the multiplier shape) that capture finer structural distinctions, perhaps through second-order Lagrange-multiplier sensitivities. Hierarchical Regime Refinement Develop a multi-level taxonomy by introducing operationally meaningful sub-regimes (e.g., power-limited, interference-limited, and QoS-limited variants inside the resource-limited regime). This extension is particularly relevant for wireless resource allocation problems and will be explored in a companion paper. Algorithmic extensions On the algorithmic side, the natural next step is a regime-aware meta-algorithm with provable rate guarantees. A specific question is whether the worst-case rate of such a meta-algorithm can match the best regime-specific rate, and whether the overhead of regime detection is asymptotically dominated by the per-regime solver work. Stochastic optimization is a particularly fertile setting: the sample-complexity bound of Theorem 14 is the natural primitive for finite-sample stochastic optimization, and regime-aware variance-reduction methods may inherit improved sample complexity in low-margin instances. Application domains The taxonomy applies in principle to any constrained nonlinear optimization problem, but several application domains are particularly natural. In wireless communications, the natural problems—resource allocation, beamforming, power control, scheduling, network slicing—exhibit precisely the constraint structure (resource budgets, QoS bounds, coupling constraints) that the regimes were designed to identify. The classifier-aided algorithms developed under the framework of this paper provide structural primitives for wireless system design under uncertainty. A series of forthcoming companion papers develops these instantiations in detail. Beyond wireless, the framework is applicable to power-systems optimization, optimal control under constraints, structured machine learning (e.g., constrained reinforcement learning), and operations research more broadly. Cross-disciplinary connections The equilibrium reading of Section 3, together with the multiplier-based structural theory, invites connections to neighboring fields. In economics, the regime taxonomy parallels classifications of market equilibria by which scarcity constraints bind; in control, the transition theorem resonates with the theory of switching systems and hybrid dynamical systems; in learning theory, the no-regret view of Mirror Descent and Frank–Wolfe (Section 3.6, Section 3.7) suggests regret bounds under regime switching, extending recent work on adversarial online optimization. We see these cross-disciplinary connections as the most exciting frontier opened by the present work. 9 Conclusion We have presented a structural theory of operational regimes for constrained optimization, motivated by a unified game-theoretic reading of eight classical algorithm families. The central object is the regime classification map Ψ , which assigns to each KKT multiplier vector one of five labels (Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, Hybrid) based on four scale-free features. Four structural theorems establish that this classification is invariant under the natural symmetries of the KKT system, locally constant under perturbation of problem data, characterized by isolated codimension-one transitions along data paths, and bordered by a topologically precise Hybrid set. A regime classifier (Algorithm 1) computes Ψ in linear time per call and admits four guarantees—deterministic correctness, classifier-stabilization along solver trajectories, sample complexity, and online tracking under drift—that turn the taxonomy into a computational primitive available to downstream papers. The unifying message is that, beneath the surface differences among optimization algorithms, the multipliers they compute carry a compact, method-independent structural signature. Recognizing this signature opens a path to regime-aware algorithm design, to robust certification of solution structure under noise and drift, and to a structural language that connects the theory of constrained optimization with the equilibrium theory of games. We see the present paper as a foundation on which a series of follow-up works, both theoretical and applied, will build. References Beck and Tetruashvili (2013) Beck, A., Tetruashvili, L.: On the convergence of block coordinate descent type methods. SIAM Journal on Optimization 23(4), 2037–2060 (2013) Monderer and Shapley (1996) Monderer, D., Shapley, L.S.: Potential games. Games and Economic Behavior 14(1), 124–143 (1996) https://doi.org/10.1006/game.1996.0044 Tseng (2001) Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. Journal of Optimization Theory and Applications 109(3), 475–494 (2001) Attouch et al. (2013) Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized gauss–seidel methods. Mathematical Programming 137, 91–129 (2013) Razaviyayn et al. (2013) Razaviyayn, M., Hong, M., Luo, Z.-Q.: A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM Journal on Optimization 23(2), 1126–1153 (2013) Geoffrion (1972) Geoffrion, A.M.: Generalized benders decomposition. Journal of Optimization Theory and Applications 10(4), 237–260 (1972) von Stackelberg (1934) Stackelberg, H.: Marktform und Gleichgewicht. Julius Springer, Berlin (1934) Başar and Olsder (1999) Başar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory, 2nd edn. SIAM, Philadelphia, PA (1999) Boyd et al. (2011) Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3(1), 1–122 (2011) He and Yuan (2012) He, B., Yuan, X.: On the (1/n)O(1/n) convergence rate of the douglas–rachford alternating direction method. SIAM Journal on Numerical Analysis 50(2), 700–709 (2012) Eckstein and Bertsekas (1992) Eckstein, J., Bertsekas, D.P.: On the douglas–rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming 55, 293–318 (1992) Scutari et al. (2014) Scutari, G., Facchinei, F., Song, P., Palomar, D.P., Pang, J.-S.: Decomposition by partial linearization: Parallel optimization of multi-agent systems. IEEE Transactions on Signal Processing 62(3), 641–656 (2014) Scutari et al. (2017) Scutari, G., Facchinei, F., Lampariello, L.: Parallel and distributed methods for constrained nonconvex optimization—part i: Theory. IEEE Transactions on Signal Processing 65(8), 1929–1944 (2017) Sun et al. (2017) Sun, Y., Babu, P., Palomar, D.P.: Majorization-minimization algorithms in signal processing, communications, and machine learning. IEEE Transactions on Signal Processing 65(3), 794–816 (2017) https://doi.org/10.1109/TSP.2016.2601299 Nemirovsky and Yudin (1983) Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York, NY (1983) Beck and Teboulle (2003) Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters 31, 167–175 (2003) Jaggi (2013) Jaggi, M.: Revisiting frank-wolfe: Projection-free sparse convex optimization. In: Proc. International Conference on Machine Learning (ICML), p. 427–435 (2013) Lacoste-Julien and Jaggi (2015) Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of frank-wolfe optimization variants. In: Advances in Neural Information Processing Systems (NeurIPS), p. 496–504 (2015) Hazan (2008) Hazan, E.: Sparse approximate solutions to semidefinite programs. In: Latin American Theoretical Informatics Symposium (LATIN), p. 306–316 (2008) Absil et al. (2008) Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton, NJ (2008) Boumal (2023) Boumal, N.: An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge (2023) Nesterov and Nemirovski (1994) Nesterov, Y., Nemirovski, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, PA (1994) Wright (1997) Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia, PA (1997) Forsgren et al. (2002) Forsgren, A., Gill, P.E., Wright, M.H.: Interior methods for nonlinear optimization. SIAM Review 44(4), 525–597 (2002) Boucheron et al. (2013) Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford (2013) Bonnans and Shapiro (2000) Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York, NY (2000) Nash (1950) Nash, J.: Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36(1), 48–49 (1950) https://doi.org/10.1073/pnas.36.1.48 Nash (1951) Nash, J.: Non-cooperative games. Annals of Mathematics 54(2), 286–295 (1951) https://doi.org/10.2307/1969529 Vershynin (2018) Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, Cambridge (2018) Facchinei and Pang (2003) Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York, NY (2003) Hong et al. (2016) Hong, M., Luo, Z.-Q., Razaviyayn, M.: Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM Journal on Optimization 26(1), 337–364 (2016) Bubeck (2015) Bubeck, S.: Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning 8(3–4), 231–357 (2015) Cesa-Bianchi and Lugosi (2006) Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, Cambridge (2006) Boumal et al. (2019) Boumal, N., Absil, P.-A., Cartis, C.: Global rates of convergence for nonconvex optimization on manifolds. IMA Journal of Numerical Analysis 39(1), 1–33 (2019) Nocedal and Wright (2006) Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York, NY (2006) Hazan and Kale (2012) Hazan, E., Kale, S.: Projection-free Online Learning (2012). https://arxiv.org/abs/1206.4657 Chen et al. (2018) Chen, L., Harshaw, C., Hassani, H., Karbasi, A.: Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity (2018). https://arxiv.org/abs/1802.08183 Hestenes (1969) Hestenes, M.R.: Multiplier and gradient methods. Journal of Optimization Theory and Applications 4(5), 303–320 (1969) Powell (1969) Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, p. 283–298. Academic Press, London (1969) Rockafellar (1976) Rockafellar, R.T.: Augmented lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Research 1(2), 97–116 (1976) Combettes and Wajs (2005) Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Modeling and Simulation 4(4), 1168–1200 (2005) Beck and Teboulle (2009) Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences 2(1), 183–202 (2009) Parikh and Boyd (2014) Parikh, N., Boyd, S.: Proximal algorithms. Foundations and Trends in Optimization 1(3), 127–239 (2014) Chambolle and Pock (2011) Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40(1), 120–145 (2011) Robinson (1980) Robinson, S.M.: Strongly regular generalized equations. Mathematics of Operations Research 5(1), 43–62 (1980) Sard (1942) Sard, A.: The measure of the critical values of differentiable maps. Bulletin of the American Mathematical Society 48(12), 883–890 (1942) Blum et al. (1973) Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences 7(4), 448–461 (1973) Musser (1997) Musser, D.R.: Introspective sorting and selection algorithms. Software: Practice and Experience 27(8), 983–993 (1997) Cormen et al. (2022) Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 4th edn. MIT Press, Cambridge, MA (2022) Nesterov (2018) Nesterov, Y.: Lectures on Convex Optimization, 2nd edn. Springer, Cham (2018)