Theoretical analysis and numerical experiments show the proposed methods substantially outperform the existing approaches to solve monotone linear-quadratic v-GNE problems.
Abstract
We consider generalized Nash equilibrium problems among $N$ players with convex quadratic costs and shared affine constraints, assuming only that the game's pseudogradient is merely monotone. We show that computing a variational generalized Nash equilibrium (v-GNE) is equivalent to solving a single convex quadratic program (QP) derived from the players'joint Karush--Kuhn--Tucker conditions. Building on this, we show that the regularization of such a QP yields an $\varepsilon$-approximated v-GNE with suboptimality vanishing linearly in the regularization parameter. Next, we propose an accelerated proximal-point scheme and an accelerated projected-gradient method, both attaining an $\mathcal O(1/k^2)$-approximated v-GNE at the $k$-th iteration. We also demonstrate that an invertible Jacobian of the game allows for reduction to a lower-dimensional QP. Theoretical analysis and numerical experiments show the proposed methods substantially outperform the existing approaches to solve monotone linear-quadratic v-GNE problems.
This work proposes a nonlinear-residual linearized augmented Lagrangian method (NR-LALM) that replaces this subproblem by a regularized Gauss-Newton-type step while retaining the classical multiplier update based on the nonlinear constraint residual.
Benqi Liu, Kangkang Deng, Zichen Wang et al.· 0 citations
We consider convex optimization with nonlinear inequality constraints and develop a primal--dual multiplier framework that is consistent in continuous and discrete time. We first propose continuous-time dynamics with Nesterov-type vanishing damping $\alpha/t$, together with suitable extrapolations of the dual variable and the nonlinear constraint mapping. Under convexity assumptions and $\alpha\geq3$, we establish $\mathcal O(t^{-2})$ convergence rates for both nonlinear feasibility and the objective residual. We then derive an inexact accelerated primal--dual algorithm through a compatible discretization of a perturbed version of the dynamics. For composite convex objectives, a weighted summability condition on the primal inexactness yields the $\mathcal O(k^{-2})$ rates for feasibility and the objective residual, thereby matching the accelerated rates of their continuous-time counterparts. To the best of our knowledge, this is the first Nesterov-type primal--dual multiplier framework for convex optimization with nonlinear inequality constraints.
Finite-player nonzero-sum optimal stopping games typically lead to coupled equilibrium systems whose complexity grows rapidly with the number of players. We introduce an independently randomized formulation in which each stopping rule is represented by an adapted, nondecreasing cumulative stopping process. The canonical embedding preserves pure-profile payoffs, and a pure profile is a Nash equilibrium of the original game if and only if its embedding is a Nash equilibrium of the randomized game. We adopt the $\alpha$-potential approach to construct an $\alpha_N$-potential function, with the error $\alpha_N=O(N^{-1})$ under weak-interaction. We also identify an exact-potential subclass with a closed-form threshold equilibrium. For local stopped-status interactions, randomized payoffs admit a local stopped-mass representation, and potential maximization can be formulated as a multidimensional singular-control problem with local gradient constraints and a nonlocal condition for finite jumps. Under suitable regularity assumptions, we study the associated Hamilton-Jacobi-Bellman quasi-variational inequality and its regularity properties. For unknown model coefficients, we propose a bounded-intensity Potential-CT-DDPG learning algorithm. Numerical experiments closely match the analytical benchmark and yield estimated best-response improvements consistent with $N^{-1}$ scaling.
This paper studies $N$-player stochastic linear-quadratic (LQ) differential games from the perspective of $\alpha$-potential games. We first consider a closed-loop LQ game with multiplicative noise, where both the drift and the diffusion coefficients depend linearly on the state and the full control vector. For this model, we derive probabilistic and partial differential equation (PDE) representations for the first- and second-order linear derivatives of the players'cost function and prove the equivalence between them. We then develop an open-loop stochastic LQ \(\alpha\)-potential game framework. Using the linear derivative construction, we build an \(\alpha\)-potential function and derive an explicit upper bound for the approximation parameter \(\alpha\) in terms of the model coefficients and the admissible control radius. Moreover, the minimization of the \(\alpha\)-potential function is reduced to a finite-dimensional stochastic control problem by augmenting the state with the variational process, which yields an open-loop \(\alpha\)-Nash equilibrium. As an application, we revisit a network LQ game considered in \cite{GuoLiZhang2025} and show that the feedback representation obtained from our approach coincides with the feedback in the existing conditional McKean--Vlasov approach, while our characterization follows directly from a standard finite-dimensional LQ control problem.
Quadratic optimization becomes hard as soon as either the matrix in the quadratic form has an unfavorable curvature or the feasible set is discrete, combinatorial, or otherwise nonconvex. A complementary phenomenon is also well known in the signal-processing and optimization communities: when the matrix in the quadratic form has small rank, some hard-looking quadratic programs admit exact polynomial-time algorithms for fixed rank. We study the common positive-semidefinite geometry behind this phenomenon. If $Q=BB^\top$ is positive semidefinite, the objective depends on $x$ only through the rank-space shadow $y=B^\top x$. Every optimal shadow $y^*$ uniquely maximizes the linear functional defined by its own direction and satisfies a quantitative quadratic margin. Thus nonlinear optimality collapses to a low-dimensional, self-generated linear exposure direction. We call this the rank-collapse principle. The principle alone does not imply a finite candidate set: efficient exact optimization additionally depends on the projected or active geometry of the feasible family. We organize this distinction through projected-shadow scattering and active-structure collapse, relate it explicitly to established zonotope, convex-combinatorial, edge-skeleton, projected-normal-fan, and fixed-rank sparse-PCA methods, and derive tie-safe consequences for binary and finite-phase vectors, cardinality constraints, matroid bases, and sparse PCA. We also give directional-stability and approximately low-rank certificates, together with reproducible experiments. The paper's contribution is a unified, careful framework and a set of quantitative consequences, rather than a claim to originate the known fixed-rank tractability results that motivate it.
Featuring Hessian-driven damping, two inertial primal dual dynamical systems are proposed for solving smooth saddle point problems with bilinear coupling. For convex-concave functions, we establish a convergence rate $\mathcal{O}\left( \frac{1}{t^2} \right)$ for the primal dual gap; for strongly convex-strongly concave functions, we obtain an asymptotic rate $\mathcal{O}\left( \frac{1}{t^{\alpha-1}} \right)$ ($\alpha\ge 3$ is the damping parameter) without knowledge of the strong convexity parameters, and an accelerated linear convergence rate when the strong convexity parameters are known. As an application of the proposed inertial systems, we also consider the affinely constrained convex optimization problem, and develop an inertial system with Hessian-driven damping, which complements existing results.
Zepeng Wang, J. Peypouquet· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
