Authors are encouraged to submit new papers to INFORMS journals by means of a style file template, which includes the journal title. However, use of a template does not certify that the paper has been accepted for publication in the named journal. INFORMS journal templates are for the exclusive purpose of submitting to an INFORMS journal and are not intended to be a true representation of the article’s final published form. Use of this template to distribute papers in print or online or to submit papers to another non-INFORM publication is prohibited.
Funding: This research was supported by the Air Force Office of Scientific Research grant FA9550-25-1-0278.
Introduction
Many equilibrium models incorporate functional constraints to capture operational and physical restrictions on decentralized decisions. For example, in transportation networks, Wardrop equilibrium route choices could yield network flows subject to traffic-control, network-wide emission, or battery-range constraints [10 , 18 ] . Similar structures arise in communication and computing systems, where users compete for bandwidth under quality-of-service constraints [5 ] . In supply-chain and oligopoly models, firms may compete in a Cournot equilibrium subject to limited supplier capacities or firm-level resource constraints [3 , 2 ] . These problems can be formulated as constrained variational inequalities (CVIs), where equilibrium solutions are subject to many nonlinear functional constraints. These feasibility requirements pose substantial computational challenges beyond those of unconstrained equilibrium problems.
We consider the CVIs of finding a point x ∗ ∈ X ~ x^* \in\widetilde{X} x ∗ ∈ X such that
⟨ F ( x ∗ ) , x ∗ − x ⟩ ≤ 0 , ∀ x ∈ X ~ : = { x ∈ X : G ( x ) ≤ 0 } . (1) \langle F(x^*),x^*-x\rangle\le0,\quad\forall x\in\widetilde{X}:=\{x\in X:G(x)\le0\}. \tag*{(1)} ⟨ F ( x ∗ ) , x ∗ − x ⟩ ≤ 0 , ∀ x ∈ X := { x ∈ X : G ( x ) ≤ 0 } . (1)
Here, X ⊆ R n X\subseteq\mathbb{R}^n X ⊆ R n is a compact convex set onto which projection is computationally inexpensive. The operator F : R n → R n F:\mathbb{R}^n\to\mathbb{R}^n F : R n → R n is monotone and Lipschitz continuous with respect to the Euclidean norm, that is, there exists M > 0 M>0 M > 0 such that
⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ 0 , ∥ F ( u ) − F ( v ) ∥ ≤ M ∥ u − v ∥ , ∀ u , v ∈ X . \langle F(u)-F(v),u-v\rangle\ge0,\qquad\|F(u)-F(v)\|\le M\|u-v\|,\quad\forall u,v\in X. ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ 0 , ∥ F ( u ) − F ( v ) ∥ ≤ M ∥ u − v ∥ , ∀ u , v ∈ X .
The constraint mapping G ( x ) : = ( g 1 ( x ) , … , g m ( x ) ) ⊤ G(x):=(g_1(x),\ldots,g_m(x))^\top G ( x ) := ( g 1 ( x ) , … , g m ( x ) ) ⊤ consists of convex and differentiable functions g i : R n → R g_i:\mathbb{R}^n\to\mathbb{R} g i : R n → R , with G ( x ) ≤ 0 G(x)\le0 G ( x ) ≤ 0 interpreted componentwise. ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ denotes the Euclidean norm for vectors and the induced operator norm for matrices Its Jacobian J ( x ) J(x) J ( x ) has ∇ g i ( x ) ⊤ \nabla g_i(x)^\top ∇ g i ( x ) ⊤ as its i i i th row. In addition, each g i g_i g i has an L ( i ) L_{(i)} L ( i ) -Lipschitz continuous gradient on X X X , with L ( i ) > 0 L_{(i)}>0 L ( i ) > 0 , so that
0 ≤ g i ( v ) − g i ( u ) − ⟨ ∇ g i ( u ) , v − u ⟩ ≤ L ( i ) 2 ∥ v − u ∥ 2 , ∀ u , v ∈ X . 0\le g_i(v)-g_i(u)-\langle\nabla g_i(u),v-u\rangle\le\frac{L_{(i)}}{2}\|v-u\|^2,\quad\forall u,v\in X. 0 ≤ g i ( v ) − g i ( u ) − ⟨ ∇ g i ( u ) , v − u ⟩ ≤ 2 L ( i ) ∥ v − u ∥ 2 , ∀ u , v ∈ X .
We denote the aggregate smoothness constant by L : = ( ∑ i = 1 m L ( i ) 2 ) 1 / 2 L:=\left(\sum_{i=1}^m L_{(i)}^2\right)^{1/2} L := ( ∑ i = 1 m L ( i ) 2 ) 1/2 .
A point x ∗ x^* x ∗ satisfying (1) is called an exact strong (Stampacchia) solution. In contrast, an exact weak (Minty) solution is a point x ∗ ∈ X ~ x^*\in\widetilde{X} x ∗ ∈ X satisfying ⟨ F ( x ) , x ∗ − x ⟩ ≤ 0 \langle F(x),x^*-x\rangle\le0 ⟨ F ( x ) , x ∗ − x ⟩ ≤ 0 for all x ∈ X ~ x\in\widetilde{X} x ∈ X . The exact strong and weak solution sets coincide when F F F is continuous and monotone. Our goal is to compute an ε \varepsilon ε -approximate weak solution, namely, a point x ˉ ∈ X \bar{x}\in X x ˉ ∈ X such that
sup x ∈ X ~ ⟨ F ( x ) , x ˉ − x ⟩ ≤ ε , ∥ [ G ( x ˉ ) ] + ∥ ≤ ε , (2) \sup_{x\in\widetilde{X}}\langle F(x),\bar{x}-x\rangle\le\varepsilon,\quad\|[G(\bar{x})]_+\|\le\varepsilon, \tag*{(2)} x ∈ X sup ⟨ F ( x ) , x ˉ − x ⟩ ≤ ε , ∥ [ G ( x ˉ ) ] + ∥ ≤ ε , (2)
where [ ⋅ ] + [\cdot]_+ [ ⋅ ] + denotes the componentwise maximum with zero.
Let ri ( C ) \operatorname{ri}(C) ri ( C ) denote the relative interior of a set C C C . We further impose the following assumption such that the CVI problem admits an optimal primal–dual solution pair, which is standard in literature [19 ] :
ASSUMPTION 1. There exist x ∗ ∈ X x^*\in X x ∗ ∈ X and λ ∗ ∈ R + m \lambda^*\in\mathbb{R}_+^m λ ∗ ∈ R + m such that
⟨ F ( x ∗ ) + J ( x ∗ ) ⊤ λ ∗ , x − x ∗ ⟩ ≥ 0 , ∀ x ∈ X , G ( x ∗ ) ≤ 0 , ⟨ λ ∗ , G ( x ∗ ) ⟩ = 0. (3) \langle F(x^*)+J(x^*)^\top\lambda^*,x-x^*\rangle\ge0,\ \forall x\in X,\quad G(x^*)\le0,\quad\langle\lambda^*,G(x^*)\rangle=0. \tag*{(3)} ⟨ F ( x ∗ ) + J ( x ∗ ) ⊤ λ ∗ , x − x ∗ ⟩ ≥ 0 , ∀ x ∈ X , G ( x ∗ ) ≤ 0 , ⟨ λ ∗ , G ( x ∗ )⟩ = 0. (3) In addition, Slater’s condition holds: there exists x s l ∈ ri ( X ) x^{\mathrm{sl}}\in\operatorname{ri}(X) x sl ∈ ri ( X ) such that g i ( x s l ) < 0 , ∀ i = 1 , … , m g_i(x^{\mathrm{sl}})<0,\ \forall i=1,\ldots,m g i ( x sl ) < 0 , ∀ i = 1 , … , m .
Related Literature and Research Objective
First-order methods for VIs defined over a simple set X X X are well studied. For Lipschitz continuous monotone operators F F F , mirror-prox [12 ] and dual extrapolation [13 ] compute an ε \varepsilon ε -approximate weak solution using O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator evaluations. This dependence on ε \varepsilon ε is optimal in the worst case, matching the Ω ( 1 / ε ) \Omega(1/\varepsilon) Ω ( 1/ ε ) lower bound established by Ouyang and Xu [14 ] for a saddle-point subclass of monotone VIs.
For VIs with functional constraints, however, several research gaps remain in the existing literature. One main challenge is to design first-order methods that avoid repeated projections onto the functionally constrained set X ~ \widetilde{X} X . So far, there are two closely related studies partially closing this gap. Boob et al. [1 ] develop adaptive operator extrapolation methods that, in the smooth setting, achieve ε \varepsilon ε -accuracy in both the weak VI gap and constraint violation using O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) evaluations of both the operator and the constraint gradients. Alternatively, Zhang et al. [17 ] develop a primal gradient-descent method using local quadratic programs. Without requiring Lipschitz continuity of the operator or information about optimal multipliers, their method achieves these accuracy guarantees in O ( 1 / ε 2 ) O(1/\varepsilon^2) O ( 1/ ε 2 ) iterations. This leaves a fundamental question: can we design first-order methods that require fewer oracle evaluations and provide sharper constraint-violation bounds without relying on local quadratic programs?
Our work is motivated by results from smooth convex optimization, which suggest that faster constraint-gradient bounds may be attainable. For an O ( 1 ) O(1) O ( 1 ) number of constraints, Xu [16 ] obtain O ~ ( 1 / ε ) \widetilde{O}(1/\sqrt{\varepsilon}) O ( 1/ ε ) first-order evaluation complexity for finding ε \varepsilon ε -approximate Karush–Kuhn–Tucker (KKT) points, where O ~ \widetilde{O} O suppresses logarithmic factors. For the multiple-constraint case, Zhang and Lan [19 ] achieve O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) evaluation complexity for objective accuracy and feasibility. These optimization results suggest that O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) constraint-gradient complexity may also be attainable for monotone CVIs. However, the worst-case Ω ( 1 / ε ) \Omega(1/\varepsilon) Ω ( 1/ ε ) operator lower bound discussed above applies even without functional constraints. Achieving the desired O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) constraint-gradient bound therefore requires separating the two oracle costs. Gradient sliding [7 ] provides a way to achieve such separation by reusing gradient information across multiple updates involving another component. For structured VIs whose operator is the sum of a smooth convex gradient and a Lipschitz continuous monotone component, Lan and Ouyang [9 ] obtain O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) gradient evaluations and O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) evaluations of the monotone component. However, in CVIs, the smooth functions define the feasible set rather than an additive component of the operator. Extending this separation to CVIs therefore requires controlling constraint violation together with the weak VI gap.
Another feature we seek is parameter-free, meaning that the algorithm can adapt to unknown Lipschitz constant of the operator and smoothness constants of the constraint functions while retaining the same complexity bounds. The adaptive golden ratio algorithm Malitsky [11 ] and past-extragradient methods Ene and Nguyen [4 ] compute ε \varepsilon ε -approximate weak solutions to Lipschitz continuous monotone VIs on bounded domains using O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator evaluations, without prior knowledge of the Lipschitz constant. However, these methods require proximal updates over the feasible domain, so applying them directly to CVIs retains the difficulty of projecting onto X ~ \tilde{X} X ~ . Adaptive extensions are also available for convex composite optimization Wu et al. [15 ] and convex optimization with functional constraints Zhang and Lan [19 ] .
In summary, our objective is to design first-order algorithms that compute an ε \varepsilon ε -approximate weak solution to monotone CVIs with convex smooth functional constraints using O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator evaluations and O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) constraint-gradient evaluations, without projections onto X ~ \tilde{X} X ~ or prior knowledge of Lipschitz constant M M M , smoothness constant L L L , or a uniform bound on ∥ J ( x ) ∥ \lVert J(x)\rVert ∥ J ( x )∥ over X X X .
Organization and Main Results
The remainder of this paper is organized as follows. § 2 introduces the parameter-free accelerated operator sliding method (PFAOS) for the single-constraint case. PFAOS achieves O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator and O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) constraint-gradient evaluation complexities without prior knowledge of the Lipschitz constant of F F F or the smoothness constant of G G G or projections onto X ~ \tilde{X} X ~ . These bounds retain the optimal operator-complexity order for unconstrained VIs while improving the existing constraint-gradient complexity of CVIs from O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) to O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) . § 3 extends PFAOS to the multi-constrained parameter-free accelerated operator sliding method (MC-PFAOS) for solving the multi-constraint case. MC-PFAOS attains O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator and O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) Jacobian evaluation complexities without projections onto X ~ \tilde{X} X ~ or prior knowledge of the Lipschitz or smoothness constants or a uniform bound on ∥ J ( x ) ∥ \lVert J(x)\rVert ∥ J ( x )∥ over X X X . To the best of our knowledge, these results substantially improve the complexity bounds established for CVI algorithms, including those assuming known smoothness parameters [1 , 17 ] .
Next, we provide two complementary results that relax the requirements needed to implement PFAOS and MC-PFAOS. § 4 modifies the first-iteration search for both methods to allow an arbitrarily small initial estimate while preserving the same optimal complexities. § 5 develops an automatic stopping rule for both methods that requires no knowledge of the diameter of the set X X X while preserving these complexities. Section 6 reports numerical experiments on large-scale games with coupling constraints, and Section 7 concludes the paper.
Parameter-free Accelerated Operator Sliding (PFAOS)
Algorithm 1 presents the PFAOS method for solving the monotone CVI in (2) with a single constraint (m = 1 m=1 m = 1 ). For notational simplicity, we write g : = g 1 g := g_1 g := g 1 , throughout this section.
Overview of PFAOS
Algorithm 1 Parameter-Free Accelerated Operator Sliding (PFAOS)
Initialization: x ˉ 0 = x 0 ∈ X \bar{x}_0=x_0\in X x ˉ 0 = x 0 ∈ X , L 0 ∈ ( 0 , L ] L_0\in(0,L] L 0 ∈ ( 0 , L ] , Λ > 0 \Lambda>0 Λ > 0 , M 0 = η 0 S 0 = 2 Λ L 0 M_0=\eta_0^{S_0}=2\Lambda L_0 M 0 = η 0 S 0 = 2Λ L 0
for k = 1 , … , N k=1,\ldots,N k = 1 , … , N do
Set s = 1 s=1 s = 1 , M k 0 = M k − 1 M_k^0=M_{k-1} M k 0 = M k − 1
Set η k s = 2 s − 2 η k S k − 1 \eta_k^s=2^{s-2}\eta_k^{S_{k-1}} η k s = 2 s − 2 η k S k − 1 and compute x k s = ( 1 − γ k s ) x ˉ k − 1 + γ k s x k − 1 x_k^s=(1-\gamma_k^s)\bar{x}_{k-1}+\gamma_k^s x_{k-1} x k s = ( 1 − γ k s ) x ˉ k − 1 + γ k s x k − 1 , where γ 1 s = 1 \gamma_1^s=1 γ 1 s = 1 , and γ k s > 0 \gamma_k^s>0 γ k s > 0 satisfying η k s γ k s = η k − 1 S k − 1 γ k − 1 S k − 1 ( 1 − γ k s ) \eta_k^s\gamma_k^s=\eta_{k-1}^{S_{k-1}}\gamma_{k-1}^{S_{k-1}}(1-\gamma_k^s) η k s γ k s = η k − 1 S k − 1 γ k − 1 S k − 1 ( 1 − γ k s ) , ∀ k ≥ 2 \forall k\ge2 ∀ k ≥ 2 (4)
Set t = 1 t=1 t = 1 , M k 0 , s = max { η k s , M k s − 1 } M_k^{0,s}=\max\{\eta_k^s,M_k^{s-1}\} M k 0 , s = max { η k s , M k s − 1 } , T k 0 , s = M k 0 , s / η k s T_k^{0,s}=M_k^{0,s}/\eta_k^s T k 0 , s = M k 0 , s / η k s , x k 0 , s = x k − 1 x_k^{0,s}=x_{k-1} x k 0 , s = x k − 1 and x ˉ k − 1 , s = x k − 1 \bar{x}_k^{-1,s}=x_{k-1} x ˉ k − 1 , s = x k − 1 . Here, x ˉ 0 S 0 − 1 , S 0 = x 0 \bar{x}_0^{S_0-1,S_0}=x_0 x ˉ 0 S 0 − 1 , S 0 = x 0 .
Compute x k t , s x_k^{t,s} x k t , s by solving
min x ∈ X ⟨ F ( x k t − 1 , s ) + θ k t , s [ F ( x k t − 1 , s ) − F ( x k t − 2 , s ) ] , x ⟩ + η k s 2 ∥ x − x k ∥ 2 + p k t , s 2 ∥ x − x k t − 1 , s ∥ 2 \min_{x\in X}\ \langle F(x_k^{t-1,s})+\theta_k^{t,s}[F(x_k^{t-1,s})-F(x_k^{t-2,s})],x\rangle+\frac{\eta_k^s}{2}\|x-x_k\|^2+\frac{p_k^{t,s}}{2}\|x-x_k^{t-1,s}\|^2 x ∈ X min ⟨ F ( x k t − 1 , s ) + θ k t , s [ F ( x k t − 1 , s ) − F ( x k t − 2 , s )] , x ⟩ + 2 η k s ∥ x − x k ∥ 2 + 2 p k t , s ∥ x − x k t − 1 , s ∥ 2 subject to
g ( x k s ) + ⟨ ∇ g ( x k s ) , x − x k s ⟩ ≤ 0 g(x_{k}^{s})+\langle\nabla g(x_{k}^{s}),x-x_{k}^{s}\rangle\le0 g ( x k s ) + ⟨ ∇ g ( x k s ) , x − x k s ⟩ ≤ 0 Here θ k 1 , s = 1 \theta_k^{1,s}=1 θ k 1 , s = 1 , θ k s = M k 1 , s / M k − 1 \theta_k^{s}=M_k^{1,s}/M_{k-1} θ k s = M k 1 , s / M k − 1 , ∀ k ≥ 2 \forall k\ge2 ∀ k ≥ 2 , θ k t , s = M k t , s / M k t − 1 , s \theta_k^{t,s}=M_k^{t,s}/M_k^{t-1,s} θ k t , s = M k t , s / M k t − 1 , s , ∀ t ≥ 2 \forall t\ge2 ∀ t ≥ 2 , and p k t , s = 2 M k t , s + η k s M k t , s ∑ i = 1 t − 1 ( 1 / M k i , s ) p_k^{t,s}=2M_k^{t,s}+\eta_k^sM_k^{t,s}\sum_{i=1}^{t-1}(1/M_k^{i,s}) p k t , s = 2 M k t , s + η k s M k t , s ∑ i = 1 t − 1 ( 1/ M k i , s ) , where M k t , s = 2 q k t , s M k t − 1 , s M_k^{t,s}=2^{q_k^{t,s}}M_k^{t-1,s} M k t , s = 2 q k t , s M k t − 1 , s and q k t , s ≥ 0 q_k^{t,s}\ge0 q k t , s ≥ 0 is the smallest integer such that ∥ F ( x k t , s ) − F ( x k t − 1 , s ) ∥ ≤ M k t , s ∥ x k t , s − x k t − 1 , s ∥ \|F(x_k^{t,s})-F(x_k^{t-1,s})\|\le M_k^{t,s}\|x_k^{t,s}-x_k^{t-1,s}\| ∥ F ( x k t , s ) − F ( x k t − 1 , s ) ∥ ≤ M k t , s ∥ x k t , s − x k t − 1 , s ∥ .
Set T k t , s ← t − 1 + 2 q k t , s ( T k t − 1 , s − t + 1 ) T_k^{t,s}\leftarrow t-1+2^{q_k^{t,s}}(T_k^{t-1,s}-t+1) T k t , s ← t − 1 + 2 q k t , s ( T k t − 1 , s − t + 1 )
if t < T k t , s t<T_k^{t,s} t < T k t , s , then set t ← t + 1 t\leftarrow t+1 t ← t + 1 and go to line 6; otherwise let T k s = T k t , s T_k^s=T_k^{t,s} T k s = T k t , s , M k s = M k t , s M_k^s=M_k^{t,s} M k s = M k t , s ,
x k s = x k T k s , x ^ k s = ( ∑ i = 1 T k s 1 M k i , s ) − 1 ∑ i = 1 T k s x k i , s M k i , s , x ˉ k s = ( 1 − γ k s ) x ˉ k − 1 + γ k s x ^ k s x_k^s=x_k^{T_k^s},\qquad\hat{x}_k^s=\left(\sum_{i=1}^{T_k^s}\frac{1}{M_k^{i,s}}\right)^{-1}\sum_{i=1}^{T_k^s}\frac{x_k^{i,s}}{M_k^{i,s}},\qquad\bar{x}_k^s=(1-\gamma_k^s)\bar{x}_{k-1}+\gamma_k^s\hat{x}_k^s x k s = x k T k s , x ^ k s = i = 1 ∑ T k s M k i , s 1 − 1 i = 1 ∑ T k s M k i , s x k i , s , x ˉ k s = ( 1 − γ k s ) x ˉ k − 1 + γ k s x ^ k s if g ( x ˉ k s ) ≤ g ( x k s ) + ⟨ ∇ g ( x k s ) , x ˉ k s − x k s ⟩ + η k s 2 λ γ k s ∥ x ˉ k s − x k s ∥ 2 g(\bar{x}_k^s)\le g(x_k^s)+\langle\nabla g(x_k^s),\bar{x}_k^s-x_k^s\rangle+\frac{\eta_k^s}{2\lambda\gamma_k^s}\|\bar{x}_k^s-x_k^s\|^2 g ( x ˉ k s ) ≤ g ( x k s ) + ⟨ ∇ g ( x k s ) , x ˉ k s − x k s ⟩ + 2 λ γ k s η k s ∥ x ˉ k s − x k s ∥ 2 does not hold, then update s ← s + 1 s\leftarrow s+1 s ← s + 1 and go to line 4; else set S k = s S_k=s S k = s , M k = M k S k M_k=M_k^{S_k} M k = M k S k , x k = x k S k x_k=x_k^{S_k} x k = x k S k , x ^ k = x ^ k S k \hat{x}_k=\hat{x}_k^{S_k} x ^ k = x ^ k S k and x ˉ k = x ˉ k S k \bar{x}_k=\bar{x}_k^{S_k} x ˉ k = x ˉ k S k .
end for
return x ˉ N \bar{x}_N x ˉ N
PFAOS has three iteration levels. The outer loop, indexed by k k k , generates the accelerated sequence { x ˉ k } \{\bar{x}_k\} { x ˉ k } . At each outer iteration, the middle loop, indexed by s s s , performs a line search for the constraint-curvature parameter η k s \eta_k^s η k s . Each middle trial ( k , s ) (k,s) ( k , s ) runs an inner operator-sliding loop, indexed by t t t , and updates the local Lipschitz estimate M k t , s M_k^{t,s} M k t , s of F F F . We use the superscript s s s to index middle-loop trials and ( t , s ) (t,s) ( t , s ) to index inner-loop iterations within each trial, with S k S_k S k denoting the accepted middle-trial index and T k s T_k^s T k s the final inner-loop index of trial ( k , s ) (k,s) ( k , s ) .
Constraint Linearization and Operator Sliding
Operator sliding is implemented within each middle-trial ( k , s ) (k,s) ( k , s ) . Given η k s \eta_k^s η k s , the algorithm determines γ k s \gamma_k^s γ k s using (4) and forms x k s x_k^s x k s in line 4. In subproblem (5), we approximate the functional constraint g g g by its affine linearization with ∇ g ( x k s ) \nabla g(x_k^s) ∇ g ( x k s ) . This constraint remains fixed throughout the corresponding inner loop.
At each inner iteration t t t , the algorithm solves subproblem (5), whose objective combines an extrapolated evaluation of F F F with two quadratic regularization terms. Each inner line-search trial requires one new evaluation of F F F , while the fixed affine constraint is reused without reevaluating ∇ g \nabla g ∇ g . After T k s T_k^s T k s inner iterations, line 8 retains the last iterate x k s = x k T k s , s x_k^s=x_k^{T_k^s,s} x k s = x k T k s , s , computes the weighted average x ^ k s \hat{x}_k^s x ^ k s with weights proportional to 1 / M k t , s 1/M_k^{t,s} 1/ M k t , s , and forms the candidate outer iterate x ˉ k s \bar{x}_k^s x ˉ k s .
Parameter Adaptation
PFAOS employs two line searches to adapt the local constraint-curvature parameter η k s \eta_k^s η k s and the local Lipschitz estimate M k t , s M_k^{t,s} M k t , s of F F F , respectively. For initialization, L 0 ∈ ( 0 , L ] L_0\in(0,L] L 0 ∈ ( 0 , L ] can be obtained from any distinct u , v ∈ X u,v\in X u , v ∈ X with positive linearization error by setting L 0 = 2 [ g ( v ) − g ( u ) − ⟨ ∇ g ( u ) , v − u ⟩ ] / ∥ v − u ∥ 2 L_0=2[g(v)-g(u)-\langle\nabla g(u),v-u\rangle]/\lVert v-u\rVert^2 L 0 = 2 [ g ( v ) − g ( u ) − ⟨ ∇ g ( u ) , v − u ⟩] / ∥ v − u ∥ 2 . The smoothness of g g g guarantees L 0 ≤ L L_0\le L L 0 ≤ L , so this construction does not require knowing L L L a priori.
At the start of middle trial ( k , s ) (k,s) ( k , s ) , the algorithm sets η k s = 2 s − 2 η k − 1 S k − 1 \eta_k^s=2^{s-2}\eta_{k-1}^{S_{k-1}} η k s = 2 s − 2 η k − 1 S k − 1 . We treat the first and subsequent trials separately: the first trial uses half of the previously accepted estimate, and each subsequent trial doubles the current estimate. Within each middle trial, the initial estimate M k 0 , s M_k^{0,s} M k 0 , s of the Lipschitz constant of F F F is updated in line 5, where M k 0 = M k − 1 M_k^0=M_{k-1} M k 0 = M k − 1 . At inner iteration t t t , the algorithm first tests the preceding estimate M k t − 1 , s M_k^{t-1,s} M k t − 1 , s . For each trial value of M k t , s M_k^{t,s} M k t , s , it computes the parameters in line 6, solves subproblem (5), and tests the condition ∥ F ( x k t , s ) − F ( x k t − 1 , s ) ∥ ≤ M k t , s ∥ x k t , s − x k t − 1 , s ∥ \lVert F(x_k^{t,s})-F(x_k^{t-1,s})\rVert\le M_k^{t,s}\lVert x_k^{t,s}-x_k^{t-1,s}\rVert ∥ F ( x k t , s ) − F ( x k t − 1 , s )∥ ≤ M k t , s ∥ x k t , s − x k t − 1 , s ∥ . If this condition fails, the estimate is doubled, the parameters are updated, and the subproblem is solved again. Thus, q k t , s q_k^{t,s} q k t , s records the smallest number of doublings required to satisfy this condition, with M k t , s = 2 q k t , s M k t − 1 , s M_k^{t,s}=2^{q_k^{t,s}}M_k^{t-1,s} M k t , s = 2 q k t , s M k t − 1 , s .
The algorithm initializes the inner-loop horizon as T k 0 , s = M k 0 , s / η k s T_k^{0,s}=M_k^{0,s}/\eta_k^s T k 0 , s = M k 0 , s / η k s . After accepting M k t , s M_k^{t,s} M k t , s , the algorithm updates T k t , s T_k^{t,s} T k t , s in line 7. This update leaves the first t − 1 t-1 t − 1 iterations unchanged and scales the remaining horizon by M k t , s / M k t − 1 , s M_k^{t,s}/M_k^{t-1,s} M k t , s / M k t − 1 , s . In particular, the update preserves
∑ i = 1 t 1 M k i , s + T k t , s − t M k t , s = 1 η k s . \sum_{i=1}^{t}\frac{1}{M_k^{i,s}}+\frac{T_k^{t,s}-t}{M_k^{t,s}}=\frac{1}{\eta_k^s}. i = 1 ∑ t M k i , s 1 + M k t , s T k t , s − t = η k s 1 .
Consequently, a larger operator estimate requires additional inner updates to compensate for the smaller weights 1 / M k t , s 1/M_k^{t,s} 1/ M k t , s . The inner loop terminates when t = T k t , s t=T_k^{t,s} t = T k t , s , and its final horizon is recorded as T k s T_k^s T k s . At termination, the accumulated weights satisfy ∑ t = 1 T k s 1 / M k t , s = 1 / η k s \sum_{t=1}^{T_k^s}1/M_k^{t,s}=1/\eta_k^s ∑ t = 1 T k s 1/ M k t , s = 1/ η k s .
After completing the inner loop, PFAOS checks whether the candidate x ˉ k s \bar{x}_k^s x ˉ k s satisfies the quadratic upper-bound condition g ( x ˉ k s ) ≤ g ( x k s ) + ⟨ ∇ g ( x k s ) , x ˉ k s − x k s ⟩ + η k s 2 γ k s ∥ x ˉ k s − x k s ∥ 2 g(\bar{x}_k^s)\le g(x_k^s)+\langle\nabla g(x_k^s),\bar{x}_k^s-x_k^s\rangle+\frac{\eta_k^s}{2\gamma_k^s}\lVert\bar{x}_k^s-x_k^s\rVert^2 g ( x ˉ k s ) ≤ g ( x k s ) + ⟨ ∇ g ( x k s ) , x ˉ k s − x k s ⟩ + 2 γ k s η k s ∥ x ˉ k s − x k s ∥ 2 . If this condition fails, the algorithm goes back to line 4, increases η k s \eta_k^s η k s , updates the constraint linearization, and restarts the inner loop from the preceding accepted outer iterate. Otherwise, the trial is accepted, and its candidate iterates and parameter estimates are retained for outer iteration k k k .
Finally, PFAOS verifies that the adaptive inner loop terminates in finitely many iterations. The curvature and operator estimates remain dyadic multiples of their common initial value M 0 = η 0 S 0 M_0 = \eta_0^{S_0} M 0 = η 0 S 0 . Since M k 0 , s ≥ η k s M_k^{0,s} \geq\eta_k^s M k 0 , s ≥ η k s , the initial horizon T k 0 , s = M k 0 , s / η k s T_k^{0,s} = M_k^{0,s}/\eta_k^s T k 0 , s = M k 0 , s / η k s is a positive integer. The horizon update preserves integrality and ensures T k t , s ≥ t T_k^{t,s} \geq t T k t , s ≥ t throughout the inner loop. Moreover, the local Lipschitz condition holds whenever M k t , s ≥ M M_k^{t,s} \geq M M k t , s ≥ M , and the minimality of q k t , s q_k^{t,s} q k t , s implies M k t , s < 2 M M_k^{t,s} < 2M M k t , s < 2 M . Thus, the operator estimate and inner-loop horizon can increase only finitely many times.
The adaptive inner-loop horizon allows multiple operator updates per constraint linearization. Combined with acceleration, this separation is a key to achieving O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) constraint-gradient evaluations and O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator evaluations, as established in the following analysis.
Convergence Analysis of PFAOS
In this subsection, we establish the convergence properties of Algorithm 1. The following quantities are introduced for the analyses. For each middle trial ( k , s ) (k,s) ( k , s ) , define the total averaging weight, the affine constraint model, and the operator differences by
B k s : = ∑ t = 1 T k s 1 M k t , s , ℓ k s ( z ) : = g ( x k s ) + ⟨ ∇ g ( x k s ) , z − x k s ⟩ , Δ k t , s : = F ( x k t , s ) − F ( x k t − 1 , s ) , 0 ≤ t ≤ T k s . \mathcal{B}_k^s := \sum_{t=1}^{T_k^s} \frac{1}{M_k^{t,s}},\qquad\ell_k^s(z) := g(x_k^s) + \langle\nabla g(x_k^s), z - x_k^s\rangle,\qquad\Delta_k^{t,s} := F(x_k^{t,s}) - F(x_k^{t-1,s}),\quad0 \leq t \leq T_k^s. B k s := t = 1 ∑ T k s M k t , s 1 , ℓ k s ( z ) := g ( x k s ) + ⟨ ∇ g ( x k s ) , z − x k s ⟩ , Δ k t , s := F ( x k t , s ) − F ( x k t − 1 , s ) , 0 ≤ t ≤ T k s .
In particular, Δ k 0 , s = F ( x k − 1 ) − F ( x k − 1 , s ) \Delta_k^{0,s} = F(x_{k-1}) - F(x_k^{-1,s}) Δ k 0 , s = F ( x k − 1 ) − F ( x k − 1 , s ) .
Let λ k t , s ≥ 0 \lambda_k^{t,s} \geq0 λ k t , s ≥ 0 be a KKT multiplier associated with x k t , s x_k^{t,s} x k t , s in (5). Using the same averaging weights as for the primal iterates, define
λ ^ k s : = 1 B k s ∑ t = 1 T k s λ k t , s M k t , s , λ ^ k : = λ ^ k S k , λ ‾ 0 = 0 , λ ‾ k : = ( 1 − γ S k ) λ ‾ k − 1 + γ S k λ ^ k . \widehat{\lambda}_k^s := \frac{1}{\mathcal{B}_k^s}\sum_{t=1}^{T_k^s}\frac{\lambda_k^{t,s}}{M_k^{t,s}},\qquad\widehat{\lambda}_k := \widehat{\lambda}_k^{S_k},\qquad\overline{\lambda}_0 = 0,\qquad\overline{\lambda}_k := (1-\gamma^{S_k})\overline{\lambda}_{k-1}+\gamma^{S_k}\widehat{\lambda}_k. λ k s := B k s 1 t = 1 ∑ T k s M k t , s λ k t , s , λ k := λ k S k , λ 0 = 0 , λ k := ( 1 − γ S k ) λ k − 1 + γ S k λ k .
Denoting Γ k s : = η k s γ k s \Gamma_k^s := \eta_k^s\gamma_k^s Γ k s := η k s γ k s , by (4), we have Γ k s = Γ k − 1 S k − 1 ( 1 − γ k s ) \Gamma_k^s = \Gamma_{k-1}^{S_{k-1}}(1-\gamma_k^s) Γ k s = Γ k − 1 S k − 1 ( 1 − γ k s ) , for k ≥ 2 k \geq2 k ≥ 2 , s ≥ 1 s \geq1 s ≥ 1 . Given an initial point x 0 ∈ X x_0 \in X x 0 ∈ X , let D X : = max x ∈ X ∥ x − x 0 ∥ D_X := \max_{x\in X}\|x-x_0\| D X := max x ∈ X ∥ x − x 0 ∥ . Finally, for any x ∈ X x \in X x ∈ X and λ ≥ 0 \lambda\geq0 λ ≥ 0 , define the primal-dual gap function
G k ( x , λ ) : = ⟨ F ( x ) , x ‾ k − x ⟩ + λ g ( x ‾ k ) − λ ‾ k g ( x ) . G_k(x,\lambda) := \langle F(x),\overline{x}_k-x\rangle+\lambda g(\overline{x}_k)-\overline{\lambda}_k g(x). G k ( x , λ ) := ⟨ F ( x ) , x k − x ⟩ + λ g ( x k ) − λ k g ( x ) .
Lemma 1 provides a constrained three-point inequality used repeatedly in the subsequent analysis. Its proof is a straightforward adaptation of the argument in [8 Lemma 3.5] , using the Lagrangian and the KKT conditions.
LEMMA 1. Let Z ⊆ R n Z \subseteq\mathbb{R}^n Z ⊆ R n be a nonempty closed convex set, let q : Z → R q:Z\to\mathbb{R} q : Z → R be convex, and let c = ( c 1 , … , c m ) : Z → R m c=(c_1,\ldots,c_m):Z\to\mathbb{R}^m c = ( c 1 , … , c m ) : Z → R m have convex components. Given z , z ′ ∈ Z z,z'\in Z z , z ′ ∈ Z and μ 1 , μ 2 ≥ 0 \mu_1,\mu_2\geq0 μ 1 , μ 2 ≥ 0 , suppose that v ∈ a r g m i n u ∈ Z { q ( u ) + μ 1 2 ∥ u − z ∥ 2 + μ 2 2 ∥ u − z ′ ∥ 2 : c ( u ) ≤ 0 } v\in\mathop{\rm arg\,min}_{u\in Z}\{q(u)+\frac{\mu_1}{2}\|u-z\|^2+\frac{\mu_2}{2}\|u-z'\|^2:c(u)\leq0\} v ∈ arg min u ∈ Z { q ( u ) + 2 μ 1 ∥ u − z ∥ 2 + 2 μ 2 ∥ u − z ′ ∥ 2 : c ( u ) ≤ 0 } , and let λ + ∈ R + m \lambda^+\in\mathbb{R}_+^m λ + ∈ R + m be a KKT multiplier associated with v v v . Then, for every u ∈ Z u\in Z u ∈ Z and λ ∈ R + m \lambda\in\mathbb{R}_+^m λ ∈ R + m ,
q ( v ) − q ( u ) + ⟨ λ , c ( v ) ⟩ − ⟨ λ + , c ( u ) ⟩ + μ 1 + μ 2 2 ∥ v − u ∥ 2 ≤ μ 1 2 ( ∥ u − z ∥ 2 − ∥ v − z ∥ 2 ) + μ 2 2 ( ∥ u − z ′ ∥ 2 − ∥ v − z ′ ∥ 2 ) q(v)-q(u)+\langle\lambda,c(v)\rangle-\langle\lambda^+,c(u)\rangle+\frac{\mu_1+\mu_2}{2}\|v-u\|^2\leq\frac{\mu_1}{2}\left(\|u-z\|^2-\|v-z\|^2\right)+\frac{\mu_2}{2}\left(\|u-z'\|^2-\|v-z'\|^2\right) q ( v ) − q ( u ) + ⟨ λ , c ( v )⟩ − ⟨ λ + , c ( u )⟩ + 2 μ 1 + μ 2 ∥ v − u ∥ 2 ≤ 2 μ 1 ( ∥ u − z ∥ 2 − ∥ v − z ∥ 2 ) + 2 μ 2 ( ∥ u − z ′ ∥ 2 − ∥ v − z ′ ∥ 2 )
A key feature of PFAOS is that the inner-loop horizon is not prescribed in advance. Whenever the operator line search increases M k t , s M_k^{t,s} M k t , s , the remaining horizon is adjusted accordingly at line 7. Lemma 2 shows that this adaptive rule preserves an exact balancing invariant, which is a key property leading the subsequent convergence analyses.
Lemma 2. For every middle trial ( k , s ) (k,s) ( k , s ) executed by Algorithm 1, η k s B k s = 1 \eta_k^s B_k^s=1 η k s B k s = 1 .
Proof. The horizon update and M k t , s = 2 q k t , s M k t − 1 , s M_k^{t,s}=2^{q_k^{t,s}}M_k^{t-1,s} M k t , s = 2 q k t , s M k t − 1 , s give
1 M k t , s + T k t , s − t M k t , s = T k t − 1 , s − t + 1 M k t − 1 , s . \frac{1}{M_k^{t,s}}+\frac{T_k^{t,s}-t}{M_k^{t,s}}=\frac{T_k^{t-1,s}-t+1}{M_k^{t-1,s}}. M k t , s 1 + M k t , s T k t , s − t = M k t − 1 , s T k t − 1 , s − t + 1 . Starting from T k 0 , s / M k 0 , s = 1 / η k s T_k^{0,s}/M_k^{0,s}=1/\eta_k^s T k 0 , s / M k 0 , s = 1/ η k s and summing over the executed inner iterations yields
∑ i = 1 t 1 M k i , s + T k t , s − t M k t , s = 1 η k s . \sum_{i=1}^{t}\frac{1}{M_k^{i,s}}+\frac{T_k^{t,s}-t}{M_k^{t,s}}=\frac{1}{\eta_k^s}. i = 1 ∑ t M k i , s 1 + M k t , s T k t , s − t = η k s 1 . At termination, t = T k T , s = T k s t=T_k^{T,s}=T_k^s t = T k T , s = T k s , so the remaining-horizon term vanishes. □
Using the invariant in Lemma 2, Proposition 1 establishes an inner-loop bound for each middle trial ( k , s ) (k,s) ( k , s ) , which will be used in the subsequent outer-loop analysis.
Proposition 1. Fix any k ≥ 1 k\ge1 k ≥ 1 and 1 ≤ s ≤ S k 1\le s\le S_k 1 ≤ s ≤ S k . For any point x ∈ X x\in X x ∈ X and scalar λ ≥ 0 \lambda\ge0 λ ≥ 0 , the iterates generated by Algorithm 1 guarantee B k s ⟨ F ( x ) , x ^ k s − x ⟩ ≤ U k s + V k s + W k s \mathcal{B}_k^s\langle F(x),\hat{x}_k^s-x\rangle\le U_k^s+V_k^s+W_k^s B k s ⟨ F ( x ) , x ^ k s − x ⟩ ≤ U k s + V k s + W k s , where
U k s : = 1 M k s ⟨ Δ k T k s , s , x k s − x ⟩ − θ k 1 , s M k s ⟨ Δ k 0 , s , x k − 1 − x ⟩ + p k 1 , s 2 M k 1 , s ∥ x − x k − 1 ∥ 2 − η k s + p k T k s , s 2 M k T k s , s ∥ x − x k s ∥ 2 , U_k^s:=\frac{1}{M_k^s}\langle\Delta_k^{T_k^s,s},x_k^s-x\rangle-\frac{\theta_k^{1,s}}{M_k^s}\langle\Delta_k^{0,s},x_{k-1}-x\rangle+\frac{p_k^{1,s}}{2M_k^{1,s}}\lVert x-x_{k-1}\rVert^2-\frac{\eta_k^s+p_k^{T_k^s,s}}{2M_k^{T_k^s,s}}\lVert x-x_k^s\rVert^2, U k s := M k s 1 ⟨ Δ k T k s , s , x k s − x ⟩ − M k s θ k 1 , s ⟨ Δ k 0 , s , x k − 1 − x ⟩ + 2 M k 1 , s p k 1 , s ∥ x − x k − 1 ∥ 2 − 2 M k T k s , s η k s + p k T k s , s ∥ x − x k s ∥ 2 , V k s : = θ k 1 , s M k 1 , s ∥ Δ k 0 , s ∥ ∥ x k 1 , s − x k − 1 ∥ − p k 1 , s 4 M k 1 , s ∥ x k 1 , s − x k − 1 ∥ 2 − p k T k s , s 4 M k T k , s ∥ x k s − x k T k s − 1 , s ∥ 2 , V_k^s:=\frac{\theta_k^{1,s}}{M_k^{1,s}}\lVert\Delta_k^{0,s}\rVert\lVert x_k^{1,s}-x_{k-1}\rVert-\frac{p_k^{1,s}}{4M_k^{1,s}}\lVert x_k^{1,s}-x_{k-1}\rVert^2-\frac{p_k^{T_k^s,s}}{4M_k^{T_k,s}}\lVert x_k^{s}-x_k^{T_k^{s-1},s}\rVert^2, V k s := M k 1 , s θ k 1 , s ∥ Δ k 0 , s ∥ ∥ x k 1 , s − x k − 1 ∥ − 4 M k 1 , s p k 1 , s ∥ x k 1 , s − x k − 1 ∥ 2 − 4 M k T k , s p k T k s , s ∥ x k s − x k T k s − 1 , s ∥ 2 , W k s : = B k s λ k s ℓ k s ( x ) − B k s λ k s ( x ^ k s ) + 1 2 ∥ x − x k − 1 ∥ 2 − 1 2 ∥ x ^ k s − x k − 1 ∥ 2 . W_k^s:=\mathcal{B}_k^s\lambda_k^s\ell_k^s(x)-\mathcal{B}_k^s\lambda_k^s(\hat{x}_k^s)+\frac{1}{2}\lVert x-x_{k-1}\rVert^2-\frac{1}{2}\lVert\hat{x}_k^s-x_{k-1}\rVert^2. W k s := B k s λ k s ℓ k s ( x ) − B k s λ k s ( x ^ k s ) + 2 1 ∥ x − x k − 1 ∥ 2 − 2 1 ∥ x ^ k s − x k − 1 ∥ 2 . Proof. Fix any t ≥ 1 t\ge1 t ≥ 1 . Applying Lemma 1 to the inner subproblem (5) yields that
⟨ F ( x k t − 1 , s ) + θ k t , s Δ k t − 1 , s + λ k t , s ∇ g ( x k s ) , x k t , s − x ⟩ + η k s + p k t , s 2 ∥ x − x k t , s ∥ 2 ≤ η k s 2 ( ∥ x − x k − 1 ∥ 2 − ∥ x k t , s − x k − 1 ∥ 2 ) + p k t , s 2 ( ∥ x − x k t − 1 , s ∥ 2 − ∥ x k t , s − x k t − 1 , s ∥ 2 ) . \left\langle F(x_k^{t-1,s})+\theta_k^{t,s}\Delta_k^{t-1,s}+\lambda_k^{t,s}\nabla g(x_k^s),x_k^{t,s}-x\right\rangle+\frac{\eta_k^s+p_k^{t,s}}{2}\lVert x-x_k^{t,s}\rVert^2
\le\frac{\eta_k^s}{2}\left(\lVert x-x_{k-1}\rVert^2-\lVert x_k^{t,s}-x_{k-1}\rVert^2\right)+\frac{p_k^{t,s}}{2}\left(\lVert x-x_k^{t-1,s}\rVert^2-\lVert x_k^{t,s}-x_k^{t-1,s}\rVert^2\right). ⟨ F ( x k t − 1 , s ) + θ k t , s Δ k t − 1 , s + λ k t , s ∇ g ( x k s ) , x k t , s − x ⟩ + 2 η k s + p k t , s ∥ x − x k t , s ∥ 2 ≤ 2 η k s ( ∥ x − x k − 1 ∥ 2 − ∥ x k t , s − x k − 1 ∥ 2 ) + 2 p k t , s ( ∥ x − x k t − 1 , s ∥ 2 − ∥ x k t , s − x k t − 1 , s ∥ 2 ) . The primal feasibility and complementary slackness of this inner subproblem also guarantee that − λ k s ℓ k s ( x k t , s ) ≥ 0 -\lambda_k^s\ell_k^s(x_k^{t,s})\ge0 − λ k s ℓ k s ( x k t , s ) ≥ 0 and λ k t , s ℓ k s ( x k t , s ) = 0 \lambda_k^{t,s}\ell_k^s(x_k^{t,s})=0 λ k t , s ℓ k s ( x k t , s ) = 0 . Combining the above relations with the inequality ⟨ F ( x ) − F ( x k t , s ) , x k t , s − x ⟩ ≤ 0 \langle F(x)-F(x_k^{t,s}),x_k^{t,s}-x\rangle\le0 ⟨ F ( x ) − F ( x k t , s ) , x k t , s − x ⟩ ≤ 0 coming from the monotonicity of F F F , applying the Cauchy–Schwarz inequality, and rearranging terms, we obtain ⟨ F ( x ) , x k t , s − x ⟩ ≤ U k t , s + V k t , s + W k t , s \langle F(x),x_k^{t,s}-x\rangle\le U_k^{t,s}+V_k^{t,s}+W_k^{t,s} ⟨ F ( x ) , x k t , s − x ⟩ ≤ U k t , s + V k t , s + W k t , s , where
U k t , s : = ⟨ Δ k t , s , x k t , s − x ⟩ − θ k t , s ⟨ Δ k t − 1 , s , x k t − 1 , s − x ⟩ + p k t , s 2 ∥ x − x k t − 1 , s ∥ 2 − η k s + p k t , s 2 ∥ x − x k t , s ∥ 2 , U_k^{t,s}:=\langle\Delta_k^{t,s},x_k^{t,s}-x\rangle-\theta_k^{t,s}\langle\Delta_k^{t-1,s},x_k^{t-1,s}-x\rangle+\frac{p_k^{t,s}}{2}\lVert x-x_k^{t-1,s}\rVert^2-\frac{\eta_k^s+p_k^{t,s}}{2}\lVert x-x_k^{t,s}\rVert^2, U k t , s := ⟨ Δ k t , s , x k t , s − x ⟩ − θ k t , s ⟨ Δ k t − 1 , s , x k t − 1 , s − x ⟩ + 2 p k t , s ∥ x − x k t − 1 , s ∥ 2 − 2 η k s + p k t , s ∥ x − x k t , s ∥ 2 , V k t , s : = θ k t , s ∥ Δ k t − 1 , s ∥ ∥ x k t , s − x k t − 1 , s ∥ − p k t , s 2 ∥ x k t , s − x k t − 1 , s ∥ 2 , V_k^{t,s}:=\theta_k^{t,s}\lVert\Delta_k^{t-1,s}\rVert\lVert x_k^{t,s}-x_k^{t-1,s}\rVert-\frac{p_k^{t,s}}{2}\lVert x_k^{t,s}-x_k^{t-1,s}\rVert^2, V k t , s := θ k t , s ∥ Δ k t − 1 , s ∥ ∥ x k t , s − x k t − 1 , s ∥ − 2 p k t , s ∥ x k t , s − x k t − 1 , s ∥ 2 , W k t , s : = − λ k s ℓ k s ( x k t , s ) + λ k s ℓ k s ( x ) + η k s 2 [ ∥ x − x k − 1 ∥ 2 − ∥ x k t , s − x k − 1 ∥ 2 ] . W_k^{t,s}:=-\lambda_k^s\ell_k^s(x_k^{t,s})+\lambda_k^s\ell_k^s(x)+\frac{\eta_k^s}{2}\left[\lVert x-x_{k-1}\rVert^2-\lVert x_k^{t,s}-x_{k-1}\rVert^2\right]. W k t , s := − λ k s ℓ k s ( x k t , s ) + λ k s ℓ k s ( x ) + 2 η k s [ ∥ x − x k − 1 ∥ 2 − ∥ x k t , s − x k − 1 ∥ 2 ] . Multiplying both sides of the above relation by 1 / M k t , s 1/M_k^{t,s} 1/ M k t , s and summing over t = 1 , … , T k s t=1,\ldots,T_k^s t = 1 , … , T k s , while considering the definition of x ^ k s \hat{x}_k^s x ^ k s yield
B k s ⟨ F ( x ) , x ^ k s − x ⟩ ≤ ∑ t = 1 T k s U k t , s M k t , s + ∑ t = 1 T k s V k t , s M k t , s + ∑ t = 1 T k s W k t , s M k t , s . \mathcal{B}_k^s\langle F(x),\hat{x}_k^s-x\rangle\le\sum_{t=1}^{T_k^s}\frac{U_k^{t,s}}{M_k^{t,s}}+\sum_{t=1}^{T_k^s}\frac{V_k^{t,s}}{M_k^{t,s}}+\sum_{t=1}^{T_k^s}\frac{W_k^{t,s}}{M_k^{t,s}}. B k s ⟨ F ( x ) , x ^ k s − x ⟩ ≤ t = 1 ∑ T k s M k t , s U k t , s + t = 1 ∑ T k s M k t , s V k t , s + t = 1 ∑ T k s M k t , s W k t , s . We bound the right-hand side in three parts: (i) The settings of θ k t , s \theta_k^{t,s} θ k t , s and p k t , s p_k^{t,s} p k t , s in Algorithm 1 give θ k t , s / M k t , s = 1 / M k t − 1 , s \theta_k^{t,s}/M_k^{t,s}=1/M_k^{t-1,s} θ k t , s / M k t , s = 1/ M k t − 1 , s , p k t , s / M k t , s = ( η k s + p k t − 1 , s ) / M k t − 1 , s p_k^{t,s}/M_k^{t,s}=(\eta_k^s+p_k^{t-1,s})/M_k^{t-1,s} p k t , s / M k t , s = ( η k s + p k t − 1 , s ) / M k t − 1 , s for 2 ≤ t ≤ T k s 2\le t\le T_k^s 2 ≤ t ≤ T k s . Then, canceling the recursive
terms while noticing the definitions of M k s M_k^s M k s , x k s x_k^s x k s and x k 0 , s x_k^{0,s} x k 0 , s yields ∑ t = 1 T k s U k t , s / M k t , s = U k s \sum_{t=1}^{T_k^s} U_k^{t,s}/M_k^{t,s}=U_k^s ∑ t = 1 T k s U k t , s / M k t , s = U k s . (ii) The inner line search gives ∥ Δ k t − 1 , s ∥ ≤ M k t − 1 , s ∥ x k t − 1 , s − x k t − 2 , s ∥ \|\Delta_k^{t-1,s}\|\le M_k^{t-1,s}\|x_k^{t-1,s}-x_k^{t-2,s}\| ∥ Δ k t − 1 , s ∥ ≤ M k t − 1 , s ∥ x k t − 1 , s − x k t − 2 , s ∥ for t ≥ 2 t\ge2 t ≥ 2 . p k t , s / M k t , s ≥ 2 p_k^{t,s}/M_k^{t,s}\ge2 p k t , s / M k t , s ≥ 2 yields
θ k t , s M k t , s ∥ Δ k t − 1 , s ∥ ∥ x k t , s − x k t − 1 , s ∥ ≤ p k t − 1 , s 4 M k t , s ∥ x k t − 1 , s − x k t − 2 , s ∥ 2 + p k t , s 4 M k t , s ∥ x k t , s − x k t − 1 , s ∥ 2 . \frac{\theta_k^{t,s}}{M_k^{t,s}}\|\Delta_k^{t-1,s}\|\|x_k^{t,s}-x_k^{t-1,s}\|\le\frac{p_k^{t-1,s}}{4M_k^{t,s}}\|x_k^{t-1,s}-x_k^{t-2,s}\|^2+\frac{p_k^{t,s}}{4M_k^{t,s}}\|x_k^{t,s}-x_k^{t-1,s}\|^2. M k t , s θ k t , s ∥ Δ k t − 1 , s ∥∥ x k t , s − x k t − 1 , s ∥ ≤ 4 M k t , s p k t − 1 , s ∥ x k t − 1 , s − x k t − 2 , s ∥ 2 + 4 M k t , s p k t , s ∥ x k t , s − x k t − 1 , s ∥ 2 .
Thus, the interior cross terms are absorbed by the negative squared-step terms, leaving the boundary expression ∑ t = 1 T k s V k t , s / M k t , s ≤ V k s \sum_{t=1}^{T_k^s} V_k^{t,s}/M_k^{t,s}\le V_k^s ∑ t = 1 T k s V k t , s / M k t , s ≤ V k s . This also covers T k s = 1 T_k^s=1 T k s = 1 , when there are no interior cross terms. (iii) The affinity of ℓ k s \ell_k^s ℓ k s and the definitions of the weighted averages give the following:
∑ t = 1 T k s W k t , s M k t , s = B k s λ k s ℓ k s ( x ) − B k s λ k s ℓ k s ( x ^ k s ) + η k s β k s 2 ∥ x − x k − 1 ∥ 2 − η k s 2 ∑ t = 1 T k s ∥ x k t , s − x k t − 1 , s ∥ 2 M k t , s . \sum_{t=1}^{T_k^s}\frac{W_k^{t,s}}{M_k^{t,s}}=\mathcal{B}_k^s\lambda_k^s\ell_k^s(x)-\mathcal{B}_k^s\lambda_k^s\ell_k^s(\hat{x}_k^s)+\frac{\eta_k^s\beta_k^s}{2}\|x-x_{k-1}\|^2-\frac{\eta_k^s}{2}\sum_{t=1}^{T_k^s}\frac{\|x_k^{t,s}-x_k^{t-1,s}\|^2}{M_k^{t,s}}. t = 1 ∑ T k s M k t , s W k t , s = B k s λ k s ℓ k s ( x ) − B k s λ k s ℓ k s ( x ^ k s ) + 2 η k s β k s ∥ x − x k − 1 ∥ 2 − 2 η k s t = 1 ∑ T k s M k t , s ∥ x k t , s − x k t − 1 , s ∥ 2 .
By the convexity of the squared norm, we have ∑ t = 1 T k s ∥ x k t , s − x k − 1 ∥ 2 M k t , s ≥ B k s ∥ x ^ k s − x k − 1 ∥ 2 \sum_{t=1}^{T_k^s}\frac{\|x_k^{t,s}-x_{k-1}\|^2}{M_k^{t,s}}\ge\mathcal{B}_k^s\|\hat{x}_k^s-x_{k-1}\|^2 ∑ t = 1 T k s M k t , s ∥ x k t , s − x k − 1 ∥ 2 ≥ B k s ∥ x ^ k s − x k − 1 ∥ 2 . Using the Lemma 2, we obtain the bound ∑ t = 1 T k s W k t , s M k t , s ≤ W k s \sum_{t=1}^{T_k^s}\frac{W_k^{t,s}}{M_k^{t,s}}\le W_k^s ∑ t = 1 T k s M k t , s W k t , s ≤ W k s . Combining the three bounds proves the result. □
Combining Proposition 1 at s = S k s=S_k s = S k with the middle-loop acceptance condition at line 9 of Algorithm 1 yields the following one-step bound on the outer primal–dual gap.
Proposition 2. For every k ≥ 1 k\ge1 k ≥ 1 , x ∈ X x\in X x ∈ X and λ ≥ 0 \lambda\ge0 λ ≥ 0 , the iterates generated by Algorithm 1 satisfy
G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) ≤ H k + I k + R k ( λ ) , (4) G_k(x,\lambda)-(1-\gamma_k^{S_k})G_{k-1}(x,\lambda)\le H_k+I_k+R_k(\lambda), \tag*{(4)} G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) ≤ H k + I k + R k ( λ ) , (4) where R k ( λ ) : = γ k S k η k S k 2 ( λ Λ − 1 ) ∥ x ^ k − x k − 1 ∥ 2 R_k(\lambda):=\frac{\gamma_k^{S_k}\eta_k^{S_k}}{2}\left(\frac{\lambda}{\Lambda}-1\right)\|\hat{x}_k-x_{k-1}\|^2 R k ( λ ) := 2 γ k S k η k S k ( Λ λ − 1 ) ∥ x ^ k − x k − 1 ∥ 2 , and
H k : = γ k S k B k s M k S k ⟨ Δ k S k , S k , x k − x ⟩ − γ k S k θ k 1 , S k B k s M k 1 , S k ⟨ Δ k 0 , S k , x k − 1 − x ⟩ H_k:=\frac{\gamma_k^{S_k}}{\mathcal{B}_k^s M_k^{S_k}}\langle\Delta_k^{S_k,S_k},x_k-x\rangle-\frac{\gamma_k^{S_k}\theta_k^{1,S_k}}{\mathcal{B}_k^s M_k^{1,S_k}}\langle\Delta_k^{0,S_k},x_{k-1}-x\rangle H k := B k s M k S k γ k S k ⟨ Δ k S k , S k , x k − x ⟩ − B k s M k 1 , S k γ k S k θ k 1 , S k ⟨ Δ k 0 , S k , x k − 1 − x ⟩ + ( γ k S k 2 B k s + γ k S k θ k 1 , S k 2 B k s M k 1 , S k ) ∥ x − x k − 1 ∥ 2 − γ k S k ( η k S k + p k S k , S k ) 2 B k s M k S k ∥ x − x k ∥ 2 , \qquad+\left(\frac{\gamma_k^{S_k}}{2\mathcal{B}_k^s}+\frac{\gamma_k^{S_k}\theta_k^{1,S_k}}{2\mathcal{B}_k^s M_k^{1,S_k}}\right)\|x-x_{k-1}\|^2-\frac{\gamma_k^{S_k}(\eta_k^{S_k}+p_k^{S_k,S_k})}{2\mathcal{B}_k^s M_k^{S_k}}\|x-x_k\|^2, + ( 2 B k s γ k S k + 2 B k s M k 1 , S k γ k S k θ k 1 , S k ) ∥ x − x k − 1 ∥ 2 − 2 B k s M k S k γ k S k ( η k S k + p k S k , S k ) ∥ x − x k ∥ 2 , I k : = − γ k S k θ k 1 , S k B k s M k 1 , S k ∥ Δ k 0 , S k ∥ ∥ x k 1 , S k − x k − 1 ∥ − γ k S k p k 1 , S k 4 B k s M k 1 , S k ∥ x k 1 , S k − x k − 1 ∥ 2 − γ k S k p k S k , S k 4 B k s M k S k ∥ x k − x k T k s − 1 , S k ∥ 2 . I_k:=-\frac{\gamma_k^{S_k}\theta_k^{1,S_k}}{\mathcal{B}_k^s M_k^{1,S_k}}\|\Delta_k^{0,S_k}\|\|x_k^{1,S_k}-x_{k-1}\|-\frac{\gamma_k^{S_k}p_k^{1,S_k}}{4\mathcal{B}_k^s M_k^{1,S_k}}\|x_k^{1,S_k}-x_{k-1}\|^2-\frac{\gamma_k^{S_k}p_k^{S_k,S_k}}{4\mathcal{B}_k^s M_k^{S_k}}\|x_k-x_k^{T_k^s-1,S_k}\|^2. I k := − B k s M k 1 , S k γ k S k θ k 1 , S k ∥ Δ k 0 , S k ∥∥ x k 1 , S k − x k − 1 ∥ − 4 B k s M k 1 , S k γ k S k p k 1 , S k ∥ x k 1 , S k − x k − 1 ∥ 2 − 4 B k s M k S k γ k S k p k S k , S k ∥ x k − x k T k s − 1 , S k ∥ 2 . Proof. From the definitions of x ˉ k \bar{x}_k x ˉ k and λ ˉ k \bar{\lambda}_k λ ˉ k , it follows that
G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) = γ k S k ⟨ F ( x ) , x ^ k S k − x ⟩ + λ g ( x ˉ k ) − ( 1 − γ k S k ) λ g ( x ˉ k − 1 ) − γ k S k λ ˉ k S k g ( x ) . G_k(x,\lambda)-(1-\gamma_k^{S_k})G_{k-1}(x,\lambda)=\gamma_k^{S_k}\langle F(x),\hat{x}_k^{S_k}-x\rangle+\lambda g(\bar{x}_k)-(1-\gamma_k^{S_k})\lambda g(\bar{x}_{k-1})-\gamma_k^{S_k}\bar{\lambda}_k^{S_k}g(x). G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) = γ k S k ⟨ F ( x ) , x ^ k S k − x ⟩ + λ g ( x ˉ k ) − ( 1 − γ k S k ) λ g ( x ˉ k − 1 ) − γ k S k λ ˉ k S k g ( x ) . Here, we make two observations. First, Proposition 1 and γ k S k / B k S k = Γ k S k \gamma_k^{S_k}/\mathcal{B}_k^{S_k}=\Gamma_k^{S_k} γ k S k / B k S k = Γ k S k give γ k S k ⟨ F ( x ) , x ^ k S k − x ⟩ ≤ Γ k S k ( U k S k + V k S k + W k S k ) \gamma_k^{S_k}\langle F(x),\hat{x}_k^{S_k}-x\rangle\le\Gamma_k^{S_k}(U_k^{S_k}+V_k^{S_k}+W_k^{S_k}) γ k S k ⟨ F ( x ) , x ^ k S k − x ⟩ ≤ Γ k S k ( U k S k + V k S k + W k S k ) .
Second, the acceptance test described at line 9 together with the definitions of x k S k x_k^{S_k} x k S k and x ˉ k \bar{x}_k x ˉ k ensures
g ( x ˉ k ) ≤ ℓ k S k ( x ˉ k ) + η k S k 2 Λ γ k S k ∥ x ˉ k − x k S k ∥ 2 = ℓ k S k ( x ˉ k ) + η k S k γ k S k 2 Λ ∥ x k − 1 − x ^ k ∥ 2 , g(\bar{x}_k)\le\ell_k^{S_k}(\bar{x}_k)+\frac{\eta_k^{S_k}}{2\Lambda\gamma_k^{S_k}}\|\bar{x}_k-x_k^{S_k}\|^2=\ell_k^{S_k}(\bar{x}_k)+\frac{\eta_k^{S_k}\gamma_k^{S_k}}{2\Lambda}\|x_{k-1}-\hat{x}_k\|^2, g ( x ˉ k ) ≤ ℓ k S k ( x ˉ k ) + 2Λ γ k S k η k S k ∥ x ˉ k − x k S k ∥ 2 = ℓ k S k ( x ˉ k ) + 2Λ η k S k γ k S k ∥ x k − 1 − x ^ k ∥ 2 , and the convexity of g g g gives that − g ( x ˉ k − 1 ) ≤ − ℓ k S k ( x ˉ k − 1 ) -g(\bar{x}_{k-1})\le-\ell_k^{S_k}(\bar{x}_{k-1}) − g ( x ˉ k − 1 ) ≤ − ℓ k S k ( x ˉ k − 1 ) and − g ( x ) ≤ − ℓ k S k ( x ) -g(x)\le-\ell_k^{S_k}(x) − g ( x ) ≤ − ℓ k S k ( x ) . Then, it follows
λ g ( x ˉ k ) − ( 1 − γ k S k ) λ g ( x ˉ k − 1 ) ≤ η k S k γ k S k 2 Λ ∥ x k − 1 − x ^ k ∥ 2 + λ γ k S k ℓ k S k ( x ^ k ) . \lambda g(\bar{x}_k)-(1-\gamma_k^{S_k})\lambda g(\bar{x}_{k-1})\le\frac{\eta_k^{S_k}\gamma_k^{S_k}}{2\Lambda}\|x_{k-1}-\hat{x}_k\|^2+\lambda\gamma_k^{S_k}\ell_k^{S_k}(\hat{x}_k). λ g ( x ˉ k ) − ( 1 − γ k S k ) λ g ( x ˉ k − 1 ) ≤ 2Λ η k S k γ k S k ∥ x k − 1 − x ^ k ∥ 2 + λ γ k S k ℓ k S k ( x ^ k ) . Then, the conclusion follows immediately with Lemma 2 and definitions of x k x_k x k and x ^ k \hat{x}_k x ^ k . □
Using the conclusion of Propositions 2, Theorem 1 establishes a global primal–dual gap bound.
Theorem 1. For every N ≥ 1 N \ge1 N ≥ 1 , x ∈ X x \in X x ∈ X , and λ ≥ 0 \lambda\ge0 λ ≥ 0 , the iterates generated by Algorithm 1 satisfy
G N ( x , λ ) ≤ Γ N S N 2 ( 3 ∥ x − x 0 ∥ 2 + ( λ Λ − 1 ) ∑ k = 1 N ∥ x k S k − x k − 1 ∥ 2 ) . (5) G_N(x,\lambda) \le\frac{\Gamma_N^{S_N}}{2}\left(3\lVert x-x_0\rVert^2+\left(\frac{\lambda}{\Lambda}-1\right)\sum_{k=1}^{N}\lVert x_k^{S_k}-x_{k-1}\rVert^2\right). \tag*{(5)} G N ( x , λ ) ≤ 2 Γ N S N ( 3 ∥ x − x 0 ∥ 2 + ( Λ λ − 1 ) k = 1 ∑ N ∥ x k S k − x k − 1 ∥ 2 ) . (5) In particular, if Λ ≥ λ \Lambda\ge\lambda Λ ≥ λ , G N ( x , λ ) ≤ ( 3 Γ N S N / 2 ) ∥ x − x 0 ∥ 2 G_N(x,\lambda) \le(3\Gamma_N^{S_N}/2)\lVert x-x_0\rVert^2 G N ( x , λ ) ≤ ( 3 Γ N S N /2 ) ∥ x − x 0 ∥ 2 .
Proof. Notice that the conclusion of Proposition 2 holds for all k ≥ 1 k \ge1 k ≥ 1 , x ∈ X x \in X x ∈ X and λ ≥ 0 \lambda\ge0 λ ≥ 0 . Dividing both sides of (4) by Γ k S k \Gamma_k^{S_k} Γ k S k for each k ≥ 1 k \ge1 k ≥ 1 , then summing from k = 1 k=1 k = 1 to N N N while considering the definition and recursive relation of Γ k S k \Gamma_k^{S_k} Γ k S k yields
G N ( x , λ ) Γ N S N ≤ ∑ k = 1 N H k Γ k S k + ∑ k = 1 N I k Γ k S k + ∑ k = 1 N R k ( λ ) Γ k S k . (6) \frac{G_N(x,\lambda)}{\Gamma_N^{S_N}} \le\sum_{k=1}^{N}\frac{H_k}{\Gamma_k^{S_k}}+\sum_{k=1}^{N}\frac{I_k}{\Gamma_k^{S_k}}+\sum_{k=1}^{N}\frac{R_k(\lambda)}{\Gamma_k^{S_k}}. \tag*{(6)} Γ N S N G N ( x , λ ) ≤ k = 1 ∑ N Γ k S k H k + k = 1 ∑ N Γ k S k I k + k = 1 ∑ N Γ k S k R k ( λ ) . (6)
Here, we make three observations. First, the initialization of the inner iterates gives Δ k + 1 0 , S k + 1 = Δ k T k S k , S k \Delta_{k+1}^{0,S_{k+1}}=\Delta_k^{T_k^{S_k},S_k} Δ k + 1 0 , S k + 1 = Δ k T k S k , S k . Together with Δ 1 0 , S 1 = 0 \Delta_1^{0,S_1}=0 Δ 1 0 , S 1 = 0 , this makes the normalized H k H_k H k terms telescope to
∑ k = 1 N H k Γ k S k = 1 M N ⟨ Δ N T N S N , S N , x N − x ⟩ + 3 2 ∥ x − x 0 ∥ 2 − 3 2 ∥ x − x N ∥ 2 . \sum_{k=1}^{N}\frac{H_k}{\Gamma_k^{S_k}}=\frac{1}{M_N}\langle\Delta_N^{T_N^{S_N},S_N},x_N-x\rangle+\frac{3}{2}\lVert x-x_0\rVert^2-\frac{3}{2}\lVert x-x_N\rVert^2. k = 1 ∑ N Γ k S k H k = M N 1 ⟨ Δ N T N S N , S N , x N − x ⟩ + 2 3 ∥ x − x 0 ∥ 2 − 2 3 ∥ x − x N ∥ 2 .
Second, for k ≥ 2 k \ge2 k ≥ 2 , the final inner-loop acceptance condition at outer iteration k − 1 k-1 k − 1 , together with the relation Δ k 0 , S k = Δ k − 1 T k − 1 S k − 1 , S k − 1 \Delta_k^{0,S_k}=\Delta_{k-1}^{T_{k-1}^{S_{k-1}},S_{k-1}} Δ k 0 , S k = Δ k − 1 T k − 1 S k − 1 , S k − 1 , gives ∥ Δ k 0 , S k ∥ ≤ M k − 1 ∥ x k − 1 − x k − 1 T k − 1 S k − 1 , S k − 1 ∥ \lVert\Delta_k^{0,S_k}\rVert\le M_{k-1}\lVert x_{k-1}-x_{k-1}^{T_{k-1}^{S_{k-1}},S_{k-1}}\rVert ∥ Δ k 0 , S k ∥ ≤ M k − 1 ∥ x k − 1 − x k − 1 T k − 1 S k − 1 , S k − 1 ∥ , which leads
∥ Δ k 0 , S k ∥ M k − 1 ∥ x k 1 , S k − x k − 1 ∥ ≤ 1 2 ∥ x k 1 , S k − x k − 1 ∥ 2 + 1 2 ∥ x k − 1 − x k − 1 T k − 1 S k − 1 , S k − 1 ∥ 2 . \frac{\lVert\Delta_k^{0,S_k}\rVert}{M_{k-1}}\lVert x_k^{1,S_k}-x_{k-1}\rVert\le\frac{1}{2}\lVert x_k^{1,S_k}-x_{k-1}\rVert^2+\frac{1}{2}\lVert x_{k-1}-x_{k-1}^{T_{k-1}^{S_{k-1}},S_{k-1}}\rVert^2. M k − 1 ∥ Δ k 0 , S k ∥ ∥ x k 1 , S k − x k − 1 ∥ ≤ 2 1 ∥ x k 1 , S k − x k − 1 ∥ 2 + 2 1 ∥ x k − 1 − x k − 1 T k − 1 S k − 1 , S k − 1 ∥ 2 .
Absorbing the first term by I k / Γ k S k I_k/\Gamma_k^{S_k} I k / Γ k S k and the second term by I k − 1 / Γ k − 1 S k − 1 I_{k-1}/\Gamma_{k-1}^{S_{k-1}} I k − 1 / Γ k − 1 S k − 1 leaves
∑ k = 1 N I k Γ k S k ≤ − p N T N S N , S N 4 M N ∥ x N − x N T N S N − 1 , S N ∥ 2 . \sum_{k=1}^{N}\frac{I_k}{\Gamma_k^{S_k}}\le-\frac{p_N^{T_N^{S_N},S_N}}{4M_N}\lVert x_N-x_N^{T_N^{S_N}-1,S_N}\rVert^2. k = 1 ∑ N Γ k S k I k ≤ − 4 M N p N T N S N , S N ∥ x N − x N T N S N − 1 , S N ∥ 2 .
Finally, the final inner-loop acceptance condition at the accepted trial s = S N s=S_N s = S N gives ∥ Δ N T N S N , S N ∥ ≤ M N S N ∥ x N − x N T N S N − 1 , S N ∥ \lVert\Delta_N^{T_N^{S_N},S_N}\rVert\le M_N^{S_N}\lVert x_N-x_N^{T_N^{S_N}-1,S_N}\rVert ∥ Δ N T N S N , S N ∥ ≤ M N S N ∥ x N − x N T N S N − 1 , S N ∥ . Moreover, since p N T N S N , S N / M N S N ≥ 2 p_N^{T_N^{S_N},S_N}/M_N^{S_N}\ge2 p N T N S N , S N / M N S N ≥ 2 , the Cauchy–Schwarz inequality yields
1 M N S N ⟨ Δ N T N S N , S N , x N − x ⟩ − 3 2 ∥ x − x N ∥ 2 − ( p N T N S N , S N 4 M N S N ) ∥ x N − x N T N S N − 1 , S N ∥ 2 ≤ 0. \frac{1}{M_N^{S_N}}\langle\Delta_N^{T_N^{S_N},S_N},x_N-x\rangle-\frac{3}{2}\lVert x-x_N\rVert^2-\left(\frac{p_N^{T_N^{S_N},S_N}}{4M_N^{S_N}}\right)\lVert x_N-x_N^{T_N^{S_N}-1,S_N}\rVert^2\le0. M N S N 1 ⟨ Δ N T N S N , S N , x N − x ⟩ − 2 3 ∥ x − x N ∥ 2 − 4 M N S N p N T N S N , S N ∥ x N − x N T N S N − 1 , S N ∥ 2 ≤ 0.
Substituting into (6) and using the definition of R k ( λ ) R_k(\lambda) R k ( λ ) proves (5) . □
Convergence Rate and Evaluation Complexity of PFAOS
The preceding subsection provides an upper bound of the duality gap involving a scalar Γ N S N \Gamma_N^{S_N} Γ N S N . In this subsection, we first estimate Γ k S k \Gamma_k^{S_k} Γ k S k and then show the evaluation complexities of PFAOS.
Lemma 3. Every middle-loop line search in Algorithm 1 terminates after finitely many trials, namely, S k < ∞ S_k<\infty S k < ∞ is well defined and that η k S k / γ k S k ≤ 4 Λ L \eta_k^{S_k}/\gamma_k^{S_k}\le4\Lambda L η k S k / γ k S k ≤ 4Λ L and Γ k S k ≤ 16 Λ L / ( k + 1 ) 2 \Gamma_k^{S_k}\le16\Lambda L/(k+1)^2 Γ k S k ≤ 16Λ L / ( k + 1 ) 2 , ∀ k ≥ 1 \forall k\ge1 ∀ k ≥ 1 .
Proof: Given the L L L -smoothness of g g g , the middle-loop acceptance test in line 9 is guaranteed whenever η k s / γ k s ≥ Λ L \eta_k^s/\gamma_k^s \ge\Lambda L η k s / γ k s ≥ Λ L . We first verify that 0 < γ k s ≤ 1 0 < \gamma_k^s \le1 0 < γ k s ≤ 1 , for every ( k , s ) (k,s) ( k , s ) trial, and the middle line search terminates within finitely many trials, namely S k < ∞ S_k < \infty S k < ∞ is well defined. For k = 1 k=1 k = 1 , Algorithm 1 sets γ 1 s = 1 \gamma_1^s=1 γ 1 s = 1 , hence η 1 s / γ 1 s = η 1 s \eta_1^s/\gamma_1^s=\eta_1^s η 1 s / γ 1 s = η 1 s . Since η 1 s \eta_1^s η 1 s is doubled after every rejection by line 9, it eventually satisfies the preceding sufficient acceptance condition. Thus, we have S 1 < ∞ S_1 < \infty S 1 < ∞ , and Γ 1 S 1 = η 1 S 1 γ 1 S 1 > 0 \Gamma_1^{S_1}=\eta_1^{S_1}\gamma_1^{S_1}>0 Γ 1 S 1 = η 1 S 1 γ 1 S 1 > 0 . Suppose that S k − 1 < ∞ S_{k-1}<\infty S k − 1 < ∞ and Γ k − 1 S k − 1 > 0 \Gamma_{k-1}^{S_{k-1}}>0 Γ k − 1 S k − 1 > 0 for some k ≥ 2 k\ge2 k ≥ 2 . Then the recursion (4) gives γ k s = Γ k − 1 S k − 1 / ( Γ k − 1 S k − 1 + η k s ) ∈ ( 0 , 1 ) \gamma_k^s=\Gamma_{k-1}^{S_{k-1}}/(\Gamma_{k-1}^{S_{k-1}}+\eta_k^s)\in(0,1) γ k s = Γ k − 1 S k − 1 / ( Γ k − 1 S k − 1 + η k s ) ∈ ( 0 , 1 ) . Indeed, if the middle line search did not terminate, then Algorithm 1 would generate η k s = 2 s − 2 η k − 1 S k − 1 → + ∞ \eta_k^s=2^{s-2}\eta_{k-1}^{S_{k-1}}\to+\infty η k s = 2 s − 2 η k − 1 S k − 1 → + ∞ as s → ∞ s\to\infty s → ∞ . Since Λ L < ∞ \Lambda L<\infty Λ L < ∞ , there would then exist a finite trial s s s such that η k s / γ k s ≥ η k s ≥ Λ L \eta_k^s/\gamma_k^s\ge\eta_k^s\ge\Lambda L η k s / γ k s ≥ η k s ≥ Λ L , at which the middle-loop acceptance test is guaranteed to hold. Thus, S k < ∞ S_k<\infty S k < ∞ is well defined for all k ≥ 1 k\ge1 k ≥ 1 .
Next, we prove η k S k / γ k S k ≤ 4 Λ L \eta_k^{S_k}/\gamma_k^{S_k}\le4\Lambda L η k S k / γ k S k ≤ 4Λ L . For k = 1 k=1 k = 1 , we have γ 1 s = 1 \gamma_1^s=1 γ 1 s = 1 . If S 1 = 1 S_1=1 S 1 = 1 , then η 1 S 1 / γ 1 S 1 = η 1 0 / 2 = Λ L 0 ≤ Λ L \eta_1^{S_1}/\gamma_1^{S_1}=\eta_1^0/2=\Lambda L_0\le\Lambda L η 1 S 1 / γ 1 S 1 = η 1 0 /2 = Λ L 0 ≤ Λ L . Otherwise, the trial immediately preceding the accepted trial failed and therefore satisfies η 1 S 1 − 1 / γ 1 S 1 − 1 = η 1 S 1 − 1 < Λ L \eta_1^{S_1-1}/\gamma_1^{S_1-1}=\eta_1^{S_1-1}<\Lambda L η 1 S 1 − 1 / γ 1 S 1 − 1 = η 1 S 1 − 1 < Λ L . Since the next trial doubles the previous η 1 s \eta_1^s η 1 s , the accepted value satisfies η 1 S 1 / γ 1 S 1 = 2 η 1 S 1 − 1 < 2 Λ L \eta_1^{S_1}/\gamma_1^{S_1}=2\eta_1^{S_1-1}<2\Lambda L η 1 S 1 / γ 1 S 1 = 2 η 1 S 1 − 1 < 2Λ L . For k ≥ 2 k\ge2 k ≥ 2 and s ≥ 1 s\ge1 s ≥ 1 , the recursion (4) gives η k s / γ k s = η k s + ( η k s ) 2 / Γ k − 1 S k − 1 \eta_k^s/\gamma_k^s=\eta_k^s+(\eta_k^s)^2/\Gamma_{k-1}^{S_{k-1}} η k s / γ k s = η k s + ( η k s ) 2 / Γ k − 1 S k − 1 , and hence for the first middle-loop trial at iteration k k k , we have
η k 1 γ k 1 = η k − 1 S k − 1 2 + ( η k − 1 S k − 1 ) 2 4 Γ k − 1 S k − 1 = ( 1 4 + η k − 1 S k − 1 2 γ k − 1 S k − 1 ) η k − 1 S k − 1 γ k − 1 S k − 1 ≤ 3 η k − 1 S k − 1 4 γ k − 1 S k − 1 . \frac{\eta_k^1}{\gamma_k^1}=\frac{\eta_{k-1}^{S_{k-1}}}{2}+\frac{(\eta_{k-1}^{S_{k-1}})^2}{4\Gamma_{k-1}^{S_{k-1}}}=\left(\frac{1}{4}+\frac{\eta_{k-1}^{S_{k-1}}}{2\gamma_{k-1}^{S_{k-1}}}\right)\frac{\eta_{k-1}^{S_{k-1}}}{\gamma_{k-1}^{S_{k-1}}}\le\frac{3\eta_{k-1}^{S_{k-1}}}{4\gamma_{k-1}^{S_{k-1}}}. γ k 1 η k 1 = 2 η k − 1 S k − 1 + 4 Γ k − 1 S k − 1 ( η k − 1 S k − 1 ) 2 = ( 4 1 + 2 γ k − 1 S k − 1 η k − 1 S k − 1 ) γ k − 1 S k − 1 η k − 1 S k − 1 ≤ 4 γ k − 1 S k − 1 3 η k − 1 S k − 1 .
Therefore, if S k = 1 S_k=1 S k = 1 , then the induction hypothesis yields η k S k / γ k S k ≤ 3 Λ L ≤ 4 Λ L \eta_k^{S_k}/\gamma_k^{S_k}\le3\Lambda L\le4\Lambda L η k S k / γ k S k ≤ 3Λ L ≤ 4Λ L . Otherwise, S k ≥ 2 S_k\ge2 S k ≥ 2 and η k S k − 1 / γ k S k − 1 < Λ L \eta_k^{S_k-1}/\gamma_k^{S_k-1}<\Lambda L η k S k − 1 / γ k S k − 1 < Λ L . Since η k S k = 2 η k S k − 1 \eta_k^{S_k}=2\eta_k^{S_k-1} η k S k = 2 η k S k − 1 , we have
η k S k γ k S k = 2 η k S k − 1 + 4 ( η k S k − 1 ) 2 Γ k − 1 S k − 1 = 4 ( η k S k − 1 + ( η k S k − 1 ) 2 Γ k − 1 S k − 1 ) − 2 η k S k − 1 = 4 η k S k − 1 γ k S k − 1 − 2 η k S k − 1 < 4 η k S k − 1 γ k S k − 1 < 4 Λ L , \frac{\eta_k^{S_k}}{\gamma_k^{S_k}}=2\eta_k^{S_k-1}+\frac{4(\eta_k^{S_k-1})^2}{\Gamma_{k-1}^{S_{k-1}}}=4\left(\eta_k^{S_k-1}+\frac{(\eta_k^{S_k-1})^2}{\Gamma_{k-1}^{S_{k-1}}}\right)-2\eta_k^{S_k-1}=4\frac{\eta_k^{S_k-1}}{\gamma_k^{S_k-1}}-2\eta_k^{S_k-1}<4\frac{\eta_k^{S_k-1}}{\gamma_k^{S_k-1}}<4\Lambda L, γ k S k η k S k = 2 η k S k − 1 + Γ k − 1 S k − 1 4 ( η k S k − 1 ) 2 = 4 ( η k S k − 1 + Γ k − 1 S k − 1 ( η k S k − 1 ) 2 ) − 2 η k S k − 1 = 4 γ k S k − 1 η k S k − 1 − 2 η k S k − 1 < 4 γ k S k − 1 η k S k − 1 < 4Λ L ,
which proves by induction that η k S k / γ k S k ≤ 4 Λ L \eta_k^{S_k}/\gamma_k^{S_k}\le4\Lambda L η k S k / γ k S k ≤ 4Λ L , for k ≥ 1 k\ge1 k ≥ 1 .
It remains to bound Γ k S k \Gamma_k^{S_k} Γ k S k . For k = 1 k=1 k = 1 , we have Γ 1 S 1 = η 1 S 1 γ 1 S 1 = η 1 S 1 / γ 1 S 1 ≤ 4 Λ L \Gamma_1^{S_1}=\eta_1^{S_1}\gamma_1^{S_1}=\eta_1^{S_1}/\gamma_1^{S_1}\le4\Lambda L Γ 1 S 1 = η 1 S 1 γ 1 S 1 = η 1 S 1 / γ 1 S 1 ≤ 4Λ L . For k ≥ 2 k\ge2 k ≥ 2 , from the recursion (4) and the fact 1 − 1 − γ ≥ γ / 2 1-\sqrt{1-\gamma}\ge\gamma/2 1 − 1 − γ ≥ γ /2 for γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] , it follows
1 Γ k S k − 1 Γ k − 1 S k − 1 = 1 − 1 − γ k S k Γ k S k ≥ γ k S k 2 Γ k S k = 1 2 η k S k / γ k S k ≥ 1 4 Λ L . \frac{1}{\sqrt{\Gamma_k^{S_k}}}-\frac{1}{\sqrt{\Gamma_{k-1}^{S_{k-1}}}}=\frac{1-\sqrt{1-\gamma_k^{S_k}}}{\sqrt{\Gamma_k^{S_k}}}\ge\frac{\gamma_k^{S_k}}{2\sqrt{\Gamma_k^{S_k}}}=\frac{1}{2\sqrt{\eta_k^{S_k}/\gamma_k^{S_k}}}\ge\frac{1}{4\sqrt{\Lambda L}}. Γ k S k 1 − Γ k − 1 S k − 1 1 = Γ k S k 1 − 1 − γ k S k ≥ 2 Γ k S k γ k S k = 2 η k S k / γ k S k 1 ≥ 4 Λ L 1 .
Summing gives
1 Γ N S N = 1 Γ 1 S 1 + ∑ k = 2 N ( 1 Γ k S k − 1 Γ k − 1 S k − 1 ) ≥ 1 2 Λ L + N − 1 4 Λ L = N + 1 4 Λ L . \frac{1}{\sqrt{\Gamma_N^{S_N}}}=\frac{1}{\sqrt{\Gamma_1^{S_1}}}+\sum_{k=2}^{N}\left(\frac{1}{\sqrt{\Gamma_k^{S_k}}}-\frac{1}{\sqrt{\Gamma_{k-1}^{S_{k-1}}}}\right)\ge\frac{1}{2\sqrt{\Lambda L}}+\frac{N-1}{4\sqrt{\Lambda L}}=\frac{N+1}{4\sqrt{\Lambda L}}. Γ N S N 1 = Γ 1 S 1 1 + k = 2 ∑ N Γ k S k 1 − Γ k − 1 S k − 1 1 ≥ 2 Λ L 1 + 4 Λ L N − 1 = 4 Λ L N + 1 .
Combining Lemma 3 with Theorem 1 gives an explicit upper bound for the primal–dual gap. We next translate this bound into guarantees for the weak VI gap and constraint violation in (2) .
Corollary 1. Let ( x ∗ , λ ∗ ) (x^*,\lambda^*) ( x ∗ , λ ∗ ) satisfy (3) . For every N ≥ 1 N\ge1 N ≥ 1 , both sup x ∈ X ~ ⟨ F ( x ) , x ‾ N − x ⟩ \sup_{x\in\widetilde X}\langle F(x),\overline{x}_N-x\rangle sup x ∈ X ⟨ F ( x ) , x N − x ⟩ and ( Λ − λ ∗ ) [ g ( x ‾ N ) ] + (\Lambda-\lambda^*)[g(\overline{x}_N)]_+ ( Λ − λ ∗ ) [ g ( x N ) ] + are bounded above by 3 2 Γ N S N D X 2 ≤ 24 Λ L D X 2 ( N + 1 ) 2 \frac{3}{2}\Gamma_N^{S_N}D_X^2\le\frac{24\Lambda L D_X^2}{(N+1)^2} 2 3 Γ N S N D X 2 ≤ ( N + 1 ) 2 24Λ L D X 2 . In particular, if Λ ≥ λ ∗ + 1 \Lambda\ge\lambda^*+1 Λ ≥ λ ∗ + 1 , then x ‾ N \overline{x}_N x N is an ε \varepsilon ε -approximate solution of (2) whenever 3 2 Γ N S N D X 2 ≤ ε \frac{3}{2}\Gamma_N^{S_N}D_X^2\le\varepsilon 2 3 Γ N S N D X 2 ≤ ε , which is guaranteed by N + 1 ≥ 24 Λ L D X 2 ε N+1\ge\sqrt{\frac{24\Lambda L D_X^2}{\varepsilon}} N + 1 ≥ ε 24Λ L D X 2 .
Proof: For any x ∈ X ~ x \in\widetilde{X} x ∈ X , since g ( x ) ≤ 0 g(x) \le0 g ( x ) ≤ 0 and λ ‾ N ≥ 0 \overline{\lambda}_N \ge0 λ N ≥ 0 , Theorem 1 gives ⟨ F ( x ) , x ‾ N − x ⟩ ≤ G N ( x , 0 ) ≤ 3 2 Γ N S N ∥ x − x 0 ∥ 2 \langle F(x),\overline{x}_N-x\rangle\le G_N(x,0) \le\frac{3}{2}\Gamma_N^{S_N}\lVert x-x_0\rVert^2 ⟨ F ( x ) , x N − x ⟩ ≤ G N ( x , 0 ) ≤ 2 3 Γ N S N ∥ x − x 0 ∥ 2 . Taking the supremum over x ∈ X ~ x \in\widetilde{X} x ∈ X yields the weak VI gap bound. Next, by the conditions in (3) and the convexity of g g g , we have ⟨ F ( x ∗ ) , x ‾ N − x ∗ ⟩ ≥ − λ ∗ ⟨ ∇ g ( x ∗ ) , x ‾ N − x ∗ ⟩ ≥ − λ ∗ ( g ( x ‾ N ) − g ( x ∗ ) ) = − λ ∗ g ( x ‾ N ) \langle F(x^*),\overline{x}_N-x^*\rangle\ge-\lambda^*\langle\nabla g(x^*),\overline{x}_N-x^*\rangle\ge-\lambda^*(g(\overline{x}_N)-g(x^*))=-\lambda^*g(\overline{x}_N) ⟨ F ( x ∗ ) , x N − x ∗ ⟩ ≥ − λ ∗ ⟨ ∇ g ( x ∗ ) , x N − x ∗ ⟩ ≥ − λ ∗ ( g ( x N ) − g ( x ∗ )) = − λ ∗ g ( x N ) . It follows that ( Λ − λ ∗ ) [ g ( x ‾ N ) ] + ≤ [ ⟨ F ( x ∗ ) , x ‾ N − x ∗ ⟩ + Λ g ( x ‾ N ) ] + ≤ [ G N ( x ∗ , Λ ) ] + ≤ 3 2 Γ N S N D X 2 (\Lambda-\lambda^*)[g(\overline{x}_N)]_+ \le[\langle F(x^*),\overline{x}_N-x^*\rangle+\Lambda g(\overline{x}_N)]_+ \le[G_N(x^*,\Lambda)]_+ \le\frac{3}{2}\Gamma_N^{S_N}D_X^2 ( Λ − λ ∗ ) [ g ( x N ) ] + ≤ [⟨ F ( x ∗ ) , x N − x ∗ ⟩ + Λ g ( x N ) ] + ≤ [ G N ( x ∗ , Λ ) ] + ≤ 2 3 Γ N S N D X 2 . The explicit rate directly follows from Lemma 3. □
Corollary 1 gives a sufficient number of outer iterations to obtain an ε \varepsilon ε -approximate solution.
Using this result, Proposition 3 bounds the numbers of constraint-gradient and operator evaluations.
PROPOSITION 3. Suppose Λ ≥ λ ∗ + 1 \Lambda\ge\lambda^*+1 Λ ≥ λ ∗ + 1 . For any ε > 0 \varepsilon>0 ε > 0 , Algorithm 1 obtains an ε \varepsilon ε -approximate solution of (2) using at most 3 + 2 24 Λ L D X 2 ε + ⌈ log 2 2 L L 0 ⌉ 3+2\sqrt{\frac{24\Lambda L D_X^2}{\varepsilon}}+\left\lceil\log_2\frac{2L}{L_0}\right\rceil 3 + 2 ε 24Λ L D X 2 + ⌈ log 2 L 0 2 L ⌉ evaluations of ∇ g \nabla g ∇ g and 1 + 4 M ‾ η 0 0 + 6 M ‾ D X 2 ε + ⌈ log 2 M ‾ M 0 ⌉ 1+\frac{4\overline{M}}{\eta_0^0}+\frac{6\overline{M}D_X^2}{\varepsilon}+\left\lceil\log_2\frac{\overline{M}}{M_0}\right\rceil 1 + η 0 0 4 M + ε 6 M D X 2 + ⌈ log 2 M 0 M ⌉ evaluations of F F F , where M ‾ : = 2 max { 2 Λ L , M } \overline{M}:=2\max\{2\Lambda L,M\} M := 2 max { 2Λ L , M } . These bounds include evaluations at initialization and in accepted and rejected line-search trials.
Proof: Let N ε ≥ 1 N_\varepsilon\ge1 N ε ≥ 1 be the first outer iteration satisfying 3 2 Γ N ε S N ε D X 2 ≤ ε \frac{3}{2}\Gamma_{N_\varepsilon}^{S_{N_\varepsilon}}D_X^2\le\varepsilon 2 3 Γ N ε S N ε D X 2 ≤ ε . By Corollary 1, x ‾ N ε \overline{x}_{N_\varepsilon} x N ε is an ε \varepsilon ε -approximate solution to (2) and N ε ≤ 1 + 24 Λ L D X 2 ε N_\varepsilon\le1+\sqrt{\frac{24\Lambda L D_X^2}{\varepsilon}} N ε ≤ 1 + ε 24Λ L D X 2 . Each middle trial requires one evaluation of ∇ g \nabla g ∇ g . The update η k S k = 2 S k − 2 η k S k − 1 \eta_k^{S_k}=2^{S_k-2}\eta_k^{S_k-1} η k S k = 2 S k − 2 η k S k − 1 gives ∑ k = 1 N ε S k = 2 N ε + log 2 η N ε S N ε η 0 0 ≤ 2 N ε + log 2 2 L L 0 \sum_{k=1}^{N_\varepsilon}S_k=2N_\varepsilon+\log_2\frac{\eta_{N_\varepsilon}^{S_{N_\varepsilon}}}{\eta_0^0}\le2N_\varepsilon+\log_2\frac{2L}{L_0} ∑ k = 1 N ε S k = 2 N ε + log 2 η 0 0 η N ε S N ε ≤ 2 N ε + log 2 L 0 2 L , where the inequality follows from η N ε S N ε ≤ 4 Λ L \eta_{N_\varepsilon}^{S_{N_\varepsilon}}\le4\Lambda L η N ε S N ε ≤ 4Λ L by Lemma 3 and η 0 0 = 2 Λ L 0 \eta_0^0=2\Lambda L_0 η 0 0 = 2Λ L 0 . Allowing one initialization evaluation and using the bound on N ε N_\varepsilon N ε yields the stated constraint-gradient complexity.
For the operator evaluations, note that M 0 ≤ 2 Λ L M_0\le2\Lambda L M 0 ≤ 2Λ L and η k s ≤ η k S k ≤ 4 Λ L \eta_k^s\le\eta_k^{S_k}\le4\Lambda L η k s ≤ η k S k ≤ 4Λ L for every executed middle trial. Thus, the initialization M k 0 , s = max { η k s , M k S k − 1 } M_k^{0,s}=\max\{\eta_k^s,M_k^{S_{k-1}}\} M k 0 , s = max { η k s , M k S k − 1 } preserves the bound M ‾ \overline{M} M . Each inner update either leaves the estimate unchanged or, when backtracking occurs, gives M k t , s < 2 M k t − 1 , s M_k^{t,s}<2M_k^{t-1,s} M k t , s < 2 M k t − 1 , s by the M M M -Lipschitz continuity of F F F and the minimality of q k t , s q_k^{t,s} q k t , s . Induction therefore yields M k t , s ≤ M ‾ M_k^{t,s}\le\overline{M} M k t , s ≤ M for every executed inner iteration. Using this bound and Lemma 2, we obtain T k s ≤ ∑ t = 1 T k s M ‾ M k t , s ≤ M ‾ η k s T_k^s\le\sum_{t=1}^{T_k^s}\frac{\overline{M}}{M_k^{t,s}}\le\frac{\overline{M}}{\eta_k^s} T k s ≤ ∑ t = 1 T k s M k t , s M ≤ η k s M . Moreover, η k s = 2 s − 2 η k s − 1 \eta_k^s=2^{s-2}\eta_k^{s-1} η k s = 2 s − 2 η k s − 1 gives ∑ s = 1 S k 1 η k s < 4 η k S k − 1 \sum_{s=1}^{S_k}\frac{1}{\eta_k^s}<\frac{4}{\eta_k^{S_k-1}} ∑ s = 1 S k η k s 1 < η k S k − 1 4 . Hence, for N ε ≥ 2 N_\varepsilon\ge2 N ε ≥ 2 ,
∑ k = 1 N ε ∑ s = 1 S k T k s < 4 M ‾ ( 1 η 0 0 + ∑ k = 1 N ε − 1 1 η k S k ) = 4 M ‾ ( 1 η 0 0 + 1 Γ N ε − 1 S N ε − 1 ) < 4 M ‾ η 0 0 + 6 M ‾ D X 2 ε . \sum_{k=1}^{N_\varepsilon}\sum_{s=1}^{S_k}T_k^s<4\overline{M}\left(\frac{1}{\eta_0^0}+\sum_{k=1}^{N_\varepsilon-1}\frac{1}{\eta_k^{S_k}}\right)=4\overline{M}\left(\frac{1}{\eta_0^0}+\frac{1}{\Gamma_{N_\varepsilon-1}^{S_{N_\varepsilon-1}}}\right)<\frac{4\overline{M}}{\eta_0^0}+\frac{6\overline{M}D_X^2}{\varepsilon}. k = 1 ∑ N ε s = 1 ∑ S k T k s < 4 M ( η 0 0 1 + k = 1 ∑ N ε − 1 η k S k 1 ) = 4 M ( η 0 0 1 + Γ N ε − 1 S N ε − 1 1 ) < η 0 0 4 M + ε 6 M D X 2 .
The equality follows by telescoping 1 / Γ k S k − 1 / Γ k − 1 S k − 1 = 1 / η k S k 1/\Gamma_k^{S_k}-1/\Gamma_{k-1}^{S_{k-1}}=1/\eta_k^{S_k} 1/ Γ k S k − 1/ Γ k − 1 S k − 1 = 1/ η k S k for k ≥ 2 k\ge2 k ≥ 2 , with Γ 1 S 1 = η 1 S 1 \Gamma_1^{S_1}=\eta_1^{S_1} Γ 1 S 1 = η 1 S 1 . The last inequality follows from 3 2 Γ N ε − 1 S N ε − 1 D X 2 > ε \frac{3}{2}\Gamma_{N_\varepsilon-1}^{S_{N_\varepsilon-1}}D_X^2>\varepsilon 2 3 Γ N ε − 1 S N ε − 1 D X 2 > ε , by the minimality of N ε N_\varepsilon N ε . For N ε = 1 N_\varepsilon=1 N ε = 1 , the geometric-series bound gives ∑ s = 1 S 1 T 1 s < 4 M ‾ / η 0 0 \sum_{s=1}^{S_1}T_1^s<4\overline{M}/\eta_0^0 ∑ s = 1 S 1 T 1 s < 4 M / η 0 0 . Finally, each rejected inner trial doubles the nondecreasing operator estimate, so ∑ k = 1 N ε ∑ s = 1 S k ∑ t = 1 T k s q k t , s ≤ log 2 M ‾ M 0 \sum_{k=1}^{N_\varepsilon}\sum_{s=1}^{S_k}\sum_{t=1}^{T_k^s}q_k^{t,s}\le\log_2\frac{\overline{M}}{M_0} ∑ k = 1 N ε ∑ s = 1 S k ∑ t = 1 T k s q k t , s ≤ log 2 M 0 M . Counting one F F F evaluation per completed inner iteration or rejected inner trial, and one at x 0 x_0 x 0 , gives the operator complexity. □
Provided Λ ≥ λ ∗ + 1 \Lambda\ge\lambda^*+1 Λ ≥ λ ∗ + 1 , Proposition 3 shows that PFAOS requires at most O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) constraint-gradient evaluations and O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator evaluations to obtain an ε \varepsilon ε -approximate solution. Two remarks clarify the parameter dependence of these bounds in the conclusion of Proposition 3. First, the operator bound involves M ‾ = 2 max { 2 Λ L , M } \overline{M} = 2\max\{2\Lambda L, M\} M = 2 max { 2Λ L , M } . When M ≥ 2 Λ L M \ge2\Lambda L M ≥ 2Λ L , the M ‾ D X 2 / ε \overline{M}D_X^2/\varepsilon M D X 2 / ε term becomes O ( M D X 2 / ε ) O(MD_X^2/\varepsilon) O ( M D X 2 / ε ) . Note that such comparison between M M M and Λ L \Lambda L Λ L is not required for the preceding convergence or complexity results. Second, the term M ‾ / η 0 S 0 \overline{M}/\eta_0^{S_0} M / η 0 S 0 can be large when η 0 S 0 \eta_0^{S_0} η 0 S 0 is too small. The condition η 0 S 0 ≳ ε / D X 2 \eta_0^{S_0} \gtrsim\varepsilon/D_X^2 η 0 S 0 ≳ ε / D X 2 allows this term to be absorbed into O ( M ‾ D X 2 / ε ) O(\overline{M}D_X^2/\varepsilon) O ( M D X 2 / ε ) . § 4 modifies the search at k = 1 k=1 k = 1 to remove this inverse dependence on η 0 S 0 \eta_0^{S_0} η 0 S 0 , allowing arbitrarily small initial estimates.
Multi-Constrained Parameter-Free Accelerated Operator Sliding (MC-PFAOS)
Extending the single-constraint PFAOS approach directly to the setting with multiple constraints would require solving each primal subproblem over X X X intersected with m m m halfspaces, which can be computationally expensive, especially for large m m m . MC-PFAOS, presented in Algorithm 2, dualizes these affine constraints and uses coupled primal–dual updates requiring only projections onto X X X and R + m \mathbb{R}_{+}^{m} R + m , respectively.
Algorithm 2 retains the same outer-, middle-, and inner-loop structure as PFAOS. The updates of η k s \eta_k^s η k s , γ k s \gamma_k^s γ k s , θ k t , s \theta_k^{t,s} θ k t , s , and T k t , s T_k^{t,s} T k t , s , as well as the weighted averaging that defines x ^ k s \widehat{x}_k^s x k s , follow the same mechanisms. We therefore focus on the modifications introduced in MC-PFAOS relative to PFAOS.
First, at each middle trial ( k , s ) (k,s) ( k , s ) , MC-PFAOS linearizes the vector constraint mapping G ( x ) G(x) G ( x ) at x k s x_k^s x k s as G ( x k s ) + J ( x k s ) ( x − x k s ) G(x_k^s) + J(x_k^s)(x-x_k^s) G ( x k s ) + J ( x k s ) ( x − x k s ) , and reuses the same Jacobian J ( x k s ) J(x_k^s) J ( x k s ) throughout the inner loop. Instead of imposing this affine model as a primal constraint, MC-PFAOS maintains a dual vector λ k t , s ∈ R + m \lambda_k^{t,s} \in\mathbb{R}_{+}^{m} λ k t , s ∈ R + m for each inner iterate and performs coupled primal–dual hybrid-gradient-type proximal updates, resulting in strongly convex quadratic primal and dual problems over X X X and R + m \mathbb{R}_{+}^{m} R + m , respectively.
Second, the primal update retains the operator extrapolation in PFAOS and adds dual extrapolation. For t ≥ 2 t \ge2 t ≥ 2 , the extrapolated dual vector λ k t − 1 , s + θ k t , s ( λ k t − 1 , s − λ k t − 2 , s ) \lambda_k^{t-1,s}+\theta_k^{t,s}(\lambda_k^{t-1,s}-\lambda_k^{t-2,s}) λ k t − 1 , s + θ k t , s ( λ k t − 1 , s − λ k t − 2 , s ) is paired with the current Jacobian J ( x k s ) J(x_k^s) J ( x k s ) . We treat the first inner iteration separately: the base vector λ k 0 , s \lambda_k^{0,s} λ k 0 , s is paired with J ( x k s ) J(x_k^s) J ( x k s ) , whereas the inherited dual increment λ k 0 , s − λ k − 1 , s \lambda_k^{0,s}-\lambda_k^{-1,s} λ k 0 , s − λ k − 1 , s is paired with J ( x k − 1 S k − 1 ) J(x_{k-1}^{S_{k-1}}) J ( x k − 1 S k − 1 ) . This use of the previously accepted Jacobian allows the dual boundary terms to telescope across outer iterations.
Third, the inner line search adapts simultaneously to the local variation of F F F and the Jacobian–dual coupling. Unlike in PFAOS, where the local estimate M k t , s M_k^{t,s} M k t , s controls only the variation of F F F , in MC-PFAOS the same estimate also controls the action of J ( x k s ) T J(x_k^s)^{\mathsf{T}} J ( x k s ) T on the current dual increment. Accordingly, M k t , s M_k^{t,s} M k t , s is increased until both ∥ F ( x k t , s ) − F ( x k t − 1 , s ) ∥ ≤ M k t , s ∥ x k t , s − x k t − 1 , s ∥ \|F(x_k^{t,s})-F(x_k^{t-1,s})\| \le M_k^{t,s}\|x_k^{t,s}-x_k^{t-1,s}\| ∥ F ( x k t , s ) − F ( x k t − 1 , s ) ∥ ≤ M k t , s ∥ x k t , s − x k t − 1 , s ∥ and ∥ J ( x k s ) T ( λ k t , s − λ k t − 1 , s ) ∥ ≤ M k t , s ∥ λ k t , s − λ k t − 1 , s ∥ \|J(x_k^s)^{\mathsf{T}}(\lambda_k^{t,s}-\lambda_k^{t-1,s})\| \le M_k^{t,s}\|\lambda_k^{t,s}-\lambda_k^{t-1,s}\| ∥ J ( x k s ) T ( λ k t , s − λ k t − 1 , s ) ∥ ≤ M k t , s ∥ λ k t , s − λ k t − 1 , s ∥ hold. This is how the MC-PFAOS removes the prior knowledge of both the Lipschitz constant and a uniform bound on ∥ J ( x ) ∥ \|J(x)\| ∥ J ( x ) ∥ over X X X .
Algorithm 2 Multi-constrained parameter-free accelerated operator sliding (MC-PFAOS)
Initialization: x ˉ 0 = x 0 S 0 = x 0 ∈ X \bar{x}_0=x_0^{S_0}=x_0\in X x ˉ 0 = x 0 S 0 = x 0 ∈ X , λ ˉ 0 = λ 0 = 0 \bar{\lambda}_0=\lambda_0=0 λ ˉ 0 = λ 0 = 0 , L 0 ∈ ( 0 , L ) L_0\in(0,L) L 0 ∈ ( 0 , L ) , Λ > 0 \Lambda>0 Λ > 0 , and M 0 = η 0 S 0 = 2 Λ L 0 M_0=\eta_0^{S_0}=2\Lambda L_0 M 0 = η 0 S 0 = 2Λ L 0
for k = 1 , … , N k=1,\ldots,N k = 1 , … , N do
Set s = 1 s=1 s = 1 and M k 0 = M k − 1 M_k^0=M_{k-1} M k 0 = M k − 1
Set η k s = 2 s − 2 η k − 1 S k − 1 \eta_k^s=2^{s-2}\eta_{k-1}^{S_{k-1}} η k s = 2 s − 2 η k − 1 S k − 1 and compute x k s = ( 1 − γ k s ) x ˉ k − 1 + γ k s x k − 1 x_k^s=(1-\gamma_k^s)\bar{x}_{k-1}+\gamma_k^s x_{k-1} x k s = ( 1 − γ k s ) x ˉ k − 1 + γ k s x k − 1 with γ k s \gamma_k^s γ k s defined by (4)
Set t = 1 t=1 t = 1 , M k 0 , s = max { η k s , M k s − 1 } M_k^{0,s}=\max\{\eta_k^s,M_k^{s-1}\} M k 0 , s = max { η k s , M k s − 1 } , T k 0 , s = M k 0 , s / η k s T_k^{0,s}=M_k^{0,s}/\eta_k^s T k 0 , s = M k 0 , s / η k s , x k 0 , s = x ˉ k − 1 x_k^{0,s}=\bar{x}_{k-1} x k 0 , s = x ˉ k − 1 , λ k 0 , s = λ k − 1 \lambda_k^{0,s}=\lambda_{k-1} λ k 0 , s = λ k − 1 , x k − 1 , s = x k − 1 T k S k − 1 − 1 , S k − 1 x_k^{-1,s}=x_{k-1}^{T_k^{S_{k-1}-1,S_{k-1}}} x k − 1 , s = x k − 1 T k S k − 1 − 1 , S k − 1 and λ k − 1 , s = λ k − 1 T k S k − 1 − 1 , S k − 1 \lambda_k^{-1,s}=\lambda_{k-1}^{T_k^{S_{k-1}-1,S_{k-1}}} λ k − 1 , s = λ k − 1 T k S k − 1 − 1 , S k − 1 . Here, x 0 T 0 S 0 − 1 , S 0 = x 0 x_{0}^{T_0^{S_0-1,S_0}}=x_0 x 0 T 0 S 0 − 1 , S 0 = x 0 and λ 0 T 0 S 0 − 1 , S 0 = 0 \lambda_{0}^{T_0^{S_0-1,S_0}}=0 λ 0 T 0 S 0 − 1 , S 0 = 0 .
Compute
x k t , s = arg min x ∈ X ⟨ F ( x k t − 1 , s ) + θ k t , s [ F ( x k t − 1 , s ) − F ( x k t − 2 , s ) ] , x ⟩ + η k s 2 ∥ x − x k − 1 ∥ 2 + p k t , s 2 ∥ x − x k t − 1 , s ∥ 2 x_k^{t,s}=\mathop{\arg\min}_{x\in X}\left\langle F(x_k^{t-1,s})+\theta_k^{t,s}\left[F(x_k^{t-1,s})-F(x_k^{t-2,s})\right],x\right\rangle+\frac{\eta_k^s}{2}\lVert x-x_{k-1}\rVert^2+\frac{p_k^{t,s}}{2}\lVert x-x_k^{t-1,s}\rVert^2 x k t , s = arg min x ∈ X ⟨ F ( x k t − 1 , s ) + θ k t , s [ F ( x k t − 1 , s ) − F ( x k t − 2 , s ) ] , x ⟩ + 2 η k s ∥ x − x k − 1 ∥ 2 + 2 p k t , s ∥ x − x k t − 1 , s ∥ 2
+ { ⟨ λ k t − 1 , s + θ k t , s ( λ k t − 1 , s − λ k t − 2 , s ) , J ( x k s ) x ⟩ , if t ≥ 2 , ⟨ λ k 0 , s , J ( x k s ) x ⟩ + θ k t , s ⟨ λ k − 1 , s , J ( x k − 1 s ) x ⟩ , if t = 1 , (7) \qquad+\begin{cases}
\left\langle\lambda_k^{t-1,s}+\theta_k^{t,s}\left(\lambda_k^{t-1,s}-\lambda_k^{t-2,s}\right),J(x_k^s)x\right\rangle, & \text{if }t\ge2,\\
\left\langle\lambda_k^{0,s},J(x_k^s)x\right\rangle+\theta_k^{t,s}\left\langle\lambda_k^{-1,s},J(x_{k-1}^s)x\right\rangle, & \text{if }t=1,
\end{cases} \tag*{(7)} + ⎩ ⎨ ⎧ ⟨ λ k t − 1 , s + θ k t , s ( λ k t − 1 , s − λ k t − 2 , s ) , J ( x k s ) x ⟩ , ⟨ λ k 0 , s , J ( x k s ) x ⟩ + θ k t , s ⟨ λ k − 1 , s , J ( x k − 1 s ) x ⟩ , if t ≥ 2 , if t = 1 , (7)
λ k t , s = arg min λ ∈ R + m − ⟨ G ( x k s ) + J ( x k s ) ( x k t , s − x k s ) , λ ⟩ + η k s 2 ∥ λ − λ k − 1 ∥ 2 + p k t , s 2 ∥ λ − λ k t − 1 , s ∥ 2 \lambda_k^{t,s}=\mathop{\arg\min}_{\lambda\in\mathbb{R}_+^m}-\left\langle G(x_k^s)+J(x_k^s)(x_k^{t,s}-x_k^s),\lambda\right\rangle+\frac{\eta_k^s}{2}\lVert\lambda-\lambda_{k-1}\rVert^2+\frac{p_k^{t,s}}{2}\lVert\lambda-\lambda_k^{t-1,s}\rVert^2 λ k t , s = arg min λ ∈ R + m − ⟨ G ( x k s ) + J ( x k s ) ( x k t , s − x k s ) , λ ⟩ + 2 η k s ∥ λ − λ k − 1 ∥ 2 + 2 p k t , s ∥ λ − λ k t − 1 , s ∥ 2
Here θ k 0 , 1 = 1 \theta_k^{0,1}=1 θ k 0 , 1 = 1 , θ k 0 , s = M k 1 , s / M k − 1 \theta_k^{0,s}=M_k^{1,s}/M_{k-1} θ k 0 , s = M k 1 , s / M k − 1 , ∀ k ≥ 2 \forall k\ge2 ∀ k ≥ 2 , θ k t , s = M k t , s / M k t − 1 , s \theta_k^{t,s}=M_k^{t,s}/M_k^{t-1,s} θ k t , s = M k t , s / M k t − 1 , s , ∀ t ≥ 2 \forall t\ge2 ∀ t ≥ 2 , and p k t , s = 3 M k t , s + η k s M k t , s ∑ i = 1 t − 1 ( 1 / M k i , s ) p_k^{t,s}=3M_k^{t,s}+\eta_k^s M_k^{t,s}\sum_{i=1}^{t-1}(1/M_k^{i,s}) p k t , s = 3 M k t , s + η k s M k t , s ∑ i = 1 t − 1 ( 1/ M k i , s ) , where M k t , s = 2 q k t , s M k t − 1 , s M_k^{t,s}=2^{q_k^{t,s}}M_k^{t-1,s} M k t , s = 2 q k t , s M k t − 1 , s and q k t , s ≥ 0 q_k^{t,s}\ge0 q k t , s ≥ 0 is the smallest integer such that ∥ F ( x k t , s ) − F ( x k t − 1 , s ) ∥ ≤ M k t , s ∥ x k t , s − x k t − 1 , s ∥ \lVert F(x_k^{t,s})-F(x_k^{t-1,s})\rVert\le M_k^{t,s}\lVert x_k^{t,s}-x_k^{t-1,s}\rVert ∥ F ( x k t , s ) − F ( x k t − 1 , s )∥ ≤ M k t , s ∥ x k t , s − x k t − 1 , s ∥ and ∥ J ( x k s ) ⊤ ( λ k t , s − λ k t − 1 , s ) ∥ ≤ M k t , s ∥ λ k t , s − λ k t − 1 , s ∥ \lVert J(x_k^s)^\top(\lambda_k^{t,s}-\lambda_k^{t-1,s})\rVert\le M_k^{t,s}\lVert\lambda_k^{t,s}-\lambda_k^{t-1,s}\rVert ∥ J ( x k s ) ⊤ ( λ k t , s − λ k t − 1 , s )∥ ≤ M k t , s ∥ λ k t , s − λ k t − 1 , s ∥
Set T k t , s ← t − 1 + 2 q k t , s ( T k t − 1 , s − t + 1 ) T_k^{t,s}\leftarrow t-1+2^{q_k^{t,s}}(T_k^{t-1,s}-t+1) T k t , s ← t − 1 + 2 q k t , s ( T k t − 1 , s − t + 1 )
if t < T k t , s t<T_k^{t,s} t < T k t , s , then set t ← t + 1 t\leftarrow t+1 t ← t + 1 and go to line 6; else set T k s = T k t , s T_k^s=T_k^{t,s} T k s = T k t , s , M k s = M k T k s , s M_k^s=M_k^{T_k^s,s} M k s = M k T k s , s ,
x k s = x k T k s , s x_k^s=x_k^{T_k^s,s} x k s = x k T k s , s , x ^ k s = ( ∑ i = 1 T k s 1 / M k i , s ) − 1 ∑ i = 1 T k s x k i , s / M k i , s \hat{x}_k^s=\left(\sum_{i=1}^{T_k^s}1/M_k^{i,s}\right)^{-1}\sum_{i=1}^{T_k^s}x_k^{i,s}/M_k^{i,s} x ^ k s = ( ∑ i = 1 T k s 1/ M k i , s ) − 1 ∑ i = 1 T k s x k i , s / M k i , s , x ˉ k s = ( 1 − γ k s ) x ˉ k − 1 + γ k s x ^ k s \bar{x}_k^s=(1-\gamma_k^s)\bar{x}_{k-1}+\gamma_k^s\hat{x}_k^s x ˉ k s = ( 1 − γ k s ) x ˉ k − 1 + γ k s x ^ k s , and λ k s = λ k T k s , s \lambda_k^s=\lambda_k^{T_k^s,s} λ k s = λ k T k s , s
if ∥ G ( x ˉ k s ) − G ( x k s ) − J ( x k s ) ( x ˉ k s − x k s ) ∥ ≤ η k s 2 λ γ k s ∥ x ˉ k s − x k s ∥ 2 \lVert G(\bar{x}_k^s)-G(x_k^s)-J(x_k^s)(\bar{x}_k^s-x_k^s)\rVert\le\frac{\eta_k^s}{2\lambda\gamma_k^s}\lVert\bar{x}_k^s-x_k^s\rVert^2 ∥ G ( x ˉ k s ) − G ( x k s ) − J ( x k s ) ( x ˉ k s − x k s )∥ ≤ 2 λ γ k s η k s ∥ x ˉ k s − x k s ∥ 2 does not hold, then update s ← s + 1 s\leftarrow s+1 s ← s + 1 and go to line 4; else set S k = s S_k=s S k = s , M k = M k S k M_k=M_k^{S_k} M k = M k S k , x k = x k S k x_k=x_k^{S_k} x k = x k S k , x ^ k = x ^ k S k \hat{x}_k=\hat{x}_k^{S_k} x ^ k = x ^ k S k , x ˉ k = x ˉ k S k \bar{x}_k=\bar{x}_k^{S_k} x ˉ k = x ˉ k S k , λ k = λ k S k \lambda_k=\lambda_k^{S_k} λ k = λ k S k
end for
return x ˉ N \bar{x}_N x ˉ N
Finally, after the inner loop terminates, the middle-loop acceptance test is replaced by the vector Euclidean-norm condition ∥ G ( x ˉ k s ) − G ( x k s ) − J ( x k s ) ( x ˉ k s − x k s ) ∥ ≤ η k s 2 λ γ k s ∥ x ˉ k s − x k s ∥ 2 \lVert G(\bar{x}_k^s)-G(x_k^s)-J(x_k^s)(\bar{x}_k^s-x_k^s)\rVert\le\frac{\eta_k^s}{2\lambda\gamma_k^s}\lVert\bar{x}_k^s-x_k^s\rVert^2 ∥ G ( x ˉ k s ) − G ( x k s ) − J ( x k s ) ( x ˉ k s − x k s )∥ ≤ 2 λ γ k s η k s ∥ x ˉ k s − x k s ∥ 2 . If this condition fails, η k s \eta_k^s η k s is doubled and the next middle trial ( k , s + 1 ) (k,s+1) ( k , s + 1 ) is performed; otherwise, the candidate is accepted as the output of outer iteration k k k .
Convergence Analysis of MC-PFAOS
In this subsection, we establish the convergence properties of Algorithm 2. We retain the definitions of B k s \mathcal{B}_k^s B k s , Δ k t , s \Delta_k^{t,s} Δ k t , s , and Γ k s \Gamma_k^s Γ k s from § 2 . For the dual iterates λ k t , s ∈ R + m \lambda_k^{t,s}\in\mathbb{R}_+^m λ k t , s ∈ R + m generated by Algorithm 2, we define λ ^ k s \hat{\lambda}_k^s λ ^ k s , λ ^ k \hat{\lambda}_k λ ^ k , and λ ˉ k \bar{\lambda}_k λ ˉ k using the same averaging rules as in § 2 . We also denote the extrapolated dual variable by λ ~ k t , s : = λ k t − 1 , s + θ k t , s ( λ k t − 1 , s − λ k t − 2 , s ) \tilde{\lambda}_k^{t,s}:=\lambda_k^{t-1,s}+\theta_k^{t,s}(\lambda_k^{t-1,s}-\lambda_k^{t-2,s}) λ ~ k t , s := λ k t − 1 , s + θ k t , s ( λ k t − 1 , s − λ k t − 2 , s ) . In the multi-constraint setting, the affine constraint model and primal–dual gap function become, for x ∈ X x\in X x ∈ X and λ ∈ R + m \lambda\in\mathbb{R}_+^m λ ∈ R + m ,
ℓ k s ( z ) : = G ( x k s ) + J ( x k s ) ( z − x k s ) , G k ( x , λ ) : = ⟨ F ( x ) , x ˉ k − x ⟩ + ⟨ G ( x ˉ k ) , λ ⟩ − ⟨ G ( x ) , λ ˉ k ⟩ . \ell_k^s(z):=G(x_k^s)+J(x_k^s)(z-x_k^s),\qquad\mathcal{G}_k(x,\lambda):=\langle F(x),\bar{x}_k-x\rangle+\langle G(\bar{x}_k),\lambda\rangle-\langle G(x),\bar{\lambda}_k\rangle. ℓ k s ( z ) := G ( x k s ) + J ( x k s ) ( z − x k s ) , G k ( x , λ ) := ⟨ F ( x ) , x ˉ k − x ⟩ + ⟨ G ( x ˉ k ) , λ ⟩ − ⟨ G ( x ) , λ ˉ k ⟩ .
The horizon initialization and update are unchanged, so Lemma 2 also gives η k s B k s = 1 \eta_k^{s}\mathcal{B}_k^{s}=1 η k s B k s = 1 for every middle trial in Algorithm 2. The convergence analysis follows similar inner-to-outer arguments as for PFAOS, with additional terms arising from the dual updates. Given this similarity, we defer the proofs of the results in this and the next subsection to Appendix A to streamline the presentation.
Proposition 4. Fix any outer iteration k ≥ 1 k \ge1 k ≥ 1 and its middle trial 1 ≤ s ≤ S k 1 \le s \le S_k 1 ≤ s ≤ S k . For any x ∈ X x \in X x ∈ X and vector λ ∈ R + m \lambda\in\mathbb{R}_{+}^{m} λ ∈ R + m , the iterates generated by Algorithm 2 guarantee
B k s ⟨ F ( x ) , x ^ k s − x ⟩ ≤ B k s + C k s + D k s − ∑ t = 1 T k s 1 M k t , s ⟨ A k t , s , x k t , s − x ⟩ , (8) \mathcal{B}_k^{s}\langle F(x),\hat{x}_k^{s}-x\rangle\le\mathcal{B}_k^{s}+C_k^{s}+D_k^{s}-\sum_{t=1}^{T_k^{s}}\frac{1}{M_k^{t,s}}\langle A_k^{t,s},x_k^{t,s}-x\rangle, \tag*{(8)} B k s ⟨ F ( x ) , x ^ k s − x ⟩ ≤ B k s + C k s + D k s − t = 1 ∑ T k s M k t , s 1 ⟨ A k t , s , x k t , s − x ⟩ , (8) where A k t , s A_k^{t,s} A k t , s is the dual contribution to the primal objective: A k 1 , s = J ( x k s ) T λ k 0 , s + θ k 1 , s J ( x k − 1 s ) T ( λ k 0 , s − λ k − 1 , s ) A_k^{1,s}=J(x_k^{s})^{\mathsf{T}}\lambda_k^{0,s}+\theta_k^{1,s}J(x_{k-1}^{s})^{\mathsf{T}}(\lambda_k^{0,s}-\lambda_k^{-1,s}) A k 1 , s = J ( x k s ) T λ k 0 , s + θ k 1 , s J ( x k − 1 s ) T ( λ k 0 , s − λ k − 1 , s ) and A k t , s = J ( x k s ) T λ k t , s A_k^{t,s}=J(x_k^{s})^{\mathsf{T}}\lambda_k^{t,s} A k t , s = J ( x k s ) T λ k t , s , for t ≥ 2 t\ge2 t ≥ 2 and
B k s : = 1 M k s ⟨ Δ k T k s , s , x k s − x ⟩ − θ k 1 , s M k 1 , s ⟨ Δ k 0 , s , x k − 1 − x ⟩ + p k 1 , s 2 M k 1 , s ( ∥ x − x k − 1 ∥ 2 + ∥ λ − λ k − 1 ∥ 2 ) − η k s + p k T k s , s 2 M k s ( ∥ x − x k s ∥ 2 + ∥ λ − λ k s ∥ 2 ) B_k^{s}:=\frac{1}{M_k^{s}}\langle\Delta_k^{T_k^{s},s},x_k^{s}-x\rangle-\frac{\theta_k^{1,s}}{M_k^{1,s}}\langle\Delta_k^{0,s},x_{k-1}-x\rangle+\frac{p_k^{1,s}}{2M_k^{1,s}}(\|x-x_{k-1}\|^2+\|\lambda-\lambda_{k-1}\|^2)-\frac{\eta_k^{s}+p_k^{T_k^{s},s}}{2M_k^{s}}(\|x-x_k^{s}\|^2+\|\lambda-\lambda_k^{s}\|^2) B k s := M k s 1 ⟨ Δ k T k s , s , x k s − x ⟩ − M k 1 , s θ k 1 , s ⟨ Δ k 0 , s , x k − 1 − x ⟩ + 2 M k 1 , s p k 1 , s ( ∥ x − x k − 1 ∥ 2 + ∥ λ − λ k − 1 ∥ 2 ) − 2 M k s η k s + p k T k s , s ( ∥ x − x k s ∥ 2 + ∥ λ − λ k s ∥ 2 ) C k s : = θ k 1 , s M k 1 , s ∥ Δ k 0 , s ∥ ∥ x k 1 , s − x k − 1 ∥ − p k 1 , s 6 M k 1 , s ∥ x k 1 , s − x k − 1 ∥ 2 − p k T k s , s 6 M k T k s , s ∥ x k s − x k T k s − 1 , s ∥ 2 − ∑ t = 1 T k s p k t , s 6 M k t , s ∥ x k t , s − x k t − 1 , s ∥ 2 C_k^{s}:=\frac{\theta_k^{1,s}}{M_k^{1,s}}\|\Delta_k^{0,s}\|\|x_k^{1,s}-x_{k-1}\|-\frac{p_k^{1,s}}{6M_k^{1,s}}\|x_k^{1,s}-x_{k-1}\|^2-\frac{p_k^{T_k^{s},s}}{6M_k^{T_k^{s},s}}\|x_k^{s}-x_k^{T_k^{s}-1,s}\|^2-\sum_{t=1}^{T_k^{s}}\frac{p_k^{t,s}}{6M_k^{t,s}}\|x_k^{t,s}-x_k^{t-1,s}\|^2 C k s := M k 1 , s θ k 1 , s ∥ Δ k 0 , s ∥∥ x k 1 , s − x k − 1 ∥ − 6 M k 1 , s p k 1 , s ∥ x k 1 , s − x k − 1 ∥ 2 − 6 M k T k s , s p k T k s , s ∥ x k s − x k T k s − 1 , s ∥ 2 − t = 1 ∑ T k s 6 M k t , s p k t , s ∥ x k t , s − x k t − 1 , s ∥ 2 D k s : = 1 2 ( ∥ x − x k − 1 ∥ 2 + ∥ λ − λ k − 1 ∥ 2 − ∥ x ^ k s − x k − 1 ∥ 2 ) + ∑ t = 1 T k s ( 1 M k t ⟨ ξ k s ( x k t , s ) , λ k t , s − λ ⟩ − p k t , s 2 M k t , s ∥ λ k t , s − λ k t − 1 , s ∥ 2 ) . D_k^{s}:=\frac{1}{2}(\|x-x_{k-1}\|^2+\|\lambda-\lambda_{k-1}\|^2-\|\hat{x}_k^{s}-x_{k-1}\|^2)+\sum_{t=1}^{T_k^{s}}\left(\frac{1}{M_k^{t}}\langle\xi_k^{s}(x_k^{t,s}),\lambda_k^{t,s}-\lambda\rangle-\frac{p_k^{t,s}}{2M_k^{t,s}}\|\lambda_k^{t,s}-\lambda_k^{t-1,s}\|^2\right). D k s := 2 1 ( ∥ x − x k − 1 ∥ 2 + ∥ λ − λ k − 1 ∥ 2 − ∥ x ^ k s − x k − 1 ∥ 2 ) + t = 1 ∑ T k s ( M k t 1 ⟨ ξ k s ( x k t , s ) , λ k t , s − λ ⟩ − 2 M k t , s p k t , s ∥ λ k t , s − λ k t − 1 , s ∥ 2 ) .
Combining the conclusion of Proposition 4 at s = S k s=S_k s = S k with the middle-loop acceptance condition at line 9 of Algorithm 2 yields the following one-step bound on the outer primal–dual gap.
Proposition 5. For k ≥ 1 k \ge1 k ≥ 1 , x ∈ X x \in X x ∈ X , and λ ∈ R + m \lambda\in\mathbb{R}_{+}^{m} λ ∈ R + m , the iterates generated by Algorithm 2 satisfy
G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) ≤ γ k S k B k S k ( E k + F k + R k ′ ( λ ) ) , (9) G_k(x,\lambda)-(1-\gamma_k^{S_k})G_{k-1}(x,\lambda)\le\frac{\gamma_k^{S_k}}{\mathcal{B}_k^{S_k}}(E_k+F_k+R_k'(\lambda)), \tag*{(9)} G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) ≤ B k S k γ k S k ( E k + F k + R k ′ ( λ )) , (9) where R k ′ ( λ ) : = 1 2 ( ∥ λ ∥ Λ − 1 ) ∥ x ^ k − x k − 1 ∥ 2 R_k'(\lambda):=\frac{1}{2}\left(\frac{\|\lambda\|}{\Lambda}-1\right)\|\hat{x}_k-x_{k-1}\|^2 R k ′ ( λ ) := 2 1 ( Λ ∥ λ ∥ − 1 ) ∥ x ^ k − x k − 1 ∥ 2 and
E k : = 1 M k S k ⟨ Δ k T k S k , S k , x k − x ⟩ − θ k 1 , S k M k 1 , S k ⟨ Δ k 0 , S k , x k − 1 − x ⟩ E_k:=\frac{1}{M_k^{S_k}}\langle\Delta_k^{T_k^{S_k},S_k},x_k-x\rangle-\frac{\theta_k^{1,S_k}}{M_k^{1,S_k}}\langle\Delta_k^{0,S_k},x_{k-1}-x\rangle E k := M k S k 1 ⟨ Δ k T k S k , S k , x k − x ⟩ − M k 1 , S k θ k 1 , S k ⟨ Δ k 0 , S k , x k − 1 − x ⟩ + 1 M k S k ⟨ J ( x k S k ) ( x k − x ) , λ k − λ k T k S k − 1 , S k ⟩ − θ k 1 , S k M k 1 , S k ⟨ J ( x k − 1 S k − 1 ) ( x k − 1 − x ) , λ k − 1 − λ k − 1 T k S k − 1 − 1 , S k − 1 ⟩ \quad+\frac{1}{M_k^{S_k}}\langle J(x_k^{S_k})(x_k-x),\lambda_k-\lambda_k^{T_k^{S_k}-1,S_k}\rangle-\frac{\theta_k^{1,S_k}}{M_k^{1,S_k}}\langle J(x_{k-1}^{S_k-1})(x_{k-1}-x),\lambda_{k-1}-\lambda_{k-1}^{T_k^{S_k-1}-1,S_k-1}\rangle + M k S k 1 ⟨ J ( x k S k ) ( x k − x ) , λ k − λ k T k S k − 1 , S k ⟩ − M k 1 , S k θ k 1 , S k ⟨ J ( x k − 1 S k − 1 ) ( x k − 1 − x ) , λ k − 1 − λ k − 1 T k S k − 1 − 1 , S k − 1 ⟩ + 1 2 ( 1 + p k 1 , S k M k 1 , S k ) ( ∥ x − x k − 1 ∥ 2 + ∥ λ − λ k − 1 ∥ 2 ) − η k S k + p k T k S k , S k 2 M k S k ( ∥ x − x k ∥ 2 + ∥ λ − λ k ∥ 2 ) , \quad+\frac{1}{2}\left(1+\frac{p_k^{1,S_k}}{M_k^{1,S_k}}\right)(\|x-x_{k-1}\|^2+\|\lambda-\lambda_{k-1}\|^2)-\frac{\eta_k^{S_k}+p_k^{T_k^{S_k},S_k}}{2M_k^{S_k}}(\|x-x_k\|^2+\|\lambda-\lambda_k\|^2), + 2 1 ( 1 + M k 1 , S k p k 1 , S k ) ( ∥ x − x k − 1 ∥ 2 + ∥ λ − λ k − 1 ∥ 2 ) − 2 M k S k η k S k + p k T k S k , S k ( ∥ x − x k ∥ 2 + ∥ λ − λ k ∥ 2 ) , F k : = θ k 1 , S k M k 1 , S k ∥ Δ k 0 , S k ∥ ∥ x k 1 , S k − x k − 1 ∥ + θ k 1 , S k M k 1 , S k ∥ J ( x k − 1 S k − 1 ) T ( λ k − 1 − λ k 1 , S k ) ∥ ∥ x k 1 , S k − x k − 1 ∥ F_k:=\frac{\theta_k^{1,S_k}}{M_k^{1,S_k}}\|\Delta_k^{0,S_k}\|\|x_k^{1,S_k}-x_{k-1}\|+\frac{\theta_k^{1,S_k}}{M_k^{1,S_k}}\|J(x_{k-1}^{S_k-1})^{\mathsf{T}}(\lambda_{k-1}-\lambda_k^{1,S_k})\|\|x_k^{1,S_k}-x_{k-1}\| F k := M k 1 , S k θ k 1 , S k ∥ Δ k 0 , S k ∥∥ x k 1 , S k − x k − 1 ∥ + M k 1 , S k θ k 1 , S k ∥ J ( x k − 1 S k − 1 ) T ( λ k − 1 − λ k 1 , S k ) ∥∥ x k 1 , S k − x k − 1 ∥ − p k 1 , S k 3 M k 1 , S k ∥ x k 1 , S k − x k − 1 ∥ 2 − p k T k S k , S k 6 M k T k S k , S k ∥ x k − x k T k S k − 1 , S k ∥ 2 − p k T k S k , S k 2 M k S k ∥ λ k − λ k T k S k − 1 , S k ∥ 2 . \quad-\frac{p_k^{1,S_k}}{3M_k^{1,S_k}}\|x_k^{1,S_k}-x_{k-1}\|^2-\frac{p_k^{T_k^{S_k},S_k}}{6M_k^{T_k^{S_k},S_k}}\|x_k-x_k^{T_k^{S_k}-1,S_k}\|^2-\frac{p_k^{T_k^{S_k},S_k}}{2M_k^{S_k}}\|\lambda_k-\lambda_k^{T_k^{S_k}-1,S_k}\|^2. − 3 M k 1 , S k p k 1 , S k ∥ x k 1 , S k − x k − 1 ∥ 2 − 6 M k T k S k , S k p k T k S k , S k ∥ x k − x k T k S k − 1 , S k ∥ 2 − 2 M k S k p k T k S k , S k ∥ λ k − λ k T k S k − 1 , S k ∥ 2 .
With the help of Proposition 5, Theorem 2 next presents a global primal–dual gap bound.
Theorem 2. For every N ≥ 1 N \ge1 N ≥ 1 , x ∈ X x \in X x ∈ X , and λ ∈ R + m \lambda\in\mathbb{R}_{+}^{m} λ ∈ R + m , the iterates generated by Algorithm 2 satisfy
G N ( x , λ ) ≤ γ N S N 2 ( 4 ∥ x − x 0 ∥ 2 + 4 ∥ λ − λ 0 ∥ 2 + ( ∥ λ ∥ Λ − 1 ) ∑ k = 1 N ∥ x ^ k − x k − 1 ∥ 2 ) . (10) G_N(x,\lambda)\le\frac{\gamma_N^{S_N}}{2}\left(4\|x-x_0\|^2+4\|\lambda-\lambda_0\|^2+\left(\frac{\|\lambda\|}{\Lambda}-1\right)\sum_{k=1}^{N}\|\hat{x}_k-x_{k-1}\|^2\right). \tag*{(10)} G N ( x , λ ) ≤ 2 γ N S N ( 4∥ x − x 0 ∥ 2 + 4∥ λ − λ 0 ∥ 2 + ( Λ ∥ λ ∥ − 1 ) k = 1 ∑ N ∥ x ^ k − x k − 1 ∥ 2 ) . (10) In particular, if Λ ≥ ∥ λ ∥ \Lambda\ge\|\lambda\| Λ ≥ ∥ λ ∥ , then G N ( x , λ ) ≤ 2 Γ N S N ( ∥ x − x 0 ∥ 2 + ∥ λ − λ 0 ∥ 2 ) G_N(x,\lambda)\le2\Gamma_N^{S_N}(\|x-x_0\|^2+\|\lambda-\lambda_0\|^2) G N ( x , λ ) ≤ 2 Γ N S N ( ∥ x − x 0 ∥ 2 + ∥ λ − λ 0 ∥ 2 ) .
Convergence Rate and Evaluation Complexity of MC-PFAOS
The preceding subsection provides an upper bound on the primal–dual gap in terms of Γ N S N \Gamma^{S_N}_N Γ N S N . As in § 2.3 , we first bound Γ N S N \Gamma^{S_N}_N Γ N S N and then derive the evaluation complexities of MC-PFAOS.
Lemma 4. Algorithm 2 guarantees that every middle-loop line search terminates after finitely many trials and that η k S k / γ k S k ≤ 4 Λ L \eta^{S_k}_k/\gamma^{S_k}_k \le4\Lambda L η k S k / γ k S k ≤ 4Λ L , and Γ k S k ≤ 16 Λ L / ( k + 1 ) 2 \Gamma^{S_k}_k \le16\Lambda L/(k+1)^2 Γ k S k ≤ 16Λ L / ( k + 1 ) 2 , ∀ k ≥ 1 \forall k \ge1 ∀ k ≥ 1 ,
Combining Lemma 4 with Theorem 2 yields an explicit primal–dual gap rate. We next translate it into bounds on the weak VI gap and constraint violation in Corollary 2.
Corollary 2. Let ( x ∗ , λ ∗ ) (x^*,\lambda^*) ( x ∗ , λ ∗ ) satisfy (3). For every N ≥ 1 N \ge1 N ≥ 1 , we have
sup x ∈ X ~ ⟨ F ( x ) , x ˉ N − x ⟩ ≤ 2 Γ N S N D X 2 ≤ 32 Λ L D X 2 ( N + 1 ) 2 , and ( Λ − ∥ λ ∗ ∥ ) ∥ [ G ( x ˉ N ) ] + ∥ ≤ 2 Γ N S N ( D X 2 + Λ 2 ) ≤ 32 Λ L ( D X 2 + Λ 2 ) ( N + 1 ) 2 . \sup_{x\in\widetilde{X}}\langle F(x),\bar{x}_N-x\rangle\le2\Gamma^{S_N}_N D_X^2 \le\frac{32\Lambda L D_X^2}{(N+1)^2},\quad\text{and}\quad(\Lambda-\|\lambda^*\|)\|[G(\bar{x}_N)]_+\| \le2\Gamma^{S_N}_N(D_X^2+\Lambda^2)\le\frac{32\Lambda L(D_X^2+\Lambda^2)}{(N+1)^2}. x ∈ X sup ⟨ F ( x ) , x ˉ N − x ⟩ ≤ 2 Γ N S N D X 2 ≤ ( N + 1 ) 2 32Λ L D X 2 , and ( Λ − ∥ λ ∗ ∥ ) ∥ [ G ( x ˉ N ) ] + ∥ ≤ 2 Γ N S N ( D X 2 + Λ 2 ) ≤ ( N + 1 ) 2 32Λ L ( D X 2 + Λ 2 ) . *In particular, if Λ ≥ ∥ λ ∗ ∥ + 1 \Lambda\ge\|\lambda^*\|+1 Λ ≥ ∥ λ ∗ ∥ + 1 , then x ˉ N \bar{x}_N x ˉ N is an ε \varepsilon ε -approximate solution of (2) whenever 2 Γ N S N ( D X 2 + Λ 2 ) ≤ ε 2\Gamma^{S_N}_N(D_X^2+\Lambda^2)\le\varepsilon 2 Γ N S N ( D X 2 + Λ 2 ) ≤ ε , which is guaranteed by N + 1 ≥ 32 Λ L ( D X 2 + Λ 2 ) ε N+1\ge\sqrt{\frac{32\Lambda L(D_X^2+\Lambda^2)}{\varepsilon}} N + 1 ≥ ε 32Λ L ( D X 2 + Λ 2 ) .
Corollary 2 gives a sufficient number of outer iterations to obtain an ε \varepsilon ε -approximate solution. Using this result, Proposition 6 counts the number of Jacobian and operator evaluations.
Proposition 6. Suppose Λ ≥ ∥ λ ∗ ∥ + 1 \Lambda\ge\|\lambda^*\|+1 Λ ≥ ∥ λ ∗ ∥ + 1 . For any ε > 0 \varepsilon>0 ε > 0 , Algorithm 2 obtains an ε \varepsilon ε -approximate solution of (2) using at most 3 + 2 32 Λ L ( D X 2 + Λ 2 ) ε + ⌈ log 2 2 L L 0 ⌉ 3+2\sqrt{\frac{32\Lambda L(D_X^2+\Lambda^2)}{\varepsilon}}+\left\lceil\log_2\frac{2L}{L_0}\right\rceil 3 + 2 ε 32Λ L ( D X 2 + Λ 2 ) + ⌈ log 2 L 0 2 L ⌉ evaluations of J J J and 1 + 4 M ‾ M C η 0 S 0 + 8 M ‾ M C ( D X 2 + Λ 2 ) ε + ⌈ log 2 M ‾ M C M 0 ⌉ 1+\frac{4\overline{M}_{\mathrm{MC}}}{\eta^{S_0}_0}+\frac{8\overline{M}_{\mathrm{MC}}(D_X^2+\Lambda^2)}{\varepsilon}+\left\lceil\log_2\frac{\overline{M}_{\mathrm{MC}}}{M_0}\right\rceil 1 + η 0 S 0 4 M MC + ε 8 M MC ( D X 2 + Λ 2 ) + ⌈ log 2 M 0 M MC ⌉ evaluations of F F F , where M ‾ M C : = 2 max { 2 Λ L , M , max x ∈ X ∥ J ( x ) ∥ } \overline{M}_{\mathrm{MC}}:=2\max\{2\Lambda L,M,\max_{x\in X}\|J(x)\|\} M MC := 2 max { 2Λ L , M , max x ∈ X ∥ J ( x ) ∥ } . These bounds include evaluations at initialization and in accepted and rejected line-search trials.
Provided Λ ≥ ∥ λ ∗ ∥ + 1 \Lambda\ge\|\lambda^*\|+1 Λ ≥ ∥ λ ∗ ∥ + 1 , Proposition 6 shows that MC-PFAOS requires at most O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) Jacobian evaluations and O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator evaluations for obtaining an ε \varepsilon ε -approximate solution. Three remarks apply here. First, no prior bound on ∥ J ( x ) ∥ \|J(x)\| ∥ J ( x ) ∥ is required by the algorithm. Second, when M ≥ max { 2 Λ L , max x ∈ X ∥ J ( x ) ∥ } M\ge\max\{2\Lambda L,\max_{x\in X}\|J(x)\|\} M ≥ max { 2Λ L , max x ∈ X ∥ J ( x ) ∥ } , the M ‾ M C ( D X 2 + Λ 2 ) / ε \overline{M}_{\mathrm{MC}}(D_X^2+\Lambda^2)/\varepsilon M MC ( D X 2 + Λ 2 ) / ε term in the operator bound becomes O ( M ( D X 2 + Λ 2 ) / ε ) O(M(D_X^2+\Lambda^2)/\varepsilon) O ( M ( D X 2 + Λ 2 ) / ε ) . This condition is not required for the preceding convergence or complexity results. Third, the term M ‾ M C / η 0 S 0 \overline{M}_{\mathrm{MC}}/\eta^{S_0}_0 M MC / η 0 S 0 is absorbed into O ( M ‾ M C ( D X 2 + Λ 2 ) / ε ) O(\overline{M}_{\mathrm{MC}}(D_X^2+\Lambda^2)/\varepsilon) O ( M MC ( D X 2 + Λ 2 ) / ε ) when η 0 S 0 ≳ ε / ( D X 2 + Λ 2 ) \eta^{S_0}_0\gtrsim\varepsilon/(D_X^2+\Lambda^2) η 0 S 0 ≳ ε / ( D X 2 + Λ 2 ) . Such initialization restriction of η 0 S 0 \eta^{S_0}_0 η 0 S 0 is removed in § 4 through a modified search at k = 1 k=1 k = 1 .
Modified First-Iteration Parameter Search
The operator-complexity bounds in Propositions 3 and 6 contain the terms M ‾ / η 0 S 0 \overline{M}/\eta^{S_0}_0 M / η 0 S 0 and M ‾ M C / η 0 S 0 \overline{M}_{\mathrm{MC}}/\eta^{S_0}_0 M MC / η 0 S 0 , respectively, which can be arbitrarily large when the initial estimate η 0 S 0 \eta^{S_0}_0 η 0 S 0 is small. Absorbing these terms directly into the desired O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator complexity bounds requires, respectively, η 0 S 0 ≳ ε / D X 2 \eta^{S_0}_0\gtrsim\varepsilon/D_X^2 η 0 S 0 ≳ ε / D X 2 and η 0 S 0 ≳ ε / ( D X 2 + Λ 2 ) \eta^{S_0}_0\gtrsim\varepsilon/(D_X^2+\Lambda^2) η 0 S 0 ≳ ε / ( D X 2 + Λ 2 ) . However, these conditions are not guaranteed by the initialization η 0 S 0 = 2 Λ L 0 \eta_0^{S_0}=2\Lambda L_0 η 0 S 0 = 2Λ L 0 with 0 < L 0 ≤ L 0<L_0\le L 0 < L 0 ≤ L . This section modifies the search order for η 1 s \eta_1^s η 1 s at k = 1 k=1 k = 1 in Algorithms 1 and 2 to achieve the desired O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator complexity without these initialization requirements.
We retain the names PFAOS and MC-PFAOS because it modifies only the search order of the first outer iteration.
First-Iteration Modifications
Algorithms 3 and 4 replace the k = 1 k=1 k = 1 iteration of Algorithms 1 and 2, respectively. At s = 1 s=1 s = 1 , an upward search doubles the operator and curvature estimates together from M 0 = η 0 S 0 M_0=\eta_0^{S_0} M 0 = η 0 S 0 until all inner and middle acceptance conditions hold. For s ≥ 2 s\ge2 s ≥ 2 , a downward search halves η 1 s \eta_1^s η 1 s between middle trials while retaining the original inner-loop rules. It returns x ˉ 1 s \bar{x}_1^s x ˉ 1 s if the s s s -th trial is accepted and satisfies the accuracy certificates of 3 2 η 1 s D X 2 ≤ ε \frac{3}{2}\eta_1^sD_X^2\le\varepsilon 2 3 η 1 s D X 2 ≤ ε or 2 η 1 s ( D X 2 + Λ 2 ) ≤ ε 2\eta_1^s(D_X^2+\Lambda^2)\le\varepsilon 2 η 1 s ( D X 2 + Λ 2 ) ≤ ε . If a downward trial fails the middle test, then its preceding trial is retained and the original algorithm resumes at k = 2 k=2 k = 2 . Here, each upward or downward trial starts from x 1 0 , s = x 1 − 1 , s = x 0 x_1^{0,s}=x_1^{-1,s}=x_0 x 1 0 , s = x 1 − 1 , s = x 0 , with λ 1 0 , s = λ 1 − 1 , s = 0 \lambda_1^{0,s}=\lambda_1^{-1,s}=0 λ 1 0 , s = λ 1 − 1 , s = 0 for MC-PFAOS. Since γ 1 s = 1 \gamma_1^s=1 γ 1 s = 1 and x 1 s = x 0 x_1^s=x_0 x 1 s = x 0 throughout both searches, one evaluation of ∇ g ( x 0 ) \nabla g(x_0) ∇ g ( x 0 ) or J ( x 0 ) J(x_0) J ( x 0 ) suffices.
Algorithm 3 Modified first outer iteration for PFAOS
Same initialization and input as in Algorithm 1
Upward search: Set k = 1 k=1 k = 1 , s = 1 s=1 s = 1 ; Run lines 4–8 in Algorithm 1 with fixed T 1 1 , 1 = 1 T_1^{1,1}=1 T 1 1 , 1 = 1 and η 1 1 = M 1 1 , 1 = 2 q M 0 \eta_1^1=M_1^{1,1}=2^qM_0 η 1 1 = M 1 1 , 1 = 2 q M 0 , where q ≥ 0 q\ge0 q ≥ 0 is the smallest integer such that both ∥ F ( x 1 1 , 1 ) − F ( x 0 ) ∥ ≤ M 1 1 , 1 ∥ x 1 1 , 1 − x 0 ∥ \|F(x_1^{1,1})-F(x_0)\|\le M_1^{1,1}\|x_1^{1,1}-x_0\| ∥ F ( x 1 1 , 1 ) − F ( x 0 ) ∥ ≤ M 1 1 , 1 ∥ x 1 1 , 1 − x 0 ∥ and g ( x ˉ 1 1 ) − g ( x 0 ) − ⟨ ∇ g ( x 0 ) , x ˉ 1 1 − x 0 ⟩ ≤ η 1 1 2 Λ ∥ x ˉ 1 1 − x 0 ∥ 2 g(\bar{x}_1^1)-g(x_0)-\langle\nabla g(x_0),\bar{x}_1^1-x_0\rangle\le\frac{\eta_1^1}{2\Lambda}\|\bar{x}_1^1-x_0\|^2 g ( x ˉ 1 1 ) − g ( x 0 ) − ⟨ ∇ g ( x 0 ) , x ˉ 1 1 − x 0 ⟩ ≤ 2Λ η 1 1 ∥ x ˉ 1 1 − x 0 ∥ 2 hold
If 3 2 η 1 1 D X 2 ≤ ε \frac{3}{2}\eta_1^1D_X^2\le\varepsilon 2 3 η 1 1 D X 2 ≤ ε , then set S 1 = 1 S_1=1 S 1 = 1 , M 1 = M 1 S 1 M_1=M_1^{S_1} M 1 = M 1 S 1 , x 1 = x 1 S 1 x_1=x_1^{S_1} x 1 = x 1 S 1 , x ^ 1 = x ^ 1 S 1 \hat{x}_1=\hat{x}_1^{S_1} x ^ 1 = x ^ 1 S 1 and output x ˉ 1 = x ˉ 1 S 1 \bar{x}_1=\bar{x}_1^{S_1} x ˉ 1 = x ˉ 1 S 1 ; Else set s = 2 s=2 s = 2
Downward search: Run line 4–8 in Algorithm 1 with η 1 s = η 1 s − 1 / 2 \eta_1^s=\eta_1^{s-1}/2 η 1 s = η 1 s − 1 /2
If the middle test condition g ( x ˉ 1 s ) ≤ g ( x 0 ) + ⟨ ∇ g ( x 0 ) , x ˉ 1 s − x 0 ⟩ + η 1 s 2 Λ ∥ x ˉ 1 s − x 0 ∥ 2 g(\bar{x}_1^s)\le g(x_0)+\langle\nabla g(x_0),\bar{x}_1^s-x_0\rangle+\frac{\eta_1^s}{2\Lambda}\|\bar{x}_1^s-x_0\|^2 g ( x ˉ 1 s ) ≤ g ( x 0 ) + ⟨ ∇ g ( x 0 ) , x ˉ 1 s − x 0 ⟩ + 2Λ η 1 s ∥ x ˉ 1 s − x 0 ∥ 2 does not hold, then set S 1 = s − 1 S_1=s-1 S 1 = s − 1 , M 1 = M 1 S 1 M_1=M_1^{S_1} M 1 = M 1 S 1 , x 1 = x 1 S 1 x_1=x_1^{S_1} x 1 = x 1 S 1 , x ^ 1 = x ^ 1 S 1 \hat{x}_1=\hat{x}_1^{S_1} x ^ 1 = x ^ 1 S 1 , x ˉ 1 = x ˉ 1 S 1 \bar{x}_1=\bar{x}_1^{S_1} x ˉ 1 = x ˉ 1 S 1 and resume Algorithm 1 at k = 2 k=2 k = 2 ; Else if 3 2 η 1 s D X 2 ≤ ε \frac{3}{2}\eta_1^sD_X^2\le\varepsilon 2 3 η 1 s D X 2 ≤ ε then set S 1 = s S_1=s S 1 = s , M 1 = M 1 S 1 M_1=M_1^{S_1} M 1 = M 1 S 1 , x 1 = x 1 S 1 x_1=x_1^{S_1} x 1 = x 1 S 1 , x ^ 1 = x ^ 1 S 1 \hat{x}_1=\hat{x}_1^{S_1} x ^ 1 = x ^ 1 S 1 and output x ˉ 1 = x ˉ 1 S 1 \bar{x}_1=\bar{x}_1^{S_1} x ˉ 1 = x ˉ 1 S 1 ; Else set s ← s + 1 s\leftarrow s+1 s ← s + 1 and go to line 4
Algorithm 4 Modified first outer iteration for MC-PFAOS
Same initialization and input as in Algorithm 2
Upward search: Set k = 1 k=1 k = 1 , s = 1 s=1 s = 1 ; Run lines 4–8 in Algorithm 2 with fixed T 1 1 , 1 = 1 T_1^{1,1}=1 T 1 1 , 1 = 1 and η 1 1 = M 1 1 , 1 = 2 q M 0 \eta_1^1=M_1^{1,1}=2^qM_0 η 1 1 = M 1 1 , 1 = 2 q M 0 , where q ≥ 0 q\ge0 q ≥ 0 is the smallest integer such that ∥ F ( x 1 1 , 1 ) − F ( x 0 ) ∥ ≤ M 1 1 , 1 ∥ x 1 1 , 1 − x 0 ∥ \|F(x_1^{1,1})-F(x_0)\|\le M_1^{1,1}\|x_1^{1,1}-x_0\| ∥ F ( x 1 1 , 1 ) − F ( x 0 ) ∥ ≤ M 1 1 , 1 ∥ x 1 1 , 1 − x 0 ∥ , ∥ J ( x 0 ) ⊤ ( λ 1 1 , 1 − λ 0 ) ∥ ≤ M 1 1 , 1 ∥ λ 1 1 , 1 − λ 0 ∥ \|J(x_0)^\top(\lambda_1^{1,1}-\lambda_0)\|\le M_1^{1,1}\|\lambda_1^{1,1}-\lambda_0\| ∥ J ( x 0 ) ⊤ ( λ 1 1 , 1 − λ 0 ) ∥ ≤ M 1 1 , 1 ∥ λ 1 1 , 1 − λ 0 ∥ and ∥ G ( x ˉ 1 1 ) − G ( x 0 ) − J ( x 0 ) ( x ˉ 1 1 − x 0 ) ∥ ≤ η 1 1 2 Λ ∥ x ˉ 1 1 − x 0 ∥ 2 \|G(\bar{x}_1^1)-G(x_0)-J(x_0)(\bar{x}_1^1-x_0)\|\le\frac{\eta_1^1}{2\Lambda}\|\bar{x}_1^1-x_0\|^2 ∥ G ( x ˉ 1 1 ) − G ( x 0 ) − J ( x 0 ) ( x ˉ 1 1 − x 0 ) ∥ ≤ 2Λ η 1 1 ∥ x ˉ 1 1 − x 0 ∥ 2 hold
If 2 η 1 1 ( D X 2 + Λ 2 ) ≤ ε 2\eta_1^1(D_X^2+\Lambda^2)\le\varepsilon 2 η 1 1 ( D X 2 + Λ 2 ) ≤ ε , then set S 1 = 1 S_1=1 S 1 = 1 , M 1 = M 1 S 1 M_1=M_1^{S_1} M 1 = M 1 S 1 , λ 1 = λ 1 S 1 \lambda_1=\lambda_1^{S_1} λ 1 = λ 1 S 1 , x 1 = x 1 S 1 x_1=x_1^{S_1} x 1 = x 1 S 1 , x ^ 1 = x ^ 1 S 1 \hat{x}_1=\hat{x}_1^{S_1} x ^ 1 = x ^ 1 S 1 and output x ˉ 1 = x ˉ 1 S 1 \bar{x}_1=\bar{x}_1^{S_1} x ˉ 1 = x ˉ 1 S 1 ; Else set s = 2 s=2 s = 2
Downward search: Run line 4–8 in Algorithm 2 with η 1 s = η 1 s − 1 / 2 \eta_1^s=\eta_1^{s-1}/2 η 1 s = η 1 s − 1 /2
If the middle test condition ∥ G ( x ˉ 1 s ) − G ( x 0 ) − J ( x 0 ) ( x ˉ 1 s − x 0 ) ∥ ≤ η 1 s 2 Λ ∥ x ˉ 1 s − x 0 ∥ 2 \|G(\bar{x}_1^s)-G(x_0)-J(x_0)(\bar{x}_1^s-x_0)\|\le\frac{\eta_1^s}{2\Lambda}\|\bar{x}_1^s-x_0\|^2 ∥ G ( x ˉ 1 s ) − G ( x 0 ) − J ( x 0 ) ( x ˉ 1 s − x 0 ) ∥ ≤ 2Λ η 1 s ∥ x ˉ 1 s − x 0 ∥ 2 does not hold, then set S 1 = s − 1 S_1=s-1 S 1 = s − 1 , M 1 = M 1 S 1 M_1=M_1^{S_1} M 1 = M 1 S 1 , λ 1 = λ 1 S 1 \lambda_1=\lambda_1^{S_1} λ 1 = λ 1 S 1 , x 1 = x 1 S 1 x_1=x_1^{S_1} x 1 = x 1 S 1 , x ^ 1 = x ^ 1 S 1 \hat{x}_1=\hat{x}_1^{S_1} x ^ 1 = x ^ 1 S 1 , x ˉ 1 = x ˉ 1 S 1 \bar{x}_1=\bar{x}_1^{S_1} x ˉ 1 = x ˉ 1 S 1 and resume Algorithm 2 at k = 2 k=2 k = 2 ; Else if 2 η 1 s ( D X 2 + Λ 2 ) ≤ ε 2\eta_1^s(D_X^2+\Lambda^2)\le\varepsilon 2 η 1 s ( D X 2 + Λ 2 ) ≤ ε , then set S 1 = s S_1=s S 1 = s , M 1 = M 1 S 1 M_1=M_1^{S_1} M 1 = M 1 S 1 , λ 1 = λ 1 S 1 \lambda_1=\lambda_1^{S_1} λ 1 = λ 1 S 1 , x 1 = x 1 S 1 x_1=x_1^{S_1} x 1 = x 1 S 1 , x ^ 1 = x ^ 1 S 1 \hat{x}_1=\hat{x}_1^{S_1} x ^ 1 = x ^ 1 S 1 and output x ˉ 1 = x ˉ 1 S 1 \bar{x}_1=\bar{x}_1^{S_1} x ˉ 1 = x ˉ 1 S 1 ; Else set s ← s + 1 s\leftarrow s+1 s ← s + 1 and go to line 4
Termination and Convergence Guarantees
We first establish the finite termination of Algorithms 3 and 4, and estimate the evaluation bounds of the modified first outer iteration in Lemma 5.
Lemma 5. Algorithms 3 and 4 terminate after finitely many trials. If it continues to k = 2 k=2 k = 2 , then η 1 S 1 < 2 Λ L \eta_{1}^{S_{1}}<2\Lambda L η 1 S 1 < 2Λ L . The first outer iteration requires one evaluation of ∇ g \nabla g ∇ g or J J J and at most 2 + 6 M ‾ D X 2 ε + ⌈ log 2 M ‾ M 0 ⌉ 2+\frac{6\overline{M}D_{X}^{2}}{\varepsilon}+\left\lceil\log_{2}\frac{\overline{M}}{M_{0}}\right\rceil 2 + ε 6 M D X 2 + ⌈ log 2 M 0 M ⌉ or 2 + 8 M ‾ M C ( D X 2 + Λ 2 ) ε + ⌈ log 2 M ‾ M C M 0 ⌉ 2+\frac{8\overline{M}_{\mathrm{MC}}(D_{X}^{2}+\Lambda^{2})}{\varepsilon}+\left\lceil\log_{2}\frac{\overline{M}_{\mathrm{MC}}}{M_{0}}\right\rceil 2 + ε 8 M MC ( D X 2 + Λ 2 ) + ⌈ log 2 M 0 M MC ⌉ evaluations of F F F for PFAOS and MC-PFAOS, respectively. Both bounds include evaluations at initialization and in accepted and rejected trials.
Proof: By the sufficient acceptance conditions and the doubling rule at s = 1 s=1 s = 1 , the upward search terminates with a common estimate at most M ‾ \overline{M} M or M ‾ M C \overline{M}_{\mathrm{MC}} M MC , respectively. For s ≥ 2 s\ge2 s ≥ 2 , halving η 1 s \eta_{1}^{s} η 1 s preserves M 1 t , s ≤ M ‾ M_{1}^{t,s}\le\overline{M} M 1 t , s ≤ M for PFAOS and M 1 t , s ≤ M ‾ M C M_{1}^{t,s}\le\overline{M}_{\mathrm{MC}} M 1 t , s ≤ M MC for MC-PFAOS by the arguments in Propositions 3 and 6, and ensures S 1 < ∞ S_{1}<\infty S 1 < ∞ , since each inner loop is finite and either a middle test fails or an accepted trial eventually satisfies the accuracy certificate. If the method continues to k = 2 k=2 k = 2 , the final middle trial s s s failed, so η 1 s < Λ L \eta_{1}^{s}<\Lambda L η 1 s < Λ L . Retaining S 1 = s − 1 S_{1}=s-1 S 1 = s − 1 therefore gives η 1 S 1 = 2 η 1 s < 2 Λ L \eta_{1}^{S_{1}}=2\eta_{1}^{s}<2\Lambda L η 1 S 1 = 2 η 1 s < 2Λ L for both methods. Since x 1 s = x 0 x_{1}^{s}=x_{0} x 1 s = x 0 throughout the search, one evaluation of ∇ g ( x 0 ) \nabla g(x_{0}) ∇ g ( x 0 ) or J ( x 0 ) J(x_{0}) J ( x 0 ) suffices. For the PFAOS operator count, let s s s be the final tested middle-trial index, including the rejected downward trial, if any. If s ≥ 2 s\ge2 s ≥ 2 , the preceding accepted trial did not satisfy the accuracy certificate, so η 1 s = η 1 s − 1 / 2 > ε / ( 3 D X 2 ) \eta_{1}^{s}=\eta_{1}^{s-1}/2>\varepsilon/(3D_{X}^{2}) η 1 s = η 1 s − 1 /2 > ε / ( 3 D X 2 ) . Using η 1 i β 1 i = 1 \eta_{1}^{i}\beta_{1}^{i}=1 η 1 i β 1 i = 1 and M 1 t , i ≤ M ‾ M_{1}^{t,i}\le\overline{M} M 1 t , i ≤ M gives ∑ i = 1 s T 1 i ≤ M ‾ ∑ i = 1 s 1 η 1 i < 2 M ‾ η 1 s < 6 M ‾ D X 2 ε \sum_{i=1}^{s}T_{1}^{i}\le\overline{M}\sum_{i=1}^{s}\frac{1}{\eta_{1}^{i}}<\frac{2\overline{M}}{\eta_{1}^{s}}<\frac{6\overline{M}D_{X}^{2}}{\varepsilon} ∑ i = 1 s T 1 i ≤ M ∑ i = 1 s η 1 i 1 < η 1 s 2 M < ε 6 M D X 2 . Here, T 1 1 = 1 T_{1}^{1}=1 T 1 1 = 1 counts only the accepted upward attempt. For s = 1 s=1 s = 1 , the sum equals one, so it is at most 1 + 6 M ‾ D X 2 / ε 1+6\overline{M}D_{X}^{2}/\varepsilon 1 + 6 M D X 2 / ε in either case. Each rejected upward attempt or inner backtracking trial doubles the nondecreasing operator estimate, so their total number is at most ⌈ log 2 ( M ‾ / M 0 ) ⌉ \left\lceil\log_{2}(\overline{M}/M_{0})\right\rceil ⌈ log 2 ( M / M 0 ) ⌉ . Adding these evaluations and F ( x 0 ) F(x_{0}) F ( x 0 ) to the completed-iteration count proves the PFAOS bound. For MC-PFAOS, the same argument uses M ‾ M C \overline{M}_{\mathrm{MC}} M MC and η 1 s > ε / [ 4 ( D X 2 + Λ 2 ) ] \eta_{1}^{s}>\varepsilon/[4(D_{X}^{2}+\Lambda^{2})] η 1 s > ε / [ 4 ( D X 2 + Λ 2 )] for s ≥ 2 s\ge2 s ≥ 2 , yielding the stated bound. □ \square □
Next, we establish in Lemma 6 the gap and parameter bounds for the modified methods.
Lemma 6. The bounds in Theorems 1 and 2 remain valid with the first-iteration modification in Algorithms 3 and 4. If Λ ≥ ∥ λ ∗ ∥ + 1 \Lambda\ge\lVert\lambda^{*}\rVert+1 Λ ≥ ∥ λ ∗ ∥ + 1 , then any point returned at k = 1 k=1 k = 1 is an ε \varepsilon ε -approximate solution of (2) . If the method continues to k = 2 k=2 k = 2 , then η k S k / γ k S k ≤ 4 Λ L \eta_{k}^{S_{k}}/\gamma_{k}^{S_{k}}\le4\Lambda L η k S k / γ k S k ≤ 4Λ L and Γ k S k ≤ 16 Λ L / ( k + 1 ) 2 \Gamma_{k}^{S_{k}}\le16\Lambda L/(k+1)^{2} Γ k S k ≤ 16Λ L / ( k + 1 ) 2 for k ≥ 1 k\ge1 k ≥ 1 .
Proof: Each retained trial satisfies the original inner and middle acceptance conditions and uses the original initialization, inner updates, and averaging rules. The invariant η 1 S 1 β 1 S 1 = 1 \eta_{1}^{S_{1}}\beta_{1}^{S_{1}}=1 η 1 S 1 β 1 S 1 = 1 holds because the accepted upward attempt has M 1 1 , 1 = η 1 1 M_{1}^{1,1}=\eta_{1}^{1} M 1 1 , 1 = η 1 1 and T 1 1 = 1 T_{1}^{1}=1 T 1 1 = 1 , while downward trials use the original horizon update. So, the arguments in Theorems 1 and 2 remain valid. Since Γ 1 S 1 = η 1 S 1 \Gamma_{1}^{S_{1}}=\eta_{1}^{S_{1}} Γ 1 S 1 = η 1 S 1 , the stopping tests at k = 1 k=1 k = 1 ensure the claimed accuracy by Corollaries 1 and 2. If the method continues to k = 2 k=2 k = 2 , Lemma 5 gives η 1 S 1 < 2 Λ L \eta_1^{S_1}<2\Lambda L η 1 S 1 < 2Λ L . Together with γ 1 S 1 = 1 \gamma_1^{S_1}=1 γ 1 S 1 = 1 , this provides the base case. Then induction and telescoping arguments in Lemmas 3 and 4 yield the stated bounds. □
Overall Evaluation Complexity
Combining the preceding Lemmas 5 and 6 with the counting arguments in Propositions 3 and 6 yields the following overall evaluation bounds for the modified methods.
Theorem 3. Suppose Λ ≥ ∥ λ ∗ ∥ + 1 \Lambda\ge\lVert\lambda^*\rVert+ 1 Λ ≥ ∥ λ ∗ ∥ + 1 . For any ε > 0 \varepsilon> 0 ε > 0 , both methods with the modification in Algorithm 3 and 4 obtain an ε \varepsilon ε -approximate solution of (2) . PFAOS requires at most 2 + 2 24 Λ L D X 2 ε + ⌈ log 2 ( 1 + 6 Λ L D X 2 ε ) ⌉ 2+2\sqrt{\frac{24\Lambda L D_X^2}{\varepsilon}}+\left\lceil\log_2\left(1+\frac{6\Lambda L D_X^2}{\varepsilon}\right)\right\rceil 2 + 2 ε 24Λ L D X 2 + ⌈ log 2 ( 1 + ε 6Λ L D X 2 ) ⌉ evaluations of ∇ g \nabla g ∇ g and 2 + 12 M ‾ D X 2 ε + 2 ⌈ log 2 M ‾ M 0 ⌉ 2+\frac{12\overline{M}D_X^2}{\varepsilon}+2\left\lceil\log_2\frac{\overline{M}}{M_0}\right\rceil 2 + ε 12 M D X 2 + 2 ⌈ log 2 M 0 M ⌉ evaluations of F F F . For MC-PFAOS, the corresponding bounds are 2 + 2 32 Λ L ( D X 2 + Λ 2 ) ε + ⌈ log 2 ( 1 + 8 Λ L ( D X 2 + Λ 2 ) ε ) ⌉ 2+2\sqrt{\frac{32\Lambda L(D_X^2+\Lambda^2)}{\varepsilon}}+\left\lceil\log_2\left(1+\frac{8\Lambda L(D_X^2+\Lambda^2)}{\varepsilon}\right)\right\rceil 2 + 2 ε 32Λ L ( D X 2 + Λ 2 ) + ⌈ log 2 ( 1 + ε 8Λ L ( D X 2 + Λ 2 ) ) ⌉ evaluations of J J J and 2 + 16 M ‾ M C ( D X 2 + Λ 2 ) ε + 2 ⌈ log 2 M ‾ M C M 0 ⌉ 2+\frac{16\overline{M}_{\mathrm{MC}}(D_X^2+\Lambda^2)}{\varepsilon}+2\left\lceil\log_2\frac{\overline{M}_{\mathrm{MC}}}{M_0}\right\rceil 2 + ε 16 M MC ( D X 2 + Λ 2 ) + 2 ⌈ log 2 M 0 M MC ⌉ evaluations of F F F . These bounds include evaluations at initialization and in accepted and rejected line-search trials.
Proof. We first consider PFAOS. Let N ε ≥ 1 N_\varepsilon\ge1 N ε ≥ 1 be the first outer iteration satisfying 3 2 Γ N ε S N ε D X 2 ≤ ε \frac{3}{2}\Gamma^{S_{N_\varepsilon}}_{N_\varepsilon}D_X^2\le\varepsilon 2 3 Γ N ε S N ε D X 2 ≤ ε . By Lemma 6 and Corollary 1, x ˉ N ε \bar{x}_{N_\varepsilon} x ˉ N ε is an ε \varepsilon ε -approximate solution. If N ε = 1 N_\varepsilon=1 N ε = 1 , the evaluation bounds follow from Lemma 5, allowing one additional initialization evaluation of ∇ g \nabla g ∇ g . Hence, assume N ε ≥ 2 N_\varepsilon\ge2 N ε ≥ 2 . Lemma 6 then gives N ε ≤ 1 + 24 Λ L D X 2 ε N_\varepsilon\le1+\sqrt{\frac{24\Lambda L D_X^2}{\varepsilon}} N ε ≤ 1 + ε 24Λ L D X 2 . For ∇ g \nabla g ∇ g evaluations, the retained trial at k = 1 k=1 k = 1 did not satisfy the accuracy certificate, so η 1 S 1 > 2 ε / ( 3 D X 2 ) \eta_1^{S_1}>2\varepsilon/(3D_X^2) η 1 S 1 > 2 ε / ( 3 D X 2 ) . Together with η N ε S N ε ≤ 4 Λ L \eta_{N_\varepsilon}^{S_{N_\varepsilon}}\le4\Lambda L η N ε S N ε ≤ 4Λ L , the η k \eta_k η k updates give
∑ k = 2 N ε S k = 2 ( N ε − 1 ) + log 2 η N ε S N ε η 1 S 1 < 2 ( N ε − 1 ) + log 2 ( 1 + 6 Λ L D X 2 ε ) . \sum_{k=2}^{N_\varepsilon}S_k=2(N_\varepsilon-1)+\log_2\frac{\eta_{N_\varepsilon}^{S_{N_\varepsilon}}}{\eta_1^{S_1}}<2(N_\varepsilon-1)+\log_2\left(1+\frac{6\Lambda L D_X^2}{\varepsilon}\right). k = 2 ∑ N ε S k = 2 ( N ε − 1 ) + log 2 η 1 S 1 η N ε S N ε < 2 ( N ε − 1 ) + log 2 ( 1 + ε 6Λ L D X 2 ) . Each middle trial requires one gradient evaluation. Adding the evaluation at x 0 x_0 x 0 , as in Proposition 3, and using the bound on N ε N_\varepsilon N ε yields the stated constraint-gradient complexity. For the operator evaluations, the invariant and the geometric-series argument in Proposition 3 give
∑ k = 2 N ε ∑ s = 1 S k T k s < 4 M ‾ ∑ k = 1 N ε − 1 1 η k S k = 4 M ‾ 1 / η N ε − 1 S N ε − 1 < 6 M ‾ D X 2 ε . \sum_{k=2}^{N_\varepsilon}\sum_{s=1}^{S_k}T_k^s<4\overline{M}\sum_{k=1}^{N_\varepsilon-1}\frac{1}{\eta_k^{S_k}}=\frac{4\overline{M}}{1/\eta_{N_\varepsilon-1}^{S_{N_\varepsilon-1}}}<\frac{6\overline{M}D_X^2}{\varepsilon}. k = 2 ∑ N ε s = 1 ∑ S k T k s < 4 M k = 1 ∑ N ε − 1 η k S k 1 = 1/ η N ε − 1 S N ε − 1 4 M < ε 6 M D X 2 . Retaining the preceding trial at k = 1 k=1 k = 1 may lower the operator estimate to M 1 = M 1 S 1 M_1=M_1^{S_1} M 1 = M 1 S 1 . For k ≥ 2 k\ge2 k ≥ 2 , the estimates are nondecreasing from M 1 ≥ M 0 M_1\ge M_0 M 1 ≥ M 0 and remain bounded by M ‾ \overline{M} M . So, there are at most ⌈ log 2 ( M ‾ / M 0 ) ⌉ \left\lceil\log_2(\overline{M}/M_0)\right\rceil ⌈ log 2 ( M / M 0 ) ⌉ additional rejected inner trials. Combining these counts with Lemma 5 gives the stated operator complexity. For MC-PFAOS, the same argument replaces M ‾ \overline{M} M and D X 2 D_X^2 D X 2 by M ‾ M C \overline{M}_{\mathrm{MC}} M MC and D X 2 + Λ 2 D_X^2+\Lambda^2 D X 2 + Λ 2 , respectively, and uses the stopping condition 2 Γ N ε S N ε ( D X 2 + Λ 2 ) ≤ ε 2\Gamma_{N_\varepsilon}^{S_{N_\varepsilon}}(D_X^2+\Lambda^2)\le\varepsilon 2 Γ N ε S N ε ( D X 2 + Λ 2 ) ≤ ε . □
Theorem 3 indicates that the special first-iteration searches in Algorithms 3 and 4 allow arbitrarily small positive initial estimates η 0 S 0 \eta_0^{S_0} η 0 S 0 while preserving O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) constraint-gradient or Jacobian complexity and O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator complexity for both PFAOS and MC-PFAOS. These guarantees use accuracy tests involving D X D_X D X , both during the special first iteration and when determining the number of outer iterations N N N . Since γ 1 s = 1 \gamma^s_1 = 1 γ 1 s = 1 gives Γ 1 s = η 1 s \Gamma^s_1 = \eta^s_1 Γ 1 s = η 1 s , both types of tests can be written as 3 2 Γ N S N D X 2 ≤ ε \frac{3}{2}\Gamma^{S_N}_N D_X^2 \le\varepsilon 2 3 Γ N S N D X 2 ≤ ε for PFAOS and 2 Γ N S N ( D X 2 + Λ 2 ) ≤ ε 2\Gamma^{S_N}_N(D_X^2+\Lambda^2) \le\varepsilon 2 Γ N S N ( D X 2 + Λ 2 ) ≤ ε for MC-PFAOS, respectively, with N = 1 N=1 N = 1 and S 1 = s S_1=s S 1 = s when testing an accepted first-iteration trial. However, D X D_X D X is not available. § 5 therefore replaces these tests with an automatic stopping rule that certifies an ε \varepsilon ε -approximate solution without requiring knowledge of D X D_X D X and preserves these evaluation-complexity bounds.
Computable Stopping Criteria
In this section, we construct a computable weak VI gap certificate from quantities generated by PFAOS and MC-PFAOS. Combined with the observed constraint violation, it provides an automatic stopping rule that requires no knowledge of D X D_X D X and preserves the established complexity bounds. The proofs of the results in this section are provided in Appendix § 10 .
A Computable Gap Certificate
We use vector notations for both methods, with m = 1 m=1 m = 1 for PFAOS, and define
C N : = [ max x ∈ X Φ N ( x ) ] + with Φ N ( x ) : = Γ N S N ∑ k = 1 N ∑ t = 1 S k [ ⟨ F ( x k t , S k ) , x k t , S k − x ⟩ − ⟨ λ k t , S k , ℓ S k ( x ) ⟩ ] / M k t , S k . (11) C_N := \left[\max_{x\in X}\Phi_N(x)\right]_+ \text{ with } \Phi_N(x) := \Gamma^{S_N}_N \sum_{k=1}^{N}\sum_{t=1}^{S_k}\left[\left\langle F(x^{t,S_k}_k),x^{t,S_k}_k-x\right\rangle-\left\langle\lambda^{t,S_k}_k,\ell_{S_k}(x)\right\rangle\right]/M^{t,S_k}_k. \tag*{(11)} C N := [ x ∈ X max Φ N ( x ) ] + with Φ N ( x ) := Γ N S N k = 1 ∑ N t = 1 ∑ S k [ ⟨ F ( x k t , S k ) , x k t , S k − x ⟩ − ⟨ λ k t , S k , ℓ S k ( x ) ⟩ ] / M k t , S k . (11)
Here, evaluating C N C_N C N requires only linear optimization over the simple set X X X . It uses stored quantities and requires no additional evaluations of F F F , ∇ g \nabla g ∇ g or J J J . The following proposition shows that this certificate bounds the weak VI gap and is controlled by the preceding D X D_X D X -based bounds.
Proposition 7. For both methods, with or without the special first-iteration search, every retained outer iterate satisfies sup x ∈ X ~ ⟨ F ( x ) , x ˉ N − x ⟩ ≤ C N \sup_{x\in\widetilde{X}}\langle F(x),\bar{x}_N-x\rangle\le C_N sup x ∈ X ⟨ F ( x ) , x ˉ N − x ⟩ ≤ C N . Moreover, C N ≤ 3 2 Γ N S N D X 2 C_N\le\frac{3}{2}\Gamma^{S_N}_N D_X^2 C N ≤ 2 3 Γ N S N D X 2 for PFAOS and C N ≤ 2 Γ N S N D X 2 C_N\le2\Gamma^{S_N}_N D_X^2 C N ≤ 2 Γ N S N D X 2 for MC-PFAOS.
Stopping Rule and Complexity
With the help of Proposition 7, we can replace the preceding D X D_X D X -based accuracy tests by the following rule: after obtaining an accepted outer update, return x ˉ N \bar{x}_N x ˉ N if
C N ≤ ε , ∥ [ G ( x ˉ N ) ] + ∥ ≤ ε . (12) C_N\le\varepsilon,\qquad\left\|[G(\bar{x}_N)]_+\right\|\le\varepsilon. \tag*{(12)} C N ≤ ε , ∥ [ G ( x ˉ N ) ] + ∥ ≤ ε . (12)
For the special first iteration in Algorithms 3 and 4, replace each accuracy test with (12) . For a trial s s s that passes the inner and middle acceptance conditions, evaluate the certificate with N = 1 N=1 N = 1 , S 1 = s S_1=s S 1 = s , and Γ 1 s = η 1 s \Gamma^s_1=\eta^s_1 Γ 1 s = η 1 s , using only that trial’s inner iterates. All other updates remain unchanged. The following proposition establishes the accuracy and complexity guarantees of this replacement.
Proposition 8. *For any Λ > 0 \Lambda>0 Λ > 0 , any point returned by (12) is an ε \varepsilon ε -approximate solution of (2) . If Λ ≥ ∥ λ ∗ ∥ + 1 \Lambda\ge\|\lambda^*\|+1 Λ ≥ ∥ λ ∗ ∥ + 1 , (12) preserves the respective complexities in Propositions 3 and 6, and Theorem 3.
Therefore, the stopping rules in (12) certify an ε \varepsilon ε -approximate solution without requiring D X D_X D X , while retaining the established complexity bounds.
Numerical Experiments
To our knowledge, no established parameter-free method directly applies to CVI setting, and adapting parameter-dependent CVI methods is nontrivial. We therefore benchmark PFAOS and MC-PFAOS against unconstrained VI methods using projections onto the full feasible set. To assess robustness, we generate instances across multiple random seeds, ensuring the required monotonicity and feasibility conditions as described below.
Experiment Setting
Test Instances
We generate randomized instances inspired by bilinear games with a singular positive semidefinite (PSD) regularizer. Let X = { x ∈ R n : ∥ x ∥ 2 ≤ 2 } X = \{x \in\mathbb{R}^{n} : \lVert x \rVert_{2} \le2\} X = { x ∈ R n : ∥ x ∥ 2 ≤ 2 } and generate operator F ( x ) = ( R − R T + H ) x − d F(x) = (R - R^{\mathsf{T}} + H)x - d F ( x ) = ( R − R T + H ) x − d and quadratic constraints g i ( x ) = 1 2 x T A i x + b i T x + c i g_i(x) = \frac{1}{2}x^{\mathsf{T}}A_i x + b_i^{\mathsf{T}}x + c_i g i ( x ) = 2 1 x T A i x + b i T x + c i , where R , H , A i ∈ R n × n R, H, A_i \in\mathbb{R}^{n \times n} R , H , A i ∈ R n × n , d , b i ∈ R n d, b_i \in\mathbb{R}^{n} d , b i ∈ R n , and c i ∈ R c_i \in\mathbb{R} c i ∈ R . Uniform draws are used to generate R R R , d d d , b i b_i b i and the positive eigenvalues of H H H and A i A_i A i , with ⌊ n / 2 ⌋ \lfloor n/2 \rfloor ⌊ n /2 ⌋ eigenvalues fixed at zero. We construct H H H as a diagonal PSD matrix and A i A_i A i as symmetric PSD matrices by conjugating the corresponding diagonal matrix with a random orthogonal matrix. Thus, F F F is nonconservative and monotone but not strongly monotone, and the constraints are convex but not strongly convex. The constants c i c_i c i are chosen so that a common point x s l ∈ ri ( X ) x^{\mathrm{sl}} \in\operatorname{ri}(X) x sl ∈ ri ( X ) satisfies g i ( x s l ) < 0 g_i(x^{\mathrm{sl}}) < 0 g i ( x sl ) < 0 for all i = 1 , … , m i = 1, \ldots, m i = 1 , … , m . Consequently, Slater’s condition in Assumption 1 holds, and the full feasible set X ~ = X ∩ { x : g i ( x ) ≤ 0 , i = 1 , … , m } \widetilde{X} = X \cap\{x : g_i(x) \le0, i = 1, \ldots, m\} X = X ∩ { x : g i ( x ) ≤ 0 , i = 1 , … , m } is nonempty, compact, and convex, ensuring that the VI admits a solution. The instance-generation and implementation code is available at https://github.com/qluorocky/CVI_IJOC.
Benchmark Methods
We adapt two advanced first-order algorithms that achieve competitive sample complexity for unconstrained VIs.
Benchmark 1 applies the operator-extrapolation (OE) method in Kotsalis et al. [6 ] . For a fixed estimate M ^ > 0 \widehat{M} > 0 M > 0 , OE updates x k + 1 = Π X ~ ( x k − ( 2 F ( x k ) − F ( x k − 1 ) ) / ( 2 M ^ ) ) x_{k+1} = \Pi_{\widetilde{X}}(x_k - (2F(x_k) - F(x_{k-1}))/(2\widehat{M})) x k + 1 = Π X ( x k − ( 2 F ( x k ) − F ( x k − 1 )) / ( 2 M )) at iteration k k k . For each instance, we run fixed-M ^ \widehat{M} M trajectories in parallel with trial values spanning [ 0.1 M , 10 M ] [0.1M, 10M] [ 0.1 M , 10 M ] .
Benchmark 2 applies the golden-ratio algorithm in Malitsky [11 ] , which is a parameter-free method. Given initializations, the method updates x ˉ k = ( ( ϕ − 1 ) x k + x ˉ k − 1 ) / ϕ \bar{x}_k = ((\phi- 1)x_k + \bar{x}_{k-1})/\phi x ˉ k = (( ϕ − 1 ) x k + x ˉ k − 1 ) / ϕ and x k + 1 = Π X ~ ( x ˉ k − λ k F ( x k ) ) x_{k+1} = \Pi_{\widetilde{X}}(\bar{x}_k - \lambda_k F(x_k)) x k + 1 = Π X ( x ˉ k − λ k F ( x k )) , where φ = ( 1 + 5 ) / 2 \varphi= (1+\sqrt{5})/2 φ = ( 1 + 5 ) /2 , ϕ ∈ ( 1 , φ ] \phi\in(1,\varphi] ϕ ∈ ( 1 , φ ] and λ k = min { ( 1 ϕ + 1 ϕ 2 ) λ k − 1 , ϕ 2 4 λ k − 2 ∥ x k − x k − 1 ∥ 2 ∥ F ( x k ) − F ( x k − 1 ) ∥ 2 , λ ˉ } \lambda_k = \min\left\{\left(\frac{1}{\phi} + \frac{1}{\phi^2}\right)\lambda_{k-1}, \frac{\phi^2}{4\lambda_{k-2}}\frac{\lVert x_k-x_{k-1}\rVert^2}{\lVert F(x_k)-F(x_{k-1})\rVert^2}, \bar{\lambda}\right\} λ k = min { ( ϕ 1 + ϕ 2 1 ) λ k − 1 , 4 λ k − 2 ϕ 2 ∥ F ( x k ) − F ( x k − 1 ) ∥ 2 ∥ x k − x k − 1 ∥ 2 , λ ˉ } .
Both benchmarks compute projections Π X ~ \Pi_{\widetilde{X}} Π X with a generic convex solver at every iteration.
Evaluation Protocol
All methods run with the same set of realized instances and initial points. The runs were performed on an Apple M4 MacBook Pro (10 CPU cores and 16 GB memory), using CVXPY 1.9.3 and Clarabel 0.11.1. For a reported average x ˉ \bar{x} x ˉ , we report both the VI gap Gap ( x ˉ ) = [ sup y ∈ X ~ ⟨ F ( y ) , x ˉ − y ⟩ ] + \operatorname{Gap}(\bar{x}) = [\sup_{y\in\widetilde{X}}\langle F(y),\bar{x}-y\rangle]_+ Gap ( x ˉ ) = [ sup y ∈ X ⟨ F ( y ) , x ˉ − y ⟩ ] + , and constraint violation V ( x ˉ ) = ∥ [ G ( x ˉ ) ] + ∥ 2 V(\bar{x}) = \|[G(\bar{x})]_+\|_2 V ( x ˉ ) = ∥ [ G ( x ˉ ) ] + ∥ 2 . We denote the combined error E ^ = max { Gap ( x ˉ ) , ∥ [ G ( x ˉ ) ] + ∥ 2 } \widehat{E} = \max\{\operatorname{Gap}(\bar{x}),\|[G(\bar{x})]_+\|_2\} E = max { Gap ( x ˉ ) , ∥ [ G ( x ˉ ) ] + ∥ 2 } . The common stopping target is 10 − 5 10^{-5} 1 0 − 5 and we also report their runtime along the convergence paths.
Results
Figure 1 shows a substantial computational advantage for PFAOS and MC-PFAOS over the projection-based benchmarks. Each configuration uses 10 paired random seeds. After 1000 seconds, PFAOS attains a median estimated weak gap in order of 10 − 4 10^{-4} 1 0 − 4 , compared with 10 − 1 10^{-1} 1 0 − 1 for OE initialized at the true operator constant M M M . MC-PFAOS achieves a zero estimated weak gap, although its remaining constraint violation yields a median combined error of 10 − 4 10^{-4} 1 0 − 4 . OE is sensitive to its fixed smoothness estimate: using 10 M 10M 10 M leads to failed convergence substantially, whereas using 0.1 M 0.1M 0.1 M leads to persistently large errors. The adaptive golden-ratio benchmark also reduces the gap but converges considerably more slowly than the proposed methods. These comparisons reflect the computational savings of PFAOS from avoiding full projection onto the nonlinear feasible set at every step.
Figure 1. Combined error versus solver time for (a) PFAOS and (b) MC-PFAOS, compared with OE and the Golden Ratio Algorithm. Here Gap ^ \widehat{\operatorname{Gap}} Gap denotes the numerical gap estimate. Central curves show medians over 10 random instances, and shaded bands show 95% bootstrap confidence intervals for the medians. The dashed line marks the target accuracy 10 − 5 10^{-5} 1 0 − 5 .
The single-constraint study fixes m = 1 m = 1 m = 1 and uses n ∈ { 10 , 50 , 100 , 200 , 500 , 1000 } n \in\{10, 50, 100, 200, 500, 1000\} n ∈ { 10 , 50 , 100 , 200 , 500 , 1000 } , with ten paired random seeds per dimension. For the experiments in Table 1 , PFAOS reaches the joint numerical-error threshold 10 − 4 10^{-4} 1 0 − 4 in all 60 runs and reaches 10 − 5 10^{-5} 1 0 − 5 in every run with n ≤ 500 n \le500 n ≤ 500 . At n = 1000 n = 1000 n = 1000 , all ten runs reach 10 − 4 10^{-4} 1 0 − 4 , but none reaches 10 − 5 10^{-5} 1 0 − 5 within the 1000-second budget. For thresholds attained by both PFAOS and a baseline, PFAOS has the smaller conditional mean hitting time. In contrast, fixed OE with M ^ = M \hat{M}=M M ^ = M reaches 10 − 5 10^{-5} 1 0 − 5 in only two of the ten n = 10 n=10 n = 10 runs, and the Golden Ratio method also records no 10 − 5 10^{-5} 1 0 − 5 crossing. These results demonstrate PFAOS’s stronger empirical performance regarding both the the VI gap and constraint violations.
Table 1. First observed valid joint numerical-error threshold times (seconds) and terminal constraint violation (m=1) over 10 attempted runs per configuration, with a 1000-second method cap. Note: Each threshold cell shows observed valid successes s / N s/N s / N , then best/mean/worst times over those successful runs only. – means no observed valid crossing before the recorded termination. Final V V V gives best/mean/worst over all terminal outputs. Times are in seconds.
Conclusion
This work develops PFAOS and MC-PFAOS for monotone VIs with convex smooth functional constraints. Both methods separate operator evaluations from constraint-gradient or Jacobian evaluations, while avoiding projections onto the complex feasible set. Neither method requires prior knowledge of the Lipschitz constant of the operator or the smoothness constants of the constraints; MC-PFAOS also requires no prior uniform bound on the Jacobian. Under Λ ≥ ∥ λ ∗ ∥ + 1 \Lambda\ge\lVert\lambda^*\rVert+ 1 Λ ≥ ∥ λ ∗ ∥ + 1 , both methods require at most O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) constraint-gradient or Jacobian evaluations and O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) operator evaluations, including evaluations in rejected line-search trials, to obtain an ε \varepsilon ε -approximate solution. With the special first-iteration search and automatic stopping rule, both methods accommodate arbitrarily small positive initial estimates and certify an ε \varepsilon ε -approximate solution without requiring knowledge of the diameter of the set X X X , while preserving these optimal complexity bounds.
Acknowledgments
This work is partially supported by the AFOSR grant FA9550-25-1-0278. During the preparation of this work, all theoretical derivations and numerical algorithms were developed by the authors without the use of AI tools. The authors used ChatGPT to improve the readability of the manuscript. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the content of the publication. The authors also used ChatGPT to debug the implementation code for the numerical experiments and reviewed the code as needed to ensure that it faithfully implements the proposed algorithms. This work was supported in part by OpenAI API credits provided by Clemson University and administered by Clemson University Research Computing and Data (RCD).
Proofs for Section 3
Proof of Proposition 4. Fix any t ≥ 1 t \ge1 t ≥ 1 . Applying Lemma 1 to the primal and dual subproblems in (7) , we have
0 ≤ ⟨ ℓ k s ( x k t , s ) , λ k t , s − λ ⟩ − η k s + p k t , s 2 ∥ λ − λ k t , s ∥ 2 + η k s 2 ∥ λ − λ k − 1 ∥ 2 + p k t , s 2 ( ∥ λ − λ k t − 1 , s ∥ 2 − ∥ λ k t , s − λ k t − 1 , s ∥ 2 ) , 0 \le\langle\ell_k^s(x_k^{t,s}),\lambda_k^{t,s}-\lambda\rangle-\frac{\eta_k^s+p_k^{t,s}}{2}\|\lambda-\lambda_k^{t,s}\|^2+\frac{\eta_k^s}{2}\|\lambda-\lambda_{k-1}\|^2+\frac{p_k^{t,s}}{2}\left(\|\lambda-\lambda_k^{t-1,s}\|^2-\|\lambda_k^{t,s}-\lambda_k^{t-1,s}\|^2\right), 0 ≤ ⟨ ℓ k s ( x k t , s ) , λ k t , s − λ ⟩ − 2 η k s + p k t , s ∥ λ − λ k t , s ∥ 2 + 2 η k s ∥ λ − λ k − 1 ∥ 2 + 2 p k t , s ( ∥ λ − λ k t − 1 , s ∥ 2 − ∥ λ k t , s − λ k t − 1 , s ∥ 2 ) ,
0 ≤ − ⟨ F ( x k t − 1 , s ) + θ k t , s Δ k t − 1 , s + A k t , s x k t , s − x ⟩ − η k s + p k t , s 2 ∥ x − x k t , s ∥ 2 + η k s 2 ( ∥ x − x k − 1 ∥ 2 − ∥ x k t , s − x k − 1 ∥ 2 ) + p k t , s 2 ( ∥ x − x k t − 1 , s ∥ 2 − ∥ x k t , s − x k t − 1 , s ∥ 2 ) . 0 \le-\langle F(x_k^{t-1,s})+\theta_k^{t,s}\Delta_k^{t-1,s}+A_k^{t,s}x_k^{t,s}-x\rangle-\frac{\eta_k^s+p_k^{t,s}}{2}\|x-x_k^{t,s}\|^2
+\frac{\eta_k^s}{2}\left(\|x-x_{k-1}\|^2-\|x_k^{t,s}-x_{k-1}\|^2\right)+\frac{p_k^{t,s}}{2}\left(\|x-x_k^{t-1,s}\|^2-\|x_k^{t,s}-x_k^{t-1,s}\|^2\right). 0 ≤ − ⟨ F ( x k t − 1 , s ) + θ k t , s Δ k t − 1 , s + A k t , s x k t , s − x ⟩ − 2 η k s + p k t , s ∥ x − x k t , s ∥ 2 + 2 η k s ( ∥ x − x k − 1 ∥ 2 − ∥ x k t , s − x k − 1 ∥ 2 ) + 2 p k t , s ( ∥ x − x k t − 1 , s ∥ 2 − ∥ x k t , s − x k t − 1 , s ∥ 2 ) .
Combining the above relations with ⟨ F ( x ) , x k t , s − x ⟩ ≤ ⟨ F ( x k t , s ) , x k t , s − x ⟩ \langle F(x),x_k^{t,s}-x\rangle\le\langle F(x_k^{t,s}),x_k^{t,s}-x\rangle ⟨ F ( x ) , x k t , s − x ⟩ ≤ ⟨ F ( x k t , s ) , x k t , s − x ⟩ from the monotonicity of F F F , and applying the Cauchy–Schwarz inequality and rearranging terms yields ⟨ F ( x ) , x k t , s − x ⟩ ≤ − ⟨ A k t , s , x k t , s − x ⟩ + B k t , s + C k t , s + D k t , s \langle F(x),x_k^{t,s}-x\rangle\le-\langle A_k^{t,s},x_k^{t,s}-x\rangle+B_k^{t,s}+C_k^{t,s}+D_k^{t,s} ⟨ F ( x ) , x k t , s − x ⟩ ≤ − ⟨ A k t , s , x k t , s − x ⟩ + B k t , s + C k t , s + D k t , s , where
B k t , s : = ⟨ Δ k t , s , x k t , s − x ⟩ − θ k t , s ⟨ Δ k t − 1 , s , x k t − 1 , s − x ⟩ + p k t , s 2 ( ∥ x − x k t − 1 , s ∥ 2 + ∥ λ − λ k t − 1 , s ∥ 2 ) B_k^{t,s}:=\langle\Delta_k^{t,s},x_k^{t,s}-x\rangle-\theta_k^{t,s}\langle\Delta_k^{t-1,s},x_k^{t-1,s}-x\rangle+\frac{p_k^{t,s}}{2}\left(\|x-x_k^{t-1,s}\|^2+\|\lambda-\lambda_k^{t-1,s}\|^2\right) B k t , s := ⟨ Δ k t , s , x k t , s − x ⟩ − θ k t , s ⟨ Δ k t − 1 , s , x k t − 1 , s − x ⟩ + 2 p k t , s ( ∥ x − x k t − 1 , s ∥ 2 + ∥ λ − λ k t − 1 , s ∥ 2 )
− η k s + p k t , s 2 ( ∥ x − x k t , s ∥ 2 + ∥ λ − λ k t , s ∥ 2 ) , -\frac{\eta_k^s+p_k^{t,s}}{2}\left(\|x-x_k^{t,s}\|^2+\|\lambda-\lambda_k^{t,s}\|^2\right), − 2 η k s + p k t , s ( ∥ x − x k t , s ∥ 2 + ∥ λ − λ k t , s ∥ 2 ) ,
C k t , s : = θ k t , s ∥ Δ k t − 1 , s ∥ ∥ x k t , s − x k t − 1 , s ∥ − p k t , s 2 ∥ x k t , s − x k t − 1 , s ∥ 2 C_k^{t,s}:=\theta_k^{t,s}\|\Delta_k^{t-1,s}\|\|x_k^{t,s}-x_k^{t-1,s}\|-\frac{p_k^{t,s}}{2}\|x_k^{t,s}-x_k^{t-1,s}\|^2 C k t , s := θ k t , s ∥ Δ k t − 1 , s ∥∥ x k t , s − x k t − 1 , s ∥ − 2 p k t , s ∥ x k t , s − x k t − 1 , s ∥ 2
D k t , s : = η k s 2 ( ∥ x − x k − 1 ∥ 2 − ∥ x k t , s − x k − 1 ∥ 2 + ∥ λ − λ k − 1 ∥ 2 ) − p k t , s 2 ∥ λ k t , s − λ k t − 1 , s ∥ 2 + ⟨ ℓ k s ( x k t , s ) , λ k t , s − λ ⟩ . D_k^{t,s}:=\frac{\eta_k^s}{2}\left(\|x-x_{k-1}\|^2-\|x_k^{t,s}-x_{k-1}\|^2+\|\lambda-\lambda_{k-1}\|^2\right)-\frac{p_k^{t,s}}{2}\|\lambda_k^{t,s}-\lambda_k^{t-1,s}\|^2+\langle\ell_k^s(x_k^{t,s}),\lambda_k^{t,s}-\lambda\rangle. D k t , s := 2 η k s ( ∥ x − x k − 1 ∥ 2 − ∥ x k t , s − x k − 1 ∥ 2 + ∥ λ − λ k − 1 ∥ 2 ) − 2 p k t , s ∥ λ k t , s − λ k t − 1 , s ∥ 2 + ⟨ ℓ k s ( x k t , s ) , λ k t , s − λ ⟩ .
Multiplying both sides of the above relation by 1 / M k t , s 1/M_k^{t,s} 1/ M k t , s , and summing over t = 1 , … , T k s t=1,\ldots,T_k^s t = 1 , … , T k s , while considering the definition of x ^ k s \hat{x}_k^s x ^ k s gives immediately that
B k s ⟨ F ( x ) , x ^ k s − x ⟩ ≤ − ∑ t = 1 T k s 1 M k t , s ⟨ A k t , s , x k t , s − x ⟩ + ∑ t = 1 T k s B k t , s M k t , s + ∑ t = 1 T k s C k t , s M k t , s + ∑ t = 1 T k s D k t , s M k t , s . (13) \mathcal{B}_k^s\langle F(x),\hat{x}_k^s-x\rangle\le-\sum_{t=1}^{T_k^s}\frac{1}{M_k^{t,s}}\langle A_k^{t,s},x_k^{t,s}-x\rangle+\sum_{t=1}^{T_k^s}\frac{B_k^{t,s}}{M_k^{t,s}}+\sum_{t=1}^{T_k^s}\frac{C_k^{t,s}}{M_k^{t,s}}+\sum_{t=1}^{T_k^s}\frac{D_k^{t,s}}{M_k^{t,s}}. \tag*{(13)} B k s ⟨ F ( x ) , x ^ k s − x ⟩ ≤ − t = 1 ∑ T k s M k t , s 1 ⟨ A k t , s , x k t , s − x ⟩ + t = 1 ∑ T k s M k t , s B k t , s + t = 1 ∑ T k s M k t , s C k t , s + t = 1 ∑ T k s M k t , s D k t , s . (13)
Now, we bound the last three sums in the right hand side of (13) one by one. First, the parameter settings in Algorithm 2 ensure that θ k t , s = M k t , s / M k t − 1 , s \theta_k^{t,s}=M_k^{t,s}/M_k^{t-1,s} θ k t , s = M k t , s / M k t − 1 , s and p k t , s / M k t , s = ( p k t − 1 , s + η k s ) / M k t − 1 , s p_k^{t,s}/M_k^{t,s}=(p_k^{t-1,s}+\eta_k^s)/M_k^{t-1,s} p k t , s / M k t , s = ( p k t − 1 , s + η k s ) / M k t − 1 , s , ∀ t ≥ 2 \forall t\ge2 ∀ t ≥ 2 . Thus, canceling out the recursive terms while considering the definitions of M k s M_k^s M k s , x k s x_k^s x k s , x k 0 , s x_k^{0,s} x k 0 , s , we have ∑ t = 1 T k s B k t , s / M k t , s = B k s \sum_{t=1}^{T_k^s}B_k^{t,s}/M_k^{t,s}=B_k^s ∑ t = 1 T k s B k t , s / M k t , s = B k s . Second, Algorithm 2 also indicates that p k t , s / M k t , s ≥ 3 p_k^{t,s}/M_k^{t,s}\ge3 p k t , s / M k t , s ≥ 3 , ∀ t ≥ 1 \forall t\ge1 ∀ t ≥ 1 , so
∥ x k t − 1 , s − x k t − 2 , s ∥ ∥ x k t , s − x k t − 1 , s ∥ − p k t , s 6 M k t , s ∥ x k t , s − x k t − 1 , s ∥ 2 − p k t − 1 , s 6 M k t − 1 , s ∥ x k t − 1 , s − x k t − 2 , s ∥ 2 ≤ 0 , ∀ t ≥ 2. \|x_k^{t-1,s}-x_k^{t-2,s}\|\|x_k^{t,s}-x_k^{t-1,s}\|-\frac{p_k^{t,s}}{6M_k^{t,s}}\|x_k^{t,s}-x_k^{t-1,s}\|^2-\frac{p_k^{t-1,s}}{6M_k^{t-1,s}}\|x_k^{t-1,s}-x_k^{t-2,s}\|^2\le0,\quad\forall t\ge2. ∥ x k t − 1 , s − x k t − 2 , s ∥∥ x k t , s − x k t − 1 , s ∥ − 6 M k t , s p k t , s ∥ x k t , s − x k t − 1 , s ∥ 2 − 6 M k t − 1 , s p k t − 1 , s ∥ x k t − 1 , s − x k t − 2 , s ∥ 2 ≤ 0 , ∀ t ≥ 2.
Thus, given the relations ∥ Δ k t − 1 , s ∥ ≤ M k t − 1 , s ∥ x k t − 1 , s − x k t − 2 , s ∥ \|\Delta_k^{t-1,s}\|\le M_k^{t-1,s}\|x_k^{t-1,s}-x_k^{t-2,s}\| ∥ Δ k t − 1 , s ∥ ≤ M k t − 1 , s ∥ x k t − 1 , s − x k t − 2 , s ∥ and θ k t , s = M k t , s / M k t − 1 , s \theta_k^{t,s}=M_k^{t,s}/M_k^{t-1,s} θ k t , s = M k t , s / M k t − 1 , s , ∀ t ≥ 2 \forall t\ge2 ∀ t ≥ 2 guaranteed by the algorithm, and the definitions of x k 0 , s x_k^{0,s} x k 0 , s and x k s x_k^s x k s , we have ∑ t = 1 T k s C k t , s / M k t , s ≤ C k s \sum_{t=1}^{T_k^s}C_k^{t,s}/M_k^{t,s}\le C_k^s ∑ t = 1 T k s C k t , s / M k t , s ≤ C k s . Finally, with the help of the convexity of ∥ ⋅ ∥ 2 \|\cdot\|^2 ∥ ⋅ ∥ 2 , the invariant relation B k s B k s = 1 \mathcal{B}_k^s\mathcal{B}_k^s=1 B k s B k s = 1 , together with the definitions of x ^ k s \hat{x}_k^s x ^ k s , it is easy to see that ∑ t = 1 T k s D k t , s / M k t , s ≤ D k s \sum_{t=1}^{T_k^s}D_k^{t,s}/M_k^{t,s}\le D_k^s ∑ t = 1 T k s D k t , s / M k t , s ≤ D k s . □ \square □
Proof of Proposition 5. Immediately from the definitions of x ˉ k \bar{x}_k x ˉ k , x ^ k \hat{x}_k x ^ k , λ ˉ k \bar{\lambda}_k λ ˉ k and λ ^ k \hat{\lambda}_k λ ^ k , it follows that
G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) = γ k S k ⟨ F ( x ) , x ^ k − x ⟩ + ⟨ G ( x ˉ k ) , λ ⟩ − ( 1 − γ k S k ) ⟨ G ( x ˉ k − 1 ) , λ ⟩ − γ k S k ⟨ G ( x ) , λ ^ k ⟩ . (14) G_k(x,\lambda)-(1-\gamma_k^{S_k})G_{k-1}(x,\lambda)=\gamma_k^{S_k}\langle F(x),\hat{x}_k-x\rangle+\langle G(\bar{x}_k),\lambda\rangle-(1-\gamma_k^{S_k})\langle G(\bar{x}_{k-1}),\lambda\rangle-\gamma_k^{S_k}\langle G(x),\hat{\lambda}_k\rangle. \tag*{(14)} G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) = γ k S k ⟨ F ( x ) , x ^ k − x ⟩ + ⟨ G ( x ˉ k ) , λ ⟩ − ( 1 − γ k S k ) ⟨ G ( x ˉ k − 1 ) , λ ⟩ − γ k S k ⟨ G ( x ) , λ ^ k ⟩ . (14)
Here, we make two observations. First, the acceptance test described at line 9 gives ∥ G ( x ˉ k ) − ρ k S k ( x ˉ k ) ∥ ≤ η k S k 2 λ k S k ∥ x ˉ k − x k S ∥ 2 \|G(\bar{x}_k)-\rho_k^{S_k}(\bar{x}_k)\|\le\frac{\eta_k^{S_k}}{2\lambda_k^{S_k}}\|\bar{x}_k-x_k^S\|^2 ∥ G ( x ˉ k ) − ρ k S k ( x ˉ k ) ∥ ≤ 2 λ k S k η k S k ∥ x ˉ k − x k S ∥ 2 . Second, since ρ k S k \rho_k^{S_k} ρ k S k is affine and each g i g_i g i is convex, we have ρ k S k ( x ˉ k ) = ( 1 − γ k S k ) ρ k S k ( x ˉ k − 1 ) + γ k S k ρ k S k ( x ^ k ) \rho_k^{S_k}(\bar{x}_k)=(1-\gamma_k^{S_k})\rho_k^{S_k}(\bar{x}_{k-1})+\gamma_k^{S_k}\rho_k^{S_k}(\hat{x}_k) ρ k S k ( x ˉ k ) = ( 1 − γ k S k ) ρ k S k ( x ˉ k − 1 ) + γ k S k ρ k S k ( x ^ k ) , while G ( x ˉ k − 1 ) ≥ ρ k S k ( x ˉ k − 1 ) G(\bar{x}_{k-1})\ge\rho_k^{S_k}(\bar{x}_{k-1}) G ( x ˉ k − 1 ) ≥ ρ k S k ( x ˉ k − 1 ) and G ( x ) ≥ ρ k S k ( x ) G(x)\ge\rho_k^{S_k}(x) G ( x ) ≥ ρ k S k ( x ) componentwise. Hence, using λ , λ ^ k ≥ 0 \lambda,\hat{\lambda}_k\ge0 λ , λ ^ k ≥ 0 , Cauchy–Schwarz inequality and the relation x ˉ k − x k S k = γ k S k ( x ^ k − x k − 1 ) \bar{x}_k-x_k^{S_k}=\gamma_k^{S_k}(\hat{x}_k-x_{k-1}) x ˉ k − x k S k = γ k S k ( x ^ k − x k − 1 ) ensured by the algorithm, we obtain
⟨ G ( x ˉ k ) , λ ⟩ − ( 1 − γ k S k ) ⟨ G ( x ˉ k − 1 ) , λ ⟩ − γ k S k ⟨ G ( x ) , λ ^ k ⟩ ≤ γ k S k ( ⟨ ρ k S k ( x ^ k ) , λ ⟩ − ⟨ ρ k S k ( x ) , λ ^ k ⟩ + η k S k ∥ λ ∥ 2 Λ ∥ x ^ k − x k − 1 ∥ 2 ) . (15) \langle G(\bar{x}_k),\lambda\rangle-(1-\gamma_k^{S_k})\langle G(\bar{x}_{k-1}),\lambda\rangle-\gamma_k^{S_k}\langle G(x),\hat{\lambda}_k\rangle\le\gamma_k^{S_k}\left(\langle\rho_k^{S_k}(\hat{x}_k),\lambda\rangle-\langle\rho_k^{S_k}(x),\hat{\lambda}_k\rangle+\frac{\eta_k^{S_k}\|\lambda\|}{2\Lambda}\|\hat{x}_k-x_{k-1}\|^2\right). \tag*{(15)} ⟨ G ( x ˉ k ) , λ ⟩ − ( 1 − γ k S k ) ⟨ G ( x ˉ k − 1 ) , λ ⟩ − γ k S k ⟨ G ( x ) , λ ^ k ⟩ ≤ γ k S k ( ⟨ ρ k S k ( x ^ k ) , λ ⟩ − ⟨ ρ k S k ( x ) , λ ^ k ⟩ + 2Λ η k S k ∥ λ ∥ ∥ x ^ k − x k − 1 ∥ 2 ) . (15)
To reach the conclusion, we also need the following five facts. First, we have
1 B k S k ∑ t = 1 T k S k 1 M k t , S k ( ⟨ ρ k S k ( x k t , S k ) , λ k t , S k − λ ⟩ − ⟨ J ( x k t , S k ) ( x k t , S k − x ) , λ k t , S k ⟩ ) = 1 B k S k ∑ t = 1 T k S k 1 M k t , S k ( ⟨ ρ k S k ( x ) , λ k t , S k ⟩ − ⟨ ρ k S k ( x k t , S k ) , λ ⟩ ) = ⟨ ρ k S k ( x ) , λ ^ k ⟩ − ⟨ ρ k S k ( x ^ k ) , λ ⟩ . (16) \begin{aligned}
\frac{1}{\mathcal{B}_k^{S_k}}\sum_{t=1}^{T_k^{S_k}}\frac{1}{M_k^{t,S_k}}\left(\langle\rho_k^{S_k}(x_k^{t,S_k}),\lambda_k^{t,S_k}-\lambda\rangle-\langle J(x_k^{t,S_k})(x_k^{t,S_k}-x),\lambda_k^{t,S_k}\rangle\right) \\
&=\frac{1}{\mathcal{B}_k^{S_k}}\sum_{t=1}^{T_k^{S_k}}\frac{1}{M_k^{t,S_k}}\left(\langle\rho_k^{S_k}(x),\lambda_k^{t,S_k}\rangle-\langle\rho_k^{S_k}(x_k^{t,S_k}),\lambda\rangle\right)=\langle\rho_k^{S_k}(x),\hat{\lambda}_k\rangle-\langle\rho_k^{S_k}(\hat{x}_k),\lambda\rangle. \tag*{(16)}
\end{aligned} B k S k 1 t = 1 ∑ T k S k M k t , S k 1 ( ⟨ ρ k S k ( x k t , S k ) , λ k t , S k − λ ⟩ − ⟨ J ( x k t , S k ) ( x k t , S k − x ) , λ k t , S k ⟩ ) = B k S k 1 t = 1 ∑ T k S k M k t , S k 1 ( ⟨ ρ k S k ( x ) , λ k t , S k ⟩ − ⟨ ρ k S k ( x k t , S k ) , λ ⟩ ) = ⟨ ρ k S k ( x ) , λ ^ k ⟩ − ⟨ ρ k S k ( x ^ k ) , λ ⟩ . (16)
Here the first equality holds due to ℓ k S k ( x k t , S k ) − J ( x k S k ) ( x k t , S k − x ) = ℓ k S k ( x ) \ell_k^{S_k}(x_k^{t,S_k})-J(x_k^{S_k})(x_k^{t,S_k}-x)=\ell_k^{S_k}(x) ℓ k S k ( x k t , S k ) − J ( x k S k ) ( x k t , S k − x ) = ℓ k S k ( x ) , while the second one comes from the definitions of x ^ k \hat{x}_k x ^ k and λ ^ k \hat{\lambda}_k λ ^ k and the affinity of ℓ k S k \ell_k^{S_k} ℓ k S k . Second, directly from the definitions of λ ~ k t , S k \tilde{\lambda}_k^{t,S_k} λ ~ k t , S k and the relation θ k t , S k = M k t , S k / M k t − 1 , S k \theta_k^{t,S_k}=M_k^{t,S_k}/M_k^{t-1,S_k} θ k t , S k = M k t , S k / M k t − 1 , S k , ∀ t ≥ 2 \forall t\ge2 ∀ t ≥ 2 , given by the algorithm, it follows that
∑ t = 2 T k S k ( 1 M k t , S k ⟨ J ( x k S k ) ( x k t , S k − x ) , λ k t , S k − λ ~ k t , S k ⟩ + θ k t , S k M k t , S k ⟨ J ( x k S k ) ( x k t , S k − x k t − 1 , S k ) , λ k t − 1 , S k − λ k t − 2 , S k ⟩ ) = 1 M k S k ⟨ J ( x k S k ) ( x k − x ) , λ k − λ k T k S k − 1 , S k ⟩ − 1 M k S k ⟨ J ( x k S k ) ( x k 1 , S k − x ) , λ k 1 , S k − λ k − 1 ⟩ , (17) \begin{aligned}
\sum_{t=2}^{T_k^{S_k}}\left(\frac{1}{M_k^{t,S_k}}\left\langle J(x_k^{S_k})(x_k^{t,S_k}-x),\lambda_k^{t,S_k}-\tilde{\lambda}_k^{t,S_k}\right\rangle+\frac{\theta_k^{t,S_k}}{M_k^{t,S_k}}\left\langle J(x_k^{S_k})(x_k^{t,S_k}-x_k^{t-1,S_k}),\lambda_k^{t-1,S_k}-\lambda_k^{t-2,S_k}\right\rangle\right) \\
&=\frac{1}{M_k^{S_k}}\left\langle J(x_k^{S_k})(x_k-x),\lambda_k-\lambda_k^{T_k^{S_k}-1,S_k}\right\rangle-\frac{1}{M_k^{S_k}}\left\langle J(x_k^{S_k})(x_k^{1,S_k}-x),\lambda_k^{1,S_k}-\lambda_{k-1}\right\rangle, \tag*{(17)}
\end{aligned} t = 2 ∑ T k S k ( M k t , S k 1 ⟨ J ( x k S k ) ( x k t , S k − x ) , λ k t , S k − λ ~ k t , S k ⟩ + M k t , S k θ k t , S k ⟨ J ( x k S k ) ( x k t , S k − x k t − 1 , S k ) , λ k t − 1 , S k − λ k t − 2 , S k ⟩ ) = M k S k 1 ⟨ J ( x k S k ) ( x k − x ) , λ k − λ k T k S k − 1 , S k ⟩ − M k S k 1 ⟨ J ( x k S k ) ( x k 1 , S k − x ) , λ k 1 , S k − λ k − 1 ⟩ , (17)
where the last equality also uses the definitions of M k S k M_k^{S_k} M k S k , x k x_k x k , λ k \lambda_k λ k , and λ k 0 , S k \lambda_k^{0,S_k} λ k 0 , S k . This identity also holds when T k S k = 1 T_k^{S_k}=1 T k S k = 1 , with the sums interpreted as zero. Third, reindexing terms yields
− ∑ t = 1 T k S k p k t , S k 2 M k t , S k ∥ λ k t , S k − λ k t − 1 , S k ∥ 2 = − p k T k S k , S k 2 M k S k ∥ λ k − λ k T k S k − 1 , S k ∥ 2 − ∑ t = 2 T k S k p k t − 1 , S k 2 M k t − 1 , S k ∥ λ k t − 1 , S k − λ k t − 2 , S k ∥ 2 . (18) -\sum_{t=1}^{T_k^{S_k}}\frac{p_k^{t,S_k}}{2M_k^{t,S_k}}\left\|\lambda_k^{t,S_k}-\lambda_k^{t-1,S_k}\right\|^2=-\frac{p_k^{T_k^{S_k},S_k}}{2M_k^{S_k}}\left\|\lambda_k-\lambda_k^{T_k^{S_k}-1,S_k}\right\|^2-\sum_{t=2}^{T_k^{S_k}}\frac{p_k^{t-1,S_k}}{2M_k^{t-1,S_k}}\left\|\lambda_k^{t-1,S_k}-\lambda_k^{t-2,S_k}\right\|^2. \tag*{(18)} − t = 1 ∑ T k S k 2 M k t , S k p k t , S k λ k t , S k − λ k t − 1 , S k 2 = − 2 M k S k p k T k S k , S k λ k − λ k T k S k − 1 , S k 2 − t = 2 ∑ T k S k 2 M k t − 1 , S k p k t − 1 , S k λ k t − 1 , S k − λ k t − 2 , S k 2 . (18)
Fourth, by utilizing Cauchy–Schwarz inequality, the Jacobian–dual line-search condition described at line 6 and the relations θ k t , S k / M k t , S k = 1 / M k t − 1 , S k \theta_k^{t,S_k}/M_k^{t,S_k}=1/M_k^{t-1,S_k} θ k t , S k / M k t , S k = 1/ M k t − 1 , S k and p k t , S k / M k t , S k ≥ 3 p_k^{t,S_k}/M_k^{t,S_k}\ge3 p k t , S k / M k t , S k ≥ 3 , we have, for t ≥ 2 t\ge2 t ≥ 2 ,
− θ k t , S k M k t , S k ⟨ J ( x k S k ) ( x k t , S k − x k t − 1 , S k ) , λ k t − 1 , S k − λ k t − 2 , S k ⟩ − p k t − 1 , S k 2 M k t − 1 , S k ∥ λ k t − 1 , S k − λ k t − 2 , S k ∥ 2 − p k t , S k 6 M k t , S k ∥ x k t , S k − x k t − 1 , S k ∥ 2 ≤ ∥ λ k t − 1 , S k − λ k t − 2 , S k ∥ ∥ x k t , S k − x k t − 1 , S k ∥ − 3 2 ∥ λ k t − 1 , S k − λ k t − 2 , S k ∥ 2 − 1 2 ∥ x k t , S k − x k t − 1 , S k ∥ 2 ≤ 0. (19) \begin{aligned}
-\frac{\theta_k^{t,S_k}}{M_k^{t,S_k}}\left\langle J(x_k^{S_k})(x_k^{t,S_k}-x_k^{t-1,S_k}),\lambda_k^{t-1,S_k}-\lambda_k^{t-2,S_k}\right\rangle-\frac{p_k^{t-1,S_k}}{2M_k^{t-1,S_k}}\left\|\lambda_k^{t-1,S_k}-\lambda_k^{t-2,S_k}\right\|^2-\frac{p_k^{t,S_k}}{6M_k^{t,S_k}}\left\|x_k^{t,S_k}-x_k^{t-1,S_k}\right\|^2 \\
&\le\left\|\lambda_k^{t-1,S_k}-\lambda_k^{t-2,S_k}\right\|\left\|x_k^{t,S_k}-x_k^{t-1,S_k}\right\|-\frac{3}{2}\left\|\lambda_k^{t-1,S_k}-\lambda_k^{t-2,S_k}\right\|^2-\frac{1}{2}\left\|x_k^{t,S_k}-x_k^{t-1,S_k}\right\|^2\le0. \tag*{(19)}
\end{aligned} − M k t , S k θ k t , S k ⟨ J ( x k S k ) ( x k t , S k − x k t − 1 , S k ) , λ k t − 1 , S k − λ k t − 2 , S k ⟩ − 2 M k t − 1 , S k p k t − 1 , S k λ k t − 1 , S k − λ k t − 2 , S k 2 − 6 M k t , S k p k t , S k x k t , S k − x k t − 1 , S k 2 ≤ λ k t − 1 , S k − λ k t − 2 , S k x k t , S k − x k t − 1 , S k − 2 3 λ k t − 1 , S k − λ k t − 2 , S k 2 − 2 1 x k t , S k − x k t − 1 , S k 2 ≤ 0. (19)
Lastly, using the Cauchy–Schwarz inequality gives
− ⟨ J ( x k − 1 S k − 1 ) ( x k 1 , S k − x ) , λ k − 1 − λ k − 1 , S k ⟩ ≤ − ⟨ J ( x k − 1 S k − 1 ) ( x k − 1 − x ) , λ k − 1 − λ k − 1 , S k ⟩ + ∥ J ( x k − 1 S k − 1 ) T ( λ k − 1 − λ k − 1 , S k ) ∥ ∥ x k 1 , S k − x k − 1 ∥ . (20) \begin{aligned}
-\left\langle J(x_{k-1}^{S_k-1})(x_k^{1,S_k}-x),\lambda_{k-1}-\lambda_k^{-1,S_k}\right\rangle\\
&\le-\left\langle J(x_{k-1}^{S_k-1})(x_{k-1}-x),\lambda_{k-1}-\lambda_k^{-1,S_k}\right\rangle+\left\|J(x_{k-1}^{S_k-1})^{\mathsf T}(\lambda_{k-1}-\lambda_k^{-1,S_k})\right\|\left\|x_k^{1,S_k}-x_{k-1}\right\|. \tag*{(20)}
\end{aligned} − ⟨ J ( x k − 1 S k − 1 ) ( x k 1 , S k − x ) , λ k − 1 − λ k − 1 , S k ⟩ ≤ − ⟨ J ( x k − 1 S k − 1 ) ( x k − 1 − x ) , λ k − 1 − λ k − 1 , S k ⟩ + J ( x k − 1 S k − 1 ) T ( λ k − 1 − λ k − 1 , S k ) x k 1 , S k − x k − 1 . (20)
Substitute (8) from Proposition 4 at s = S k s=S_k s = S k and (15) into (14) . Then (9) follows from (16) –(20) , B k S k η k S k = 1 \mathcal{B}_k^{S_k}\eta_k^{S_k}=1 B k S k η k S k = 1 , the inner-loop initializations and the definitions of the accepted outer iterates. □
Proof of Theorem 2. Divide (9) by Γ k S k \Gamma_k^{S_k} Γ k S k and sum over k = 1 , … , N k=1,\ldots,N k = 1 , … , N . Since γ 1 S 1 = 1 \gamma_1^{S_1}=1 γ 1 S 1 = 1 and Γ k S k = Γ k − 1 S k − 1 ( 1 − γ k S k ) \Gamma_k^{S_k}=\Gamma_{k-1}^{S_{k-1}}(1-\gamma_k^{S_k}) Γ k S k = Γ k − 1 S k − 1 ( 1 − γ k S k ) for k ≥ 2 k\ge2 k ≥ 2 , the left-hand side telescopes:
G N ( x , λ ) Γ N S N = ∑ k = 1 N G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) Γ k S k ≤ ∑ k = 1 N ( E k + F k + R k ′ ( λ ) ) . (21) \frac{G_N(x,\lambda)}{\Gamma_N^{S_N}}=\sum_{k=1}^{N}\frac{G_k(x,\lambda)-(1-\gamma_k^{S_k})G_{k-1}(x,\lambda)}{\Gamma_k^{S_k}}\le\sum_{k=1}^{N}(E_k+F_k+R'_k(\lambda)). \tag*{(21)} Γ N S N G N ( x , λ ) = k = 1 ∑ N Γ k S k G k ( x , λ ) − ( 1 − γ k S k ) G k − 1 ( x , λ ) ≤ k = 1 ∑ N ( E k + F k + R k ′ ( λ )) . (21)
Here, the expression of E k E_k E k in (9) is structured so that its terms telescope over the outer iterations. To see this, the definition of p k t , S k p_k^{t,S_k} p k t , S k gives ( η k S k + p k S k , S k ) / M k S k = 3 + η k S k ∑ t = 1 T k S k 1 / M k t , S k = 3 + η k S k B k S k = 4 (\eta_k^{S_k}+p_k^{S_k,S_k})/M_k^{S_k}=3+\eta_k^{S_k}\sum_{t=1}^{T_k^{S_k}}1/M_k^{t,S_k}=3+\eta_k^{S_k}\mathcal{B}_k^{S_k}=4 ( η k S k + p k S k , S k ) / M k S k = 3 + η k S k ∑ t = 1 T k S k 1/ M k t , S k = 3 + η k S k B k S k = 4 and p k 1 , S k / M k 1 , S k = 3 p_k^{1,S_k}/M_k^{1,S_k}=3 p k 1 , S k / M k 1 , S k = 3 . Moreover, for k ≥ 2 k\ge2 k ≥ 2 , the parameter settings imply θ k 1 , S k / M k 1 , S k = 1 / M k − 1 S k − 1 \theta_k^{1,S_k}/M_k^{1,S_k}=1/M_{k-1}^{S_{k-1}} θ k 1 , S k / M k 1 , S k = 1/ M k − 1 S k − 1 , Δ k 1 , S k = Δ k − 1 T k − 1 S k − 1 , S k − 1 \Delta_k^{1,S_k}=\Delta_{k-1}^{T_{k-1}^{S_{k-1}},S_{k-1}} Δ k 1 , S k = Δ k − 1 T k − 1 S k − 1 , S k − 1 . Using Δ 1 0 , S 1 = 0 \Delta_1^{0,S_1}=0 Δ 1 0 , S 1 = 0 and λ 1 0 , S 1 − λ 1 − 1 , S 1 = 0 \lambda_1^{0,S_1}-\lambda_1^{-1,S_1}=0 λ 1 0 , S 1 − λ 1 − 1 , S 1 = 0 yields:
∑ k = 1 N E k ≤ 1 M N S N ⟨ Δ N T N S N , S N , x N − x ⟩ + 1 M N S N ⟨ J ( x N S N ) ( x N − x ) , λ N − λ N T N S N − 1 , S N ⟩ \sum_{k=1}^{N}E_k\le\frac{1}{M_N^{S_N}}\left\langle\Delta_N^{T_N^{S_N},S_N},x_N-x\right\rangle+\frac{1}{M_N^{S_N}}\left\langle J(x_N^{S_N})(x_N-x),\lambda_N-\lambda_N^{T_N^{S_N}-1,S_N}\right\rangle k = 1 ∑ N E k ≤ M N S N 1 ⟨ Δ N T N S N , S N , x N − x ⟩ + M N S N 1 ⟨ J ( x N S N ) ( x N − x ) , λ N − λ N T N S N − 1 , S N ⟩
+ 2 ( ∥ x − x 0 ∥ 2 + ∥ λ − λ 0 ∥ 2 − ∥ x − x N ∥ 2 ) . (22) \qquad+2\left(\|x-x_0\|^2+\|\lambda-\lambda_0\|^2-\|x-x_N\|^2\right). \tag*{(22)} + 2 ( ∥ x − x 0 ∥ 2 + ∥ λ − λ 0 ∥ 2 − ∥ x − x N ∥ 2 ) . (22)
Furthermore, the final inner-loop acceptance conditions in line 6 give ∥ Δ N T N S N , S N ∥ ≤ M N S N ∥ x N − x N T N S N − 1 , S N ∥ \|\Delta_N^{T_N^{S_N},S_N}\|\le M_N^{S_N}\|x_N-x_N^{T_N^{S_N}-1,S_N}\| ∥ Δ N T N S N , S N ∥ ≤ M N S N ∥ x N − x N T N S N − 1 , S N ∥ and ∥ J ( x N S N ) T ( λ N − λ N T N S N − 1 , S N ) ∥ ≤ M N S N ∥ λ N − λ N T N S N − 1 , S N ∥ \|J(x_N^{S_N})^{\mathsf T}(\lambda_N-\lambda_N^{T_N^{S_N}-1,S_N})\|\le M_N^{S_N}\|\lambda_N-\lambda_N^{T_N^{S_N}-1,S_N}\| ∥ J ( x N S N ) T ( λ N − λ N T N S N − 1 , S N ) ∥ ≤ M N S N ∥ λ N − λ N T N S N − 1 , S N ∥ . Using p N T N S N , S N / M N S N ≥ 3 p_N^{T_N^{S_N},S_N}/M_N^{S_N}\ge3 p N T N S N , S N / M N S N ≥ 3 and Cauchy–Schwarz inequality, we have, respectively,
1 M N S N ⟨ Δ N T N S N , S N , x N − x ⟩ − ∥ x − x N ∥ 2 ≤ p N T N S N , S N 6 M N S N ∥ x N − x N T N S N − 1 , S N ∥ 2 , \frac{1}{M_N^{S_N}}\left\langle\Delta_N^{T_N^{S_N},S_N},x_N-x\right\rangle-\|x-x_N\|^2\le\frac{p_N^{T_N^{S_N},S_N}}{6M_N^{S_N}}\left\|x_N-x_N^{T_N^{S_N}-1,S_N}\right\|^2, M N S N 1 ⟨ Δ N T N S N , S N , x N − x ⟩ − ∥ x − x N ∥ 2 ≤ 6 M N S N p N T N S N , S N x N − x N T N S N − 1 , S N 2 ,
1 M N S N ⟨ J ( x N S N ) ( x N − x ) , λ N − λ N T N S N − 1 , S N ⟩ − ∥ x − x N ∥ 2 ≤ p N T N S N , S N 2 M N S N ∥ λ N − λ N T N S N − 1 , S N ∥ 2 . \frac{1}{M_N^{S_N}}\left\langle J(x_N^{S_N})(x_N-x),\lambda_N-\lambda_N^{T_N^{S_N}-1,S_N}\right\rangle-\|x-x_N\|^2\le\frac{p_N^{T_N^{S_N},S_N}}{2M_N^{S_N}}\left\|\lambda_N-\lambda_N^{T_N^{S_N}-1,S_N}\right\|^2. M N S N 1 ⟨ J ( x N S N ) ( x N − x ) , λ N − λ N T N S N − 1 , S N ⟩ − ∥ x − x N ∥ 2 ≤ 2 M N S N p N T N S N , S N λ N − λ N T N S N − 1 , S N 2 .
Thus, substituting the above two inequalities into (22) gives
∑ k = 1 N E k ≤ 2 ( ∥ x − x 0 ∥ 2 + ∥ λ − λ 0 ∥ 2 ) + p N S N , S N 6 M N S N ∥ x N − x N T N − 1 , S N ∥ 2 + p N S N , S N 2 M N S N ∥ λ N − λ N T N − 1 , S N ∥ 2 . (23) \sum_{k=1}^{N} E_k \le2(\lVert x-x_0\rVert^2+\lVert\lambda-\lambda_0\rVert^2)+\frac{p_N^{S_N,S_N}}{6M_N^{S_N}}\lVert x_N-x_N^{T_{N-1,S_N}}\rVert^2+\frac{p_N^{S_N,S_N}}{2M_N^{S_N}}\lVert\lambda_N-\lambda_N^{T_{N-1,S_N}}\rVert^2. \tag*{(23)} k = 1 ∑ N E k ≤ 2 (∥ x − x 0 ∥ 2 + ∥ λ − λ 0 ∥ 2 ) + 6 M N S N p N S N , S N ∥ x N − x N T N − 1 , S N ∥ 2 + 2 M N S N p N S N , S N ∥ λ N − λ N T N − 1 , S N ∥ 2 . (23)
We now derive the following facts to bound ∑ k = 1 N F k \sum_{k=1}^{N}F_k ∑ k = 1 N F k . First, by changing indices and using the inner-loop initializations, we have
∑ k = 1 N p k T k S k , S k 6 M k S k ∥ x k − x k T k − 1 , S k ∥ 2 = p N T N S N , S N 6 M N S N ∥ x N − x N T N − 1 , S N ∥ 2 + ∑ k = 2 N p k − 1 T k − 1 S k − 1 , S k − 1 6 M k − 1 S k − 1 ∥ x k − 1 − x k T k − 1 , S k ∥ 2 , ∑ k = 1 N p k T k S k , S k 2 M k S k ∥ λ k − λ k T k − 1 , S k ∥ 2 = p N T N S N , S N 2 M N S N ∥ λ N − λ N T N − 1 , S N ∥ 2 + ∑ k = 2 N p k − 1 T k − 1 S k − 1 , S k − 1 2 M k − 1 S k − 1 ∥ λ k − 1 − λ k T k − 1 , S k ∥ 2 . (24) \begin{aligned}
\sum_{k=1}^{N}\frac{p_k^{T_{k}^{S_k},S_k}}{6M_k^{S_k}}\lVert x_k-x_k^{T_{k-1,S_k}}\rVert^2&=\frac{p_N^{T_N^{S_N},S_N}}{6M_N^{S_N}}\lVert x_N-x_N^{T_{N-1,S_N}}\rVert^2+\sum_{k=2}^{N}\frac{p_{k-1}^{T_{k-1}^{S_{k-1}},S_{k-1}}}{6M_{k-1}^{S_{k-1}}}\lVert x_{k-1}-x_k^{T_{k-1,S_k}}\rVert^2,\\
\sum_{k=1}^{N}\frac{p_k^{T_{k}^{S_k},S_k}}{2M_k^{S_k}}\lVert\lambda_k-\lambda_k^{T_{k-1,S_k}}\rVert^2&=\frac{p_N^{T_N^{S_N},S_N}}{2M_N^{S_N}}\lVert\lambda_N-\lambda_N^{T_{N-1,S_N}}\rVert^2+\sum_{k=2}^{N}\frac{p_{k-1}^{T_{k-1}^{S_{k-1}},S_{k-1}}}{2M_{k-1}^{S_{k-1}}}\lVert\lambda_{k-1}-\lambda_k^{T_{k-1,S_k}}\rVert^2. \tag*{(24)}
\end{aligned} k = 1 ∑ N 6 M k S k p k T k S k , S k ∥ x k − x k T k − 1 , S k ∥ 2 k = 1 ∑ N 2 M k S k p k T k S k , S k ∥ λ k − λ k T k − 1 , S k ∥ 2 = 6 M N S N p N T N S N , S N ∥ x N − x N T N − 1 , S N ∥ 2 + k = 2 ∑ N 6 M k − 1 S k − 1 p k − 1 T k − 1 S k − 1 , S k − 1 ∥ x k − 1 − x k T k − 1 , S k ∥ 2 , = 2 M N S N p N T N S N , S N ∥ λ N − λ N T N − 1 , S N ∥ 2 + k = 2 ∑ N 2 M k − 1 S k − 1 p k − 1 T k − 1 S k − 1 , S k − 1 ∥ λ k − 1 − λ k T k − 1 , S k ∥ 2 . (24)
Second, for k ≥ 2 k\ge2 k ≥ 2 , the final inner-loop acceptance conditions in line (4) imply ∥ Δ k 0 , S k ∥ ≤ M k − 1 S k − 1 ∥ x k − 1 − x k T k − 1 , S k ∥ \lVert\Delta_k^{0,S_k}\rVert\le M_{k-1}^{S_{k-1}}\lVert x_{k-1}-x_k^{T_{k-1,S_k}}\rVert ∥ Δ k 0 , S k ∥ ≤ M k − 1 S k − 1 ∥ x k − 1 − x k T k − 1 , S k ∥ and ∥ J ( x k T k − 1 , S k ) T ( λ k − 1 − λ k T k − 1 , S k ) ∥ ≤ M k − 1 S k − 1 ∥ λ k − 1 − λ k T k − 1 , S k ∥ \lVert J(x_k^{T_{k-1,S_k}})^{\mathsf{T}}(\lambda_{k-1}-\lambda_k^{T_{k-1,S_k}})\rVert\le M_{k-1}^{S_{k-1}}\lVert\lambda_{k-1}-\lambda_k^{T_{k-1,S_k}}\rVert ∥ J ( x k T k − 1 , S k ) T ( λ k − 1 − λ k T k − 1 , S k )∥ ≤ M k − 1 S k − 1 ∥ λ k − 1 − λ k T k − 1 , S k ∥ . Thus, utilizing the relations θ k 1 , S k / M k 1 , S k = 1 / M k − 1 S k − 1 \theta_k^{1,S_k}/M_k^{1,S_k}=1/M_{k-1}^{S_{k-1}} θ k 1 , S k / M k 1 , S k = 1/ M k − 1 S k − 1 , p k 1 , S k / M k 1 , S k = 3 p_k^{1,S_k}/M_k^{1,S_k}=3 p k 1 , S k / M k 1 , S k = 3 , and p k − 1 T k − 1 S k − 1 , S k − 1 / M k − 1 S k − 1 ≥ 3 p_{k-1}^{T_{k-1}^{S_{k-1}},S_{k-1}}/M_{k-1}^{S_{k-1}}\ge3 p k − 1 T k − 1 S k − 1 , S k − 1 / M k − 1 S k − 1 ≥ 3 guaranteed by the Algorithm 2, we obtain, for k ≥ 2 k\ge2 k ≥ 2 ,
θ k 1 , S k M k 1 , S k ∥ Δ k 0 , S k ∥ ∥ x k 1 , S k − x k − 1 ∥ − p k 1 , S k 6 M k 1 , S k ∥ x k 1 , S k − x k − 1 ∥ 2 − p k − 1 T k − 1 S k − 1 , S k − 1 6 M k − 1 S k − 1 ∥ x k − 1 − x k T k − 1 , S k ∥ 2 ≤ 0 , \frac{\theta_k^{1,S_k}}{M_k^{1,S_k}}\lVert\Delta_k^{0,S_k}\rVert\lVert x_k^{1,S_k}-x_{k-1}\rVert-\frac{p_k^{1,S_k}}{6M_k^{1,S_k}}\lVert x_k^{1,S_k}-x_{k-1}\rVert^2-\frac{p_{k-1}^{T_{k-1}^{S_{k-1}},S_{k-1}}}{6M_{k-1}^{S_{k-1}}}\lVert x_{k-1}-x_k^{T_{k-1,S_k}}\rVert^2\le0, M k 1 , S k θ k 1 , S k ∥ Δ k 0 , S k ∥ ∥ x k 1 , S k − x k − 1 ∥ − 6 M k 1 , S k p k 1 , S k ∥ x k 1 , S k − x k − 1 ∥ 2 − 6 M k − 1 S k − 1 p k − 1 T k − 1 S k − 1 , S k − 1 ∥ x k − 1 − x k T k − 1 , S k ∥ 2 ≤ 0 ,
θ k 1 , S k M k 1 , S k ∥ J ( x k T k − 1 , S k ) T ( λ k − 1 − λ k T k − 1 , S k ) ∥ ∥ x k 1 , S k − x k − 1 ∥ − p k 1 , S k 6 M k 1 , S k ∥ x k 1 , S k − x k − 1 ∥ 2 − p k − 1 T k − 1 S k − 1 , S k − 1 2 M k − 1 S k − 1 ∥ λ k − 1 − λ k T k − 1 , S k ∥ 2 ≤ 0. (25) \frac{\theta_k^{1,S_k}}{M_k^{1,S_k}}\lVert J(x_k^{T_{k-1,S_k}})^{\mathsf{T}}(\lambda_{k-1}-\lambda_k^{T_{k-1,S_k}})\rVert\lVert x_k^{1,S_k}-x_{k-1}\rVert-\frac{p_k^{1,S_k}}{6M_k^{1,S_k}}\lVert x_k^{1,S_k}-x_{k-1}\rVert^2-\frac{p_{k-1}^{T_{k-1}^{S_{k-1}},S_{k-1}}}{2M_{k-1}^{S_{k-1}}}\lVert\lambda_{k-1}-\lambda_k^{T_{k-1,S_k}}\rVert^2\le0. \tag*{(25)} M k 1 , S k θ k 1 , S k ∥ J ( x k T k − 1 , S k ) T ( λ k − 1 − λ k T k − 1 , S k )∥ ∥ x k 1 , S k − x k − 1 ∥ − 6 M k 1 , S k p k 1 , S k ∥ x k 1 , S k − x k − 1 ∥ 2 − 2 M k − 1 S k − 1 p k − 1 T k − 1 S k − 1 , S k − 1 ∥ λ k − 1 − λ k T k − 1 , S k ∥ 2 ≤ 0. (25)
Applying (24) and (25) , using Δ 1 0 , S 1 = 0 \Delta_1^{0,S_1}=0 Δ 1 0 , S 1 = 0 and λ 0 − λ 1 T 0 , S 1 = 0 \lambda_0-\lambda_1^{T_{0,S_1}}=0 λ 0 − λ 1 T 0 , S 1 = 0 , and dropping the nonpositive term − p 1 1 , S 1 ∥ x 1 1 , S 1 − x 0 ∥ 2 / ( 3 M 1 1 , S 1 ) -p_1^{1,S_1}\lVert x_1^{1,S_1}-x_0\rVert^2/(3M_1^{1,S_1}) − p 1 1 , S 1 ∥ x 1 1 , S 1 − x 0 ∥ 2 / ( 3 M 1 1 , S 1 ) , we obtain
∑ k = 1 N F k ≤ − p N T N S N , S N 6 M N S N ∥ x N − x N T N − 1 , S N ∥ 2 − p N T N S N , S N 2 M N S N ∥ λ N − λ N T N − 1 , S N ∥ 2 . \sum_{k=1}^{N}F_k\le-\frac{p_N^{T_N^{S_N},S_N}}{6M_N^{S_N}}\lVert x_N-x_N^{T_{N-1,S_N}}\rVert^2-\frac{p_N^{T_N^{S_N},S_N}}{2M_N^{S_N}}\lVert\lambda_N-\lambda_N^{T_{N-1,S_N}}\rVert^2. k = 1 ∑ N F k ≤ − 6 M N S N p N T N S N , S N ∥ x N − x N T N − 1 , S N ∥ 2 − 2 M N S N p N T N S N , S N ∥ λ N − λ N T N − 1 , S N ∥ 2 .
Proof of Lemma 4. For any u , v ∈ X u,v\in X u , v ∈ X , the smoothness of the component functions gives
∥ G ( v ) − G ( u ) − J ( u ) ( v − u ) ∥ 2 = ∑ i = 1 m [ g i ( v ) − g i ( u ) − ⟨ ∇ g i ( u ) , v − u ⟩ ] 2 ≤ L 2 4 ∥ v − u ∥ 4 . \lVert G(v)-G(u)-J(u)(v-u)\rVert^2=\sum_{i=1}^{m}[g_i(v)-g_i(u)-\langle\nabla g_i(u),v-u\rangle]^2\le\frac{L^2}{4}\lVert v-u\rVert^4. ∥ G ( v ) − G ( u ) − J ( u ) ( v − u ) ∥ 2 = i = 1 ∑ m [ g i ( v ) − g i ( u ) − ⟨ ∇ g i ( u ) , v − u ⟩ ] 2 ≤ 4 L 2 ∥ v − u ∥ 4 .
Hence, the middle-loop acceptance condition of MC-PFAOS is guaranteed whenever η k s / γ k s ≥ Λ L \eta_k^s/\gamma_k^s\ge\Lambda L η k s / γ k s ≥ Λ L . Since the updates of η k s \eta_k^s η k s and γ k s \gamma_k^s γ k s , and the definition of Γ k s \Gamma_k^s Γ k s , are the same as those in PFAOS, the remaining proof of Lemma 3 applies. □
Proof of Corollary 2. For any x ∈ X ~ x\in\widetilde{X} x ∈ X , since G ( x ) ≤ 0 G(x)\le0 G ( x ) ≤ 0 and λ N ≥ 0 \lambda_N\ge0 λ N ≥ 0 componentwise, Theorem 2 and λ 0 = 0 \lambda_0=0 λ 0 = 0 give
⟨ F ( x ) , x N − x ⟩ ≤ G N ( x , 0 ) ≤ 2 Γ N S N D X 2 . \langle F(x),x_N-x\rangle\le G_N(x,0)\le2\Gamma_N^{S_N}D_X^2. ⟨ F ( x ) , x N − x ⟩ ≤ G N ( x , 0 ) ≤ 2 Γ N S N D X 2 .
Taking the supremum over x ∈ X ~ x\in\widetilde{X} x ∈ X gives the weak VI gap bound in terms of Γ N S N \Gamma_N^{S_N} Γ N S N .
For the constraint violation, the claim is immediate if [ G ( x ˉ N ) ] + = 0 [G(\bar{x}_N)]_+=0 [ G ( x ˉ N ) ] + = 0 . Otherwise, define u N : = [ G ( x ˉ N ) ] + / ∥ [ G ( x ˉ N ) ] + ∥ u_N:=[G(\bar{x}_N)]_+/\lVert[G(\bar{x}_N)]_+\rVert u N := [ G ( x ˉ N ) ] + / ∥[ G ( x ˉ N ) ] + ∥ . By (3) and convexity of the component functions,
⟨ F ( x ∗ ) , x ˉ N − x ∗ ⟩ ≥ − ⟨ J ( x ∗ ) T λ ∗ , x ˉ N − x ∗ ⟩ ≥ − ⟨ λ ∗ , G ( x ˉ N ) − G ( x ∗ ) ⟩ = − ⟨ λ ∗ , G ( x ˉ N ) ⟩ ≥ − ∥ λ ∗ ∥ ∥ [ G ( x ˉ N ) ] + ∥ . \langle F(x^*),\bar{x}_N-x^*\rangle\ge-\langle J(x^*)^{\mathsf{T}}\lambda^*,\bar{x}_N-x^*\rangle\ge-\langle\lambda^*,G(\bar{x}_N)-G(x^*)\rangle=-\langle\lambda^*,G(\bar{x}_N)\rangle\ge-\lVert\lambda^*\rVert\lVert[G(\bar{x}_N)]_+\rVert. ⟨ F ( x ∗ ) , x ˉ N − x ∗ ⟩ ≥ − ⟨ J ( x ∗ ) T λ ∗ , x ˉ N − x ∗ ⟩ ≥ − ⟨ λ ∗ , G ( x ˉ N ) − G ( x ∗ )⟩ = − ⟨ λ ∗ , G ( x ˉ N )⟩ ≥ − ∥ λ ∗ ∥ ∥[ G ( x ˉ N ) ] + ∥ .
Since Λ u N ∈ R + m \Lambda u_N\in\mathbb{R}_+^m Λ u N ∈ R + m , ∥ Λ u N ∥ = Λ \lVert\Lambda u_N\rVert=\Lambda ∥ Λ u N ∥ = Λ , and ⟨ G ( x ˉ N ) , u N ⟩ = ∥ [ G ( x ˉ N ) ] + ∥ \langle G(\bar{x}_N),u_N\rangle=\lVert[G(\bar{x}_N)]_+\rVert ⟨ G ( x ˉ N ) , u N ⟩ = ∥[ G ( x ˉ N ) ] + ∥ , using G ( x ∗ ) ≤ 0 G(x^*)\le0 G ( x ∗ ) ≤ 0 and λ N ≥ 0 \lambda_N\ge0 λ N ≥ 0 gives
( Λ − ∥ λ ∗ ∥ ) ∥ [ G ( x ˉ N ) ] + ∥ ≤ ⟨ F ( x ∗ ) , x ˉ N − x ∗ ⟩ + Λ ⟨ G ( x ˉ N ) , u N ⟩ ≤ G N ( x ∗ , Λ u N ) ≤ 2 Γ N S N ( D X 2 + Λ 2 ) . (\Lambda-\lVert\lambda^*\rVert)\lVert[G(\bar{x}_N)]_+\rVert\le\langle F(x^*),\bar{x}_N-x^*\rangle+\Lambda\langle G(\bar{x}_N),u_N\rangle\le G_N(x^*,\Lambda u_N)\le2\Gamma_N^{S_N}(D_X^2+\Lambda^2). ( Λ − ∥ λ ∗ ∥) ∥[ G ( x ˉ N ) ] + ∥ ≤ ⟨ F ( x ∗ ) , x ˉ N − x ∗ ⟩ + Λ ⟨ G ( x ˉ N ) , u N ⟩ ≤ G N ( x ∗ , Λ u N ) ≤ 2 Γ N S N ( D X 2 + Λ 2 ) .
The explicit rates follow from Lemma 4. □
Proof of Proposition 6. Let N ε ≥ 1 N_{\varepsilon} \ge1 N ε ≥ 1 be the first outer iteration satisfying 2 Γ N ε S N ε ( D X 2 + Λ 2 ) ≤ ε 2\Gamma_{N_{\varepsilon}}^{S_{N_{\varepsilon}}}(D_X^2+\Lambda^2) \le\varepsilon 2 Γ N ε S N ε ( D X 2 + Λ 2 ) ≤ ε . By Corollary 2, x ˉ N ε \bar{x}_{N_{\varepsilon}} x ˉ N ε is an ε \varepsilon ε -approximate solution of (2) and
N ε ≤ 1 + 32 Λ L ( D X 2 + Λ 2 ) ε . N_{\varepsilon} \le1+\sqrt{\frac{32\Lambda L(D_X^2+\Lambda^2)}{\varepsilon}}. N ε ≤ 1 + ε 32Λ L ( D X 2 + Λ 2 ) .
Each middle trial requires one evaluation of J J J . Thus, the counting argument in Proposition 3, gives at most 1 + 2 N ε + ⌈ log 2 2 L L 0 ⌉ 1+2N_{\varepsilon}+\lceil\log_2 \frac{2L}{L_0}\rceil 1 + 2 N ε + ⌈ log 2 L 0 2 L ⌉ Jacobian evaluations, including initialization. Using the bound on N ε N_{\varepsilon} N ε yields the stated complexity. For the operator evaluations, max x ∈ X ∥ J ( x ) ∥ < ∞ \max_{x\in X}\|J(x)\|<\infty max x ∈ X ∥ J ( x ) ∥ < ∞ because X X X is compact and J J J is continuous. Both inner line-search conditions hold whenever M k t , S k ≥ max { M , max x ∈ X ∥ J ( x ) ∥ } M_k^{t,S_k}\ge\max\{M,\max_{x\in X}\|J(x)\|\} M k t , S k ≥ max { M , max x ∈ X ∥ J ( x ) ∥ } .
Thus, whenever backtracking occurs, the minimality of q k t , S k q_k^{t,S_k} q k t , S k gives M k t , S k < 2 max { M , max x ∈ X ∥ J ( x ) ∥ } M_k^{t,S_k}<2\max\{M,\max_{x\in X}\|J(x)\|\} M k t , S k < 2 max { M , max x ∈ X ∥ J ( x ) ∥ } . Moreover, since M 0 ≤ 2 Λ L M_0\le2\Lambda L M 0 ≤ 2Λ L and η k S k ≤ η k S k / γ k S k ≤ 4 Λ L \eta_k^{S_k}\le\eta_k^{S_k}/\gamma_k^{S_k}\le4\Lambda L η k S k ≤ η k S k / γ k S k ≤ 4Λ L , the initialization M k 0 , S k = max { η k S k , M k S k − 1 } M_k^{0,S_k}=\max\{\eta_k^{S_k},M_k^{S_k-1}\} M k 0 , S k = max { η k S k , M k S k − 1 } preserves the bound M ‾ M C \overline{M}_{\mathrm{MC}} M MC , while an inner update without backtracking leaves the estimate unchanged. Induction therefore yields M k t , S k ≤ M ‾ M C M_k^{t,S_k}\le\overline{M}_{\mathrm{MC}} M k t , S k ≤ M MC for every executed inner iteration. Using this bound and the invariant η k S k B k S k = 1 \eta_k^{S_k}\mathcal{B}_k^{S_k}=1 η k S k B k S k = 1 , we repeat the counting argument in Proposition 3, now with the stopping condition 2 Γ N ε S N ε ( D X 2 + Λ 2 ) ≤ ε 2\Gamma_{N_{\varepsilon}}^{S_{N_{\varepsilon}}}(D_X^2+\Lambda^2)\le\varepsilon 2 Γ N ε S N ε ( D X 2 + Λ 2 ) ≤ ε , to obtain the stated operator complexity. □
Proofs for Section 5
Proof of Proposition 7. Using relations Γ k S k = γ k S k η k S k \Gamma_k^{S_k}=\gamma_k^{S_k}\eta_k^{S_k} Γ k S k = γ k S k η k S k , η k S k B k S k = 1 \eta_k^{S_k}\mathcal{B}_k^{S_k}=1 η k S k B k S k = 1 , γ 1 S 1 = 1 \gamma_1^{S_1}=1 γ 1 S 1 = 1 and Γ k S k = ( 1 − γ k S k ) Γ k − 1 S k − 1 \Gamma_k^{S_k}=(1-\gamma_k^{S_k})\Gamma_{k-1}^{S_{k-1}} Γ k S k = ( 1 − γ k S k ) Γ k − 1 S k − 1 , k ≥ 2 k\ge2 k ≥ 2 give
Γ N S N ∑ k = 1 N ∑ t = 1 T k S k 1 M k t , S k = Γ N S N ∑ k = 1 N 1 η k S k = 1 , Γ N S N ∑ k = 1 N ∑ t = 1 T k S k x k t , S k M k t , S k = Γ N S N ∑ k = 1 N B k S k x ^ k = x ˉ N . \Gamma_N^{S_N}\sum_{k=1}^{N}\sum_{t=1}^{T_k^{S_k}}\frac{1}{M_k^{t,S_k}}
=\Gamma_N^{S_N}\sum_{k=1}^{N}\frac{1}{\eta_k^{S_k}}=1,
\qquad
\Gamma_N^{S_N}\sum_{k=1}^{N}\sum_{t=1}^{T_k^{S_k}}\frac{x_k^{t,S_k}}{M_k^{t,S_k}}
=\Gamma_N^{S_N}\sum_{k=1}^{N}\mathcal{B}_k^{S_k}\hat{x}_k=\bar{x}_N. Γ N S N k = 1 ∑ N t = 1 ∑ T k S k M k t , S k 1 = Γ N S N k = 1 ∑ N η k S k 1 = 1 , Γ N S N k = 1 ∑ N t = 1 ∑ T k S k M k t , S k x k t , S k = Γ N S N k = 1 ∑ N B k S k x ^ k = x ˉ N .
Then, for any x ∈ X ~ x\in\widetilde{X} x ∈ X , monotonicity of F F F and convexity of the constraints give
⟨ F ( x ) , x ˉ N − x ⟩ = Γ N S N ∑ k = 1 N ∑ t = 1 T k S k ⟨ F ( x ) , x k t , S k − x ⟩ M k t , S k ≤ Γ N S N ∑ k = 1 N ∑ t = 1 T k S k ⟨ F ( x k t , S k ) , x k t , S k − x ⟩ M k t , S k ≤ Φ N ( x ) , \langle F(x),\bar{x}_N-x\rangle
=\Gamma_N^{S_N}\sum_{k=1}^{N}\sum_{t=1}^{T_k^{S_k}}\frac{\langle F(x),x_k^{t,S_k}-x\rangle}{M_k^{t,S_k}}
\le\Gamma_N^{S_N}\sum_{k=1}^{N}\sum_{t=1}^{T_k^{S_k}}\frac{\langle F(x_k^{t,S_k}),x_k^{t,S_k}-x\rangle}{M_k^{t,S_k}}
\le\Phi_N(x), ⟨ F ( x ) , x ˉ N − x ⟩ = Γ N S N k = 1 ∑ N t = 1 ∑ T k S k M k t , S k ⟨ F ( x ) , x k t , S k − x ⟩ ≤ Γ N S N k = 1 ∑ N t = 1 ∑ T k S k M k t , S k ⟨ F ( x k t , S k ) , x k t , S k − x ⟩ ≤ Φ N ( x ) ,
where the last inequality uses ρ k S k ( x ) ≤ G ( x ) ≤ 0 \rho_k^{S_k}(x)\le G(x)\le0 ρ k S k ( x ) ≤ G ( x ) ≤ 0 and λ k t , S k ≥ 0 \lambda_k^{t,S_k}\ge0 λ k t , S k ≥ 0 componentwise. Taking the supremum over X ~ ⊆ X \widetilde{X}\subseteq X X ⊆ X proves the weak VI gap bound.
To bound the certificate, retain ⟨ F ( x k t , S k ) , x k t , S k − x ⟩ \langle F(x_k^{t,S_k}),x_k^{t,S_k}-x\rangle ⟨ F ( x k t , S k ) , x k t , S k − x ⟩ in the inner-loop optimality inequalities, before applying monotonicity, and set the test multiplier to λ = 0 \lambda=0 λ = 0 . Specifically, for PFAOS, the proof of Proposition 1, with the affine constraint term moved to the left, gives
∑ t = 1 T k S k ⟨ F ( x k t , S k ) , x k t , S k − x ⟩ − λ k t , S k ρ k S k ( x ) M k t , S k ≤ H k + I k Γ k S k − 1 2 ∥ x ^ k − x k − 1 ∥ 2 , \sum_{t=1}^{T_k^{S_k}}\frac{\langle F(x_k^{t,S_k}),x_k^{t,S_k}-x\rangle-\lambda_k^{t,S_k}\rho_k^{S_k}(x)}{M_k^{t,S_k}}
\le\frac{H_k+I_k}{\Gamma_k^{S_k}}-\frac{1}{2}\|\hat{x}_k-x_{k-1}\|^2, t = 1 ∑ T k S k M k t , S k ⟨ F ( x k t , S k ) , x k t , S k − x ⟩ − λ k t , S k ρ k S k ( x ) ≤ Γ k S k H k + I k − 2 1 ∥ x ^ k − x k − 1 ∥ 2 ,
where H k H_k H k and I k I_k I k are defined in Proposition 2. Summing over k k k and applying the telescoping and endpoint estimates in the proof of Theorem 1 yields
Φ N ( x ) Γ N S N ≤ ∑ k = 1 N H k + I k Γ k S k − 1 2 ∑ k = 1 N ∥ x ^ k − x k − 1 ∥ 2 ≤ 3 2 ∥ x − x 0 ∥ 2 . \frac{\Phi_N(x)}{\Gamma_N^{S_N}}
\le\sum_{k=1}^{N}\frac{H_k+I_k}{\Gamma_k^{S_k}}-\frac{1}{2}\sum_{k=1}^{N}\|\hat{x}_k-x_{k-1}\|^2
\le\frac{3}{2}\|x-x_0\|^2. Γ N S N Φ N ( x ) ≤ k = 1 ∑ N Γ k S k H k + I k − 2 1 k = 1 ∑ N ∥ x ^ k − x k − 1 ∥ 2 ≤ 2 3 ∥ x − x 0 ∥ 2 .
While for MC-PFAOS, retain the same operator term in Proposition 4 and use the affine cancellation in (16) . The resulting sum is bounded by
Φ N ( x ) Γ N S N ≤ ∑ k = 1 N ( E k + F k ) ∣ λ = 0 − 1 2 ∑ k = 1 N ∥ x ^ k − x k − 1 ∥ 2 ≤ 2 ∥ x − x 0 ∥ 2 , \frac{\Phi_N(x)}{\Gamma_N^{S_N}}
\le\sum_{k=1}^{N}(E_k+F_k)\big|_{\lambda=0}-\frac{1}{2}\sum_{k=1}^{N}\|\hat{x}_k-x_{k-1}\|^2
\le2\|x-x_0\|^2, Γ N S N Φ N ( x ) ≤ k = 1 ∑ N ( E k + F k ) λ = 0 − 2 1 k = 1 ∑ N ∥ x ^ k − x k − 1 ∥ 2 ≤ 2∥ x − x 0 ∥ 2 ,
where the last inequality follows from the bounds on ∑ k E k \sum_k E_k ∑ k E k and ∑ k F k \sum_k F_k ∑ k F k in the proof of Theorem 2 and λ 0 = 0 \lambda_0=0 λ 0 = 0 . Maximizing over X X X and taking the positive part proves the stated certificate bounds. The same arguments apply to retained trials of Algorithm 3 and 4, as in Lemma 6. □
Proof of Proposition 8. The accuracy claim follows directly from Proposition 7 . Suppose now that Λ ≥ ∥ λ ∗ ∥ + 1 \Lambda\ge\lVert\lambda^* \rVert+ 1 Λ ≥ ∥ λ ∗ ∥ + 1 .
By Proposition 7 and Corollaries 1 and 2, both conditions in (14) hold whenever 3 2 Γ N S N D X 2 ≤ ε \frac{3}{2}\Gamma_N^{S_N}D_X^2 \le\varepsilon 2 3 Γ N S N D X 2 ≤ ε for PFAOS or 2 Γ N S N ( D X 2 + Λ 2 ) ≤ ε 2\Gamma_N^{S_N}(D_X^2+\Lambda^2) \le\varepsilon 2 Γ N S N ( D X 2 + Λ 2 ) ≤ ε for MC-PFAOS. Thus, the rule stops no later than the thresholds used in the original counting arguments.
The same implication holds for every trial at k = 1 k=1 k = 1 that passes the middle test. If a trial fails the new stopping test, it also fails the original accuracy test. Consequently, for a final tested index s ≥ 2 s \ge2 s ≥ 2 , the lower bounds η 1 s > ε / ( 3 D X 2 ) \eta_1^s > \varepsilon/(3D_X^2) η 1 s > ε / ( 3 D X 2 ) for PFAOS and η 1 s > ε / [ 4 ( D X 2 + Λ 2 ) ] \eta_1^s > \varepsilon/[4(D_X^2+\Lambda^2)] η 1 s > ε / [ 4 ( D X 2 + Λ 2 )] for MC-PFAOS used in Lemma 5 remain valid. If the search continues to k = 2 k=2 k = 2 , it still retains the trial preceding a failed middle test, so η 1 S 1 < 2 Λ L \eta_1^{S_1} < 2\Lambda L η 1 S 1 < 2Λ L . Hence, the first-iteration and subsequent counting arguments apply unchanged. Certificate construction uses stored oracle values, and G ( x ˉ N ) G(\bar{x}_N) G ( x ˉ N ) is already evaluated by the middle test, so the rule requires no additional evaluations of F F F , ∇ g \nabla g ∇ g , or J J J . □