Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints

# Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints
Source: [https://arxiv.org/html/2605.16262](https://arxiv.org/html/2605.16262)
11institutetext:Innopolis University, Innopolis, Universitetskaya Str\., 1, 420500, Russia\.22institutetext:Moscow Institute of Physics and Technology, 9 Institutsky lane, Dolgoprudny, 141701, Russia\.33institutetext:V\. I\. Vernadsky Crimean Federal University, 4 Academician Vernadsky Avenue, Simferopol, 295007, Republic of Crimea, Russia\.
33email:m\.alkousa@innopolis\.ru, fedyor@mail\.ru, alashkar\.ba@phystech\.edu, seydamet\.ablaev@yandex\.ru###### Abstract

Variational inequalities play a key role in machine learning research, such as generative adversarial networks, reinforcement learning, adversarial training, and generative models\. This paper is devoted to the constrained variational inequality problems with functional constraints \(inequality\-type constraints\)\. We propose some mirror descent\-type algorithms that switch between productive and non\-productive steps depending on the values of the functional constraints at iterations, with many different step size rules and stopping criteria\. We analyze the proposed algorithms and prove their optimal convergence rate to achieve a solution with desired accuracy, for problems with bounded and monotone operators and Lipschitz convex functional constraints\. In addition, we propose a modification of the proposed algorithms by considering each functional constraint in the calculation when we have a productive step, as well as the first constraint that violates the feasibility\. This modification can save the running time of algorithms when we have many functional constraints\. In addition, we provide an analysis of the proposed algorithms forδ\\delta\-monotone operators, allowing us to apply the proposed algorithms, as a special case, to constrained minimization problems when we do not have access to the exact information about the subgradient of the objective function\. Numerical experiments that illustrate the work and performance of the proposed algorithms are also given\.

## Introduction

Variational inequalities \(VIs\) cover, as a special case, many optimization problems such as minimization problems, saddle point problems, and fixed point problems\. They often arise in various mathematical problems, such as optimal control, partial differential equations, mechanics, finance, etc\. They play a key role in solving equilibrium and complementarity problems\[[1](https://arxiv.org/html/2605.16262#bib.bib1)\], in machine learning research such as generative adversarial networks\[[2](https://arxiv.org/html/2605.16262#bib.bib2)\], supervised/unsupervised learning\[[3](https://arxiv.org/html/2605.16262#bib.bib3),[4](https://arxiv.org/html/2605.16262#bib.bib4)\], adversarial training\[[5](https://arxiv.org/html/2605.16262#bib.bib5)\], and generative models\[[6](https://arxiv.org/html/2605.16262#bib.bib6),[7](https://arxiv.org/html/2605.16262#bib.bib7)\]\.

Numerous researchers have dedicated their efforts to exploring theoretical aspects related to the existence and stability of solutions and constructing iterative methods for solving the classical VIs \(by classical, we mean the problems without functional ”inequality\-type” constraints\)\. A significant contribution to the development of numerical methods for solving the classical VIs was made in the 1970s, when the extragradient method was proposed in\[[8](https://arxiv.org/html/2605.16262#bib.bib8)\]\. More recently, Nemirovski in his seminal work\[[9](https://arxiv.org/html/2605.16262#bib.bib9)\]proposed a non\-Euclidean variant of this method, called the Mirror Prox algorithm, which can be applied to Lipschitz continuous operators\. Different methods with similar complexity were also proposed in\[[10](https://arxiv.org/html/2605.16262#bib.bib10),[11](https://arxiv.org/html/2605.16262#bib.bib11)\]\. Besides that, in\[[11](https://arxiv.org/html/2605.16262#bib.bib11)\], Nesterov proposed a method for variational inequalities with a bounded variation of the operator, i\.e\., with a non\-smooth operator\. There is also extensive literature on variations of the extragradient method that avoid taking two steps or two gradient computations per iteration, and so on \(see, for example\[[12](https://arxiv.org/html/2605.16262#bib.bib12)\]\)\.

Another important class of VIs is the problem with functional constraints \(inequality\-type\), see \([4](https://arxiv.org/html/2605.16262#S1.E4)\) and \([7](https://arxiv.org/html/2605.16262#S1.E7)\)\. The presence of such constraints makes these problems more difficult to solve\. This class of problems arises in many fields of mathematics, among them are economic equilibrium models\[[13](https://arxiv.org/html/2605.16262#bib.bib13)\], constrained Markov potential games\[[14](https://arxiv.org/html/2605.16262#bib.bib14),[15](https://arxiv.org/html/2605.16262#bib.bib15)\], generalized Nash equilibrium problems with jointly\-convex constraints\[[16](https://arxiv.org/html/2605.16262#bib.bib16)\], hierarchical programming problems\[[17](https://arxiv.org/html/2605.16262#bib.bib17)\], and in mathematical physics\[[18](https://arxiv.org/html/2605.16262#bib.bib18)\]\. See\[[19](https://arxiv.org/html/2605.16262#bib.bib19)\]for more details and examples\. In addition, this class of problems encompasses important applications in machine learning, including reinforcement learning with safety constraints\[[20](https://arxiv.org/html/2605.16262#bib.bib20)\], and learning with fairness constraints\[[21](https://arxiv.org/html/2605.16262#bib.bib21),[22](https://arxiv.org/html/2605.16262#bib.bib22)\]\.

For VIs with functional constraints, the previous works have focused on primal\-dual algorithms based on the \(augmented\) Lagrangian function to handle the constraints and penalty methods\[[23](https://arxiv.org/html/2605.16262#bib.bib23),[24](https://arxiv.org/html/2605.16262#bib.bib24),[25](https://arxiv.org/html/2605.16262#bib.bib25)\]\. These algorithms and their convergence guarantees crucially depend on information about the optimal Lagrange multipliers\. In\[[26](https://arxiv.org/html/2605.16262#bib.bib26)\], a primal method was proposed without knowing any information on the optimal Lagrange multipliers, and its convergence rate was proved for the problem with monotone operators under smooth constraints\. In\[[27](https://arxiv.org/html/2605.16262#bib.bib27)\], a first\-order method \(ACVI\) was presented, which combines path\-following interior point methods and primal\-dual methods\. In\[[28](https://arxiv.org/html/2605.16262#bib.bib28)\], the authors proposed a primal\-dual approach to solve the VIs with general functional constraints by taking the last iteration of ACVI\. Although there are many works for the VIs with functional constraints, they remain very few compared to the existing works for the classical constrained problem\.

In this paper, to solve the variational inequality problem with functional constraints \(inequality\-type\) \([4](https://arxiv.org/html/2605.16262#S1.E4)\) and \([7](https://arxiv.org/html/2605.16262#S1.E7)\), we propose various mirror descent\-type methods with different step size schemes\. The mirror descent method, for minimization problems, originated in\[[29](https://arxiv.org/html/2605.16262#bib.bib29),[30](https://arxiv.org/html/2605.16262#bib.bib30)\]and was later analyzed in\[[31](https://arxiv.org/html/2605.16262#bib.bib31)\]\. It is considered as a non\-Euclidean extension of standard subgradient methods, which have a long history starting with the method for deterministic unconstrained problems and Euclidean setting in\[[32](https://arxiv.org/html/2605.16262#bib.bib32)\]and the generalization for constrained problems in\[[33](https://arxiv.org/html/2605.16262#bib.bib33),[34](https://arxiv.org/html/2605.16262#bib.bib34)\], where the idea of step’s switching between the direction of subgradient of the objective and the direction of subgradient of the constraint was suggested\. The Mirror Descent method not only generalizes the standard subgradient methods but also achieves a better convergence rate\[[35](https://arxiv.org/html/2605.16262#bib.bib35)\]\. It is also applicable to optimization problems in Banach spaces where gradient descent is not\[[35](https://arxiv.org/html/2605.16262#bib.bib35)\]\. Some of the works on first\-order methods for convex optimization problems with convex functional constraints include \(for example, but not limited to\)\[[36](https://arxiv.org/html/2605.16262#bib.bib36),[37](https://arxiv.org/html/2605.16262#bib.bib37),[38](https://arxiv.org/html/2605.16262#bib.bib38),[39](https://arxiv.org/html/2605.16262#bib.bib39)\]for the deterministic setting and\[[40](https://arxiv.org/html/2605.16262#bib.bib40),[41](https://arxiv.org/html/2605.16262#bib.bib41)\]for the stochastic setting\.

The paper consists of an introduction and five main sections, in addition to four appendices\. In Sect\.[1](https://arxiv.org/html/2605.16262#S1)we mentioned some basic facts, definitions, and tools for variational inequalities\. Sect\.[2](https://arxiv.org/html/2605.16262#S2)is devoted to the proposed algorithms\. We proposed 7 algorithms, with different step size rules and stopping criteria\. In Sect\.[3](https://arxiv.org/html/2605.16262#S3)we analyzed the proposed algorithms and proved their optimal convergence rate for the class of variational inequality problems with bounded monotone operators and Lipschitz functional constraints\. In Sect\.[4](https://arxiv.org/html/2605.16262#S4), we propose a modification of the proposed algorithms in the previous section\. In this modification, we consider each constraint in the calculation when we have a productive step, and the first constraint that violates the feasibility\. In Sect\.[5](https://arxiv.org/html/2605.16262#S5)we present numerical experiments that compare the proposed algorithms for some constrained variational inequality and saddle point problems\. In the last Section[6](https://arxiv.org/html/2605.16262#S6), we review the obtained results\. In the appendices, we provide the proofs of the theorems about the analysis of the proposed algorithms, in addition to their analysis when the operator isδ\\delta\-monotone\. We also provide additional experiments concerning the Forsaken game\.

## 1Fundamentals

Let\(𝐄,∥⋅∥\)\(\\mathbf\{E\},\\\|\\cdot\\\|\)be a normed finite\-dimensional vector space, with an arbitrary norm∥⋅∥\\\|\\cdot\\\|, and𝐄∗\\mathbf\{E\}^\{\*\}be the conjugate space of𝐄\\mathbf\{E\}with the following norm

‖y‖∗=maxx∈𝐄⁡\{⟨y,x⟩:‖x‖≤1\},\\\|y\\\|\_\{\*\}=\\max\\limits\_\{x\\in\\mathbf\{E\}\}\\\{\\langle y,x\\rangle:\\\|x\\\|\\leq 1\\\},where⟨y,x⟩\\langle y,x\\rangleis the value of the continuous linear functionaly∈𝐄∗y\\in\\mathbf\{E\}^\{\*\}atx∈𝐄x\\in\\mathbf\{E\}\.

LetQ⊂𝐄Q\\subset\\mathbf\{E\}be a convex compact set with a diameterD\>0D\>0, andψ:Q⟶ℝ\\psi:Q\\longrightarrow\\mathbb\{R\}be a proper closed differentiable andσ\\sigma\-strongly convex \(called prox\-function or distance generating function\)\. The corresponding Bregman divergence is defined as

V​\(x,y\)=ψ​\(x\)−ψ​\(y\)−⟨∇ψ​\(y\),x−y⟩∀x,y∈Q\.V\(x,y\)=\\psi\(x\)\-\\psi\(y\)\-\\langle\\nabla\\psi\(y\),x\-y\\rangle\\quad\\forall x,y\\in Q\.For the Bregman divergence, it holds the following inequality

V​\(x,y\)≥σ2​‖y−x‖2∀x,y∈Q\.V\(x,y\)\\geq\\frac\{\\sigma\}\{2\}\\\|y\-x\\\|^\{2\}\\quad\\forall x,y\\in Q\.\(1\)
For allx∈Qx\\in Qandp∈𝐄∗p\\in\\mathbf\{E\}^\{\*\},the proximal mapping operatoris defined as follows

Mirrx⁡\(p\)=arg⁡minu∈Q⁡\{⟨p,u⟩\+V​\(u,x\)\}\.\\operatorname\{Mirr\}\_\{x\}\(p\)=\\arg\\min\\limits\_\{u\\in Q\}\\big\\\{\\langle p,u\\rangle\+V\(u,x\)\\big\\\}\.We make the simplicity assumption, which means thatMirrx⁡\(p\)\\operatorname\{Mirr\}\_\{x\}\(p\)is easily computable\.

The following well\-known lemma describes the main property of the proximal mapping operator for a convex function\.

###### Lemma 1

Letf:Q⟶ℝf:Q\\longrightarrow\\mathbb\{R\}be a convex subdifferentiable function over the convex setQQandz=Mirry⁡\(h​∇f​\(y\)\)z=\\operatorname\{Mirr\}\_\{y\}\(h\\nabla f\(y\)\)for someh\>0h\>0andy,z∈Qy,z\\in Q\. Then for eachx∈Qx\\in Qwe have

h​\(f​\(y\)−f​\(x\)\)≤h​⟨∇f​\(y\),y−x⟩≤h22​‖∇f​\(y\)‖∗2\+V​\(x,y\)−V​\(x,z\)\.h\\left\(f\(y\)\-f\(x\)\\right\)\\leq h\\langle\\nabla f\(y\),y\-x\\rangle\\leq\\frac\{h^\{2\}\}\{2\}\\\|\\nabla f\(y\)\\\|\_\{\*\}^\{2\}\+V\(x,y\)\-V\(x,z\)\.\(2\)

Consider a set of convex subdifferentiable functionalsgi:Q⟶ℝg\_\{i\}:Q\\longrightarrow\\mathbb\{R\},i=1,2,…,mi=1,2,\\ldots,m\. In addition, we assume that all functionalsgig\_\{i\}are Lipschitz\-continuous with some constantMgi\>0M\_\{g\_\{i\}\}\>0, i\.e\.,

\|gi​\(x\)−gi​\(y\)\|≤Mgi​‖x−y‖∀x,y∈Q​and​i=1,…,m\.\\left\|g\_\{i\}\(x\)\-g\_\{i\}\(y\)\\right\|\\leq M\_\{g\_\{i\}\}\\\|x\-y\\\|\\quad\\forall\\;x,y\\in Q\\;\\;\\text\{and\}\\;\\;i=1,\\ldots,m\.\(3\)
It means that at every pointx∈Qx\\in Qand for anyi=1,…,mi=1,\\ldots,mthere is a subgradient∇gi​\(x\)\\nabla g\_\{i\}\(x\), such that‖∇gi​\(x\)‖∗≤Mgi\\\|\\nabla g\_\{i\}\(x\)\\\|\_\{\*\}\\leq M\_\{g\_\{i\}\}\.

In this paper, we consider the following constrained variational inequality problem

Findx∗∈Q\\displaystyle\\text\{Find\}\\quad x^\{\*\}\\in Q:⟨F​\(x\),x∗−x⟩≤0∀x∈Q,\\displaystyle:\\quad\\langle F\(x\),x^\{\*\}\-x\\rangle\\leq 0\\quad\\forall x\\in Q,\(4\)andgi​\(x\)≤0∀i=1,2​…,m,\\displaystyle\\text\{and\}\\quad g\_\{i\}\(x\)\\leq 0\\quad\\forall i=1,2\\ldots,m,whereF:Q⟶E∗F:Q\\longrightarrow\\textbf\{E\}^\{\*\}is a continuous, monotone operator, i\.e\.,

⟨F​\(x\)−F​\(y\),x−y⟩≥0∀x,y∈Q\.\\langle F\(x\)\-F\(y\),x\-y\\rangle\\geq 0\\quad\\forall x,y\\in Q\.\(5\)
It is clear that instead of a set of Lipschitz\-continuous functionals\{gi​\(⋅\)\}i=1m\\\{g\_\{i\}\(\\cdot\)\\\}\_\{i=1\}^\{m\}we can see one Lipschitz\-continuous functional constraintg:Q⟶ℝg:Q\\longrightarrow\\mathbb\{R\}, such that

g​\(x\)=max1≤i≤m⁡\{gi​\(x\)\},\|g​\(x\)−g​\(y\)\|≤Mg​‖x−y‖∀x,y∈Q,g\(x\)=\\max\\limits\_\{1\\leq i\\leq m\}\\\{g\_\{i\}\(x\)\\\},\\quad\|g\(x\)\-g\(y\)\|\\leq M\_\{g\}\\\|x\-y\\\|\\;\\quad\\forall\\;x,y\\in Q,\(6\)whereMg=max1≤i≤m⁡\{Mgi\}M\_\{g\}=\\max\_\{1\\leq i\\leq m\}\\\{M\_\{g\_\{i\}\}\\\}\. Thus, the problem \([4](https://arxiv.org/html/2605.16262#S1.E4)\), will be equivalent to the following problem

Findx∗∈Q\\displaystyle\\text\{Find\}\\quad x^\{\*\}\\in Q:⟨F​\(x\),x∗−x⟩≤0∀x∈Q,\\displaystyle:\\quad\\langle F\(x\),x^\{\*\}\-x\\rangle\\leq 0\\quad\\forall x\\in Q,\(7\)andg​\(x\)≤0\.\\displaystyle\\text\{and\}\\quad g\(x\)\\leq 0\.
We say that the operatorFFis bounded onQQ, if there existsLF\>0L\_\{F\}\>0such that

‖F​\(x\)‖∗≤LF,∀x∈Q\.\\\|F\(x\)\\\|\_\{\*\}\\leq L\_\{F\},\\quad\\forall x\\in Q\.\(8\)
To emphasize the extensiveness of the problem \([4](https://arxiv.org/html/2605.16262#S1.E4)\) \(or \([7](https://arxiv.org/html/2605.16262#S1.E7)\)\) without considering the functional constraints \(as a special case\), we mention three common special cases for VIs\.

###### Example 1\(Minimization problem\)

Let us consider the minimization problem

minx∈Q⁡f​\(x\),\\min\_\{x\\in Q\}f\(x\),\(9\)and assume thatF​\(x\)=∇f​\(x\)F\(x\)=\\nabla f\(x\), where∇f​\(x\)\\nabla f\(x\)denotes the \(sub\)gradient offfatxx\. Then, ifffis convex, it can be proved thatx∗∈Qx^\{\*\}\\in Qis a solution to \([4](https://arxiv.org/html/2605.16262#S1.E4)\) \(without considering functional constraints\) if and only ifx∗∈Qx^\{\*\}\\in Qis a solution to \([9](https://arxiv.org/html/2605.16262#S1.E9)\)\.

###### Example 2\(Saddle point problem\)

Let us consider the saddle point problem

minu∈Qu⁡maxv∈Qv⁡f​\(u,v\),\\min\_\{u\\in Q\_\{u\}\}\\max\_\{v\\in Q\_\{v\}\}f\(u,v\),\(10\)

and assume thatF​\(x\):=F​\(u,v\)=\(∇uf​\(u,v\),−∇vf​\(u,v\)\)⊤F\(x\):=F\(u,v\)=\\left\(\\nabla\_\{u\}f\(u,v\),\-\\nabla\_\{v\}f\(u,v\)\\right\)^\{\\top\}, whereQ=Qu×QvQ=Q\_\{u\}\\times Q\_\{v\}withQu⊆ℝnu,Qv⊆ℝnvQ\_\{u\}\\subseteq\\mathbb\{R\}^\{n\_\{u\}\},Q\_\{v\}\\subseteq\\mathbb\{R\}^\{n\_\{v\}\}\. Then ifffis convex inuuand concave invv, it can be proved thatx∗∈Qx^\{\*\}\\in Qis a solution to \([4](https://arxiv.org/html/2605.16262#S1.E4)\) \(without considering the functional constraints\) if and only ifx∗=\(u∗,v∗\)∈Qx^\{\*\}=\(u^\{\*\},v^\{\*\}\)\\in Qis a solution to \([10](https://arxiv.org/html/2605.16262#S1.E10)\)\.

###### Example 3\(Fixed point problem\)

Let us consider the fixed point problem

Findx∗∈Q​such thatT​\(x∗\)=x∗,\\text\{Find\}\\quad x^\{\*\}\\in Q\\;\\;\\text\{such that\}\\quad T\(x^\{\*\}\)=x^\{\*\},\(11\)whereT:ℝn⟶ℝnT:\\mathbb\{R\}^\{n\}\\longrightarrow\\mathbb\{R\}^\{n\}is an operator\. TakingF​\(x\)=x−T​\(x\)F\(x\)=x\-T\(x\), it can be proved thatx∗∈Q=ℝnx^\{\*\}\\in Q=\\mathbb\{R\}^\{n\}is a solution to \([4](https://arxiv.org/html/2605.16262#S1.E4)\) \(without considering functional constraints\) ifF​\(x∗\)=0∈ℝnF\(x^\{\*\}\)=\\textbf\{0\}\\in\\mathbb\{R\}^\{n\}, that is,x∗x^\{\*\}is a solution to \([11](https://arxiv.org/html/2605.16262#S1.E11)\)\.

###### Definition 1

For someε\>0\\varepsilon\>0, we call a pointx^∈Q\\widehat\{x\}\\in Qanε\\varepsilon\-solution of the problem \([7](https://arxiv.org/html/2605.16262#S1.E7)\), if

⟨F​\(x\),x^−x⟩≤ε∀x∈Q,andg​\(x^\)≤ε\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\\leq\\varepsilon\\quad\\forall x\\in Q,\\quad\\text\{and\}\\quad g\(\\widehat\{x\}\)\\leq\\varepsilon\.\(12\)

## 2Mirror Descent Type Algorithms for VIs with Functional Constraints

In this section, we introduce several mirror descent\-based algorithms to solve problem \([7](https://arxiv.org/html/2605.16262#S1.E7)\)\. We presentsevendistinct algorithms, differing primarily in their step sizes and stopping criteria\. The first two methods, Algorithm[1](https://arxiv.org/html/2605.16262#alg1)and Algorithm[2](https://arxiv.org/html/2605.16262#alg2), are detailed below\. The remaining algorithms \(3–7\) follow a similar structure and are summarized in Table[1](https://arxiv.org/html/2605.16262#S2.T1)\.

As can be seen from the items of the proposed algorithms, see e\.g\., Algorithm[1](https://arxiv.org/html/2605.16262#alg1), the needed point \(output point of the proposed algorithms\) is selected among the pointsxix\_\{i\}for whichg​\(xi\)≤εg\(x\_\{i\}\)\\leq\\varepsilon, as an average of these points\. Therefore, we will call stepiiproductiveifg​\(xi\)≤εg\(x\_\{i\}\)\\leq\\varepsilon\. If the reverse inequalityg​\(xi\)\>εg\(x\_\{i\}\)\>\\varepsilonholds, then stepiiwill be callednon\-productive\.

LetIIandJJdenote the set of indices of productive and non\-productive steps, respectively\.\|A\|\|A\|denotes the cardinality of the setAA\.

Algorithm 1Non\-Adaptive Mirror Descent for VIs with functional constraints\.0:

ε\>0,LF\>0,Mg\>0,D\>0\\varepsilon\>0,L\_\{F\}\>0,M\_\{g\}\>0,D\>0\(the diameter of

QQ\),

x0∈Q∘x\_\{0\}\\in Q^\{\\circ\},

R\>0R\>0such that

maxx∈Q⁡V​\(x,x0\)≤R2\\max\_\{x\\in Q\}V\(x,x\_\{0\}\)\\leq R^\{2\}\.

1:

I=:∅,J:=∅\.I=:\\emptyset,J:=\\emptyset\.Set

k=0\.k=0\.
2:repeat

3:if

g​\(xk\)≤εg\(x\_\{k\}\)\\leq\\varepsilonthen

4:

hkF:=hF=εLF2,h\_\{k\}^\{F\}:=h^\{F\}=\\frac\{\\varepsilon\}\{L\_\{F\}^\{2\}\},\\;\\;xk\+1=Mirrxk⁡\(hF​F​\(xk\)\)x\_\{k\+1\}=\\operatorname\{Mirr\}\_\{x\_\{k\}\}\\left\(h^\{F\}F\(x\_\{k\}\)\\right\)\\;\\;and add

kkto

II,

5:else

6:

hkg:=hg=εMg2,h\_\{k\}^\{g\}:=h^\{g\}=\\frac\{\\varepsilon\}\{M\_\{g\}^\{2\}\},\\;\\;xk\+1=Mirrxk⁡\(hg​∇g​\(xk\)\)x\_\{k\+1\}=\\operatorname\{Mirr\}\_\{x\_\{k\}\}\\left\(h^\{g\}\\nabla g\(x\_\{k\}\)\\right\)\\;\\;and add

kkto

JJ,

7:endif

8:Set

k:=k\+1\.k:=k\+1\.
9:until

Stopping criterion 1:R2≤ε2​\|I\|2​LF2\+ε2​\|J\|2​Mg2−ε​D​\|J\|Mg,\\text\{Stopping criterion 1:\}\\quad R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\|I\|\}\{2L\_\{F\}^\{2\}\}\+\\frac\{\\varepsilon^\{2\}\|J\|\}\{2M\_\{g\}^\{2\}\}\-\\frac\{\\varepsilon D\|J\|\}\{M\_\{g\}\},\(13\)or

Stopping criterion 2:R2≤ε2​\|I\|2​LF2\+ε2​\|J\|2​Mg2\.\\text\{Stopping criterion 2:\}\\quad R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\|I\|\}\{2L\_\{F\}^\{2\}\}\+\\frac\{\\varepsilon^\{2\}\|J\|\}\{2M\_\{g\}^\{2\}\}\.\(14\)

Algorithm 2Adaptive Mirror Descent for VIs with functional constraints\.0:

ε\>0,Mg\>0,D\>0\\varepsilon\>0,M\_\{g\}\>0,D\>0\(the diameter of

QQ\),

x0∈Q∘x\_\{0\}\\in Q^\{\\circ\},

R\>0R\>0such that

maxx∈Q⁡V​\(x,x0\)≤R2\\max\_\{x\\in Q\}V\(x,x\_\{0\}\)\\leq R^\{2\}\.

1:

I=:∅,J:=∅\.I=:\\emptyset,J:=\\emptyset\.Set

k=0\.k=0\.
2:repeat

3:if

g​\(xk\)≤εg\(x\_\{k\}\)\\leq\\varepsilonthen

4:

Mk=‖F​\(xk\)‖∗,hkF=εMk2,M\_\{k\}=\\left\\\|F\(x\_\{k\}\)\\right\\\|\_\{\*\},\\;\\;h\_\{k\}^\{F\}=\\frac\{\\varepsilon\}\{M\_\{k\}^\{2\}\},\\;\\;xk\+1=Mirrxk⁡\(hkF​F​\(xk\)\)x\_\{k\+1\}=\\operatorname\{Mirr\}\_\{x\_\{k\}\}\\left\(h\_\{k\}^\{F\}F\(x\_\{k\}\)\\right\)\\;\\;and add

kkto

II,

5:else

6:

Mk=‖∇g​\(xk\)‖∗,hkg=εMk2,M\_\{k\}=\\left\\\|\\nabla g\(x\_\{k\}\)\\right\\\|\_\{\*\},\\;\\;h\_\{k\}^\{g\}=\\frac\{\\varepsilon\}\{M\_\{k\}^\{2\}\},\\;\\;xk\+1=Mirrxk⁡\(hkg​∇g​\(xk\)\)x\_\{k\+1\}=\\operatorname\{Mirr\}\_\{x\_\{k\}\}\\left\(h\_\{k\}^\{g\}\\nabla g\(x\_\{k\}\)\\right\)\\;\\;and add

kkto

JJ,

7:endif

8:Set

k:=k\+1\.k:=k\+1\.
9:until

Stopping criterion 1:R2≤ε22​∑i=0k−11Mi2−Mg​D​ε​∑i∈J1‖∇g​\(xi\)‖∗2,\\text\{Stopping criterion 1:\}\\quad R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{M\_\{i\}^\{2\}\}\-M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\},\(15\)or

Stopping criterion 2:R2≤ε22​∑i=0k−11Mi2\.\\text\{Stopping criterion 2:\}\\quad R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{M\_\{i\}^\{2\}\}\.\(16\)

Table 1:The proposed Algorithms 3 – 7\. Mirror Descent Algorithms for VIs with functional constraints\.g​\(xk\)≤g\(x\_\{k\}\)\\leqhkF=h\_\{k\}^\{F\}=hkg=h\_\{k\}^\{g\}=Stopping criterion 1Stopping criterion 2Algorithm 3ε​Mg\\varepsilon M\_\{g\}ε‖F​\(xk\)‖∗2\\frac\{\\varepsilon\}\{\\\|F\(x\_\{k\}\)\\\|\_\{\*\}^\{2\}\}εMg\\frac\{\\varepsilon\}\{M\_\{g\}\}R2≤ε22​∑i∈I1‖F​\(xi\)‖∗2\+ε22​\|J\|−ε​D​\|J\|R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\\limits\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|\-\\varepsilon D\|J\|R2≤ε22​∑i∈I1‖F​\(xi\)‖∗2\+ε22​\|J\|R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\\limits\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|Algorithm 4ε\\varepsilonε‖F​\(xk\)‖∗\\frac\{\\varepsilon\}\{\\\|F\(x\_\{k\}\)\\\|\_\{\*\}\}ε‖∇g​\(xk\)‖∗2\\frac\{\\varepsilon\}\{\\left\\\|\\nabla g\(x\_\{k\}\)\\right\\\|\_\{\*\}^\{2\}\}R2≤ε22​\|I\|\+\(ε22−ε​Mg​D\)​∑i∈J1‖∇g​\(xi\)‖∗2R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\|I\|\+\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\-\\varepsilon M\_\{g\}D\\right\)\\sum\\limits\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}R2≤ε22​\(\|I\|\+∑i∈J1‖∇g​\(xi\)‖∗2\)R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\\left\(\|I\|\+\\sum\\limits\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)Algorithm 5ε​Mg\\varepsilon M\_\{g\}ε‖F​\(xk\)‖∗\\frac\{\\varepsilon\}\{\\left\\\|F\(x\_\{k\}\)\\right\\\|\_\{\*\}\}εMg\\frac\{\\varepsilon\}\{M\_\{g\}\}R2≤ε22​\(\|I\|\+\|J\|\)−ε​D​\|J\|R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\\left\(\|I\|\+\|J\|\\right\)\-\\varepsilon D\|J\|R2≤ε22​\(\|I\|\+\|J\|\)R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\\left\(\|I\|\+\|J\|\\right\)Algorithm 6ε\\varepsilonεMg​‖F​\(xk\)‖∗\\frac\{\\varepsilon\}\{M\_\{g\}\\left\\\|F\(x\_\{k\}\)\\right\\\|\_\{\*\}\}εMg2\\frac\{\\varepsilon\}\{M\_\{g\}^\{2\}\}R2≤ε22​Mg2​\(\|I\|\+\|J\|\)−ε​D​\|J\|MgR^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\\left\(\|I\|\+\|J\|\\right\)\-\\frac\{\\varepsilon D\|J\|\}\{M\_\{g\}\}R2≤ε22​Mg2​\(\|I\|\+\|J\|\)R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\\left\(\|I\|\+\|J\|\\right\)Algorithm 7ε\\varepsilonθ​\(∑t=0kMt2\)−1/2\\theta\\left\(\\sum\\limits\_\{t=0\}^\{k\}M\_\{t\}^\{2\}\\right\)^\{\-1/2\},Mt=‖F​\(xt\)‖∗M\_\{t\}=\\\|F\(x\_\{t\}\)\\\|\_\{\*\}θ​\(∑t=0kMt2\)−1/2\\theta\\left\(\\sum\\limits\_\{t=0\}^\{k\}M\_\{t\}^\{2\}\\right\)^\{\-1/2\},Mt=‖∇g​\(xt\)‖∗M\_\{t\}=\\\|\\nabla g\(x\_\{t\}\)\\\|\_\{\*\}k≥2​θε​\(∑t=0kMt2\)−1/2\+\|J\|​Mg​Dεk\\geq\\frac\{2\\theta\}\{\\varepsilon\}\\left\(\\sum\\limits\_\{t=0\}^\{k\}M\_\{t\}^\{2\}\\right\)^\{\-1/2\}\+\\frac\{\|J\|M\_\{g\}D\}\{\\varepsilon\}k≥2​θε​\(∑t=0kMt2\)−1/2k\\geq\\frac\{2\\theta\}\{\\varepsilon\}\\left\(\\sum\\limits\_\{t=0\}^\{k\}M\_\{t\}^\{2\}\\right\)^\{\-1/2\}

## 3Analysis of the proposed algorithms

In this section, we provide an analysis of the proposed Algorithms 1 — 7\.

Assume thatF:Q⟶𝐄∗F:Q\\longrightarrow\\mathbf\{E\}^\{\*\}is a continuous, monotone, and bounded operator \(see \([8](https://arxiv.org/html/2605.16262#S1.E8)\)\),g​\(x\):=max1≤i≤m⁡\{gi​\(x\)\}g\(x\):=\\max\\limits\_\{1\\leq i\\leq m\}\\\{g\_\{i\}\(x\)\\\}is anMgM\_\{g\}\-Lipschitz convex function, wheregi:Q⟶ℝg\_\{i\}:Q\\longrightarrow\\mathbb\{R\}fori=1,…,mi=1,\\ldots,mareMgiM\_\{g\_\{i\}\}\-Lipschitz, andMg=max1≤i≤m⁡\{Mgi\}M\_\{g\}=\\max\\limits\_\{1\\leq i\\leq m\}\\left\\\{M\_\{g\_\{i\}\}\\right\\\}\.

### 3\.1Analysis of Algorithm[1](https://arxiv.org/html/2605.16262#alg1)

For Algorithm[1](https://arxiv.org/html/2605.16262#alg1), we have the following result\.

###### Theorem 3\.1

By Algorithm[1](https://arxiv.org/html/2605.16262#alg1), we get a pointx^=1∑i∈IhiF​∑i∈IhiF​xi\\widehat\{x\}=\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}, such that

g​\(x^\)≤ε,g\(\\widehat\{x\}\)\\leq\\varepsilon,\(17\)and

1. 1\.with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε∀x∈Q,\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\quad\\forall x\\in Q,\(18\)
2. 2\.with stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε\+D​LF2​\|J\|Mg​\|I\|,∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\frac\{DL\_\{F\}^\{2\}\|J\|\}\{M\_\{g\}\|I\|\},\\quad\\forall x\\in Q\.\(19\)

###### Proof

The proof is in the Appendix\. See Subsec\.[7\.1](https://arxiv.org/html/2605.16262#S7.SS1)\.

### 3\.2Analysis of Algorithm[2](https://arxiv.org/html/2605.16262#alg2)

For Algorithm[2](https://arxiv.org/html/2605.16262#alg2), we have the following result\.

###### Theorem 3\.2

By Algorithm[2](https://arxiv.org/html/2605.16262#alg2), we get a pointx^=1∑i∈IhiF​∑i∈IhiF​xi\\widehat\{x\}=\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}, such that,

g​\(x^\)≤ε,g\(\\widehat\{x\}\)\\leq\\varepsilon,\(20\)and

1. 1\.with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε∀x∈Q,\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\quad\\forall x\\in Q,\(21\)
2. 2\.with stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε\+Mg​D​∑i∈J1‖∇g​\(xi\)‖∗2​\(∑i∈I1‖F​\(xi\)‖∗2\)−1∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+M\_\{g\}D\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)^\{\-1\}\\quad\\forall x\\in Q\.\(22\)

###### Proof

The proof is in the Appendix\. See Subsec\.[7\.2](https://arxiv.org/html/2605.16262#S7.SS2)\.

### 3\.3Analysis of Algorithm 3

For Algorithm 3, we have the following result\.

###### Theorem 3\.3

By Algorithm 3, we get a pointx^=1∑i∈IhiF​∑i∈IhiF​xi\\widehat\{x\}=\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}, such that

g​\(x^\)≤ε​Mg,g\(\\widehat\{x\}\)\\leq\\varepsilon M\_\{g\},\(23\)and

1. 1\.with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε∀x∈Q,\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\quad\\forall x\\in Q,\(24\)
2. 2\.with stopping criterion 2, we get ⟨F​\(x\),x^−x⟩​<ε\+D\|​J\|\(∑i∈I1‖F​\(xi\)‖∗2\)−1∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+D\|J\|\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)^\{\-1\}\\quad\\forall x\\in Q\.\(25\)

###### Proof

The proof is in the Appendix\. See Subsec\.[7\.3](https://arxiv.org/html/2605.16262#S7.SS3)\.

### 3\.4Analysis of Algorithm 4

For Algorithm 4, we have the following result\.

###### Theorem 3\.4

By Algorithm 4, we get a pointx^=1∑i∈IhiF​∑i∈IhiF​xi\\widehat\{x\}=\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}, such that

g​\(x^\)≤ε,g\(\\widehat\{x\}\)\\leq\\varepsilon,\(26\)and

1. 1\.with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε​LF∀x∈Q,\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\\quad\\forall x\\in Q,\(27\)
2. 2\.with stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε​LF\+Mg​D​LF\|I\|​∑i∈I1‖∇g​\(xi\)‖∗2∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\+\\frac\{M\_\{g\}DL\_\{F\}\}\{\|I\|\}\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\quad\\forall x\\in Q\.\(28\)

###### Proof

The proof is in the Appendix\. See Subsec\.[7\.4](https://arxiv.org/html/2605.16262#S7.SS4)\.

### 3\.5Analysis of Algorithm 5

For Algorithm 5, we have the following result\.

###### Theorem 3\.5

By Algorithm 5, we get a pointx^=1∑i∈IhiF​∑i∈IhiF​xi\\widehat\{x\}=\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}, such that

g​\(x^\)≤ε​Mg,g\(\\widehat\{x\}\)\\leq\\varepsilon M\_\{g\},\(29\)and

1. 1\.with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε​LF∀x∈Q,\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\\quad\\forall x\\in Q,\(30\)
2. 2\.with stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε​LF\+D​LF​\|J\|\|I\|∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\+\\frac\{DL\_\{F\}\|J\|\}\{\|I\|\}\\quad\\forall x\\in Q\.\(31\)

###### Proof

The proof is in the Appendix\. See Subsec\.[7\.5](https://arxiv.org/html/2605.16262#S7.SS5)\.

### 3\.6Analysis of Algorithm 6

For Algorithm 6, we have the following result\.

###### Theorem 3\.6

By Algorithm 6, we get a pointx^=1∑i∈IhiF​∑i∈IhiF​xi\\widehat\{x\}=\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}, such that

g​\(x^\)≤ε,g\(\\widehat\{x\}\)\\leq\\varepsilon,\(32\)and

1. 1\.with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε​LFMg∀x∈Q,\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon L\_\{F\}\}\{M\_\{g\}\}\\quad\\forall x\\in Q,\(33\)
2. 2\.with stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε​LFMg\+D​LF​\|J\|Mg​\|I\|∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon L\_\{F\}\}\{M\_\{g\}\}\+\\frac\{DL\_\{F\}\|J\|\}\{M\_\{g\}\|I\|\}\\quad\\forall x\\in Q\.\(34\)

###### Proof

The proof is in the Appendix\. See Subsec\.[7\.6](https://arxiv.org/html/2605.16262#S7.SS6)\.

### 3\.7Analysis of Algorithm 7

In Algorithm 7, we mention that the parameterθ\>0\\theta\>0is such thatmaxx,y∈Q⁡V​\(x,y\)≤θ2\\max\\limits\_\{x,y\\in Q\}V\(x,y\)\\leq\\theta^\{2\}\. For Algorithm 7, we have the following result\.

###### Theorem 3\.7

By Algorithm 7, we get a pointx^=1\|I\|​∑i∈Ixi\\widehat\{x\}=\\frac\{1\}\{\|I\|\}\\sum\_\{i\\in I\}x\_\{i\}, such that

g​\(x^\)≤ε,g\(\\widehat\{x\}\)\\leq\\varepsilon,\(35\)and

1. 1\.with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε∀x∈Q,\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\quad\\forall x\\in Q,\(36\)
2. 2\.with stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε\+\|J\|​Mg​D\|I\|∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\frac\{\|J\|M\_\{g\}D\}\{\|I\|\}\\quad\\forall x\\in Q\.\(37\)

###### Proof

The proof is in the Appendix\. See Subsec\.[7\.7](https://arxiv.org/html/2605.16262#S7.SS7)\.

## 4Modification of the Algorithms[1](https://arxiv.org/html/2605.16262#alg1)—7 for VIs with many functional constraints

In this section, we propose a modification of the previously proposed Algorithms[1](https://arxiv.org/html/2605.16262#alg1)—7, to solve the problem \([4](https://arxiv.org/html/2605.16262#S1.E4)\)\. The modification was first proposed for the minimization problems in\[[38](https://arxiv.org/html/2605.16262#bib.bib38)\]\. Instead of transforming all functional constraints into one that equals the maximum of them as in problem \([7](https://arxiv.org/html/2605.16262#S1.E7)\), we consider each constraintgig\_\{i\}in the calculation when we have a productive step, and the first constraint that violates the feasibility\. Thus, this proposed modification saves the algorithms’ running time by considering not all functional constraints on non\-productive steps\.

In the following, we list the modifications of Algorithm[2](https://arxiv.org/html/2605.16262#alg2), where the same will be for the remaining Algorithms[1](https://arxiv.org/html/2605.16262#alg1)and 3—7\.

The results of Theorems[3\.1](https://arxiv.org/html/2605.16262#S3.Thmtheorem1)–[3\.7](https://arxiv.org/html/2605.16262#S3.Thmtheorem7)extend to all modified versions of Algorithms[1](https://arxiv.org/html/2605.16262#alg1)–7\. For brevity, we present the proof only for the modification of Algorithm[2](https://arxiv.org/html/2605.16262#alg2), as the arguments for the remaining algorithms are analogous\.

Algorithm 8Modification of Algorithm[2](https://arxiv.org/html/2605.16262#alg2)with many functional constraints\.0:

ε\>0,Mg=max1≤i≤m⁡\{Mgi\}\>0,D\>0\\varepsilon\>0,M\_\{g\}=\\max\_\{1\\leq i\\leq m\}\\\{M\_\{g\_\{i\}\}\\\}\>0,D\>0\(the diameter of

QQ\),

x0∈Q∘x\_\{0\}\\in Q^\{\\circ\},

R\>0R\>0such that

maxx∈Q⁡V​\(x,x0\)≤R2\\max\_\{x\\in Q\}V\(x,x\_\{0\}\)\\leq R^\{2\}\.

1:

I=:∅,J:=∅\.I=:\\emptyset,J:=\\emptyset\.
2:Set

k=0\.k=0\.
3:repeat

4:if

gi​\(xk\)≤ε​∀i=1,2,…,mg\_\{i\}\(x\_\{k\}\)\\leq\\varepsilon\\;\\forall i=1,2,\\ldots,mthen

5:

Mk=‖F​\(xk\)‖∗,hkF=εMk2,M\_\{k\}=\\left\\\|F\(x\_\{k\}\)\\right\\\|\_\{\*\},\\;\\;h\_\{k\}^\{F\}=\\frac\{\\varepsilon\}\{M\_\{k\}^\{2\}\},\\;\\;
6:

xk\+1=Mirrxk⁡\(hkF​F​\(xk\)\)x\_\{k\+1\}=\\operatorname\{Mirr\}\_\{x\_\{k\}\}\\left\(h\_\{k\}^\{F\}F\(x\_\{k\}\)\\right\)\\;\\;and add

kkto

II,

7:else

8:\(i\.e\.,

∃N=N​\(k\)∈\{1,2,…,m\}\\exists N=N\(k\)\\in\\\{1,2,\\ldots,m\\\}, s\.t\.,

gN​\(k\)\>εg\_\{N\(k\)\}\>\\varepsilon\)

9:

Mk=‖∇gN​\(k\)​\(xk\)‖∗,hkgN​\(k\)=εMk2,M\_\{k\}=\\left\\\|\\nabla g\_\{N\(k\)\}\(x\_\{k\}\)\\right\\\|\_\{\*\},\\;\\;h\_\{k\}^\{g\_\{N\(k\)\}\}=\\frac\{\\varepsilon\}\{M\_\{k\}^\{2\}\},
10:

xk\+1=Mirrxk⁡\(hkgN​\(k\)​∇gN​\(k\)​\(xk\)\)\{\\color\[rgb\]\{0,0,0\}x\_\{k\+1\}=\\operatorname\{Mirr\}\_\{x\_\{k\}\}\\left\(h\_\{k\}^\{g\_\{N\(k\)\}\}\\nabla g\_\{N\(k\)\}\(x\_\{k\}\)\\right\)\}\\;\\;and add

kkto

JJ,

11:endif

12:Set

k:=k\+1\.k:=k\+1\.
13:until

Stopping criterion 1:R2≤ε22​∑i=0k−11Mi2−Mg​D​ε​∑i∈J1‖∇gN​\(i\)​\(xi\)‖∗2,\\text\{Stopping criterion 1:\}\\quad R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{M\_\{i\}^\{2\}\}\-M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla\{\\color\[rgb\]\{0,0,0\}g\_\{N\(i\)\}\}\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\},\(38\)or

Stopping criterion 2:R2≤ε22​∑i=0k−11Mi2\.\\text\{Stopping criterion 2:\}\\quad R^\{2\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{M\_\{i\}^\{2\}\}\.\(39\)

For Algorithm[8](https://arxiv.org/html/2605.16262#alg8), we have the following result\.

###### Theorem 4\.1

By Algorithm[8](https://arxiv.org/html/2605.16262#alg8), we get a pointx^=1∑i∈IhiF​∑i∈IhiF​xi\\widehat\{x\}=\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}, such that,

gi​\(x^\)≤ε,∀i∈\{1,2,…,m\},g\_\{i\}\(\\widehat\{x\}\)\\leq\\varepsilon,\\quad\\forall i\\in\\\{1,2,\\ldots,m\\\},and

1. 1\.with stopping criterion 1 \([38](https://arxiv.org/html/2605.16262#S4.E38)\), we get ⟨F​\(x\),x^−x⟩<ε∀x∈Q,\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\quad\\forall x\\in Q,
2. 2\.with stopping criterion 2 \([39](https://arxiv.org/html/2605.16262#S4.E39)\), ⟨F​\(x\),x^−x⟩<ε\+Mg​D​∑i∈J1‖∇gN​\(i\)​\(xi\)‖∗2​\(∑i∈I1‖F​\(xi\)‖∗2\)−1​∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+M\_\{g\}D\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\_\{N\(i\)\}\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)^\{\-1\}\\;\\forall x\\in Q\.

###### Proof

The proof is in the Appendix\. See Subsec\.[8](https://arxiv.org/html/2605.16262#S8)\.

## 5Numerical experiments

In this section, we mention the results of the conducted experiments for the proposed algorithms in Sect\.[2](https://arxiv.org/html/2605.16262#S2), for one example of the variational inequality problem \(HpHard problem\) with functional constraints\.

All experiments were implemented in Python 3\.4, on a computer fitted with Intel\(R\) Core\(TM\) i7\-8550U CPU @ 1\.80GHz, 1992 Mhz, 4 Core\(s\), 8 Logical Processor\(s\)\. The RAM of the computer is 8 GB\.

Let us consider the problem \([7](https://arxiv.org/html/2605.16262#S1.E7)\), with the following functional constraints,

g​\(x\)=max1≤i≤m⁡\{gi​\(x\)=⟨ai,x⟩−bi\},g\(x\)=\\max\_\{1\\leq i\\leq m\}\\left\\\{g\_\{i\}\(x\)=\\langle a\_\{i\},x\\rangle\-b\_\{i\}\\right\\\},\(40\)whereai∈ℝna\_\{i\}\\in\\mathbb\{R\}^\{n\}andbi∈ℝb\_\{i\}\\in\\mathbb\{R\}for anyi∈\{1,…,m\}i\\in\\\{1,\\ldots,m\\\}\.

The vectorsaja\_\{j\}and constantsbjb\_\{j\}, forj=1,2,…,mj=1,2,\\ldots,m, are randomly generated from a uniform distribution over\[0,1\)\[0,1\)\. In our experiments, we takem=10m=10\.

###### Example 4

In this example, we consider the HpHard \(or Harker\-Pang\) problem\[[42](https://arxiv.org/html/2605.16262#bib.bib42)\]\. LetF:ℝn⟶ℝnF:\\mathbb\{R\}^\{n\}\\longrightarrow\\mathbb\{R\}^\{n\}be an operator defined by

F​\(x\)=K​x\+q,K=A​A⊤\+B\+C,q∈ℝn,F\(x\)=Kx\+q,\\quad K=AA^\{\\top\}\+B\+C,q\\in\\mathbb\{R\}^\{n\},\(41\)whereA∈ℝn×nA\\in\\mathbb\{R\}^\{n\\times n\}is a matrix,B∈ℝn×nB\\in\\mathbb\{R\}^\{n\\times n\}is a skew\-symmetric matrix andC∈ℝn×nC\\in\\mathbb\{R\}^\{n\\times n\}is a diagonal matrix with non\-negative diagonal entries\. Therefore, it follows thatKKis positive semidefinite\. The operatorFFis bounded in the unit ball and monotone, whereLF=‖K‖2\+‖q‖2L\_\{F\}=\\\|K\\\|\_\{2\}\+\\\|q\\\|\_\{2\}\. Forq=0∈ℝnq=\\textbf\{0\}\\in\\mathbb\{R\}^\{n\}, the solution of the problem \([7](https://arxiv.org/html/2605.16262#S1.E7)\), isx∗=0∈ℝnx^\{\*\}=\\textbf\{0\}\\in\\mathbb\{R\}^\{n\}\.

![Refer to caption](https://arxiv.org/html/2605.16262v1/x1.png)
![Refer to caption](https://arxiv.org/html/2605.16262v1/x2.png)

Figure 1:The results of Algorithms[1](https://arxiv.org/html/2605.16262#alg1)—7 \(with first stopping criterion\), for Example[4](https://arxiv.org/html/2605.16262#Thmexample4)withn=100,m=10n=100,m=10,ε=0\.05\\varepsilon=0\.05\(left\), andε=0\.01\\varepsilon=0\.01\(right\)\.Alg\.[1](https://arxiv.org/html/2605.16262#alg1)Alg\.[2](https://arxiv.org/html/2605.16262#alg2)Alg\. 3Alg\. 4Alg\. 5Alg\. 6Alg\. 7ε=0\.05\\varepsilon=0\.05Iters\.1290051618035423360133169604Time18\.7170030\.0216460\.0166140\.7482570\.51795637\.2577670\.161242Estim\.0\.050\.050\.050\.3060\.3060\.04920\.05ε=0\.01\\varepsilon=0\.01Iters\.32322482398712867138560033366763020Time563\.8087680\.5830220\.17186815\.27486214\.675128758\.0700350\.59175Estim\.0\.010\.010\.010\.61250\.61250\.00980\.01

Table 2:The results of Algorithms[1](https://arxiv.org/html/2605.16262#alg1)—7 \(with first stopping criterion\), for Example[4](https://arxiv.org/html/2605.16262#Thmexample4)withLF≈6\.125326,Mg≈6\.22351,n=100,m=10L\_\{F\}\\approx 6\.125326,M\_\{g\}\\approx 6\.22351,n=100,m=10,ε=0\.05,0\.01\\varepsilon=0\.05,0\.01\. In this table, Iters\. denotes the number of iterations of each algorithm, Time denotes the running time of each algorithm in seconds, and Estim\. denotes the theoretical estimate of an achieved solution by each algorithm\.
## 6Conclusion

In this paper, we studied the variational inequality problem with inequality functional constraints\. To solve this problem, we proposed seven mirror descent\-type algorithms and a modification of them with different step size rules and stopping criteria\. We provided the analysis of the convergence of all algorithms for the class of problems with bounded andδ\\delta\-monotone \(the monotonicity case corresponds toδ=0\\delta=0\) operators and Lipschitz continuous functional \(inequality type\) constraints\. In the proposed modification, we consider each functional constraint in the calculation when we have a productive step \(feasible point\), and the first constraint that violates the feasibility\. We proved the optimal convergence rate of the proposed algorithms for the class of problems under consideration\. The conducted numerical experiments compare the work of the proposed algorithms for a variational inequality problem \(HpHard or Harker\-Pang\) with functional constraints and for the forsaken game \(which is a min\-max problem\)\.

## References

- \[1\]Facchinei, F\., Pang, J\. S\.: Finite\-dimensional variational inequalities and complementarity problems\. Springer, 2003\.
- \[2\]Goodfellow, I\., Pouget\-Abadie, J\., Mirza, M\., Xu, B\., Warde\-Farley, D\., Ozair, S\., Courville, A\., Bengio, Y\.: Generative adversarial networks\. Communications of the ACM 63, 139–144 \(2020\)
- \[3\]Joachims, T\.: A support vector method for multivariate performance measures, in: Proceedings of the 22nd international conference on Machine learning, 377–384 \(2005\)\.
- \[4\]Xu, L\., Neufeld, J\., Larson, B\., Schuurmans, D\.: Maximum margin clustering\. Advances in neural information processing systems 17 \(2004\)
- \[5\]Madry, A\., Makelov, A\., Schmidt, L\., Tsipras, D\., Vladu, A\.: Towards deep learning models resistant to adversarial attacks\. Published as a conference paper at ICLR 2018,[https://openreview\.net/pdf?id=rJzIBfZAb](https://openreview.net/pdf?id=rJzIBfZAb)
- \[6\]Daskalakis, C\., Ilyas, A\., Syrgkanis, V\., Zeng, H\.: Training gans with optimism\. arXiv preprint arXiv:1711\.00141
- \[7\]Gidel, G\., Berard, H\., Vignoud, G\., Vincent, P\., Lacoste\-Julien, S\.: A variational inequality perspective on generative adversarial networks\. arXiv preprint arXiv:1802\.10551
- \[8\]Korpelevich, G\. M\.: The extragradient method for finding saddle points and other problems\. Matecon 12, 747\-–756 \(1976\)
- \[9\]Nemirovski, A\.: Prox\-method with rate of convergenceo​\(1/t\)o\(1/t\)for variational inequalities with Lipschitz continuous monotone operators and smooth convex\-concave saddle point problems\. SIAM Journal on Optimization15, 229–251 \(2004\)
- \[10\]Gasnikov, A\. V\., Dvurechensky, P\. E\., Stonyakin, F\. S\., Titov, A\. A\.: An adaptive proximal method for variational inequalities\. Computational Mathematics and Mathematical Physics59, 836–841 \(2019\)
- \[11\]Nesterov, Y\.: Dual extrapolation and its applications to solving variational inequalities and related problems\. Mathematical Programming109, 319–344 \(2007\)
- \[12\]Malitsky, Y\., Tam, M\. K\.: A forward\-backward splitting method for monotone inclusions without cocoercivity\. SIAM Journal on Optimization30, 1451–1472 \(2020\)
- \[13\]Levin, M\. I\., Makarov, V\. L\., Rubinov, A\. M\.: Mathematical Models of Economic Interaction, Moscow: Fizmatgiz, 1993\.
- \[14\]Alatur, P\., Ramponi, G\., He, N\., Krause, A\.: Provably learning Nash policies in constrained Markov potential games\. 16th European Workshop on Reinforcement Learning \(EWRL 2023\)\.[https://openreview\.net/pdf?id=1EusBrDDrOK](https://openreview.net/pdf?id=1EusBrDDrOK)
- \[15\]Jordan, P\., Barakat, A\., He, N\.: Independent learning in constrained Markov potential games\. In proceedings of the 27th International Conference on Artificial Intelligence and Statistics \(AISTATS\), Valencia, Spain\. PMLR,238\(2024\)
- \[16\]Jordan, M\. I\., Lin, T\., Zampetakis, M\.: First\-order algorithms for nonlinear generalized Nash equilibrium problems\. Journal of Machine Learning Research, 24\(38\), 1–46 \(2023\)
- \[17\]Migdalas, A\., Pardalos, P\. M\.: Editorial: Hierarchical and bilevel programming, J\. Global Optim\.8, 209–215 \(1996\)
- \[18\]Baiocchi, C\., Capelo, A\.: Variational and Quasi\-variational Inequalities: Applications to Free Boundary Problems, Chichester: Wiley, 1984\.
- \[19\]Antipin, A\. S\.: Solution Methods for Variational Inequalities with Coupled Constraints\. Computational Mathematics and Mathematical Physics40\(9\), 123–1254 \(2000\)
- \[20\]Xu, T\., Liang, Y\., Lan, G\.: CRPO: A new approach for safe reinforcement learning with convergence guarantee\. In International Conference on Machine Learning, PMLR, 11480–11491 \(2021\)
- \[21\]Lowy, A\., Baharlouei, S\., Pavan, R\., Razaviyayn, M\., Beirami, A\.: A stochastic optimization framework for fair risk minimization\. Transactions on Machine Learning Research, 2835–8856 \(2022\)
- \[22\]Zafar, M\. B\., Valera, I\., Gomez\-Rodriguez, M\., Gummadi, K\. P\.: Fairness constraints: A flexible approach for fair classification\. Journal of Machine Learning Research20\(1\), 2737–2778 \(2019\)
- \[23\]Auslender, A\.: Variational inequalities over the cone of semidefinite positive symmetric matrices and over the Lorentz cone, the Second Japanese\-Sino Optimization Meeting, Part II, Kyoto, 2002\. Optim\. Methods Softw\. 18, 359–376 \(2003\)
- \[24\]He, B\. S\., Yang, H\., Zhang, C\. S\.: A modified augmented Lagrangian method for a class of monotone variational inequalities\. Eur\. J\. Oper\. Res\.159, 35–51 \(2004\)
- \[25\]Zhu, D\. L\.: Augmented Lagrangian theory, duality and decomposition methods for variational inequality problems\. J\. Optim\. Theory Appl\.117, 195–216 \(2003\)
- \[26\]Zhang, L\., He, N\., Muehlebach, M\.: Primal Methods for Variational Inequality Problems with Functional Constraints\. Math\. Program\. \(2025\)
- \[27\]Yang, T\., Jordan, M\. I\., Chavdarova, T\.: Solving constrained variational inequalities via an interior point method\. In ICLR, \(2023\)
- \[28\]Chavdarova, T\., Yang, T\., Pagliardini, M\., Jordan, M\.: A Primal\-Dual Approach to Solving Variational Inequalities with General Constraints\. Published as a conference paper at ICLR 2024[https://openreview\.net/pdf?id=RsztjXcvUf](https://openreview.net/pdf?id=RsztjXcvUf)
- \[29\]Nemirovskii, A\.: Efficient methods for large\-scale convex optimization problems\. Ekonomika i Matematicheskie Metody, 1979\. \(in Russian\)
- \[30\]Nemirovsky, A\., Yudin, D\.: Problem Complexity and Method Efficiency in Optimization\. J\. Wiley & Sons, New York 1983\.
- \[31\]Beck, A\., Teboulle, M\.: Mirror descent and nonlinear projected subgradient methods for convex optimization\. Oper\. Res\. Lett\., 31\(3\), 167–175 \(2003\)
- \[32\]Shor, N\. Z\.: Generalized gradient descent with application to block programming\. Kibernetika,3\(3\), 53–55 \(1967\)
- \[33\]Polyak, B\.: A general method of solving extremum problems\. Soviet Mathematics Doklady8\(3\), 593–597, \(1967\)
- \[34\]Dem’yanov, V\. F\., Vasil’yev, L\. V\.: Nondifferentiable Optimization\. Nauka, Moscow, 1981\.
- \[35\]Doan, T\. T\., Bose, S\., Nguyen, D\. H\., Beck, C\. L\.: Convergence of the Iterates in Mirror Descent Methods\. IEEE Control Systems Letters,3\(1\), 114–119 \(2019\)
- \[36\]Alkousa, M\. S\., Stonyakin, F\. S\., Abdo, A\. M\., Alcheikh, M\. M\.: Mirror Descent Methods with Weighting Scheme for Outputs for Optimization Problems with Functional Constraints\. Russian Journal of Nonlinear Dynamics20\(5\), 727–745 \(2024\)
- \[37\]Bayandina, A\., Dvurechensky, P\., Gasnikov, A\., Stonyakin, F\., A\. Titov: Mirror descent and convex optimization problems with non\-smooth inequality constraints\. In: Large\-Scale and Distributed Optimization, Springer, Cham 181–213 \(2018\)[https://doi\.org/10\.1007/978\-3\-319\-97478\-1\_8](https://doi.org/10.1007/978-3-319-97478-1_8)
- \[38\]Stonyakin, F\. S\., Alkousa, M\. S\., Stepanov, A\. N\., Barinov, M\. A\.: Adaptive Mirror Descent Algorithms in Convex Programming Problems with Lipschitz Constraints\. Trudy Inst\. Mat\. Mekh\. Ural\. Otdel\. Ross\. Akad\. Nauk24\(2\), 266\-279 \(2018\)
- \[39\]Stonyakin, F\. S\., Alkousa, M\. S\., Stepanov, A\. N\., Titov, A\. A\.: Adaptive Mirror Descent Algorithms for Convex and Strongly Convex Optimization Problems with Functional Constraints\. J\. Appl\. Ind\. Math\.13, 557–574 \(2019\)
- \[40\]Alkousa, M\. S\.: On Modification of an Adaptive Stochastic Mirror Descent Algorithm for Convex Optimization Problems with Functional Constraints\. In: Zeidan, D\., Padhi, S\., Burqan, A\., Ueberholz, P\. \(eds\) Computational Mathematics and Applications\. Forum for Interdisciplinary Mathematics\. Springer, Singapore, 47–63 \(2020\)[https://doi\.org/10\.1007/978\-981\-15\-8498\-5\_3](https://doi.org/10.1007/978-981-15-8498-5_3)
- \[41\]Xu, Y\.: Primal\-dual stochastic gradient method for convex programs with many functional constraints\. SIAM Journal on Optimization30\(2\) \(2020\)
- \[42\]Qu, X\., Bian, W\., Chen, X\.: An extra gradient Anderson\-accelerated algorithm for pseudomonotone variational inequalities\. arXiv:2408\.06606
- \[43\]Polyak, B\. T\.: Introduction to optimization\. Optimization Software, Inc, New York 1987\.
- \[44\]Hsieh, Y\., Mertikopoulos, P\., Cevher, V\.: The Limits of Min\-Max Optimization Algorithms: Convergence to Spurious Non\-Critical Sets\. Proceedings of the 38th International Conference on Machine Learning, PMLR 139, 4337–4348 \(2021\)

## 7Appendix 1: The Proofs of Theorems in Section[3](https://arxiv.org/html/2605.16262#S3)

### 7\.1Proof Theorem[3\.1](https://arxiv.org/html/2605.16262#S3.Thmtheorem1)

###### Proof

For anyi∈Ii\\in I, andx∈Qx\\in Q, we have

hF​⟨F​\(xi\),xi−x⟩\\displaystyle h^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle≤\(hF\)22​‖F​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h^\{F\}\)^\{2\}\}\{2\}\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)≤ε22​LF2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle\\leq\\frac\{\\varepsilon^\{2\}\}\{2L\_\{F\}^\{2\}\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(42\)For anyi∈Ji\\in J, andx∈Qx\\in Q, we have

hg​\(g​\(xi\)−g​\(x\)\)\\displaystyle h^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)≤\(hg\)22​‖∇g​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h^\{g\}\)^\{2\}\}\{2\}\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)≤ε22​Mg2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle\\leq\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(43\)
Summing up inequalities \([7\.1](https://arxiv.org/html/2605.16262#S7.Ex11)\) and \([7\.1](https://arxiv.org/html/2605.16262#S7.Ex12)\), fromi=0i=0toi=k−1i=k\-1for anyk≥1k\\geq 1, we get the following

hF​∑i∈I⟨F​\(xi\),xi−x⟩\+hg​∑i∈J\(g​\(xi\)−g​\(x\)\)\\displaystyle h^\{F\}\\sum\_\{i\\in I\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\+h^\{g\}\\sum\_\{i\\in J\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)≤ε22​LF2​\|I\|\+ε22​Mg2​\|J\|\\displaystyle\\leq\\frac\{\\varepsilon^\{2\}\}\{2L\_\{F\}^\{2\}\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|J\|\+∑i=0k−1\(V​\(x,xi\)−V​\(x,xi\+1\)\)\\displaystyle\\quad\+\\sum\_\{i=0\}^\{k\-1\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)≤ε22​LF2​\|I\|\+ε22​Mg2​\|J\|\+R2,\\displaystyle\\leq\\frac\{\\varepsilon^\{2\}\}\{2L\_\{F\}^\{2\}\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|J\|\+R^\{2\},In the last inequality, we used the fact

∑i=0k−1\(V​\(x,xi\)−V​\(x,xi\+1\)\)=V​\(x,x0\)−V​\(x,xk\)≤V​\(x,x0\)≤R2\.\\sum\_\{i=0\}^\{k\-1\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)=V\(x,x\_\{0\}\)\-V\(x,x\_\{k\}\)\\leq V\(x,x\_\{0\}\)\\leq R^\{2\}\.
Thus, we have

hF​∑i∈I⟨F​\(xi\),xi−x⟩≤ε22​LF2​\|I\|\+ε22​Mg2​\|J\|\+R2−hg​∑i∈J\(g​\(xi\)−g​\(x\)\)\.h^\{F\}\\sum\_\{i\\in I\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\\leq\\frac\{\\varepsilon^\{2\}\}\{2L\_\{F\}^\{2\}\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|J\|\+R^\{2\}\-h^\{g\}\\sum\_\{i\\in J\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)\.\(44\)
Because the operatorFFis monotone, we have

⟨F​\(x\),xi−x⟩\\displaystyle\\left\\langle F\(x\),x\_\{i\}\-x\\right\\rangle=⟨F​\(xi\),xi−x⟩−⟨F​\(xi\)−F​\(x\),xi−x⟩⏟≥0\\displaystyle=\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\-\\underbrace\{\\left\\langle F\(x\_\{i\}\)\-F\(x\),x\_\{i\}\-x\\right\\rangle\}\_\{\\geq 0\}≤⟨F​\(xi\),xi−x⟩\\displaystyle\\leq\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\(45\)
We also have

hF​∑i∈I⟨F​\(x\),xi−x⟩\\displaystyle h^\{F\}\\sum\_\{i\\in I\}\\left\\langle F\(x\),x\_\{i\}\-x\\right\\rangle=hF​⟨F​\(x\),∑i∈I\(xi−x\)⟩=hF​\|I\|​⟨F​\(x\),1\|I\|​∑i∈Ixi−x⟩\\displaystyle=h^\{F\}\\left\\langle F\(x\),\\sum\_\{i\\in I\}\(x\_\{i\}\-x\)\\right\\rangle=h^\{F\}\|I\|\\left\\langle F\(x\),\\frac\{1\}\{\|I\|\}\\sum\_\{i\\in I\}x\_\{i\}\-x\\right\\rangle=hF​\|I\|​⟨F​\(x\),x^−x⟩\.\\displaystyle=h^\{F\}\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\.\(46\)
Therefore, from \([44](https://arxiv.org/html/2605.16262#S7.E44)\), \([7\.1](https://arxiv.org/html/2605.16262#S7.Ex17)\) and \([7\.1](https://arxiv.org/html/2605.16262#S7.Ex18)\), we get the following

hF​\|I\|​⟨F​\(x\),x^−x⟩≤ε22​LF2​\|I\|\+ε22​Mg2​\|J\|\+R2−hg​∑i∈J\(g​\(xi\)−g​\(x\)\)\.\\displaystyle h^\{F\}\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\\leq\\frac\{\\varepsilon^\{2\}\}\{2L\_\{F\}^\{2\}\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|J\|\+R^\{2\}\-h^\{g\}\\sum\_\{i\\in J\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)\.
Since for anyi∈Ji\\in J, we haveg​\(xi\)−g​\(x∗\)≥g​\(xi\)\>εg\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\geq g\(x\_\{i\}\)\>\\varepsilon, wherex∗x\_\{\*\}is a solution of the problem under consideration, thus it represents a feasible point, i\.e\.,x∗∈Qx\_\{\*\}\\in Qandg​\(x∗\)≤0g\(x\_\{\*\}\)\\leq 0\. Then, from the convexity of the functiongg, we have

−hg​∑i∈J\(g​\(xi\)−g​\(x\)\)\\displaystyle\-h^\{g\}\\sum\_\{i\\in J\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)=−hg​∑i∈J\(g​\(xi\)−g​\(x∗\)\)\+hg​∑i∈J\(g​\(x\)−g​\(x∗\)\)\\displaystyle=\-h^\{g\}\\sum\_\{i\\in J\}\\left\(g\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\right\)\+h^\{g\}\\sum\_\{i\\in J\}\\left\(g\(x\)\-g\(x\_\{\*\}\)\\right\)<−hg​∑i∈Jε\+hg​∑i∈J⟨∇g​\(x\),x−x∗⟩\\displaystyle<\-h^\{g\}\\sum\_\{i\\in J\}\\varepsilon\+h^\{g\}\\sum\_\{i\\in J\}\\left\\langle\\nabla g\(x\),x\-x\_\{\*\}\\right\\rangle≤−hg​ε​\|J\|\+hg​Mg​D​\|J\|,\\displaystyle\\leq\-h^\{g\}\\varepsilon\|J\|\+h^\{g\}M\_\{g\}D\|J\|,where in the last we used the Cauchy\-Schwarz inequality and the fact thatggisMgM\_\{g\}\-Lipschitz, i\.e\.,‖∇g​\(x\)‖∗≤Mg,∀x∈Q\\\|\\nabla g\(x\)\\\|\_\{\*\}\\leq M\_\{g\},\\;\\;\\forall x\\in Q\.

Thus, we get the following

hF​\|I\|​⟨F​\(x\),x^−x⟩\\displaystyle h^\{F\}\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<ε22​LF2\|​I​\|\+ε22​Mg2\|​J​\|−hg​ε\|​J​\|\+hg​Mg​D\|​J\|\+R2\\displaystyle<\\frac\{\\varepsilon^\{2\}\}\{2L\_\{F\}^\{2\}\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|J\|\-h^\{g\}\\varepsilon\|J\|\+h^\{g\}M\_\{g\}D\|J\|\+R^\{2\}=ε2LF2​\|I\|−ε22​LF2​\|I\|−ε22​Mg2​\|J\|\+ε​D​\|J\|Mg\+R2\\displaystyle=\\frac\{\\varepsilon^\{2\}\}\{L\_\{F\}^\{2\}\}\|I\|\-\\frac\{\\varepsilon^\{2\}\}\{2L\_\{F\}^\{2\}\}\|I\|\-\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|J\|\+\\frac\{\\varepsilon D\|J\|\}\{M\_\{g\}\}\+R^\{2\}=ε2LF2​\|I\|−\(ε22​LF2​\|I\|\+ε22​Mg2​\|J\|−ε​D​\|J\|Mg\)\+R2\.\\displaystyle=\\frac\{\\varepsilon^\{2\}\}\{L\_\{F\}^\{2\}\}\|I\|\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2L\_\{F\}^\{2\}\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|J\|\-\\frac\{\\varepsilon D\|J\|\}\{M\_\{g\}\}\\right\)\+R^\{2\}\.\(47\)
- •From the first stopping rule \(i\.e\., from \([13](https://arxiv.org/html/2605.16262#S2.E13)\)\), we get hF​\|I\|​⟨F​\(x\),x^−x⟩<ε2LF2​\|I\|∀x∈Q\.h^\{F\}\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon^\{2\}\}\{L\_\{F\}^\{2\}\}\|I\|\\quad\\forall x\\in Q\.Thus, sincehF=εLF2h^\{F\}=\\frac\{\\varepsilon\}\{L\_\{F\}^\{2\}\}, we find ⟨F​\(x\),x^−x⟩<ε∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\quad\\forall x\\in Q\.
- •From the second stopping rule \(i\.e\., from \([14](https://arxiv.org/html/2605.16262#S2.E14)\)\), we get hF​\|I\|​⟨F​\(x\),x^−x⟩​<ε2LF2\|​I\|\+ε​D​\|J\|Mg∀x∈Q\.h^\{F\}\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon^\{2\}\}\{L\_\{F\}^\{2\}\}\|I\|\+\\frac\{\\varepsilon D\|J\|\}\{M\_\{g\}\}\\quad\\forall x\\in Q\.Thus, sincehF=εLF2h^\{F\}=\\frac\{\\varepsilon\}\{L\_\{F\}^\{2\}\}, we find ⟨F​\(x\),x^−x⟩<ε\+D​LF2​\|J\|Mg​\|I\|∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\frac\{DL\_\{F\}^\{2\}\|J\|\}\{M\_\{g\}\|I\|\}\\quad\\forall x\\in Q\.

Now, for anyi∈Ii\\in I, we haveg​\(xi\)≤εg\(x\_\{i\}\)\\leq\\varepsilon\. Thus, from the convexity ofgg, we have

g​\(∑i∈Ixi\)≤∑i∈Ig​\(xi\)≤ε​\|I\|\.g\\left\(\\sum\_\{i\\in I\}x\_\{i\}\\right\)\\leq\\sum\_\{i\\in I\}g\(x\_\{i\}\)\\leq\\varepsilon\|I\|\.This means that

1\|I\|​g​\(∑i∈Ixi\)≤ε⟹g​\(1\|I\|​∑i∈Ixi\)=g​\(x^\)≤ε\.\\frac\{1\}\{\|I\|\}g\\left\(\\sum\_\{i\\in I\}x\_\{i\}\\right\)\\leq\\varepsilon\\quad\\Longrightarrow\\quad g\\left\(\\frac\{1\}\{\|I\|\}\\sum\_\{i\\in I\}x\_\{i\}\\right\)=g\(\\widehat\{x\}\)\\leq\\varepsilon\.

### 7\.2Proof Theorem[3\.2](https://arxiv.org/html/2605.16262#S3.Thmtheorem2)

###### Proof

For anyi∈Ii\\in I, andx∈Qx\\in Q, we have

hiF​⟨F​\(xi\),xi−x⟩\\displaystyle h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle≤\(hiF\)22​‖F​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{F\}\)^\{2\}\}\{2\}\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)=hiF​ε2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle=\\frac\{h\_\{i\}^\{F\}\\varepsilon\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(48\)For anyi∈Ji\\in J, andx∈Qx\\in Q, we have

hig​\(g​\(xi\)−g​\(x\)\)\\displaystyle h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)≤\(hig\)22​‖∇g​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{g\}\)^\{2\}\}\{2\}\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)=hig​ε2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle=\\frac\{h\_\{i\}^\{g\}\\varepsilon\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(49\)
Summing up inequalities \([7\.2](https://arxiv.org/html/2605.16262#S7.Ex31)\) and \([7\.2](https://arxiv.org/html/2605.16262#S7.Ex32)\), fromi=0i=0toi=k−1i=k\-1for anyk≥1k\\geq 1, we get the following

∑i∈IhiF​⟨F​\(xi\),xi−x⟩\+∑i∈Jhig​\(g​\(xi\)−g​\(x\)\)\\displaystyle\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)≤∑i∈IhiF​ε2\+∑i∈Jhig​ε2\\displaystyle\\leq\\sum\_\{i\\in I\}\\frac\{h\_\{i\}^\{F\}\\varepsilon\}\{2\}\+\\sum\_\{i\\in J\}\\frac\{h\_\{i\}^\{g\}\\varepsilon\}\{2\}\+∑i=0k−1\(V​\(x,xi\)−V​\(x,xi\+1\)\)\\displaystyle\\quad\+\\sum\_\{i=0\}^\{k\-1\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)≤ε2​∑i=0k−1hi\+R2,\\displaystyle\\leq\\frac\{\\varepsilon\}\{2\}\\sum\_\{i=0\}^\{k\-1\}h\_\{i\}\+R^\{2\},where in the last inequality, we sethi:=hiFh\_\{i\}:=h\_\{i\}^\{F\}for everyi∈Ii\\in Iandhi:=high\_\{i\}:=h\_\{i\}^\{g\}for everyi∈Ji\\in J, and we used the fact

∑i=0k−1\(V​\(x,xi\)−V​\(x,xi\+1\)\)=V​\(x,x0\)−V​\(x,xk\)≤V​\(x,x0\)≤R2\.\\sum\_\{i=0\}^\{k\-1\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)=V\(x,x\_\{0\}\)\-V\(x,x\_\{k\}\)\\leq V\(x,x\_\{0\}\)\\leq R^\{2\}\.
Thus, we have

∑i∈IhiF​⟨F​\(xi\),xi−x⟩≤ε2​∑i=0k−1hi\+R2−∑i∈Jhig​\(g​\(xi\)−g​\(x\)\)\.\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\\leq\\frac\{\\varepsilon\}\{2\}\\sum\_\{i=0\}^\{k\-1\}h\_\{i\}\+R^\{2\}\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)\.\(50\)
Because the operatorFFis monotone, we have

⟨F​\(x\),xi−x⟩\\displaystyle\\left\\langle F\(x\),x\_\{i\}\-x\\right\\rangle=⟨F​\(xi\),xi−x⟩−⟨F​\(xi\)−F​\(x\),xi−x⟩⏟≥0\\displaystyle=\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\-\\underbrace\{\\left\\langle F\(x\_\{i\}\)\-F\(x\),x\_\{i\}\-x\\right\\rangle\}\_\{\\geq 0\}≤⟨F​\(xi\),xi−x⟩\.\\displaystyle\\leq\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\.\(51\)
We also have

∑i∈IhiF​⟨F​\(x\),xi−x⟩\\displaystyle\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\left\\langle F\(x\),x\_\{i\}\-x\\right\\rangle=⟨F​\(x\),∑i∈IhiF​\(xi−x\)⟩\\displaystyle=\\left\\langle F\(x\),\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\(x\_\{i\}\-x\)\\right\\rangle=\(∑i∈IhiF\)​⟨F​\(x\),1∑i∈IhiF​∑i∈IhiF​xi−x⟩\\displaystyle=\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}\-x\\right\\rangle=\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩\.\\displaystyle=\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\.\(52\)
Therefore, from \([50](https://arxiv.org/html/2605.16262#S7.E50)\), \([7\.2](https://arxiv.org/html/2605.16262#S7.Ex37)\) and \([7\.2](https://arxiv.org/html/2605.16262#S7.Ex38)\), we get the following

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩≤ε2​∑i=0k−1hi\+R2−∑i∈Jhig​\(g​\(xi\)−g​\(x\)\)\.\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\\leq\\frac\{\\varepsilon\}\{2\}\\sum\_\{i=0\}^\{k\-1\}h\_\{i\}\+R^\{2\}\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)\.
Since for anyi∈Ji\\in J, we haveg​\(xi\)−g​\(x∗\)≥g​\(xi\)\>εg\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\geq g\(x\_\{i\}\)\>\\varepsilon\. Then by the convexity of the functiongg, we have

−∑i∈Jhig​\(g​\(xi\)−g​\(x\)\)\\displaystyle\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)=−∑i∈Jhig​\(g​\(xi\)−g​\(x∗\)\)\+∑i∈Jhig​\(g​\(x\)−g​\(x∗\)\)\\displaystyle=\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\right\)\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\)\-g\(x\_\{\*\}\)\\right\)<−ε​∑i∈Jhig\+∑i∈Jhig​⟨∇g​\(x\),x−x∗⟩\\displaystyle<\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\\langle\\nabla g\(x\),x\-x\_\{\*\}\\right\\rangle≤−ε​∑i∈Jhig\+Mg​D​∑i∈Jhig,\\displaystyle\\leq\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+M\_\{g\}D\\sum\_\{i\\in J\}h\_\{i\}^\{g\},where in the last we used the Cauchy\-Schwarz inequality and the fact thatggisMgM\_\{g\}\-Lipschitz, i\.e\.,‖∇g​\(x\)‖∗≤Mg,∀x∈Q\\\|\\nabla g\(x\)\\\|\_\{\*\}\\leq M\_\{g\},\\;\\forall x\\in Q\.

Thus, we get the following

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε2​∑i=0k−1hi−ε​∑i∈Jhig\+Mg​D​∑i∈Jhig\+R2\\displaystyle\\quad\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon\}\{2\}\\sum\_\{i=0\}^\{k\-1\}h\_\{i\}\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+M\_\{g\}D\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+R^\{2\}=ε2​∑i∈IhiF\+ε2​∑i∈Jhig−ε​∑i∈Jhig\+Mg​D​∑i∈Jhig\+R2\\displaystyle=\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\+\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+M\_\{g\}D\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+R^\{2\}=ε​∑i∈IhiF−ε2​∑i∈IhiF−ε2​∑i∈Jhig\+Mg​D​∑i∈Jhig\+R2\\displaystyle=\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+M\_\{g\}D\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+R^\{2\}=ε​∑i∈IhiF−ε22​∑i∈I1‖F​\(xi\)‖∗2−ε22​∑i∈J1‖∇g​\(xi\)‖∗2\+Mg​D​ε​∑i∈J1‖∇g​\(xi\)‖∗2\\displaystyle=\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\-\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+R2\\displaystyle\\quad\+R^\{2\}=ε​∑i∈IhiF−\(ε22​∑i=0k−11Mi−Mg​D​ε​∑i∈J1‖∇g​\(xi\)‖∗2\)\+R2\.\\displaystyle=\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{M\_\{i\}\}\-M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)\+R^\{2\}\.In the last equality, we used items 5 and 9 from the listing of Algorithm[2](https://arxiv.org/html/2605.16262#alg2)\. Thus, we have

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<ε​∑i∈IhiF−\(ε22​∑i=0k−11Mi−Mg​D​ε​∑i∈J1‖∇g​\(xi\)‖∗2\)\\displaystyle<\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{M\_\{i\}\}\-M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)\+R2\.\\displaystyle\\quad\+R^\{2\}\.
- •From the first stopping rule \(i\.e\., from \([15](https://arxiv.org/html/2605.16262#S2.E15)\)\), we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε​∑i∈IhiF∀x∈Q\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\quad\\forall x\\in Q\.i\.e\., ⟨F​\(x\),x^−x⟩<ε∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\quad\\forall x\\in Q\.
- •From the second stopping rule \(i\.e\., from \([16](https://arxiv.org/html/2605.16262#S2.E16)\)\), for anyx∈Qx\\in Q, we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε​∑i∈IhiF\+Mg​D​ε​∑i∈J1‖∇g​\(xi\)‖∗2\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\+M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\.Thus, sincehiF=ε‖F​\(xi\)‖∗2h\_\{i\}^\{F\}=\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}, we find ⟨F​\(x\),x^−x⟩<ε\+Mg​D​∑i∈J1‖∇g​\(xi\)‖∗2​\(∑i∈I1‖F​\(xi\)‖∗2\)−1\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+M\_\{g\}D\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)^\{\-1\}\.

Now, for anyi∈Ii\\in I, we haveg​\(xi\)≤εg\(x\_\{i\}\)\\leq\\varepsilon\. Thus, from the convexity ofgg, we have

\(∑i∈IhiF\)​g​\(x^\)\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)g\(\\widehat\{x\}\)=\(∑i∈IhiF\)​g​\(1∑i∈IhiF​∑i∈IhiF​xi\)\\displaystyle=\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)g\\left\(\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}\\right\)≤∑i∈IhiF​g​\(xi\)≤∑i∈IhiF​ε\.\\displaystyle\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}g\(x\_\{i\}\)\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\varepsilon\.This means,

g​\(x^\)≤ε\.g\(\\widehat\{x\}\)\\leq\\varepsilon\.

### 7\.3Proof Theorem[3\.3](https://arxiv.org/html/2605.16262#S3.Thmtheorem3)

###### Proof

For anyi∈Ii\\in I, andx∈Qx\\in Q, we have

hiF​⟨F​\(xi\),xi−x⟩\\displaystyle h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle≤\(hiF\)22​‖F​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{F\}\)^\{2\}\}\{2\}\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)=ε22​‖F​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle=\\frac\{\\varepsilon^\{2\}\}\{2\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(53\)For anyi∈Ji\\in J, andx∈Qx\\in Q, we have

hig​\(g​\(xi\)−g​\(x\)\)\\displaystyle h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)≤\(hig\)22​‖∇g​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{g\}\)^\{2\}\}\{2\}\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)≤\(hig\)22​Mg2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{g\}\)^\{2\}\}\{2\}M\_\{g\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)=ε22\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle=\\frac\{\\varepsilon^\{2\}\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.
Thus, for anyi∈Ji\\in J, we have

εMg​\(g​\(xi\)−g​\(x∗\)\)\+εMg​\(g​\(x∗\)−g​\(x\)\)≤ε22\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\frac\{\\varepsilon\}\{M\_\{g\}\}\\left\(g\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\right\)\+\\frac\{\\varepsilon\}\{M\_\{g\}\}\\left\(g\(x\_\{\*\}\)\-g\(x\)\\right\)\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.
For anyi∈Ji\\in J, we haveg​\(xi\)−g​\(x∗\)≥g​\(xi\)\>ε​Mgg\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\geq g\(x\_\{i\}\)\>\\varepsilon M\_\{g\}, i\.e\.,g​\(xi\)−g​\(x∗\)Mg\>ε\\frac\{g\(x\_\{i\}\)\-g\(x\_\{\*\}\)\}\{M\_\{g\}\}\>\\varepsilon\. Thus, we get the following

ε22\\displaystyle\\frac\{\\varepsilon^\{2\}\}\{2\}<V​\(x,xi\)−V​\(x,xi\+1\)\+εMg​\(g​\(x\)−g​\(x∗\)\)\\displaystyle<V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\+\\frac\{\\varepsilon\}\{M\_\{g\}\}\\left\(g\(x\)\-g\(x\_\{\*\}\)\\right\)≤\(a\)V​\(x,xi\)−V​\(x,xi\+1\)\+εMg​⟨∇g​\(x\),x−x∗⟩\\displaystyle\\stackrel\{\{\\scriptstyle\(a\)\}\}\{\{\\leq\}\}V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\+\\frac\{\\varepsilon\}\{M\_\{g\}\}\\left\\langle\\nabla g\(x\),x\-x\_\{\*\}\\right\\rangle≤\(b\)V​\(x,xi\)−V​\(x,xi\+1\)\+εMg​‖∇g​\(x\)‖∗⋅‖x−x∗‖\\displaystyle\\stackrel\{\{\\scriptstyle\(b\)\}\}\{\{\\leq\}\}V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\+\\frac\{\\varepsilon\}\{M\_\{g\}\}\\\|\\nabla g\(x\)\\\|\_\{\*\}\\cdot\\\|x\-x\_\{\*\}\\\|≤\(c\)V​\(x,xi\)−V​\(x,xi\+1\)\+ε​D,\\displaystyle\\stackrel\{\{\\scriptstyle\(c\)\}\}\{\{\\leq\}\}V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\+\\varepsilon D,where in \(a\) we used the convexity ofgg, in \(b\) we used the Cauchy\-Schwarz inequality, and in \(c\) the fact thatggisMgM\_\{g\}\-Lipschitz andQQis bounded, its diameter isDD\. Thus, we get

ε22<V​\(x,xi\)−V​\(x,xi\+1\)\+ε​D\.\\frac\{\\varepsilon^\{2\}\}\{2\}<V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\+\\varepsilon D\.\(54\)
Summing up inequalities \([7\.3](https://arxiv.org/html/2605.16262#S7.Ex59)\) and \([54](https://arxiv.org/html/2605.16262#S7.E54)\), fromi=0i=0toi=k−1i=k\-1for anyk≥1k\\geq 1, we get the following

∑i∈IhiF​⟨F​\(xi\),xi−x⟩\\displaystyle\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle<ε22​∑i∈I1‖F​\(xi\)‖∗2\+∑i=0k−1\(V​\(x,xi\)−V​\(x,xi\+1\)\)\\displaystyle<\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+\\sum\_\{i=0\}^\{k\-1\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)−ε22​\|J\|\+ε​D​\|J\|\\displaystyle\\quad\-\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|\+\\varepsilon D\|J\|≤ε2​∑i∈IhiF−ε22​\|J\|\+ε​D​\|J\|\+R2\\displaystyle\\leq\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|\+\\varepsilon D\|J\|\+R^\{2\}=ε​∑i∈IhiF−ε2​∑i∈IhiF−ε22​\|J\|\+ε​D​\|J\|\+R2\\displaystyle=\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|\+\\varepsilon D\|J\|\+R^\{2\}=ε​∑i∈IhiF−\(ε22​∑i∈I1‖F​\(xi\)‖∗2\+ε22​\|J\|−ε​D​\|J\|\)\+R2\.\\displaystyle=\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|\-\\varepsilon D\|J\|\\right\)\+R^\{2\}\.\(55\)
But, sinceFFis monotone, then in a similar way as in the proof of Theorem[3\.2](https://arxiv.org/html/2605.16262#S3.Thmtheorem2), we have

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩≤∑i∈IhiF​⟨F​\(xi\),xi−x⟩\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\langle F\(x\),\\widehat\{x\}\-x\\rangle\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\rangle\.\(56\)
Thus, from \([7\.3](https://arxiv.org/html/2605.16262#S7.Ex68)\) and \([56](https://arxiv.org/html/2605.16262#S7.E56)\) we get

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε​∑i∈IhiF−\(ε22​∑i∈I1‖F​\(xi\)‖∗2\+ε22​\|J\|−ε​D​\|J\|\)\+R2\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\langle F\(x\),\\widehat\{x\}\-x\\rangle<\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|\-\\varepsilon D\|J\|\\right\)\+R^\{2\}\.
- •From the first stopping rule of Algorithm 3, we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε​∑i∈IhiF∀x∈Q\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\quad\\forall x\\in Q\.i\.e\., ⟨F​\(x\),x^−x⟩<ε∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\quad\\forall x\\in Q\.
- •From the second stopping rule of Algorithm 3, we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε​∑i∈IhiF\+ε​D​\|J\|∀x∈Q\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\+\\varepsilon D\|J\|\\quad\\forall x\\in Q\.Thus, sincehiF=ε‖F​\(xi\)‖∗2h\_\{i\}^\{F\}=\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}, we find ⟨F​\(x\),x^−x⟩​<ε\+D\|​J\|\(∑i∈I1‖F​\(xi\)‖∗2\)−1∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+D\|J\|\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)^\{\-1\}\\quad\\forall x\\in Q\.

Now, for anyi∈Ii\\in I, we haveg​\(xi\)≤ε​Mgg\(x\_\{i\}\)\\leq\\varepsilon M\_\{g\}\. Thus, from the convexity ofgg, we have

g​\(x^\)≤\(∑i∈IhiF\)−1​∑i∈IhiF​g​\(xi\)≤ε​Mg\.\\displaystyle g\(\\widehat\{x\}\)\\leq\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)^\{\-1\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}g\(x\_\{i\}\)\\leq\\varepsilon M\_\{g\}\.

### 7\.4Proof Theorem[3\.4](https://arxiv.org/html/2605.16262#S3.Thmtheorem4)

###### Proof

For anyi∈Ii\\in I, andx∈Qx\\in Q, we have

hiF​⟨F​\(xi\),xi−x⟩\\displaystyle h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle≤\(hiF\)22​‖F​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{F\}\)^\{2\}\}\{2\}\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)=ε22\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle=\\frac\{\\varepsilon^\{2\}\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(57\)For anyi∈Ji\\in J, andx∈Qx\\in Q, we have

hig​\(g​\(xi\)−g​\(x\)\)\\displaystyle h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)≤\(hig\)22​‖∇g​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{g\}\)^\{2\}\}\{2\}\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)=ε22​‖∇g​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle=\\frac\{\\varepsilon^\{2\}\}\{2\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(58\)
Summing up inequalities \([7\.4](https://arxiv.org/html/2605.16262#S7.Ex78)\) and \([7\.4](https://arxiv.org/html/2605.16262#S7.Ex79)\), fromi=0i=0toi=k−1i=k\-1for anyk≥1k\\geq 1, we get the following

∑i∈IhiF​⟨F​\(xi\),xi−x⟩\+∑i∈Jhig​\(g​\(xi\)−g​\(x\)\)≤ε22​\|I\|\+∑i∈Jε22​‖∇g​\(xi\)‖∗2\+R2,\\displaystyle\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\|I\|\+\\sum\_\{i\\in J\}\\frac\{\\varepsilon^\{2\}\}\{2\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+R^\{2\},where we used the fact

∑i=0k−1\(V​\(x,xi\)−V​\(x,xi\+1\)\)=V​\(x,x0\)−V​\(x,xk\)≤V​\(x,x0\)≤R2\.\\sum\_\{i=0\}^\{k\-1\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)=V\(x,x\_\{0\}\)\-V\(x,x\_\{k\}\)\\leq V\(x,x\_\{0\}\)\\leq R^\{2\}\.
But, sinceFFis monotone, then in a similar way as in the proof of Theorem[3\.2](https://arxiv.org/html/2605.16262#S3.Thmtheorem2), we have

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩≤∑i∈IhiF​⟨F​\(xi\),xi−x⟩\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\langle F\(x\),\\widehat\{x\}\-x\\rangle\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\rangle\.\(59\)
Therefore, we get the following

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩≤ε22​\|I\|\+∑i∈Jε22​‖∇g​\(xi\)‖∗2\+R2−∑i∈Jhig​\(g​\(xi\)−g​\(x\)\)\.\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\|I\|\+\\sum\_\{i\\in J\}\\frac\{\\varepsilon^\{2\}\}\{2\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+R^\{2\}\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)\.
Since for anyi∈Ji\\in J, we haveg​\(xi\)−g​\(x∗\)≥g​\(xi\)\>εg\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\geq g\(x\_\{i\}\)\>\\varepsilon\. Then by the convexity of the functiongg, we have

−∑i∈Jhig​\(g​\(xi\)−g​\(x\)\)\\displaystyle\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)=−∑i∈Jhig​\(g​\(xi\)−g​\(x∗\)\)\+∑i∈Jhig​\(g​\(x\)−g​\(x∗\)\)\\displaystyle=\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\right\)\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\)\-g\(x\_\{\*\}\)\\right\)<−ε​∑i∈Jhig\+∑i∈Jhig​⟨∇g​\(x\),x−x∗⟩\\displaystyle<\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\\langle\\nabla g\(x\),x\-x\_\{\*\}\\right\\rangle≤−∑i∈Jε2‖∇g​\(xi\)‖∗2\+ε​Mg​D​∑i∈J1‖∇g​\(xi\)‖∗2,\\displaystyle\\leq\-\\sum\_\{i\\in J\}\\frac\{\\varepsilon^\{2\}\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+\\varepsilon M\_\{g\}D\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\},where in the last we used the Cauchy\-Schwarz inequality and the fact thatggisMgM\_\{g\}\-Lipschitz, i\.e\.,‖∇g​\(x\)‖∗≤Mg,∀x∈Q\\\|\\nabla g\(x\)\\\|\_\{\*\}\\leq M\_\{g\},\\;\\;\\forall x\\in Q\.

Thus, we get the following

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩\\displaystyle\\qquad\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<ε22\|​I\|\+∑i∈Jε22​‖∇g​\(xi\)‖∗2\+R2−∑i∈Jε2‖∇g​\(xi\)‖∗2\+ε​Mg​D​∑i∈J1‖∇g​\(xi\)‖∗2\\displaystyle<\\frac\{\\varepsilon^\{2\}\}\{2\}\|I\|\+\\sum\_\{i\\in J\}\\frac\{\\varepsilon^\{2\}\}\{2\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+R^\{2\}\-\\sum\_\{i\\in J\}\\frac\{\\varepsilon^\{2\}\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+\\varepsilon M\_\{g\}D\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}=ε2​\|I\|−ε22​\|I\|−ε22​∑i∈J1‖∇g​\(xi\)‖∗2\+ε​Mg​D​∑i∈J1‖∇g​\(xi\)‖∗2\+R2\\displaystyle=\\varepsilon^\{2\}\|I\|\-\\frac\{\\varepsilon^\{2\}\}\{2\}\|I\|\-\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+\\varepsilon M\_\{g\}D\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+R^\{2\}=ε2​\|I\|−\(ε22​\|I\|\+\(ε22−ε​Mg​D\)​∑i∈J1‖∇g​\(xi\)‖∗2\)\+R2\.\\displaystyle=\\varepsilon^\{2\}\|I\|\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\|I\|\+\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\-\\varepsilon M\_\{g\}D\\right\)\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)\+R^\{2\}\.
- •From the first stopping rule of Algorithm 4, for anyx∈Qx\\in Q, we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε2​\|I\|\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon^\{2\}\|I\|\.Thus, ⟨F​\(x\),x^−x⟩​<ε2\|​I\|\(∑i∈Iε‖F​\(xi\)‖∗\)−1=ε​\|I\|​\(∑i∈I1‖F​\(xi\)‖∗\)−1\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon^\{2\}\|I\|\\left\(\\sum\_\{i\\in I\}\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\right\)^\{\-1\}=\\varepsilon\|I\|\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\right\)^\{\-1\}\. But,‖F​\(xi\)‖∗≤LF,∀i∈I\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\\leq L\_\{F\},\\;\\forall i\\in I, thus∑i∈I1‖F​\(xi\)‖∗≥\|I\|LF\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\geq\\frac\{\|I\|\}\{L\_\{F\}\}, and then we get the desired inequality, i\.e\., ⟨F​\(x\),x^−x⟩<ε​LF∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\\quad\\forall x\\in Q\.
- •From the second stopping rule of Algorithm 4, for anyx∈Qx\\in Q, we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩​<ε2\|​I\|\+Mg​D​ε​∑i∈J1‖∇g​\(xi\)‖∗2\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon^\{2\}\|I\|\+M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\.Thus, sincehiF=ε‖F​\(xi\)‖∗h\_\{i\}^\{F\}=\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}, and∑i∈I1‖F​\(xi\)‖∗≥\|I\|LF\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\geq\\frac\{\|I\|\}\{L\_\{F\}\}, we find the desired inequality, i\.e\., ⟨F​\(x\),x^−x⟩<ε​LF\+Mg​D​LF\|I\|​∑i∈J1‖∇g​\(xi\)‖∗2\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\+\\frac\{M\_\{g\}DL\_\{F\}\}\{\|I\|\}\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\.

Now, for anyi∈Ii\\in I, we haveg​\(xi\)≤εg\(x\_\{i\}\)\\leq\\varepsilon\. Thus, from the convexity ofgg, we have

\(∑i∈IhiF\)​g​\(x^\)\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)g\(\\widehat\{x\}\)=\(∑i∈IhiF\)​g​\(1∑i∈IhiF​∑i∈IhiF​xi\)\\displaystyle=\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)g\\left\(\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}\\right\)≤∑i∈IhiF​g​\(xi\)≤∑i∈IhiF​ε\.\\displaystyle\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}g\(x\_\{i\}\)\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\varepsilon\.This means,

g​\(x^\)≤ε\.g\(\\widehat\{x\}\)\\leq\\varepsilon\.

### 7\.5Proof Theorem[3\.5](https://arxiv.org/html/2605.16262#S3.Thmtheorem5)

###### Proof

For anyi∈Ii\\in I, andx∈Qx\\in Q, we have

hiF​⟨F​\(xi\),xi−x⟩\\displaystyle h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle≤\(hiF\)22​‖F​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{F\}\)^\{2\}\}\{2\}\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)=ε22\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle=\\frac\{\\varepsilon^\{2\}\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(60\)For anyi∈J,x∈Qi\\in J,x\\in Q, and since‖∇g​\(xi\)‖∗≤Mg,∀i∈J\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}\\leq M\_\{g\},\\;\\forall i\\in J, we have

hig​\(g​\(xi\)−g​\(x\)\)\\displaystyle h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)≤\(hig\)22​‖∇g​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{g\}\)^\{2\}\}\{2\}\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)≤ε22\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.
Thus, for anyi∈Ji\\in J, we have

εMg​\(g​\(xi\)−g​\(x∗\)\)\+εMg​\(g​\(x∗\)−g​\(x\)\)≤ε22\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\frac\{\\varepsilon\}\{M\_\{g\}\}\\left\(g\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\right\)\+\\frac\{\\varepsilon\}\{M\_\{g\}\}\\left\(g\(x\_\{\*\}\)\-g\(x\)\\right\)\\leq\\frac\{\\varepsilon^\{2\}\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.
For anyi∈Ji\\in J, we haveg​\(xi\)−g​\(x∗\)≥g​\(xi\)\>ε​Mgg\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\geq g\(x\_\{i\}\)\>\\varepsilon M\_\{g\}, i\.e\.,g​\(xi\)−g​\(x∗\)Mg\>ε\\frac\{g\(x\_\{i\}\)\-g\(x\_\{\*\}\)\}\{M\_\{g\}\}\>\\varepsilon\. Thus, as in the proof of Theorem[3\.3](https://arxiv.org/html/2605.16262#S3.Thmtheorem3), we get

ε22<V​\(x,xi\)−V​\(x,xi\+1\)\+ε​D\.\\frac\{\\varepsilon^\{2\}\}\{2\}<V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\+\\varepsilon D\.\(61\)
Summing up inequalities \([7\.5](https://arxiv.org/html/2605.16262#S7.Ex98)\) and \([61](https://arxiv.org/html/2605.16262#S7.E61)\), fromi=0i=0toi=k−1i=k\-1for anyk≥1k\\geq 1, we get the following

∑i∈IhiF​⟨F​\(xi\),xi−x⟩\\displaystyle\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle<ε22\|​I​\|−ε22\|​J​\|\+ε​D\|​J\|\+∑i=0k−1\(V​\(x,xi\)−V​\(x,xi\+1\)\)\\displaystyle<\\frac\{\\varepsilon^\{2\}\}\{2\}\|I\|\-\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|\+\\varepsilon D\|J\|\+\\sum\_\{i=0\}^\{k\-1\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)≤ε2​\|I\|−\(ε22​\|I\|\+ε22​\|J\|−ε​D​\|J\|\)\+R2\.\\displaystyle\\leq\\varepsilon^\{2\}\|I\|\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|\-\\varepsilon D\|J\|\\right\)\+R^\{2\}\.\(62\)
But, sinceFFis monotone, then in a similar way as in the proof of Theorem[3\.2](https://arxiv.org/html/2605.16262#S3.Thmtheorem2), we have

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩≤∑i∈IhiF​⟨F​\(xi\),xi−x⟩\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\langle F\(x\),\\widehat\{x\}\-x\\rangle\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\rangle\.\(63\)
Thus, from \([7\.5](https://arxiv.org/html/2605.16262#S7.Ex102)\) and \([63](https://arxiv.org/html/2605.16262#S7.E63)\) we get

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε2​\|I\|−\(ε22​\|I\|\+ε22​\|J\|−ε​D​\|J\|\)\+R2\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\langle F\(x\),\\widehat\{x\}\-x\\rangle<\\varepsilon^\{2\}\|I\|\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2\}\|J\|\-\\varepsilon D\|J\|\\right\)\+R^\{2\}\.
- •From the first stopping rule of Algorithm 5, for anyx∈Qx\\in Q, we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε2​\|I\|\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon^\{2\}\|I\|\.Thus, ⟨F​\(x\),x^−x⟩​<ε2\|​I\|\(∑i∈Iε‖F​\(xi\)‖∗\)−1=ε​\|I\|​\(∑i∈Iε‖F​\(xi\)‖∗\)−1\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon^\{2\}\|I\|\\left\(\\sum\_\{i\\in I\}\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\right\)^\{\-1\}=\\varepsilon\|I\|\\left\(\\sum\_\{i\\in I\}\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\right\)^\{\-1\}\. But,‖F​\(xi\)‖∗≤LF,∀i∈I\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\\leq L\_\{F\},\\;\\forall i\\in I, thus∑i∈I1‖F​\(xi\)‖∗≥\|I\|LF\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\geq\\frac\{\|I\|\}\{L\_\{F\}\}, and then we get the desired inequality, i\.e\., ⟨F​\(x\),x^−x⟩<ε​LF∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\\quad\\forall x\\in Q\.
- •From the second stopping rule of Algorithm 5, for anyx∈Qx\\in Q, we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε2​\|I\|\+ε​D​\|J\|\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon^\{2\}\|I\|\+\\varepsilon D\|J\|\.Thus, sincehiF=ε‖F​\(xi\)‖∗h\_\{i\}^\{F\}=\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}, and∑i∈I1‖F​\(xi\)‖∗≥\|I\|LF\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\geq\\frac\{\|I\|\}\{L\_\{F\}\}, we find the desired inequality, i\.e\., ⟨F​\(x\),x^−x⟩<ε​LF\+D​LF​\|J\|\|I\|∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\+\\frac\{DL\_\{F\}\|J\|\}\{\|I\|\}\\quad\\forall x\\in Q\.

Now, for anyi∈Ii\\in I, we haveg​\(xi\)≤ε​Mgg\(x\_\{i\}\)\\leq\\varepsilon M\_\{g\}\. Thus, from the convexity ofgg, we have

g​\(x^\)≤\(∑i∈IhiF\)−1​∑i∈IhiF​g​\(xi\)≤ε​Mg\.\\displaystyle g\(\\widehat\{x\}\)\\leq\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)^\{\-1\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}g\(x\_\{i\}\)\\leq\\varepsilon M\_\{g\}\.

### 7\.6Proof Theorem[3\.6](https://arxiv.org/html/2605.16262#S3.Thmtheorem6)

###### Proof

For anyi∈Ii\\in I, andx∈Qx\\in Q, we have

hiF​⟨F​\(xi\),xi−x⟩\\displaystyle h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle≤\(hiF\)22​‖F​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{F\}\)^\{2\}\}\{2\}\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)=ε22​Mg2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle=\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(64\)For anyi∈J,x∈Qi\\in J,x\\in Q, and since∇g​\(xi\)≤Mg,∀i∈J\\nabla g\(x\_\{i\}\)\\leq M\_\{g\},\\;\\forall i\\in J, we have

hig​\(g​\(xi\)−g​\(x\)\)\\displaystyle h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)≤\(hig\)22​‖∇g​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\(h\_\{i\}^\{g\}\)^\{2\}\}\{2\}\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)≤ε22​Mg2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle\\leq\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(65\)
Summing up inequalities \([7\.6](https://arxiv.org/html/2605.16262#S7.Ex110)\) and \([7\.6](https://arxiv.org/html/2605.16262#S7.Ex111)\), fromi=0i=0toi=k−1i=k\-1for anyk≥1k\\geq 1, we get the following

∑i∈IhiF⟨F\(xi\),xi−x⟩\+∑i∈Jhig\(g\(xi\)−g\(x\)\)≤ε22​Mg2\(\|I\|\+\|J\)\|\+R2,\\displaystyle\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)\\leq\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\(\|I\|\+\|J\)\|\+R^\{2\},where we used the fact

∑i=0k−1\(V​\(x,xi\)−V​\(x,xi\+1\)\)=V​\(x,x0\)−V​\(x,xk\)≤V​\(x,x0\)≤R2\.\\sum\_\{i=0\}^\{k\-1\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)=V\(x,x\_\{0\}\)\-V\(x,x\_\{k\}\)\\leq V\(x,x\_\{0\}\)\\leq R^\{2\}\.
But, sinceFFis monotone, then in a similar way as in the proof of Theorem[3\.2](https://arxiv.org/html/2605.16262#S3.Thmtheorem2), we have

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩≤∑i∈IhiF​⟨F​\(xi\),xi−x⟩\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\langle F\(x\),\\widehat\{x\}\-x\\rangle\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\rangle\.
Therefore, we get the following

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩≤ε22​Mg2​\(\|I\|\+\|J\|\)\+R2−∑i∈Jhig​\(g​\(xi\)−g​\(x\)\)\.\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\\leq\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\(\|I\|\+\|J\|\)\+R^\{2\}\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)\.
Since for anyi∈Ji\\in J, we haveg​\(xi\)−g​\(x∗\)≥g​\(xi\)\>εg\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\geq g\(x\_\{i\}\)\>\\varepsilon\. Then by the convexity of the functiongg, we have

−∑i∈Jhig​\(g​\(xi\)−g​\(x\)\)\\displaystyle\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)=−∑i∈Jhig​\(g​\(xi\)−g​\(x∗\)\)\+∑i∈Jhig​\(g​\(x\)−g​\(x∗\)\)\\displaystyle=\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\right\)\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\(g\(x\)\-g\(x\_\{\*\}\)\\right\)<−ε​∑i∈Jhig\+∑i∈Jhig​⟨∇g​\(x\),x−x∗⟩\\displaystyle<\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\}\\left\\langle\\nabla g\(x\),x\-x\_\{\*\}\\right\\rangle≤−ε​∑i∈JεMg2\+\|J\|​εMg2​‖∇g​\(x\)‖∗⋅‖x−x∗‖\\displaystyle\\leq\-\\varepsilon\\sum\_\{i\\in J\}\\frac\{\\varepsilon\}\{M\_\{g\}^\{2\}\}\+\\frac\{\|J\|\\varepsilon\}\{M\_\{g\}^\{2\}\}\\\|\\nabla g\(x\)\\\|\_\{\*\}\\cdot\\\|x\-x\_\{\*\}\\\|≤−ε2Mg2​\|J\|\+ε​DMg​\|J\|,\\displaystyle\\leq\-\\frac\{\\varepsilon^\{2\}\}\{M\_\{g\}^\{2\}\}\|J\|\+\\frac\{\\varepsilon D\}\{M\_\{g\}\}\|J\|,where in the last two inequalities we used the Cauchy\-Schwarz inequality and the fact thatggisMgM\_\{g\}\-Lipschitz, i\.e\.,‖∇g​\(x\)‖∗≤Mg,∀x∈Q\\\|\\nabla g\(x\)\\\|\_\{\*\}\\leq M\_\{g\},\\;\\;\\forall x\\in Q\.

Thus, we get

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<ε22​Mg2​\(\|I\|\+\|J\|\)−ε2Mg2​\|J\|\+ε​DMg​\|J\|\+R2\\displaystyle<\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\(\|I\|\+\|J\|\)\-\\frac\{\\varepsilon^\{2\}\}\{M\_\{g\}^\{2\}\}\|J\|\+\\frac\{\\varepsilon D\}\{M\_\{g\}\}\|J\|\+R^\{2\}=ε2Mg2​\|I\|−\(ε22​Mg2​\|I\|\+ε22​Mg2​\|J\|−ε​DMg​\|J\|\)\+R2\.\\displaystyle=\\frac\{\\varepsilon^\{2\}\}\{M\_\{g\}^\{2\}\}\|I\|\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|J\|\-\\frac\{\\varepsilon D\}\{M\_\{g\}\}\|J\|\\right\)\+R^\{2\}\.
- •From the first stopping rule of Algorithm 6, for anyx∈Qx\\in Q, we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε2​\|I\|Mg2\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon^\{2\}\|I\|\}\{M\_\{g\}^\{2\}\}\.Thus, ⟨F​\(x\),x^−x⟩<ε2​\|I\|Mg2​\(∑i∈Iε‖F​\(xi\)‖∗\)−1=ε2​\|I\|Mg2​\(∑i∈I1‖F​\(xi\)‖∗\)−1\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon^\{2\}\|I\|\}\{M\_\{g\}^\{2\}\}\\left\(\\sum\_\{i\\in I\}\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\right\)^\{\-1\}=\\frac\{\\varepsilon^\{2\}\|I\|\}\{M\_\{g\}^\{2\}\}\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\right\)^\{\-1\}\. But,‖F​\(xi\)‖∗≤LF,∀i∈I\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\\leq L\_\{F\},\\;\\forall i\\in I, thus∑i∈I1‖F​\(xi\)‖∗≥\|I\|LF\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\geq\\frac\{\|I\|\}\{L\_\{F\}\}, and then we get the desired inequality, i\.e\., ⟨F​\(x\),x^−x⟩<ε​LFMg∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon L\_\{F\}\}\{M\_\{g\}\}\\quad\\forall x\\in Q\.
- •From the second stopping rule of Algorithm 6, for anyx∈Qx\\in Q, we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε2​\|I\|Mg2\+ε​\|J\|​DMg\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon^\{2\}\|I\|\}\{M\_\{g\}^\{2\}\}\+\\frac\{\\varepsilon\|J\|D\}\{M\_\{g\}\}\.Thus, sincehiF=ε‖F​\(xi\)‖∗h\_\{i\}^\{F\}=\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}, and∑i∈I1‖F​\(xi\)‖∗≥\|I\|LF\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}\}\\geq\\frac\{\|I\|\}\{L\_\{F\}\}, we find the desired inequality, i\.e\., ⟨F​\(x\),x^−x⟩<ε​LFMg\+\|J\|​D​LFMg​\|I\|∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon L\_\{F\}\}\{M\_\{g\}\}\+\\frac\{\|J\|DL\_\{F\}\}\{M\_\{g\}\|I\|\}\\quad\\forall x\\in Q\.

Now, for anyi∈Ii\\in I, we haveg​\(xi\)≤εg\(x\_\{i\}\)\\leq\\varepsilon\. Thus, from the convexity ofgg, we have

\(∑i∈IhiF\)​g​\(x^\)\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)g\(\\widehat\{x\}\)=\(∑i∈IhiF\)​g​\(1∑i∈IhiF​∑i∈IhiF​xi\)\\displaystyle=\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)g\\left\(\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}\\right\)≤∑i∈IhiF​g​\(xi\)≤∑i∈IhiF​ε\.\\displaystyle\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}g\(x\_\{i\}\)\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\varepsilon\.This means,

g​\(x^\)≤ε\.g\(\\widehat\{x\}\)\\leq\\varepsilon\.

### 7\.7Proof Theorem[3\.7](https://arxiv.org/html/2605.16262#S3.Thmtheorem7)

###### Proof

For anyi∈Ii\\in I, andx∈Qx\\in Q, we have

⟨F​\(xi\),xi−x⟩≤hiF2​‖F​\(xi\)‖∗2\+1hiF​\(V​\(x,xi\)−V​\(x,xi\+1\)\)\.\\displaystyle\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\\leq\\frac\{h\_\{i\}^\{F\}\}\{2\}\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+\\frac\{1\}\{h\_\{i\}^\{F\}\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)\.\(66\)
For anyi∈J,x∈Qi\\in J,x\\in Q, we have

g​\(xi\)−g​\(x\)≤hig2​‖∇g​\(xi\)‖∗2\+1hig​\(V​\(x,xi\)−V​\(x,xi\+1\)\)\.\\displaystyle g\(x\_\{i\}\)\-g\(x\)\\leq\\frac\{h\_\{i\}^\{g\}\}\{2\}\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+\\frac\{1\}\{h\_\{i\}^\{g\}\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)\.\(67\)
Summing up inequalities \([66](https://arxiv.org/html/2605.16262#S7.E66)\) and \([67](https://arxiv.org/html/2605.16262#S7.E67)\), fromi=0i=0toi=k−1i=k\-1for anyk≥1k\\geq 1, and by settinghi:=hiF​∀i∈I,hi:=hig​∀i∈Jh\_\{i\}:=h\_\{i\}^\{F\}\\,\\forall i\\in I,h\_\{i\}:=h\_\{i\}^\{g\}\\,\\forall i\\in J, we get the following

∑i∈I⟨F​\(xi\),xi−x⟩\+∑i∈J\(g​\(xi\)−g​\(x\)\)\\displaystyle\\quad\\sum\_\{i\\in I\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\+\\sum\_\{i\\in J\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)≤∑i=0k−1hi​Mi22\+∑i=0k−11hi​\(V​\(x,xi\)−V​\(x,xi\+1\)\)\.\\displaystyle\\leq\\sum\_\{i=0\}^\{k\-1\}\\frac\{h\_\{i\}M\_\{i\}^\{2\}\}\{2\}\+\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{h\_\{i\}\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)\.
But, sinceFFis monotone, then

⟨F​\(x\),xi−x⟩≤⟨F​\(xi\),xi−x⟩,∀i∈I,∀x∈Q\.\\langle F\(x\),x\_\{i\}\-x\\rangle\\leq\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\rangle,\\quad\\forall i\\in I,\\,\\forall x\\in Q\.We also have,

∑i∈I⟨F​\(x\),xi−x⟩\\displaystyle\\sum\_\{i\\in I\}\\left\\langle F\(x\),x\_\{i\}\-x\\right\\rangle=⟨F​\(x\),∑i∈I\(xi−x\)⟩=\|I\|​⟨F​\(x\),1\|I\|​∑i∈Ixi−x⟩\\displaystyle=\\left\\langle F\(x\),\\sum\_\{i\\in I\}\(x\_\{i\}\-x\)\\right\\rangle=\|I\|\\left\\langle F\(x\),\\frac\{1\}\{\|I\|\}\\sum\_\{i\\in I\}x\_\{i\}\-x\\right\\rangle=\|I\|​⟨F​\(x\),x^−x⟩\.\\displaystyle=\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\.
Since for anyi∈Ji\\in J, we haveg​\(xi\)−g​\(x∗\)≥g​\(xi\)\>εg\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\geq g\(x\_\{i\}\)\>\\varepsilon\. Then by the convexity of the functiongg, we have

−∑i∈J\(g​\(xi\)−g​\(x\)\)\\displaystyle\-\\sum\_\{i\\in J\}\\left\(g\(x\_\{i\}\)\-g\(x\)\\right\)=−∑i∈J\(g​\(xi\)−g​\(x∗\)\)\+∑i∈J\(g​\(x\)−g​\(x∗\)\)\\displaystyle=\-\\sum\_\{i\\in J\}\\left\(g\(x\_\{i\}\)\-g\(x\_\{\*\}\)\\right\)\+\\sum\_\{i\\in J\}\\left\(g\(x\)\-g\(x\_\{\*\}\)\\right\)<−ε​\|J\|\+\|J\|​⟨∇g​\(x\),x−x∗⟩\\displaystyle<\-\\varepsilon\|J\|\+\|J\|\\left\\langle\\nabla g\(x\),x\-x\_\{\*\}\\right\\rangle≤−ε​\|J\|\+\|J\|⋅‖∇g​\(x\)‖∗⋅‖x−x∗‖\\displaystyle\\leq\-\\varepsilon\|J\|\+\|J\|\\cdot\\\|\\nabla g\(x\)\\\|\_\{\*\}\\cdot\\\|x\-x\_\{\*\}\\\|≤−ε​\|J\|\+Mg​D​\|J\|,\\displaystyle\\leq\-\\varepsilon\|J\|\+M\_\{g\}D\|J\|,In the last two inequalities, we used the Cauchy\-Schwarz inequality and the fact thatggisMgM\_\{g\}\-Lipschitz, i\.e\.,‖∇g​\(x\)‖∗≤Mg,∀x∈Q\\\|\\nabla g\(x\)\\\|\_\{\*\}\\leq M\_\{g\},\\;\\forall x\\in Q\.

Thus, we get the following

\|I\|​⟨F​\(x\),x^−x⟩\\displaystyle\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<∑i=0k−1hi​Mi22\+∑i=0k−11hi​\(V​\(x,xi\)−V​\(x,xi\+1\)\)\\displaystyle<\\sum\_\{i=0\}^\{k\-1\}\\frac\{h\_\{i\}M\_\{i\}^\{2\}\}\{2\}\+\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{h\_\{i\}\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)\+Mg​D​\|J\|−ε​\|J\|\\displaystyle\\quad\+M\_\{g\}D\|J\|\-\\varepsilon\|J\|=θ2​∑i=0k−1Mi2\(∑t=0iMt2\)1/2\+∑i=0k−11hi​\(V​\(x,xi\)−V​\(x,xi\+1\)\)\\displaystyle=\\frac\{\\theta\}\{2\}\\sum\\limits\_\{i=0\}^\{k\-1\}\\frac\{M\_\{i\}^\{2\}\}\{\\left\(\\sum\_\{t=0\}^\{i\}M\_\{t\}^\{2\}\\right\)^\{1/2\}\}\+\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{h\_\{i\}\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)\(68\)\+Mg​D​\|J\|−ε​\|J\|\.\\displaystyle\\quad\+M\_\{g\}D\|J\|\-\\varepsilon\|J\|\.
But,

∑i=0k−11hi​\(V​\(x,xi\)−V​\(x,xi\+1\)\)\\displaystyle\\quad\\sum\\limits\_\{i=0\}^\{k\-1\}\\frac\{1\}\{h\_\{i\}\}\\left\(V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\\right\)=1h0​V​\(x,x0\)\+∑i=0k−2\(1hi\+1−1hi\)​V​\(x,xi\+1\)−1hk−1​V​\(x,xi\)\\displaystyle=\\frac\{1\}\{h\_\{0\}\}V\(x,x\_\{0\}\)\+\\sum\_\{i=0\}^\{k\-2\}\\left\(\\frac\{1\}\{h\_\{i\+1\}\}\-\\frac\{1\}\{h\_\{i\}\}\\right\)V\(x,x\_\{i\+1\}\)\-\\frac\{1\}\{h\_\{k\-1\}\}V\(x,x\_\{i\}\)≤θ2h0\+θ2​∑i=0k−2\(1hi\+1−1hi\)=θ2hk−1=θ​\(∑i=0k−1Mi2\)1/2\.\\displaystyle\\leq\\frac\{\\theta^\{2\}\}\{h\_\{0\}\}\+\\theta^\{2\}\\sum\\limits\_\{i=0\}^\{k\-2\}\\Big\(\\frac\{1\}\{h\_\{i\+1\}\}\-\\frac\{1\}\{h\_\{i\}\}\\Big\)=\\frac\{\\theta^\{2\}\}\{h\_\{k\-1\}\}=\\theta\\left\(\\sum\_\{i=0\}^\{k\-1\}M\_\{i\}^\{2\}\\right\)^\{1/2\}\.\(69\)
By induction \(onk≥1k\\geq 1\), we can simply prove that

∑i=0k−1Mi2\(∑t=0iMt2\)1/2≤2​\(∑i=0k−1Mi2\)1/2\.\\sum\\limits\_\{i=0\}^\{k\-1\}\\frac\{M\_\{i\}^\{2\}\}\{\\left\(\\sum\_\{t=0\}^\{i\}M\_\{t\}^\{2\}\\right\)^\{1/2\}\}\\leq 2\\left\(\\sum\_\{i=0\}^\{k\-1\}M\_\{i\}^\{2\}\\right\)^\{1/2\}\.\(70\)
Therefore, from \([7\.7](https://arxiv.org/html/2605.16262#S7.Ex140)\), \([7\.7](https://arxiv.org/html/2605.16262#S7.Ex143)\) and \([70](https://arxiv.org/html/2605.16262#S7.E70)\), we get

\|I\|​⟨F​\(x\),x^−x⟩<2​θ​\(∑i=0k−1Mi2\)1/2\+\|J\|​Mg​D−ε​k\+ε​\|I\|\.\\displaystyle\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<2\\theta\\left\(\\sum\_\{i=0\}^\{k\-1\}M\_\{i\}^\{2\}\\right\)^\{1/2\}\+\|J\|M\_\{g\}D\-\\varepsilon k\+\\varepsilon\|I\|\.
- •From the first stopping rule of Algorithm 7, for anyx∈Qx\\in Q, we get \|I\|​⟨F​\(x\),x^−x⟩<ε​\|I\|⟹⟨F​\(x\),x^−x⟩<ε\.\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\|I\|\\quad\\Longrightarrow\\quad\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\.
- •From the second stopping rule of Algorithm 7, for anyx∈Qx\\in Q, we get \|I\|​⟨F​\(x\),x^−x⟩<ε​\|I\|\+\|J\|​Mg​D⟹⟨F​\(x\),x^−x⟩<ε\+\|J\|​Mg​D\|I\|\.\|I\|\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\|I\|\+\|J\|M\_\{g\}D\\quad\\Longrightarrow\\quad\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\frac\{\|J\|M\_\{g\}D\}\{\|I\|\}\.

Now, for anyi∈Ii\\in I, we haveg​\(xi\)≤εg\(x\_\{i\}\)\\leq\\varepsilon\. Thus, from the convexity ofgg, we have

\|I\|​g​\(x^\)=\|I\|​g​\(1\|I\|​∑i∈Ixi\)≤∑i∈Ig​\(xi\)≤\|I\|​ε\.\\displaystyle\|I\|g\(\\widehat\{x\}\)=\|I\|g\\left\(\\frac\{1\}\{\|I\|\}\\sum\_\{i\\in I\}x\_\{i\}\\right\)\\leq\\sum\_\{i\\in I\}g\(x\_\{i\}\)\\leq\|I\|\\varepsilon\.This means,

g​\(x^\)≤ε\.g\(\\widehat\{x\}\)\\leq\\varepsilon\.

## 8Appendix 2: Proof Theorem[4\.1](https://arxiv.org/html/2605.16262#S4.Thmtheorem1)

###### Proof

Fori∈Ii\\in I, andx∈Qx\\in Q, we have

hiF​⟨F​\(xi\),xi−x⟩≤hiF​ε2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\\leq\\frac\{h\_\{i\}^\{F\}\\varepsilon\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(71\)Fori∈Ji\\in J, andx∈Qx\\in Q, there isN​\(i\)∈\{1,2,…,m\}N\(i\)\\in\\\{1,2,\\ldots,m\\\}such that

higN​\(i\)​\(gN​\(i\)​\(xi\)−gN​\(i\)​\(x\)\)\\displaystyle h\_\{i\}^\{g\_\{N\(i\)\}\}\\left\(g\_\{N\(i\)\}\(x\_\{i\}\)\-g\_\{N\(i\)\}\(x\)\\right\)≤\(higN​\(i\)\)22​‖∇gN​\(i\)​\(xi\)‖∗2\+V​\(x,xi\)−V​\(x,xi\+1\)\\displaystyle\\leq\\frac\{\\left\(h\_\{i\}^\{g\_\{N\(i\)\}\}\\right\)^\{2\}\}\{2\}\\\|\\nabla g\_\{N\(i\)\}\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)=higN​\(i\)​ε2\+V​\(x,xi\)−V​\(x,xi\+1\)\.\\displaystyle=\\frac\{h\_\{i\}^\{g\_\{N\(i\)\}\}\\varepsilon\}\{2\}\+V\(x,x\_\{i\}\)\-V\(x,x\_\{i\+1\}\)\.\(72\)
Summing up inequalities \([71](https://arxiv.org/html/2605.16262#S8.E71)\) and \([8](https://arxiv.org/html/2605.16262#S8.Ex150)\), fromi=0i=0toi=k−1i=k\-1for anyk≥1k\\geq 1, we get the following

∑i∈IhiF​⟨F​\(xi\),xi−x⟩≤ε2​∑i=0k−1hi\+R2−∑i∈JhigN​\(i\)​\(gN​\(i\)​\(xi\)−gN​\(i\)​\(x\)\)\.\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\\leq\\frac\{\\varepsilon\}\{2\}\\sum\_\{i=0\}^\{k\-1\}h\_\{i\}\+R^\{2\}\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\\left\(g\_\{N\(i\)\}\(x\_\{i\}\)\-g\_\{N\(i\)\}\(x\)\\right\)\.
Because of the operatorFFis monotone, then we have

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩≤ε2​∑i=0k−1hi\+R2−∑i∈JhigN​\(i\)​\(gN​\(i\)​\(xi\)−gN​\(i\)​\(x\)\)\.\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\\leq\\frac\{\\varepsilon\}\{2\}\\sum\_\{i=0\}^\{k\-1\}h\_\{i\}\+R^\{2\}\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\\left\(g\_\{N\(i\)\}\(x\_\{i\}\)\-g\_\{N\(i\)\}\(x\)\\right\)\.
Since fori∈Ji\\in J, we havegN​\(i\)​\(xi\)−gN​\(i\)​\(x∗\)≥gN​\(i\)​\(xi\)\>εg\_\{N\(i\)\}\(x\_\{i\}\)\-g\_\{N\(i\)\}\(x\_\{\*\}\)\\geq g\_\{N\(i\)\}\(x\_\{i\}\)\>\\varepsilon\. Then by the convexity of the functiongN​\(i\)g\_\{N\(i\)\}, we have

−∑i∈JhigN​\(i\)​\(gN​\(i\)​\(xi\)−gN​\(i\)​\(x\)\)\\displaystyle\\quad\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\\left\(g\_\{N\(i\)\}\(x\_\{i\}\)\-g\_\{N\(i\)\}\(x\)\\right\)=−∑i∈JhigN​\(i\)​\(gN​\(i\)​\(xi\)−gN​\(i\)​\(x∗\)\)\+∑i∈JhigN​\(i\)​\(gN​\(i\)​\(x\)−gN​\(i\)​\(x∗\)\)\\displaystyle=\-\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\\left\(g\_\{N\(i\)\}\(x\_\{i\}\)\-g\_\{N\(i\)\}\(x\_\{\*\}\)\\right\)\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\\left\(g\_\{N\(i\)\}\(x\)\-g\_\{N\(i\)\}\(x\_\{\*\}\)\\right\)<−ε​∑i∈JhigN​\(i\)\+∑i∈JhigN​\(i\)​⟨∇gN​\(i\)​\(x\),x−x∗⟩\\displaystyle<\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\+\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\\left\\langle\\nabla g\_\{N\(i\)\}\(x\),x\-x\_\{\*\}\\right\\rangle≤−ε​∑i∈JhigN​\(i\)\+Mg​D​∑i∈JhigN​\(i\),\\displaystyle\\leq\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\+M\_\{g\}D\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\},where in the last we used the Cauchy\-Schwarz inequality and the fact thatgN​\(i\)g\_\{N\(i\)\}isMgM\_\{g\}\-Lipschitz, i\.e\.,‖∇gN​\(i\)​\(x\)‖∗≤Mg,∀x∈Q\\\|\\nabla g\_\{N\(i\)\}\(x\)\\\|\_\{\*\}\\leq M\_\{g\},\\;\\;\\forall x\\in Q\.

Thus, we get the following

\(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε2​∑i=0k−1hi−ε​∑i∈JhigN​\(i\)\+Mg​D​∑i∈JhigN​\(i\)\+R2\\displaystyle\\quad\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon\}\{2\}\\sum\_\{i=0\}^\{k\-1\}h\_\{i\}\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\+M\_\{g\}D\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\+R^\{2\}=ε2​∑i∈IhiF\+ε2​∑i∈JhigN​\(i\)−ε​∑i∈JhigN​\(i\)\+Mg​D​∑i∈JhigN​\(i\)\+R2\\displaystyle=\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\+\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\-\\varepsilon\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\+M\_\{g\}D\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\+R^\{2\}=ε​∑i∈IhiF−ε2​∑i∈IhiF−ε2​∑i∈JhigN​\(i\)\+Mg​D​∑i∈JhigN​\(i\)\+R2\\displaystyle=\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\frac\{\\varepsilon\}\{2\}\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\+M\_\{g\}D\\sum\_\{i\\in J\}h\_\{i\}^\{g\_\{N\(i\)\}\}\+R^\{2\}=ε​∑i∈IhiF−ε22​∑i∈I1‖F​\(xi\)‖∗2−ε22​∑i∈J1‖∇gN​\(i\)​\(xi\)‖∗2\\displaystyle=\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\-\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\_\{N\(i\)\}\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+Mg​D​ε​∑i∈J1‖∇gN​\(i\)​\(xi\)‖∗2\+R2\\displaystyle\\quad\+M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\_\{N\(i\)\}\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\+R^\{2\}=ε​∑i∈IhiF−\(ε22​∑i=0k−11Mi−Mg​D​ε​∑i∈J1‖∇gN​\(i\)​\(xi\)‖∗2\)\+R2\.\\displaystyle=\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2\}\\sum\_\{i=0\}^\{k\-1\}\\frac\{1\}\{M\_\{i\}\}\-M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\_\{N\(i\)\}\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)\+R^\{2\}\.
- •From the first stopping rule \(i\.e\., from \([38](https://arxiv.org/html/2605.16262#S4.E38)\)\), we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε​∑i∈IhiF\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\.i\.e\., ⟨F​\(x\),x^−x⟩<ε\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\.
- •From the second stopping rule \(i\.e\., from \([39](https://arxiv.org/html/2605.16262#S4.E39)\)\), we get \(∑i∈IhiF\)​⟨F​\(x\),x^−x⟩<ε​∑i∈IhiF\+Mg​D​ε​∑i∈J1‖∇gN​\(i\)​\(xi\)‖∗2\.\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\+M\_\{g\}D\\varepsilon\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\_\{N\(i\)\}\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\.Thus, sincehiF=ε‖F​\(xi\)‖∗2h\_\{i\}^\{F\}=\\frac\{\\varepsilon\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}, we find ⟨F​\(x\),x^−x⟩<ε\+Mg​D​∑i∈J1‖∇gN​\(i\)​\(xi\)‖∗2​\(∑i∈I1‖F​\(xi\)‖∗2\)−1\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+M\_\{g\}D\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\_\{N\(i\)\}\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)^\{\-1\}\.

Now, for anyi∈Ii\\in I, we havegj​\(xi\)≤ε,∀j=1,…,mg\_\{j\}\(x\_\{i\}\)\\leq\\varepsilon,\\;\\forall j=1,\\ldots,m, thusg​\(xi\)=max1≤j≤m⁡\{gj​\(xi\)\}≤εg\(x\_\{i\}\)=\\max\_\{1\\leq j\\leq m\}\\\{g\_\{j\}\(x\_\{i\}\)\\\}\\leq\\varepsilon\. Therefore, from the convexity ofgg, we have

\(∑i∈IhiF\)​g​\(x^\)\\displaystyle\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)g\(\\widehat\{x\}\)=\(∑i∈IhiF\)​g​\(1∑i∈IhiF​∑i∈IhiF​xi\)\\displaystyle=\\left\(\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\right\)g\\left\(\\frac\{1\}\{\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\}\\sum\_\{i\\in I\}h\_\{i\}^\{F\}x\_\{i\}\\right\)≤∑i∈IhiF​g​\(xi\)≤∑i∈IhiF​ε\.\\displaystyle\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}g\(x\_\{i\}\)\\leq\\sum\_\{i\\in I\}h\_\{i\}^\{F\}\\varepsilon\.This meansg​\(x^\)≤εg\(\\widehat\{x\}\)\\leq\\varepsilon, thus

gi​\(x^\)≤ε,∀i∈\{1,2,…,m\}\.g\_\{i\}\(\\widehat\{x\}\)\\leq\\varepsilon,\\quad\\forall i\\in\\\{1,2,\\ldots,m\\\}\.

## 9Appendix 3: Analysis of the proposed algorithms withδ\\delta\-monotone operators

###### Definition 2

\(δ\\delta\-monotone operator\)\. Letδ\>0\\delta\>0\. The operatorF:Q⟶E∗F:Q\\longrightarrow\\textbf\{E\}^\{\*\}is calledδ\\delta\-monotone, if it holds:

⟨F​\(y\)−F​\(x\),y−x⟩≥−δ∀x,y∈Q\.\\langle F\(y\)\-F\(x\),y\-x\\rangle\\geq\-\\delta\\quad\\forall x,y\\in Q\.\(73\)

For example, we can considerF=∇δfF=\\nabla\_\{\\delta\}fforδ\\delta\-subgradient∇δf​\(x\)\\nabla\_\{\\delta\}f\(x\)of convex functionffat pointx∈Qx\\in Q:f​\(y\)−f​\(x\)≥⟨∇δf​\(x\),y−x⟩−δf\(y\)\-f\(x\)\\geq\\langle\\nabla\_\{\\delta\}f\(x\),y\-x\\rangle\-\\deltafor eachy∈Qy\\in Q\(see e\.g\.,\[[43](https://arxiv.org/html/2605.16262#bib.bib43)\], Chapter 5\)\. Note that whenδ=0\\delta=0, we get the definition of monotone operators\.

The analysis of algorithms under the assumption that the operatorFFisδ\\delta\-monotone will be the same as the analysis with monotone operators, and the results will be the same with a slight difference, where we will have the following inequalities\.

1. 1\.For Algorithm[1](https://arxiv.org/html/2605.16262#alg1), we have, - •with stopping criterion 1 \([13](https://arxiv.org/html/2605.16262#S2.E13)\), we get ⟨F​\(x\),x^−x⟩<ε\+δ∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\delta\\quad\\forall x\\in Q\.\(74\) - •With stopping criterion 2 \([14](https://arxiv.org/html/2605.16262#S2.E14)\), we get ⟨F​\(x\),x^−x⟩<ε\+δ\+D​LF2​\|J\|Mg​\|I\|∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\delta\+\\frac\{DL\_\{F\}^\{2\}\|J\|\}\{M\_\{g\}\|I\|\}\\quad\\forall x\\in Q\.\(75\)
2. 2\.For Algorithm[2](https://arxiv.org/html/2605.16262#alg2), we have, - •with stopping criterion 1 \([15](https://arxiv.org/html/2605.16262#S2.E15)\), we get ⟨F​\(x\),x^−x⟩<ε\+δ∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\delta\\quad\\forall x\\in Q\. - •With stopping criterion 2 \([16](https://arxiv.org/html/2605.16262#S2.E16)\), we get ⟨F​\(x\),x^−x⟩<ε\+δ\+Mg​D​∑i∈J1‖∇g​\(xi\)‖∗2​\(∑i∈I1‖F​\(xi\)‖∗2\)−1∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\delta\+M\_\{g\}D\\sum\_\{i\\in J\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)^\{\-1\}\\quad\\forall x\\in Q\.
3. 3\.For Algorithm 3, we have, - •with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε\+δ∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\delta\\quad\\forall x\\in Q\. - •With stopping criterion 2, we get ⟨F​\(x\),x^−x⟩​<ε\+δ\+D\|​J\|\(∑i∈I1‖F​\(xi\)‖∗2\)−1∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\delta\+D\|J\|\\left\(\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|F\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\right\)^\{\-1\}\\quad\\forall x\\in Q\.
4. 4\.For Algorithm 4, we have, - •with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε​LF\+δ∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\+\\delta\\quad\\forall x\\in Q\. - •With stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε​LF\+δ\+Mg​D​LF\|I\|​∑i∈I1‖∇g​\(xi\)‖∗2∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\+\\delta\+\\frac\{M\_\{g\}DL\_\{F\}\}\{\|I\|\}\\sum\_\{i\\in I\}\\frac\{1\}\{\\\|\\nabla g\(x\_\{i\}\)\\\|\_\{\*\}^\{2\}\}\\quad\\forall x\\in Q\.
5. 5\.For Algorithm 5, we have, - •with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε​LF\+δ∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\+\\delta\\quad\\forall x\\in Q\. - •With stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε​LF\+δ\+D​LF​\|J\|\|I\|∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon L\_\{F\}\+\\delta\+\\frac\{DL\_\{F\}\|J\|\}\{\|I\|\}\\quad\\forall x\\in Q\.
6. 6\.For Algorithm 6, we have, - •with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε​LFMg\+δ∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon L\_\{F\}\}\{M\_\{g\}\}\+\\delta\\quad\\forall x\\in Q\. - •With stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε​LFMg\+δ\+D​LF​\|J\|Mg​\|I\|∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\frac\{\\varepsilon L\_\{F\}\}\{M\_\{g\}\}\+\\delta\+\\frac\{DL\_\{F\}\|J\|\}\{M\_\{g\}\|I\|\}\\quad\\forall x\\in Q\.
7. 7\.For Algorithm 7, we have, - •with stopping criterion 1, we get ⟨F​\(x\),x^−x⟩<ε\+δ∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\delta\\quad\\forall x\\in Q\. - •With stopping criterion 2, we get ⟨F​\(x\),x^−x⟩<ε\+\|J\|​Mg​D\|I\|\+δ∀x∈Q\.\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle<\\varepsilon\+\\frac\{\|J\|M\_\{g\}D\}\{\|I\|\}\+\\delta\\quad\\forall x\\in Q\.

Let us briefly show how we can prove the result of Algorithm[1](https://arxiv.org/html/2605.16262#alg1)forδ\\delta\-monotone operatorFF, i\.e\., the results \([74](https://arxiv.org/html/2605.16262#S9.E74)\) and \([75](https://arxiv.org/html/2605.16262#S9.E75)\)\. The proof will be the same as the proof of Theorem[3\.1](https://arxiv.org/html/2605.16262#S3.Thmtheorem1), with a slight modification concerning theδ\\deltamonotonicity of the operatorFF\.

For anyi∈Ii\\in I, andx∈Qx\\in Q, sinceFFisδ\\delta\-monotone operator, we get

⟨F​\(x\),xi−x⟩−δ≤⟨F​\(xi\),xi−x⟩\.\\left\\langle F\(x\),x\_\{i\}\-x\\right\\rangle\-\\delta\\leq\\left\\langle F\(x\_\{i\}\),x\_\{i\}\-x\\right\\rangle\.
Now, from \([44](https://arxiv.org/html/2605.16262#S7.E44)\), \([7\.1](https://arxiv.org/html/2605.16262#S7.Ex18)\) and \([47](https://arxiv.org/html/2605.16262#S7.E47)\), for anyx∈Qx\\in Q, we get

hF​\|I\|​\(⟨F​\(x\),x^−x⟩−δ\)<ε2LF2​\|I\|−\(ε22​LF2​\|I\|\+ε22​Mg2​\|J\|−ε​D​\|J\|Mg\)\+R2\.\\displaystyle h^\{F\}\|I\|\\left\(\\left\\langle F\(x\),\\widehat\{x\}\-x\\right\\rangle\-\\delta\\right\)<\\frac\{\\varepsilon^\{2\}\}\{L\_\{F\}^\{2\}\}\|I\|\-\\left\(\\frac\{\\varepsilon^\{2\}\}\{2L\_\{F\}^\{2\}\}\|I\|\+\\frac\{\\varepsilon^\{2\}\}\{2M\_\{g\}^\{2\}\}\|J\|\-\\frac\{\\varepsilon D\|J\|\}\{M\_\{g\}\}\\right\)\+R^\{2\}\.
Thus, with stopping criterion 1 \([13](https://arxiv.org/html/2605.16262#S2.E13)\) we get \([74](https://arxiv.org/html/2605.16262#S9.E74)\), and with stopping criterion 2 \([14](https://arxiv.org/html/2605.16262#S2.E14)\) we get \([75](https://arxiv.org/html/2605.16262#S9.E75)\)\.

## 10Appendix 4: Additional experiments: 2D Example for min\-max problem: Forsaken Game

In this section, we provide the following 2D example with min\-max objectives and one ellipse constraint to illustrate the trajectory of Algorithms[2](https://arxiv.org/html/2605.16262#alg2)—6\. This problem is connected with the forsaken game\[[44](https://arxiv.org/html/2605.16262#bib.bib44)\]\. It does not have constraints in its original formulation, and we add an ellipse constraint to test our algorithms\[[26](https://arxiv.org/html/2605.16262#bib.bib26)\]\.

The forsaken game has the objective

minx∈ℝ⁡maxy∈ℝ⁡\{x​\(y−0\.45\)\+h​\(x\)−h​\(y\)\},\\displaystyle\\min\_\{x\\in\\mathbb\{R\}\}\\max\_\{y\\in\\mathbb\{R\}\}\\left\\\{x\(y\-0\.45\)\+h\(x\)\-h\(y\)\\right\\\},\(76\)s\.t\.x2\+4​y2≤1,\\displaystyle\\text\{ s\.t\. \}\\quad x^\{2\}\+4y^\{2\}\\leq 1,whereh​\(x\)=x24−x42\+x66h\(x\)=\\frac\{x^\{2\}\}\{4\}\-\\frac\{x^\{4\}\}\{2\}\+\\frac\{x^\{6\}\}\{6\}\. This problem has a desirable\(x∗,y∗\)≈\(0\.08,0\.4\)\(x\_\{\*\},y\_\{\*\}\)\\approx\(0\.08,0\.4\)\. This example is known to exhibit limit cycles, complicating equilibrium computations\. Notably, the limit cycle near the solution is unstable, repelling any trajectories that approach it\.

![Refer to caption](https://arxiv.org/html/2605.16262v1/x3.png)

![Refer to caption](https://arxiv.org/html/2605.16262v1/x4.png)

Figure 2:Results of Algorithms[2](https://arxiv.org/html/2605.16262#alg2)—6, for the forsaken game with different initial points, withε=0\.001\\varepsilon=0\.001and by10410^\{4\}iterations of each algorithm, except Algorithm 6 with10510^\{5\}iterations\.