Introduction
Modern convex and quasiconvex optimization rests on classical existence and convergence results, from Polyak’s foundational work on minimizing sequences under constraints [23 ] to Rockafellar’s monotone operator theory and proximal point algorithm [24 ] . Clarke’s theory of generalized differentiation for locally Lipschitz functions [4 ] later provided the tools needed to analyze subgradient and projection-type algorithms in nonsmooth settings. Vial [26 ] and Jovanovic [10 ] clarified the structural differences between convex, strongly convex, and quasiconvex functions, while Nesterov’s work on nonsmooth convex and quasiconvex minimization [18 , 19 , 20 ] introduced algorithmic principles later extended by Nesterov and Spokoiny [21 ] to derivative-free, gradient-free (two-point finite-difference) methods with optimal complexity guarantees via Gaussian smoothing.
More recently, attention has turned to strongly quasiconvex functions, a class bridging convexity and quasiconvexity while retaining useful stability and convergence properties. A series of works [3 , 8 , 9 , 11 , 15 , 16 ] established existence results, characterizations, and algorithmic schemes (proximal point and subgradient projection methods) for quasiconvex and strongly quasiconvex problems, including convergence via strong subdifferentials [11 ] under assumptions analogous to the convex case, and a quasi-linear convergence rate for the iterates. Related dynamical-system interpretations and gradient-based methods appear in [9 , 16 ] ; see the survey [6 ] for a fuller account.
Stochastic and gradient-free methods for quasiconvex optimization have also gained recent attention. Khachatryan [13 ] studied stochastic finite-difference methods for quasiconvex black-box optimization with a maximum-type objective f ( x ) = max i ∈ I f i ( x ) f(x) = \max_{i \in I} f_i(x) f ( x ) = max i ∈ I f i ( x ) , where each f i f_i f i is quasiconvex with Lipschitz-continuous gradient on a convex compact set, obtaining an O ( 1 / k ) O(1/\sqrt{k}) O ( 1/ k ) convergence rate. However, the feasible set there is a plain set constraint x ∈ M x \in M x ∈ M ; no inequality constraints f i ( x ) ≤ 0 f_i(x) \le0 f i ( x ) ≤ 0 with quasiconvex f i f_i f i are considered, so constrained quasiconvex optimization and structure-preserving penalty functions remain unaddressed.
Zeroth-order methods for functionally constrained optimization have also been developed, notably by Nguyen and Balasubramanian [22 ] and by Li et al. [17 ] , who proposed a zeroth-order inexact augmented Lagrangian method for composite problems with functional constraints. These works motivate studying stochastic zeroth-order methods in the quasiconvex setting considered here.
Finally, Gasnikov et al. [5 ] recently studied smooth quasiconvex optimization in the comparison-oracle model, obtaining complexity guarantees from function-value comparisons alone, situating quasiconvex optimization within the broader family of oracle-based and zeroth-order methods.
Our contributions. This paper broadens the convergence theory of stochastic finite-difference methods from convex to quasiconvex optimization. This is not merely a formal weakening of assumptions: quasiconvexity includes nonconvex, nonsmooth functions lying outside the classical convex framework, and since the convex subgradient inequality is no longer available, the analysis instead exploits geometric relations between generalized gradients, distances to optimal solutions, and the structure of quasiconvex and strongly quasiconvex functions. On this basis, we develop a convergence theory for stochastic finite-difference methods on locally Lipschitz quasiconvex functions, covering problems outside the standard convex setting, and we establish convergence results and rates for the strongly quasiconvex case; since every strongly convex function is strongly quasiconvex but not conversely, this framework strictly contains the classical strongly convex setting. We further extend the analysis to constrained quasiconvex optimization through a penalty-function method for problems with strongly quasiconvex functional constraints, proving convergence under suitable regularity and nondegeneracy assumptions even when the constraints are nonconvex. Throughout, local Lipschitz continuity and these nondegeneracy conditions stand in for the missing convex structure, and the resulting rates give quantitative guarantees for a substantially broader, genuinely nonconvex class of problems than the classical convex theory covers.
The paper is organized as follows. Section 2 recalls preliminaries on generalized convexity and nonsmooth analysis. Section 3 presents a subgradient method for locally Lipschitz strongly quasiconvex functions based on the Clarke subdifferential, with a complete convergence analysis for both iterates and function values. Section 4 develops a stochastic finite-difference method for a mathematical programming problem whose constraint functions are locally Lipschitz and strongly quasiconvex and whose objective is locally Lipschitz and quasiconvex, establishing a convergence rate of O ( k − 1 / 4 ) O(k^{-1/4}) O ( k − 1/4 ) under mild assumptions. Section 5 develops a penalty function method for the same problem under quasiconvexity alone, giving a sufficient condition for convergence of the generated sequence to the optimal solution. Numerical illustrations support our theoretical findings.
Preliminaries and Basic Definitions
The inner product of R n \mathbb{R}^{n} R n and the Euclidean norm are denoted by ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ and ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ , respectively. The closed ball with center at x 0 ∈ R n x_{0}\in\mathbb{R}^{n} x 0 ∈ R n and radius ε > 0 \varepsilon>0 ε > 0 is denoted by B ε ( x 0 ) B_{\varepsilon}(x_{0}) B ε ( x 0 ) .
Given any extended-valued function h : R n → R ‾ h:\mathbb{R}^{n}\to\overline{\mathbb{R}} h : R n → R , the effective domain of h h h is defined by dom h : = { x ∈ R n : h ( x ) < + ∞ } \operatorname{dom}h:=\{x\in\mathbb{R}^{n}:h(x)<+\infty\} dom h := { x ∈ R n : h ( x ) < + ∞ } .
A function h h h with convex domain is said to be:
(a) (strongly) convex on dom h \operatorname{dom}h dom h , if there exists μ ≥ 0 \mu\geq0 μ ≥ 0 such that, for all x , y ∈ dom h x,y\in\operatorname{dom}h x , y ∈ dom h and all λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , we have
h ( λ y + ( 1 − λ ) x ) ≤ λ h ( y ) + ( 1 − λ ) h ( x ) − λ ( 1 − λ ) μ 2 ∥ x − y ∥ 2 . (1) h(\lambda y+(1-\lambda)x)\leq\lambda h(y)+(1-\lambda)h(x)-\lambda(1-\lambda)\frac{\mu}{2}\lVert x-y\rVert^{2}. \tag*{(1)} h ( λ y + ( 1 − λ ) x ) ≤ λh ( y ) + ( 1 − λ ) h ( x ) − λ ( 1 − λ ) 2 μ ∥ x − y ∥ 2 . (1)
(b) (strongly) quasiconvex on dom h \operatorname{dom}h dom h , if there exists μ ≥ 0 \mu\geq0 μ ≥ 0 such that, for all x , y ∈ dom h x,y\in\operatorname{dom}h x , y ∈ dom h and all λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , we have
h ( λ y + ( 1 − λ ) x ) ≤ max { h ( y ) , h ( x ) } − λ ( 1 − λ ) μ 2 ∥ x − y ∥ 2 . (2) h(\lambda y+(1-\lambda)x)\leq\max\{h(y),h(x)\}-\lambda(1-\lambda)\frac{\mu}{2}\lVert x-y\rVert^{2}. \tag*{(2)} h ( λ y + ( 1 − λ ) x ) ≤ max { h ( y ) , h ( x )} − λ ( 1 − λ ) 2 μ ∥ x − y ∥ 2 . (2)
A function is strongly convex (resp. quasiconvex) when μ > 0 \mu> 0 μ > 0 , and convex (resp. quasiconvex) when μ = 0 \mu= 0 μ = 0 . Hence, every (strongly) convex function is (strongly) quasiconvex, while the reverse statements does not hold in general (see [2, 7, 15]).
A locally Lipschitz function f f f is called regular in the sense of Clarke on M M M if, for every x ∈ M x \in M x ∈ M and every v ∈ R n v \in\mathbb{R}^{n} v ∈ R n , the ordinary directional derivative exists and satisfies
f ′ ( x ; v ) = f ∘ ( x ; v ) . f^{\prime}(x;v)=f^{\circ}(x;v). f ′ ( x ; v ) = f ∘ ( x ; v ) .
Remark 1. (i) Let us construct an example of a strongly quasiconvex function that is locally Lipschitz, not differentiable at all points, and not convex. Indeed, let f : R → R f : \mathbb{R} \to\mathbb{R} f : R → R be the function given by
f ( x ) = max { f 1 ( x ) , f 2 ( x ) } , f(x)=\max\{f_{1}(x),f_{2}(x)\}, f ( x ) = max { f 1 ( x ) , f 2 ( x )} ,
where f 1 ( x ) = max { 0 , x } + ∣ x ∣ 2 f_{1}(x)=\max\{0,x\}+|x|^{2} f 1 ( x ) = max { 0 , x } + ∣ x ∣ 2 and f 2 ( x ) = x 2 + 2 sin 2 ( x ) f_{2}(x)=x^{2}+2\sin^{2}(x) f 2 ( x ) = x 2 + 2 sin 2 ( x ) .
Here, f 1 f_{1} f 1 is strongly convex, thus strongly quasiconvex with modulus μ 1 = 2 \mu_{1}=2 μ 1 = 2 . The function f 2 f_{2} f 2 is also strongly quasiconvex with modulus μ 2 = 1 2 \mu_{2}=\frac{1}{2} μ 2 = 2 1 (see [16, Example 30]).
Since the maximum of strongly quasiconvex functions is again strongly quasiconvex [27 Corollary 2] , it follows that f f f is strongly quasiconvex on the whole domain with modulus μ : = min { μ 1 , μ 2 } = 1 2 \mu:=\min\{\mu_{1},\mu_{2}\}=\frac{1}{2} μ := min { μ 1 , μ 2 } = 2 1 .
On the other hand, note that f f f is locally Lipschitz as the maximum of two locally Lipschitz functions, it is not differentiable at points where f 1 ( x ) = f 2 ( x ) f_{1}(x)=f_{2}(x) f 1 ( x ) = f 2 ( x ) , and it is not convex due to f 2 f_{2} f 2 .
(ii) Let h : R n → R h : \mathbb{R}^{n} \to\mathbb{R} h : R n → R be a strongly convex (possible nonsmooth) and positive function. Let us show that the function
f ( x ) = h ( x ) − 1 h ( x ) + a , a > 0 , f(x)=h(x)-\frac{1}{h(x)+a}, \qquad a>0, f ( x ) = h ( x ) − h ( x ) + a 1 , a > 0 ,
is strongly quasiconvex. Indeed, let us define the functions:
h 1 ( x ) = h ( x ) , h 2 ( x ) = − 1 h ( x ) + a . h_{1}(x)=h(x), \qquad h_{2}(x)=-\frac{1}{h(x)+a}. h 1 ( x ) = h ( x ) , h 2 ( x ) = − h ( x ) + a 1 .
Note that h 2 h_{2} h 2 is quasiconvex since its sublevel sets are convex. Now, take x x x , y y y , and define z : = ( 1 − λ ) x + λ y z:=(1-\lambda)x+\lambda y z := ( 1 − λ ) x + λ y with λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] . Suppose without loss of generality that h 1 ( x ) ≤ h 1 ( y ) h_{1}(x)\le h_{1}(y) h 1 ( x ) ≤ h 1 ( y ) . This implies h 2 ( x ) ≤ h 2 ( y ) h_{2}(x)\le h_{2}(y) h 2 ( x ) ≤ h 2 ( y ) . By quasiconvexity of h 2 h_{2} h 2 , we get h 2 ( z ) ≤ h 2 ( y ) h_{2}(z)\le h_{2}(y) h 2 ( z ) ≤ h 2 ( y ) . Thus,
h ( z ) = h 1 ( z ) + h 2 ( z ) ≤ max { h 1 ( x ) , h 1 ( y ) } + h 2 ( y ) − μ 2 λ ( 1 − λ ) ∥ y − x ∥ 2 ≤ h ( y ) − μ 2 λ ( 1 − λ ) ∥ y − x ∥ 2 . \begin{aligned}
h(z) &= h_{1}(z)+h_{2}(z)\\
&\le\max\{h_{1}(x),h_{1}(y)\}+h_{2}(y)-\frac{\mu}{2}\lambda(1-\lambda)\lVert y-x\rVert^{2}\\
&\le h(y)-\frac{\mu}{2}\lambda(1-\lambda)\lVert y-x\rVert^{2}.
\end{aligned} h ( z ) = h 1 ( z ) + h 2 ( z ) ≤ max { h 1 ( x ) , h 1 ( y )} + h 2 ( y ) − 2 μ λ ( 1 − λ ) ∥ y − x ∥ 2 ≤ h ( y ) − 2 μ λ ( 1 − λ ) ∥ y − x ∥ 2 .
Therefore, h h h is strongly quasiconvex with modulus μ > 0 \mu>0 μ > 0 .
A Subgradient Method
This section develops the auxiliary results needed to establish the convergence properties of the proposed method. We first introduce the technical quantity that will be used throughout the analysis and explain its role in the subsequent estimates. We then present several auxiliary lemmas that provide the key inequalities required in the proof of the main convergence result. For clarity, we indicate after each result how it is used in the subsequent analysis.
Given a convex set M ⊂ R n M \subset\mathbb{R}^{n} M ⊂ R n , for arbitrary x , y ∈ M ⊂ R n x,y \in M \subset\mathbb{R}^{n} x , y ∈ M ⊂ R n and g ( x ) ∈ ∂ f ( x ) g(x) \in\partial f(x) g ( x ) ∈ ∂ f ( x ) with g ( x ) ≠ 0 g(x) \ne0 g ( x ) = 0 , we introduce the auxiliary quantity
v f ( x , y ) : = ⟨ g ( x ) ∥ g ( x ) ∥ , x − y ⟩ . (3) v_f(x,y) := \left\langle\frac{g(x)}{\lVert g(x)\rVert},x-y\right\rangle. \tag*{(3)} v f ( x , y ) := ⟨ ∥ g ( x )∥ g ( x ) , x − y ⟩ . (3)
A fundamental inequality used in our convergence analysis is provided below. It relates the subgradient of a strongly quasiconvex function at an arbitrary point x ∈ M x \in M x ∈ M to the distance from that x x x to the unique minimizer x ∗ x^* x ∗ .
Lemma 1. Let M ⊂ R n M \subset\mathbb{R}^{n} M ⊂ R n be a closed convex set, and let f : R n → R f:\mathbb{R}^{n} \to\mathbb{R} f : R n → R be a locally Lipschitz continuous, regular, and strongly quasiconvex function with modulus μ > 0 \mu> 0 μ > 0 on M M M . Then, for all x ∈ M x \in M x ∈ M , we have
μ 2 ∥ x − x ∗ ∥ 2 ≤ ⟨ v , x − x ∗ ⟩ , ∀ v ∈ ∂ f ( x ) , \frac{\mu}{2}\lVert x-x^*\rVert^2 \le\langle v,x-x^*\rangle,\ \forall v \in\partial f(x), 2 μ ∥ x − x ∗ ∥ 2 ≤ ⟨ v , x − x ∗ ⟩ , ∀ v ∈ ∂ f ( x ) , where x ∗ x^* x ∗ is the unique minimizer of f f f on M M M .
Proof. Since x ∗ x^* x ∗ is a global minimizer of f f f on M M M , we have f ( x ∗ ) ≤ f ( x ) f(x^*) \le f(x) f ( x ∗ ) ≤ f ( x ) for all x ∈ M x \in M x ∈ M . Using this and the strong quasiconvexity of f f f , we have for every t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] that
f ( x + t ( x ∗ − x ) ) ≤ f ( x ) − μ 2 t ( 1 − t ) ∥ x − x ∗ ∥ 2 . f\bigl(x+t(x^*-x)\bigr) \le f(x)-\frac{\mu}{2}t(1-t)\lVert x-x^*\rVert^2. f ( x + t ( x ∗ − x ) ) ≤ f ( x ) − 2 μ t ( 1 − t ) ∥ x − x ∗ ∥ 2 .
Dividing by t > 0 t>0 t > 0 , we obtain
f ( x + t ( x ∗ − x ) ) − f ( x ) t ≤ − μ 2 ( 1 − t ) ∥ x − x ∗ ∥ 2 . \frac{f\bigl(x+t(x^*-x)\bigr)-f(x)}{t} \le-\frac{\mu}{2}(1-t)\lVert x-x^*\rVert^2. t f ( x + t ( x ∗ − x ) ) − f ( x ) ≤ − 2 μ ( 1 − t ) ∥ x − x ∗ ∥ 2 .
Letting t ↓ 0 t \downarrow0 t ↓ 0 and using the regularity of f f f , which implies that the Clarke directional derivative coincides with the ordinary directional derivative, we obtain
f ∘ ( x ; x ∗ − x ) = f ′ ( x ; x ∗ − x ) ≤ − μ 2 ∥ x − x ∗ ∥ 2 . f^\circ(x;x^*-x)=f'(x;x^*-x)\le-\frac{\mu}{2}\lVert x-x^*\rVert^2. f ∘ ( x ; x ∗ − x ) = f ′ ( x ; x ∗ − x ) ≤ − 2 μ ∥ x − x ∗ ∥ 2 .
For a locally Lipschitz function, the Clarke directional derivative satisfies
f ∘ ( x ; d ) = max v ∈ ∂ f ( x ) ⟨ v , d ⟩ . f^\circ(x;d)=\max_{v\in\partial f(x)}\langle v,d\rangle. f ∘ ( x ; d ) = v ∈ ∂ f ( x ) max ⟨ v , d ⟩ .
Taking d = x ∗ − x d=x^*-x d = x ∗ − x , we have
max v ∈ ∂ f ( x ) ⟨ v , x ∗ − x ⟩ ≤ − μ 2 ∥ x − x ∗ ∥ 2 ⟹ ⟨ v , x − x ∗ ⟩ ≥ μ 2 ∥ x − x ∗ ∥ 2 , ∀ v ∈ ∂ f ( x ) . \max_{v\in\partial f(x)}\langle v,x^*-x\rangle\le-\frac{\mu}{2}\lVert x-x^*\rVert^2 \Longrightarrow\langle v,x-x^*\rangle\ge\frac{\mu}{2}\lVert x-x^*\rVert^2,\ \forall v\in\partial f(x). v ∈ ∂ f ( x ) max ⟨ v , x ∗ − x ⟩ ≤ − 2 μ ∥ x − x ∗ ∥ 2 ⟹ ⟨ v , x − x ∗ ⟩ ≥ 2 μ ∥ x − x ∗ ∥ 2 , ∀ v ∈ ∂ f ( x ) .
This proves the lemma.
Remark 2. The regularity assumption cannot be omitted. Indeed, let M = [ 0 , 1 ] M=[0,1] M = [ 0 , 1 ] and x ∗ = 1 x^*=1 x ∗ = 1 , and define
f ( x ) = { ( x − 1 ) 2 + 102 x , x < 0 , ( x − 1 ) 2 , x ≥ 0. f(x)=\begin{cases}
(x-1)^2+102x, & x<0,\\
(x-1)^2, & x\ge0.
\end{cases} f ( x ) = { ( x − 1 ) 2 + 102 x , ( x − 1 ) 2 , x < 0 , x ≥ 0.
Then f f f is locally Lipschitz on R \mathbb{R} R and is 2-strongly quasiconvex on M M M . However,
∂ f ( 0 ) = [ − 2 , 100 ] . \partial f(0)=[-2,100]. ∂ f ( 0 ) = [ − 2 , 100 ] .
Taking v = 100 ∈ ∂ f ( 0 ) v=100\in\partial f(0) v = 100 ∈ ∂ f ( 0 ) , we obtain μ 2 ∣ 0 − 1 ∣ 2 = 1 > 100 ( 0 − 1 ) = − 100 \frac{\mu}{2}|0-1|^2=1>100(0-1)=-100 2 μ ∣0 − 1 ∣ 2 = 1 > 100 ( 0 − 1 ) = − 100 . Thus, the claimed inequality may fail without the regularity assumption. Indeed, f f f is not Clarke regular at x = 0 x=0 x = 0 , since f ′ ( 0 ; 1 ) = − 2 f'(0;1)=-2 f ′ ( 0 ; 1 ) = − 2 while f ∘ ( 0 ; 1 ) = 100 f^\circ(0;1)=100 f ∘ ( 0 ; 1 ) = 100 . Hence, f ′ ( 0 ; 1 ) ≠ f ∘ ( 0 ; 1 ) f'(0;1)\ne f^\circ(0;1) f ′ ( 0 ; 1 ) = f ∘ ( 0 ; 1 ) , which shows that f f f is not regular at 0.
The following lemma may be viewed as a quasiconvex analogue of the first-order inequality in the convex case. It provides a subgradient-based estimate for the functional-value difference and will be used later in the analysis of the penalty function method.
Lemma 2. Let M ⊂ R n M\subset\mathbb{R}^n M ⊂ R n be a convex compact set, and f : R n → R f:\mathbb{R}^n\to\mathbb{R} f : R n → R be a strongly quasiconvex and locally Lipschitz function on R n \mathbb{R}^n R n . Then for every point x , y ∈ M x,y\in M x , y ∈ M with f ( x ) ≥ f ( y ) f(x)\ge f(y) f ( x ) ≥ f ( y ) , the following inequality holds:
f ( x ) − f ( y ) ≤ L Ω v f ( x , y ) , ∀ g ∈ ∂ f ( x ) (4) f(x)-f(y)\le L_{\Omega}v_f(x,y),\quad\forall\ g\in\partial f(x) \tag*{(4)} f ( x ) − f ( y ) ≤ L Ω v f ( x , y ) , ∀ g ∈ ∂ f ( x ) (4) where L Ω L_{\Omega} L Ω is the Lipschitz constant of the function f f f on the set Ω = M + diam ( M ) B 1 ( 0 ) \Omega=M+\operatorname{diam}(M)B_1(0) Ω = M + diam ( M ) B 1 ( 0 ) .
Proof. Let z = y + ∥ g ∥ − 2 ⟨ g , x − y ⟩ g z=y+\|g\|^{-2}\langle g,x-y\rangle g z = y + ∥ g ∥ − 2 ⟨ g , x − y ⟩ g . Clearly, ⟨ g , z − x ⟩ = 0 \langle g,z-x\rangle=0 ⟨ g , z − x ⟩ = 0 . Hence, f ( z ) ≥ f ( x ) f(z)\ge f(x) f ( z ) ≥ f ( x ) . Indeed, suppose for the contrary that f ( z ) < f ( x ) f(z)<f(x) f ( z ) < f ( x ) . Hence,
f ( x + λ ( z − x ) ) ≤ max { f ( z ) , f ( x ) } − μ 2 λ ( 1 − λ ) ∥ x − z ∥ 2 . f(x+\lambda(z-x))\le\max\{f(z),f(x)\}-\frac{\mu}{2}\lambda(1-\lambda)\|x-z\|^2. f ( x + λ ( z − x )) ≤ max { f ( z ) , f ( x )} − 2 μ λ ( 1 − λ ) ∥ x − z ∥ 2 . It follows that,
f ∘ ( x , z − x ) = lim sup u → x , λ → 0 f ( u + λ ( z − x ) ) − f ( u ) λ f^\circ(x,z-x)=\limsup_{\substack{u\to x,\lambda\to0}}\frac{f(u+\lambda(z-x))-f(u)}{\lambda} f ∘ ( x , z − x ) = u → x , λ → 0 lim sup λ f ( u + λ ( z − x )) − f ( u ) = lim sup u → x , λ → 0 f ( u + λ ( z − u ) ) − f ( u ) λ + L Ω lim sup u → x ∥ u − x ∥ − μ 2 ( 1 − λ ) ∥ u − z ∥ 2 =\limsup_{\substack{u\to x,\lambda\to0}}\frac{f(u+\lambda(z-u))-f(u)}{\lambda}+L_{\Omega}\limsup_{u\to x}\|u-x\|-\frac{\mu}{2}(1-\lambda)\|u-z\|^2 = u → x , λ → 0 lim sup λ f ( u + λ ( z − u )) − f ( u ) + L Ω u → x lim sup ∥ u − x ∥ − 2 μ ( 1 − λ ) ∥ u − z ∥ 2 ≤ − μ 2 ∥ z − x ∥ 2 . \le-\frac{\mu}{2}\|z-x\|^2. ≤ − 2 μ ∥ z − x ∥ 2 . From this it directly follows that for any g ∈ ∂ f ( x ) g\in\partial f(x) g ∈ ∂ f ( x ) , we have ⟨ g , z − x ⟩ < 0 \langle g,z-x\rangle<0 ⟨ g , z − x ⟩ < 0 , a contradiction. Therefore, f ( z ) ≥ f ( x ) f(z)\ge f(x) f ( z ) ≥ f ( x ) .
Since f f f is locally Lipschitz, it satisfies the global Lipschitz condition on the convex compact set Ω \Omega Ω . Since the points x , y , z x,y,z x , y , z lie in this domain, it follows that
f ( x ) − f ( y ) ≤ f ( z ) − f ( y ) ≤ L Ω ∥ y − z ∥ = L Ω ⟨ g , x − y ⟩ ∥ g ∥ = L Ω v f ( x , y ) , f(x)-f(y)\le f(z)-f(y)\le L_{\Omega}\|y-z\|=L_{\Omega}\frac{\langle g,x-y\rangle}{\|g\|}=L_{\Omega}v_f(x,y), f ( x ) − f ( y ) ≤ f ( z ) − f ( y ) ≤ L Ω ∥ y − z ∥ = L Ω ∥ g ∥ ⟨ g , x − y ⟩ = L Ω v f ( x , y ) , and the result follows.
The analysis in this section includes both strongly quasiconvex and quasiconvex minimization over convex compact sets. Note that for the quasiconvex case, the convergence analysis of the functional values requires a different, but closely related, subgradient property. The following lemma provides the corresponding quasiconvex counterpart of the inequality established above for strongly quasiconvex functions.
Lemma 3. ([13 Corollary 1.1] ) Let f : R n → R f : \mathbb{R}^{n} \to\mathbb{R} f : R n → R be a locally Lipschitz and quasiconvex function on the set
Ω = M + diam ( M ) B 1 ( 0 ) , \Omega= M + \operatorname{diam}(M)B_{1}(0), Ω = M + diam ( M ) B 1 ( 0 ) , and regular on M M M . Then, for every x , y ∈ M x,y \in M x , y ∈ M such that f ( y ) ≤ f ( x ) f(y) \le f(x) f ( y ) ≤ f ( x ) , and for every g ( x ) ∈ ∂ f ( x ) g(x) \in\partial f(x) g ( x ) ∈ ∂ f ( x ) with g ( x ) ≠ 0 g(x) \ne0 g ( x ) = 0 , the following inequality holds:
f ( x ) − f ( y ) ≤ L Ω ⟨ g ( x ) , x − y ⟩ ∥ g ( x ) ∥ . (5) f(x) - f(y) \le L_{\Omega} \frac{\langle g(x),x-y\rangle}{\lVert g(x)\rVert}. \tag*{(5)} f ( x ) − f ( y ) ≤ L Ω ∥ g ( x )∥ ⟨ g ( x ) , x − y ⟩ . (5)
Remark 3. The regularity assumption in Lemma 3 is essential for relation (5) . Indeed, let M = [ 0 , 1 ] M = [0,1] M = [ 0 , 1 ] and f ( x ) = min { x , 0 } f(x) = \min\{x,0\} f ( x ) = min { x , 0 } . Then, f f f is quasiconvex and locally Lipschitz, but it is not regular at x = 0 x = 0 x = 0 since
f ∘ ( 0 ; d ) = max { 0 , d } ≠ min { 0 , d } = f ′ ( 0 ; d ) ( d > 0 ) . f^{\circ}(0;d) = \max\{0,d\} \ne\min\{0,d\} = f'(0;d) \qquad(d > 0). f ∘ ( 0 ; d ) = max { 0 , d } = min { 0 , d } = f ′ ( 0 ; d ) ( d > 0 ) .
Moreover, ∂ f ( 0 ) = [ 0 , 1 ] \partial f(0) = [0,1] ∂ f ( 0 ) = [ 0 , 1 ] . Taking x = 0 x = 0 x = 0 , x ∗ = 1 x^{*} = 1 x ∗ = 1 , and g ( 0 ) = 1 ∈ ∂ f ( 0 ) g(0) = 1 \in\partial f(0) g ( 0 ) = 1 ∈ ∂ f ( 0 ) , the right-hand side of (5) equals − 1 -1 − 1 , whereas f ( 0 ) − f ( 1 ) = 0 f(0) - f(1) = 0 f ( 0 ) − f ( 1 ) = 0 . Hence (5) fails, showing that the regularity assumption cannot be omitted.
Let us consider the following method for minimizing strongly quasiconvex functions on a closed convex set M M M ,
x k + 1 = Π M ( x k − ρ k v k ) , ∀ v k ∈ ∂ f ( x k ) , x^{k+1} = \Pi_{M}(x^{k} - \rho_{k}v^{k}), \qquad\forall v^{k} \in\partial f(x^{k}), x k + 1 = Π M ( x k − ρ k v k ) , ∀ v k ∈ ∂ f ( x k ) ,
where Π M \Pi_{M} Π M denotes the projection onto the set M M M and ρ k > 0 \rho_{k} > 0 ρ k > 0 is the step size.
The following theorem provides the convergence rate of the iterates for the subgradient method applied to a strongly quasiconvex and locally Lipschitz function. It estimates how quickly the sequence of iterates { x k } k \{x^{k}\}_{k} { x k } k approaches the unique minimizer x ∗ x^{*} x ∗ of f f f on M M M .
Theorem 1. Let M M M be a compact convex set, and suppose that the function f f f satisfies all the assumptions of Lemma 1. Take ρ k = 1 k \rho_{k} = \frac{1}{k} ρ k = k 1 for all k k k . Then the following estimates hold:
∥ x k − x ∗ ∥ 2 = { O ( 1 k ) , μ > 1 , O ( ln k k ) , μ = 1 , O ( 1 k μ ) , 0 < μ < 1. \lVert x^{k} - x^{*}\rVert^{2} =
\begin{cases}
\mathcal{O}\left(\frac{1}{k}\right), & \mu> 1,\\
\mathcal{O}\left(\frac{\ln k}{k}\right), & \mu= 1,\\
\mathcal{O}\left(\frac{1}{k^{\mu}}\right), & 0 < \mu< 1.
\end{cases} ∥ x k − x ∗ ∥ 2 = ⎩ ⎨ ⎧ O ( k 1 ) , O ( k l n k ) , O ( k μ 1 ) , μ > 1 , μ = 1 , 0 < μ < 1.
Proof. Observe that
∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 + 2 ρ k ⟨ v k , x ∗ − x k ⟩ + ρ k 2 ∥ v k ∥ 2 . \lVert x^{k+1}-x^*\rVert^2 \le\lVert x^k-x^*\rVert^2 + 2\rho_k\langle v^k,x^*-x^k\rangle+\rho_k^2\lVert v^k\rVert^2. ∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 + 2 ρ k ⟨ v k , x ∗ − x k ⟩ + ρ k 2 ∥ v k ∥ 2 .
Since x ∗ x^* x ∗ is a minimizer, Lemma 1 implies
⟨ v k , x ∗ − x k ⟩ ≤ 0 , ∀ v k ∈ ∂ f ( x k ) . \langle v^k,x^*-x^k\rangle\le0,\quad\forall v^k\in\partial f(x^k). ⟨ v k , x ∗ − x k ⟩ ≤ 0 , ∀ v k ∈ ∂ f ( x k ) .
Since the sequence { x k } k \{x^k\}_k { x k } k lies in the compact set M M M , it is bounded. Hence, the sequence { v k } k \{v^k\}_k { v k } k is also bounded, i.e., there exists a constant C > 0 C>0 C > 0 such that ∥ v k ∥ ≤ C \lVert v^k\rVert\le C ∥ v k ∥ ≤ C for all k ∈ N k\in\mathbb{N} k ∈ N . Using Lemma 1, we obtain
∥ x k + 1 − x ∗ ∥ 2 ≤ ( 1 − μ k ) ∥ x k − x ∗ ∥ 2 + C 2 k 2 . (6) \lVert x^{k+1}-x^*\rVert^2\le\left(1-\frac{\mu}{k}\right)\lVert x^k-x^*\rVert^2+\frac{C^2}{k^2}. \tag*{(6)} ∥ x k + 1 − x ∗ ∥ 2 ≤ ( 1 − k μ ) ∥ x k − x ∗ ∥ 2 + k 2 C 2 . (6)
Denote a k = ∥ x k − x ∗ ∥ 2 a_k=\lVert x^k-x^*\rVert^2 a k = ∥ x k − x ∗ ∥ 2 . Then the recurrence relation is
a k + 1 ≤ ( 1 − μ k ) a k + C 2 k 2 . a_{k+1}\le\left(1-\frac{\mu}{k}\right)a_k+\frac{C^2}{k^2}. a k + 1 ≤ ( 1 − k μ ) a k + k 2 C 2 .
Iterating this inequality, we get
a k + 1 ≤ a k 0 ∏ i = k 0 k ( 1 − μ i ) + ∑ j = k 0 k C 2 j 2 ∏ i = j + 1 k ( 1 − μ i ) + C 2 k 2 . a_{k+1}\le a_{k_0}\prod_{i=k_0}^{k}\left(1-\frac{\mu}{i}\right)+\sum_{j=k_0}^{k}\frac{C^2}{j^2}\prod_{i=j+1}^{k}\left(1-\frac{\mu}{i}\right)+\frac{C^2}{k^2}. a k + 1 ≤ a k 0 i = k 0 ∏ k ( 1 − i μ ) + j = k 0 ∑ k j 2 C 2 i = j + 1 ∏ k ( 1 − i μ ) + k 2 C 2 .
Since ln ( 1 − μ / i ) ≤ − μ / i \ln(1-\mu/i)\le-\mu/i ln ( 1 − μ / i ) ≤ − μ / i , we have
∏ i = j + 1 k ( 1 − μ i ) = exp ( ∑ i = j + 1 k ln ( 1 − μ / i ) ) ≤ exp ( − μ ∑ i = j + 1 k 1 i ) . \prod_{i=j+1}^{k}\left(1-\frac{\mu}{i}\right)=\exp\left(\sum_{i=j+1}^{k}\ln(1-\mu/i)\right)\le\exp\left(-\mu\sum_{i=j+1}^{k}\frac{1}{i}\right). i = j + 1 ∏ k ( 1 − i μ ) = exp ( i = j + 1 ∑ k ln ( 1 − μ / i ) ) ≤ exp ( − μ i = j + 1 ∑ k i 1 ) .
Also,
∑ i = j + 1 k 1 i ≥ ∫ j + 1 k + 1 d x x = ln ( k + 1 ) − ln ( j + 1 ) , \sum_{i=j+1}^{k}\frac{1}{i}\ge\int_{j+1}^{k+1}\frac{dx}{x}=\ln(k+1)-\ln(j+1), i = j + 1 ∑ k i 1 ≥ ∫ j + 1 k + 1 x d x = ln ( k + 1 ) − ln ( j + 1 ) ,
thus,
∏ i = j + 1 k ( 1 − μ i ) ≤ ( j + 1 k + 1 ) μ and ∏ i = k 0 k ( 1 − μ i ) ≤ ( k 0 k + 1 ) μ . \prod_{i=j+1}^{k}\left(1-\frac{\mu}{i}\right)\le\left(\frac{j+1}{k+1}\right)^\mu
\quad\text{and}\quad
\prod_{i=k_0}^{k}\left(1-\frac{\mu}{i}\right)\le\left(\frac{k_0}{k+1}\right)^\mu. i = j + 1 ∏ k ( 1 − i μ ) ≤ ( k + 1 j + 1 ) μ and i = k 0 ∏ k ( 1 − i μ ) ≤ ( k + 1 k 0 ) μ .
Therefore, the sum term can be estimated as
S k = ∑ j = k 0 k 1 j 2 ∏ i = j + 1 k ( 1 − μ i ) ≤ ∑ j = k 0 k 1 j 2 ( j + 1 k + 1 ) μ ≤ C 2 2 μ ( k + 1 ) μ ∑ j = k 0 k j μ − 2 . S_k=\sum_{j=k_0}^{k}\frac{1}{j^2}\prod_{i=j+1}^{k}\left(1-\frac{\mu}{i}\right)\le\sum_{j=k_0}^{k}\frac{1}{j^2}\left(\frac{j+1}{k+1}\right)^\mu\le\frac{C^2 2^\mu}{(k+1)^\mu}\sum_{j=k_0}^{k}j^{\mu-2}. S k = j = k 0 ∑ k j 2 1 i = j + 1 ∏ k ( 1 − i μ ) ≤ j = k 0 ∑ k j 2 1 ( k + 1 j + 1 ) μ ≤ ( k + 1 ) μ C 2 2 μ j = k 0 ∑ k j μ − 2 .
Consider different cases of μ \mu μ . If μ < 1 \mu<1 μ < 1 , then
∑ j = k 0 k j μ − 2 ≤ ∫ k 0 k x μ − 2 d x = k μ − 1 − k 0 μ − 1 μ − 1 ≤ k 0 μ − 1 1 − μ . \sum_{j=k_0}^{k}j^{\mu-2}\le\int_{k_0}^{k}x^{\mu-2}\,dx=\frac{k^{\mu-1}-k_0^{\mu-1}}{\mu-1}\le\frac{k_0^{\mu-1}}{1-\mu}. j = k 0 ∑ k j μ − 2 ≤ ∫ k 0 k x μ − 2 d x = μ − 1 k μ − 1 − k 0 μ − 1 ≤ 1 − μ k 0 μ − 1 .
Thus,
S k ≤ 2 μ k 0 μ − 1 1 − μ 1 ( k + 1 ) μ . S_k \le\frac{2^{\mu}k_0^{\mu-1}}{1-\mu}\frac{1}{(k+1)^{\mu}}. S k ≤ 1 − μ 2 μ k 0 μ − 1 ( k + 1 ) μ 1 .
Therefore, in this case we obtain the asymptotic estimate a k = O ( 1 k μ ) a_k = O\left(\frac{1}{k^{\mu}}\right) a k = O ( k μ 1 ) . Similarly, we obtain a k = O ( ln k k ) a_k = O\left(\frac{\ln k}{k}\right) a k = O ( k l n k ) for μ = 1 \mu=1 μ = 1 , and a k = O ( 1 k ) a_k = O\left(\frac{1}{k}\right) a k = O ( k 1 ) for μ > 1 \mu>1 μ > 1 , which completes the proof. □
Remark 4 (Practical use of the strong quasiconvexity modulus). The modulus μ \mu μ is a theoretical regularity parameter and need not be known exactly in order to implement the proposed algorithm. If only a conservative lower estimate μ ^ \hat{\mu} μ ^ is available, with
0 < μ ^ ≤ μ , 0 < \hat{\mu} \le\mu, 0 < μ ^ ≤ μ ,
then the convergence analysis remains valid with μ ^ \hat{\mu} μ ^ in place of μ \mu μ . The resulting estimates may be more conservative than those obtained with the exact modulus, but the algorithm itself is unchanged. In particular, the exact value of μ \mu μ is not required for the implementation of the projected subgradient iteration.
Remark 5 (Polyak adaptive stepsize). Throughout this remark we assume, as in Theorem 1, that f f f is strongly quasiconvex with modulus μ > 0 \mu>0 μ > 0 , and, in addition, that γ : = min x ∈ M dist ( 0 , ∂ f ( x ) ) > 0 \gamma:=\min_{x\in M}\operatorname{dist}(0,\partial f(x))>0 γ := min x ∈ M dist ( 0 , ∂ f ( x )) > 0 (the nondegeneracy condition of Theorem 2). The deterministic stepsize
ρ k = 1 k \rho_k=\frac{1}{k} ρ k = k 1
used in Theorem 1 is convenient for the theoretical analysis and leads to explicit convergence rates. In practical implementations, however, an adaptive Polyak-type stepsize can also be considered. More precisely, let Δ k : = f ( x k ) − f ( x ∗ ) \Delta_k:=f(x^k)-f(x^*) Δ k := f ( x k ) − f ( x ∗ ) and consider ρ k = λ Δ k ∥ v k ∥ 2 \rho_k=\lambda\frac{\Delta_k}{\lVert v^k\rVert^2} ρ k = λ ∥ v k ∥ 2 Δ k with v k ∈ ∂ f ( x k ) v^k\in\partial f(x^k) v k ∈ ∂ f ( x k ) , where λ > 0 \lambda>0 λ > 0 is a relaxation parameter. The projected subgradient iteration then takes the form
x k + 1 = Π M ( x k − λ f ( x k ) − f ( x ∗ ) ∥ v k ∥ 2 v k ) . x^{k+1}=\Pi_M\left(x^k-\lambda\frac{f(x^k)-f(x^*)}{\lVert v^k\rVert^2}v^k\right). x k + 1 = Π M ( x k − λ ∥ v k ∥ 2 f ( x k ) − f ( x ∗ ) v k ) .
The main difference from the prescribed stepsize ρ k = 1 / k \rho_k=1/k ρ k = 1/ k is that the Polyak stepsize adapts automatically to the current objective error: larger steps are taken when the iterate is far from the solution, and the stepsize decreases automatically as f ( x k ) − f ( x ∗ ) f(x^k)-f(x^*) f ( x k ) − f ( x ∗ ) approaches zero.
Indeed, using the projection inequality and the quasiconvexity estimate
⟨ v k , x k − x ∗ ⟩ ≥ γ L Ω ( f ( x k ) − f ( x ∗ ) ) , \langle v^k,x^k-x^*\rangle\ge\frac{\gamma}{L_{\Omega}}\left(f(x^k)-f(x^*)\right), ⟨ v k , x k − x ∗ ⟩ ≥ L Ω γ ( f ( x k ) − f ( x ∗ ) ) ,
we obtain
∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 − 2 ρ k ⟨ v k , x k − x ∗ ⟩ + ρ k 2 ∥ v k ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 − λ ( 2 γ L Ω − λ ) ( f ( x k ) − f ( x ∗ ) ) 2 ∥ v k ∥ 2 . \begin{aligned}
\lVert x^{k+1}-x^*\rVert^2\le\lVert x^k-x^*\rVert^2-2\rho_k\langle v^k,x^k-x^*\rangle+\rho_k^2\lVert v^k\rVert^2 \\
&\le\lVert x^k-x^*\rVert^2-\lambda\left(\frac{2\gamma}{L_{\Omega}}-\lambda\right)\frac{\left(f(x^k)-f(x^*)\right)^2}{\lVert v^k\rVert^2}.
\end{aligned} ∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 − 2 ρ k ⟨ v k , x k − x ∗ ⟩ + ρ k 2 ∥ v k ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 − λ ( L Ω 2 γ − λ ) ∥ v k ∥ 2 ( f ( x k ) − f ( x ∗ ) ) 2 .
Consequently, the stepsize is descent-producing whenever 0 < λ < 2 γ L Ω 0 < \lambda< \frac{2\gamma}{L_{\Omega}} 0 < λ < L Ω 2 γ . If, in addition, we use the quadratic growth property of strongly quasiconvex functions (see [8 Corollary 9] ),
f ( x ) − f ( x ∗ ) ≥ μ 4 ∥ x − x ∗ ∥ 2 , f(x) - f(x^*) \ge\frac{\mu}{4}\lVert x-x^*\rVert^2, f ( x ) − f ( x ∗ ) ≥ 4 μ ∥ x − x ∗ ∥ 2 ,
together with the uniform bound ∥ v k ∥ ≤ C \lVert v^k\rVert\le C ∥ v k ∥ ≤ C on the subgradients, then
∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 − c ∥ x k − x ∗ ∥ 4 \lVert x^{k+1}-x^*\rVert^2 \le\lVert x^k-x^*\rVert^2-c\lVert x^k-x^*\rVert^4 ∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 − c ∥ x k − x ∗ ∥ 4
for some c > 0 c>0 c > 0 , and hence ∥ x k − x ∗ ∥ 2 = O ( 1 / k ) \lVert x^k-x^*\rVert^2=O(1/k) ∥ x k − x ∗ ∥ 2 = O ( 1/ k ) .
Thus, the Polyak stepsize provides an adaptive alternative to the deterministic choice ρ k = 1 / k \rho_k=1/k ρ k = 1/ k : it uses the current objective-function error rather than the iteration counter to determine the stepsize. As in the classical Polyak scheme, the exact optimal value f ( x ∗ ) f(x^*) f ( x ∗ ) is required; if it is unavailable, an estimate or a target value can be used instead.
We next establish a functional-value convergence rate for the projected method when f f f is quasiconvex, without assuming strong quasiconvexity.
Theorem 2. Let M M M be a compact convex set, and suppose that the function f f f satisfies all the assumptions of Lemma 3. If, in addition,
γ ≡ min x ∈ M dist ( 0 , ∂ f ( x ) ) > 0 , (7) \gamma\equiv\min_{x\in M}\operatorname{dist}(0,\partial f(x))>0, \tag*{(7)} γ ≡ x ∈ M min dist ( 0 , ∂ f ( x )) > 0 , (7) then, for the projected method with ρ k = 1 k \rho_k=\frac{1}{\sqrt{k}} ρ k = k 1 for all k k k , the following estimate holds:
min 1 ≤ k ≤ T ( f ( x k ) − f ( x ∗ ) ) = O ( 1 T ) . \min_{1\le k\le T}\left(f(x^k)-f(x^*)\right)=O\left(\frac{1}{\sqrt{T}}\right). 1 ≤ k ≤ T min ( f ( x k ) − f ( x ∗ ) ) = O ( T 1 ) . Proof. Since x k , x ∗ ∈ M x^k,x^*\in M x k , x ∗ ∈ M and M M M is compact, we have, for every k k k , ∥ x k − x ∗ ∥ ≤ diam ( M ) \lVert x^k-x^*\rVert\le\operatorname{diam}(M) ∥ x k − x ∗ ∥ ≤ diam ( M ) , and hence ∥ x k − x ∗ ∥ 2 ≤ diam 2 ( M ) \lVert x^k-x^*\rVert^2\le\operatorname{diam}^2(M) ∥ x k − x ∗ ∥ 2 ≤ diam 2 ( M ) . Furthermore, from the projection step x k + 1 = Π M ( x k − ρ k v k ) x^{k+1}=\Pi_M(x^k-\rho_kv^k) x k + 1 = Π M ( x k − ρ k v k ) , the nonexpansiveness of the projection gives
∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 − 2 ρ k ⟨ v k , x k − x ∗ ⟩ + ρ k 2 ∥ v k ∥ 2 . \lVert x^{k+1}-x^*\rVert^2\le\lVert x^k-x^*\rVert^2-2\rho_k\langle v^k,x^k-x^*\rangle+\rho_k^2\lVert v^k\rVert^2. ∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 − 2 ρ k ⟨ v k , x k − x ∗ ⟩ + ρ k 2 ∥ v k ∥ 2 . Using inequality (5) and the assumption ∥ v k ∥ ≥ γ \lVert v^k\rVert\ge\gamma ∥ v k ∥ ≥ γ , we obtain
f ( x k ) − f ( x ∗ ) ≤ L Ω 2 γ ( ∥ x k − x ∗ ∥ 2 − ∥ x k + 1 − x ∗ ∥ 2 ρ k + C 2 ρ k ) . (8) f(x^k)-f(x^*)\le\frac{L_{\Omega}}{2\gamma}\left(\frac{\lVert x^k-x^*\rVert^2-\lVert x^{k+1}-x^*\rVert^2}{\rho_k}+C^2\rho_k\right). \tag*{(8)} f ( x k ) − f ( x ∗ ) ≤ 2 γ L Ω ( ρ k ∥ x k − x ∗ ∥ 2 − ∥ x k + 1 − x ∗ ∥ 2 + C 2 ρ k ) . (8) Summing (7) for k = 1 , … , T k=1,\ldots,T k = 1 , … , T gives
∑ k = 1 T ( f ( x k ) − f ( x ∗ ) ) ≤ L Ω 2 γ [ ∑ k = 1 T ∥ x k − x ∗ ∥ 2 ( 1 ρ k − 1 ρ k − 1 ) + C 2 ∑ k = 1 T ρ k ] , (9) \sum_{k=1}^{T}\left(f(x^k)-f(x^*)\right)\le\frac{L_{\Omega}}{2\gamma}\left[\sum_{k=1}^{T}\lVert x^k-x^*\rVert^2\left(\frac{1}{\rho_k}-\frac{1}{\rho_{k-1}}\right)+C^2\sum_{k=1}^{T}\rho_k\right], \tag*{(9)} k = 1 ∑ T ( f ( x k ) − f ( x ∗ ) ) ≤ 2 γ L Ω [ k = 1 ∑ T ∥ x k − x ∗ ∥ 2 ( ρ k 1 − ρ k − 1 1 ) + C 2 k = 1 ∑ T ρ k ] , (9)
where 1 / ρ 0 = 0 1/\rho_0 = 0 1/ ρ 0 = 0 . Set ρ k = 1 k \rho_k = \frac{1}{\sqrt{k}} ρ k = k 1 . Then 1 ρ k = k \frac{1}{\rho_k} = \sqrt{k} ρ k 1 = k and 1 ρ k − 1 ρ k − 1 = k − k − 1 \frac{1}{\rho_k} - \frac{1}{\rho_{k-1}} = \sqrt{k} - \sqrt{k-1} ρ k 1 − ρ k − 1 1 = k − k − 1 . Thus,
∑ k = 1 T ∥ x k − x ∗ ∥ 2 ( 1 ρ k − 1 ρ k − 1 ) ≤ diam 2 ( M ) ∑ k = 1 T ( k − k − 1 ) = diam 2 ( M ) T . \sum_{k=1}^{T} \lVert x^k-x^*\rVert^2\left(\frac{1}{\rho_k}-\frac{1}{\rho_{k-1}}\right) \leq\operatorname{diam}^2(M)\sum_{k=1}^{T}\left(\sqrt{k}-\sqrt{k-1}\right)
= \operatorname{diam}^2(M)\sqrt{T}. k = 1 ∑ T ∥ x k − x ∗ ∥ 2 ( ρ k 1 − ρ k − 1 1 ) ≤ diam 2 ( M ) k = 1 ∑ T ( k − k − 1 ) = diam 2 ( M ) T .
On the other hand, ∑ k = 1 T ρ k = ∑ k = 1 T 1 k ≤ 2 T \sum_{k=1}^{T}\rho_k = \sum_{k=1}^{T}\frac{1}{\sqrt{k}} \leq2\sqrt{T} ∑ k = 1 T ρ k = ∑ k = 1 T k 1 ≤ 2 T . Substituting these estimates into (8), we obtain
∑ k = 1 T ( f ( x k ) − f ( x ∗ ) ) ≤ L Ω 2 γ ( diam 2 ( M ) + 2 C 2 ) T . \sum_{k=1}^{T}\left(f(x^k)-f(x^*)\right) \leq\frac{L_{\Omega}}{2\gamma}\left(\operatorname{diam}^2(M)+2C^2\right)\sqrt{T}. k = 1 ∑ T ( f ( x k ) − f ( x ∗ ) ) ≤ 2 γ L Ω ( diam 2 ( M ) + 2 C 2 ) T .
Since T min 1 ≤ k ≤ T ( f ( x k ) − f ( x ∗ ) ) ≤ ∑ k = 1 T ( f ( x k ) − f ( x ∗ ) ) T\min_{1\leq k\leq T}\left(f(x^k)-f(x^*)\right) \leq\sum_{k=1}^{T}\left(f(x^k)-f(x^*)\right) T min 1 ≤ k ≤ T ( f ( x k ) − f ( x ∗ ) ) ≤ ∑ k = 1 T ( f ( x k ) − f ( x ∗ ) ) , we conclude that
min 1 ≤ k ≤ T ( f ( x k ) − f ( x ∗ ) ) ≤ L Ω diam 2 ( M ) + 2 C 2 2 γ T \min_{1\leq k\leq T}\left(f(x^k)-f(x^*)\right) \leq\frac{L_{\Omega}\operatorname{diam}^2(M)+2C^2}{2\gamma\sqrt{T}} 1 ≤ k ≤ T min ( f ( x k ) − f ( x ∗ ) ) ≤ 2 γ T L Ω diam 2 ( M ) + 2 C 2
⟹ min 1 ≤ k ≤ T ( f ( x k ) − f ( x ∗ ) ) = O ( 1 T ) , \Longrightarrow\quad\min_{1\leq k\leq T}\left(f(x^k)-f(x^*)\right) = O\left(\frac{1}{\sqrt{T}}\right), ⟹ 1 ≤ k ≤ T min ( f ( x k ) − f ( x ∗ ) ) = O ( T 1 ) ,
which completes the proof.
Remark 6. The assumption γ > 0 \gamma> 0 γ > 0 cannot be removed in general. Indeed, consider M = [ − 1 , 1 ] M=[-1,1] M = [ − 1 , 1 ] and f ( x ) = x 3 f(x)=x^3 f ( x ) = x 3 . Then f f f is quasiconvex but not convex, with unique minimizer x ∗ = − 1 x^*=-1 x ∗ = − 1 , whereas
γ = min x ∈ M dist ( 0 , ∂ f ( x ) ) = min x ∈ [ − 1 , 1 ] 3 x 2 = 0. \gamma= \min_{x\in M}\operatorname{dist}(0,\partial f(x)) = \min_{x\in[-1,1]}3x^2=0. γ = x ∈ M min dist ( 0 , ∂ f ( x )) = x ∈ [ − 1 , 1 ] min 3 x 2 = 0.
Starting from x 0 = 0 x^0=0 x 0 = 0 , the projected subgradient method with ρ k = ( k + 1 ) − 1 / 2 \rho_k=(k+1)^{-1/2} ρ k = ( k + 1 ) − 1/2 remains at x k = 0 x^k=0 x k = 0 , since 0 ∈ ∂ f ( 0 ) 0\in\partial f(0) 0 ∈ ∂ f ( 0 ) . Hence f ( x k ) − f ( x ∗ ) = 1 f(x^k)-f(x^*)=1 f ( x k ) − f ( x ∗ ) = 1 for all k k k , and no convergence to the optimal value occurs. This shows that γ > 0 \gamma>0 γ > 0 is essential for the convergence result of Theorem 2.
Remark 7 (Relation to convex and strongly convex optimization). The results of this section extend the standard nonsmooth subgradient framework for convex optimization to the broader class of locally Lipschitz quasiconvex functions. As shown in [12 ] , when f f f is strongly convex with modulus μ \mu μ and has an L L L -Lipschitz gradient, gradient descent with step size 1 / L 1/L 1/ L converges linearly,
f ( x k ) − f ( x ∗ ) ≤ ( 1 − μ L ) k ( f ( x 0 ) − f ( x ∗ ) ) . f(x^k)-f(x^*) \leq\left(1-\frac{\mu}{L}\right)^k\left(f(x^0)-f(x^*)\right). f ( x k ) − f ( x ∗ ) ≤ ( 1 − L μ ) k ( f ( x 0 ) − f ( x ∗ ) ) .
Theorems 1 and 2 extend this circle of ideas to a substantially broader class of functions (quasiconvex and locally Lipschitz, for which the gradient may not exist) at the cost of sublinear rather than linear rates. This weakening is unavoidable: even for merely convex, nonsmooth objectives, subgradient methods cannot in general achieve better than sublinear rates, so the results obtained here are consistent with, rather than weaker than, what smoothness gives up. The extension is nontrivial also at the level of the underlying inequalities, since the fundamental convex subgradient inequality
f ( x ) − f ( y ) ≤ ⟨ g ( x ) , x − y ⟩ , g ( x ) ∈ ∂ f ( x ) , f(x) - f(y) \le\langle g(x), x-y\rangle,\qquad g(x) \in\partial f(x), f ( x ) − f ( y ) ≤ ⟨ g ( x ) , x − y ⟩ , g ( x ) ∈ ∂ f ( x ) ,
is generally not valid for quasiconvex functions. Instead, under the regularity assumption, we employ the first-order characterization
⟨ g ( x ) , y − x ⟩ ≤ 0 , f ( y ) ≤ f ( x ) , \langle g(x),y-x\rangle\le0,\qquad f(y) \le f(x), ⟨ g ( x ) , y − x ⟩ ≤ 0 , f ( y ) ≤ f ( x ) ,
which, together with local Lipschitz continuity, yields the normalized subgradient estimate
f ( x ) − f ( x ∗ ) ≤ L Ω ⟨ g ( x ) ∥ g ( x ) ∥ , x − x ∗ ⟩ , g ( x ) ∈ ∂ f ( x ) , g ( x ) ≠ 0. f(x)-f(x^*) \le L_{\Omega}\left\langle\frac{g(x)}{\lVert g(x)\rVert},x-x^*\right\rangle,\qquad g(x) \in\partial f(x),\ g(x) \ne0. f ( x ) − f ( x ∗ ) ≤ L Ω ⟨ ∥ g ( x )∥ g ( x ) , x − x ∗ ⟩ , g ( x ) ∈ ∂ f ( x ) , g ( x ) = 0.
Thus, the quasiconvex setting requires a different first-order inequality and, in general, an additional nondegeneracy condition γ > 0 \gamma> 0 γ > 0 . For strongly quasiconvex functions, the stronger estimate
μ 2 ∥ x − x ∗ ∥ 2 ≤ ⟨ g , x − x ∗ ⟩ , g ∈ ∂ f ( x ) , \frac{\mu}{2}\lVert x-x^*\rVert^2 \le\langle g,x-x^*\rangle,\qquad g \in\partial f(x), 2 μ ∥ x − x ∗ ∥ 2 ≤ ⟨ g , x − x ∗ ⟩ , g ∈ ∂ f ( x ) ,
provides direct control of the distance to the minimizer without requiring γ > 0 \gamma> 0 γ > 0 : under the assumptions of Theorem 1, this condition is not needed, whereas it is essential in Theorem 2 to control the normalized subgradient.
Consequently, the passage from convexity to quasiconvexity changes not only the class of admissible objective functions but also the analytical tools and assumptions required for convergence: the standard convex subgradient inequality is replaced by a normalized quasiconvex estimate, and the regularity assumption is used to connect the Clarke subdifferential with directional derivatives. This confirms that the obtained extension is substantive, and not merely a formal replacement of convexity by quasiconvexity.
A Stochastic Finite-Difference Method
In this section, we develop a projected stochastic finite-difference method for constrained quasiconvex optimization and establish explicit convergence estimates for both the objective error and constraint violation. The method employs two-point randomized finite-difference estimators in place of exact subgradient evaluations; see [14 ] .
We assume that the objective function is quasiconvex and that the constraint functions are strongly quasiconvex. Under the conditions of Lemma 4, the latter assumption yields the error bound
dist ( x , Q ) ≤ 2 μ h + ( x ) , Q = { x ∈ M : h ( x ) ≤ 0 } , ( h + ( x ) ≡ max { h ( x ) , 0 } ) \operatorname{dist}(x,Q) \le\frac{2}{\sqrt{\mu}}\sqrt{h^+(x)},\qquad Q=\{x\in M:h(x)\le0\},\quad\left(h^+(x)\equiv\max\{h(x),0\}\right) dist ( x , Q ) ≤ μ 2 h + ( x ) , Q = { x ∈ M : h ( x ) ≤ 0 } , ( h + ( x ) ≡ max { h ( x ) , 0 } )
which provides the required control of the distance to the feasible set in terms of constraint violation. Thus, the analysis does not require convexity of the constraint functions.
Let f f f be a Lipschitz continuous function with constant L Ω L_{\Omega} L Ω on the set Ω = M + diam ( M ) B 1 ( 0 ) \Omega= M + \operatorname{diam}(M)B_{1}(0) Ω = M + diam ( M ) B 1 ( 0 ) , where M ⊂ R n M \subset\mathbb{R}^{n} M ⊂ R n is a certain convex compact set with diam ( M ) ≥ 1 \operatorname{diam}(M) \ge1 diam ( M ) ≥ 1 . Define the function f ( x , α ) f(x,\alpha) f ( x , α ) as follows:
f ( x , α ) = E u ∼ B 1 ( 0 ) [ f ( x + α u ) ] = 1 Vol ( B 1 ( 0 ) ) ∫ ∥ u ∥ ≤ 1 f ( x + α u ) d u , f(x,\alpha) = \mathbb{E}_{u\sim B_{1}(0)}[f(x+\alpha u)] = \frac{1}{\operatorname{Vol}(B_{1}(0))}\int_{\lVert u\rVert\le1} f(x+\alpha u)\,\mathrm{d}u, f ( x , α ) = E u ∼ B 1 ( 0 ) [ f ( x + α u )] = Vol ( B 1 ( 0 )) 1 ∫ ∥ u ∥ ≤ 1 f ( x + α u ) d u ,
where u u u is a random vector uniformly distributed on the unit ball B 1 ( 0 ) B_{1}(0) B 1 ( 0 ) and α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] .
As it is known, the following results hold [21 ] :
∣ f ( x , α ) − f ( x ) ∣ ≤ α L Ω \lvert f(x,\alpha)-f(x)\rvert\le\alpha L_{\Omega} ∣ f ( x , α ) − f ( x )∣ ≤ α L Ω for all x ∈ M x \in M x ∈ M .
The function f ( x , α ) f(x,\alpha) f ( x , α ) is differentiable.
By differentiating this function and applying Stokes’ theorem, we obtain
f ′ ( x , α ) = n α E u ∼ S n − 1 [ f ( x + α u ) u ] f'(x,\alpha) = \frac{n}{\alpha}\mathbb{E}_{u\sim S^{n-1}}[f(x+\alpha u)u] f ′ ( x , α ) = α n E u ∼ S n − 1 [ f ( x + α u ) u ]
⟹ f ′ ( x , α ) = − n α E u ∼ S n − 1 [ f ( x − α u ) u ] . \Longrightarrow f'(x,\alpha) = -\frac{n}{\alpha}\mathbb{E}_{u\sim S^{n-1}}[f(x-\alpha u)u]. ⟹ f ′ ( x , α ) = − α n E u ∼ S n − 1 [ f ( x − α u ) u ] .
By adding these two equations, we obtain
f ′ ( x , α ) = n 2 α E u ∼ S n − 1 [ ( f ( x + α u ) − f ( x − α u ) ) u ] , (10) f'(x,\alpha) = \frac{n}{2\alpha}\mathbb{E}_{u\sim S^{n-1}}[(f(x+\alpha u)-f(x-\alpha u))u], \tag*{(10)} f ′ ( x , α ) = 2 α n E u ∼ S n − 1 [( f ( x + α u ) − f ( x − α u )) u ] , (10)
∥ f ′ ( x , α ) ∥ ≤ n L Ω , ∀ x ∈ M . (11) \lVert f'(x,\alpha)\rVert\le nL_{\Omega},\quad\forall\ x\in M. \tag*{(11)} ∥ f ′ ( x , α )∥ ≤ n L Ω , ∀ x ∈ M . (11)
If the gradient of f f f satisfies the Lipschitz condition with constant L Ω ′ L'_{\Omega} L Ω ′ on the set Ω \Omega Ω , then
∥ f ′ ( x ) − f ′ ( x , α ) ∥ ≤ α L Ω ′ , ∀ x ∈ M . (12) \lVert f'(x)-f'(x,\alpha)\rVert\le\alpha L'_{\Omega},\quad\forall\ x\in M. \tag*{(12)} ∥ f ′ ( x ) − f ′ ( x , α )∥ ≤ α L Ω ′ , ∀ x ∈ M . (12)
From this representation, it follows that the vector
g ( x , α , u ) = n 2 α [ f ( x + α u ) − f ( x − α u ) ] u , g(x,\alpha,u)=\frac{n}{2\alpha}[f(x+\alpha u)-f(x-\alpha u)]u, g ( x , α , u ) = 2 α n [ f ( x + α u ) − f ( x − α u )] u ,
is a stochastic gradient of the function f ( x , α ) f(x,\alpha) f ( x , α ) at iteration k k k . Since, according to the first point, this function is a smooth approximation of f f f , the vector g g g is often referred to in the literature as a stochastic quasi-gradient.
The following result was proved in [8 ] .
Theorem 3. ([8 Theorem 4] ) Let h h h be a function defined on a convex set M ⊂ R n M \subset\mathbb{R}^{n} M ⊂ R n . If h h h is strongly quasiconvex with modulus μ > 0 \mu> 0 μ > 0 , then for every x , y ∈ M x,y \in M x , y ∈ M and every z = x + t ( y − x ) z=x+t(y-x) z = x + t ( y − x ) with 0 < t ≤ 1 0<t\le1 0 < t ≤ 1 , the following implication holds:
h ( x ) ≤ h ( z ) ⟹ h ( z ) ≤ h ( y ) − μ 4 ( ∥ y − x ∥ 2 − ∥ z − x ∥ 2 ) . (13) h(x)\le h(z)\Longrightarrow h(z)\le h(y)-\frac{\mu}{4}\left(\lVert y-x\rVert^{2}-\lVert z-x\rVert^{2}\right). \tag*{(13)} h ( x ) ≤ h ( z ) ⟹ h ( z ) ≤ h ( y ) − 4 μ ( ∥ y − x ∥ 2 − ∥ z − x ∥ 2 ) . (13)
Using the previous theorem, we can prove the following estimate, which will be useful in the sequel.
Lemma 4. Assume that the assumptions of Theorem 3 hold. Let y ∈ M y \in M y ∈ M satisfy h ( y ) > 0 h(y)>0 h ( y ) > 0 and define
Q : = { x ∈ M : h ( x ) ≤ 0 } ≠ ∅ . Q := \{x \in M : h(x) \le0\} \ne\varnothing. Q := { x ∈ M : h ( x ) ≤ 0 } = ∅ . Then,
dist ( y , Q ) ≤ 2 h ( y ) μ . \operatorname{dist}(y,Q) \le\frac{2\sqrt{h(y)}}{\sqrt{\mu}}. dist ( y , Q ) ≤ μ 2 h ( y ) . Proof. Since Q Q Q is nonempty closed and convex, the projection of y y y onto Q Q Q exists and is unique. Denote this projection by x = P Q ( y ) x=P_Q(y) x = P Q ( y ) . Because h ( y ) > 0 h(y)>0 h ( y ) > 0 , we have y ∉ Q y \notin Q y ∈ / Q . Moreover, by the continuity of h h h , the projection point satisfies h ( x ) = 0 h(x)=0 h ( x ) = 0 .
Take z = x + t ( y − x ) z=x+t(y-x) z = x + t ( y − x ) with 0 < t < 1 0<t<1 0 < t < 1 . Since z z z belongs to the segment connecting a feasible boundary point x x x and the infeasible point y y y , we have z ∉ Q z \notin Q z ∈ / Q , thus h ( z ) > 0 h(z)>0 h ( z ) > 0 .
On the other hand, h ( x ) = 0 < h ( z ) h(x)=0<h(z) h ( x ) = 0 < h ( z ) . Hence we can apply Theorem 3 with the points z z z and x x x . Taking z = x + t ( y − x ) z=x+t(y-x) z = x + t ( y − x ) , and using the implication in Theorem 3, we obtain
h ( z ) ≤ h ( y ) − μ 4 ( ∥ y − x ∥ 2 − ∥ z − x ∥ 2 ) ⟹ h ( z ) ≤ h ( y ) − μ 4 ( 1 − t 2 ) ∥ y − x ∥ 2 . h(z) \le h(y)-\frac{\mu}{4}\left(\lVert y-x\rVert^2-\lVert z-x\rVert^2\right) \Longrightarrow h(z) \le h(y)-\frac{\mu}{4}(1-t^2)\lVert y-x\rVert^2. h ( z ) ≤ h ( y ) − 4 μ ( ∥ y − x ∥ 2 − ∥ z − x ∥ 2 ) ⟹ h ( z ) ≤ h ( y ) − 4 μ ( 1 − t 2 ) ∥ y − x ∥ 2 . because ∥ z − x ∥ 2 = t 2 ∥ y − x ∥ 2 \lVert z-x\rVert^2=t^2\lVert y-x\rVert^2 ∥ z − x ∥ 2 = t 2 ∥ y − x ∥ 2 . Let t → 0 t\to0 t → 0 . Then z → x z\to x z → x . By the continuity of h h h , h ( z ) → h ( x ) = 0 h(z)\to h(x)=0 h ( z ) → h ( x ) = 0 . Passing to the limit in the above inequality gives
μ 4 ∥ y − x ∥ 2 ≤ h ( y ) ⟹ ∥ y − x ∥ ≤ 2 h ( y ) μ . \frac{\mu}{4}\lVert y-x\rVert^2 \le h(y) \Longrightarrow\lVert y-x\rVert\le\frac{2\sqrt{h(y)}}{\sqrt{\mu}}. 4 μ ∥ y − x ∥ 2 ≤ h ( y ) ⟹ ∥ y − x ∥ ≤ μ 2 h ( y ) . Finally, since x = P Q ( y ) x=P_Q(y) x = P Q ( y ) , we have ∥ y − x ∥ = dist ( y , Q ) \lVert y-x\rVert=\operatorname{dist}(y,Q) ∥ y − x ∥ = dist ( y , Q ) .
Theorem 4 (Linear error bound under the Slater condition). Let M ⊂ R n M\subset\mathbb{R}^n M ⊂ R n be a nonempty closed convex set and let Q = { x ∈ M : h ( x ) ≤ 0 } Q=\{x\in M:h(x)\le0\} Q = { x ∈ M : h ( x ) ≤ 0 } , where h : M → R h:M\to\mathbb{R} h : M → R is a continuous strongly quasiconvex function with modulus μ > 0 \mu>0 μ > 0 . Assume that there exists a Slater point x ˉ ∈ ri ( M ) \bar{x}\in\operatorname{ri}(M) x ˉ ∈ ri ( M ) such that
h ( x ˉ ) < 0. h(\bar{x})<0. h ( x ˉ ) < 0. Then there exists a constant C > 0 C>0 C > 0 such that
dist ( x , Q ) ≤ C h ( x ) , ∀ x ∈ M ∖ Q . \operatorname{dist}(x,Q)\le Ch(x),\quad\forall x\in M\setminus Q. dist ( x , Q ) ≤ C h ( x ) , ∀ x ∈ M ∖ Q . In particular, one may take C : = 2 μ C:=\frac{2}{\mu} C := μ 2 and γ : = dist ( x ˉ , ∂ M Q ) > 0 \gamma:=\operatorname{dist}(\bar{x},\partial_M Q)>0 γ := dist ( x ˉ , ∂ M Q ) > 0 , where ∂ M Q \partial_M Q ∂ M Q denotes the boundary of Q Q Q relative to M M M .
Proof. Let x ∈ M ∖ Q x\in M\setminus Q x ∈ M ∖ Q . Then h ( x ) > 0 h(x)>0 h ( x ) > 0 . Since h ( x ˉ ) < 0 h(\bar{x})<0 h ( x ˉ ) < 0 and h h h is continuous, x ˉ ∈ ri M ( Q ) \bar{x}\in\operatorname{ri}_M(Q) x ˉ ∈ ri M ( Q ) . Hence, γ : = dist ( x ˉ , ∂ M Q ) > 0 \gamma:=\operatorname{dist}(\bar{x},\partial_M Q)>0 γ := dist ( x ˉ , ∂ M Q ) > 0 . Consider z ( t ) = ( 1 − t ) x ˉ + t x z(t)=(1-t)\bar{x}+tx z ( t ) = ( 1 − t ) x ˉ + t x with
t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] . By continuity of h h h , there exists a last t ∗ ∈ ] 0 , 1 [ t^* \in]0,1[ t ∗ ∈ ] 0 , 1 [ such that h ( z ( t ∗ ) ) = 0 h(z(t^*)) = 0 h ( z ( t ∗ )) = 0 . Set z = z ( t ∗ ) z = z(t^*) z = z ( t ∗ ) . Then z ∈ ∂ M Q z \in\partial_M Q z ∈ ∂ M Q . By strong quasiconvexity,
0 = h ( z ) ≤ h ( x ) − μ 2 t ∗ ( 1 − t ∗ ) ∥ x − x ˉ ∥ 2 ⟹ h ( x ) ≥ μ 2 ∥ x − z ∥ ∥ z − x ˉ ∥ . 0 = h(z) \le h(x) - \frac{\mu}{2}t^*(1-t^*)\lVert x-\bar{x}\rVert^2 \implies h(x) \ge\frac{\mu}{2}\lVert x-z\rVert\lVert z-\bar{x}\rVert. 0 = h ( z ) ≤ h ( x ) − 2 μ t ∗ ( 1 − t ∗ ) ∥ x − x ˉ ∥ 2 ⟹ h ( x ) ≥ 2 μ ∥ x − z ∥ ∥ z − x ˉ ∥ .
Since z ∈ ∂ M Q z \in\partial_M Q z ∈ ∂ M Q , we have ∥ z − x ˉ ∥ ≥ γ \lVert z-\bar{x}\rVert\ge\gamma ∥ z − x ˉ ∥ ≥ γ . Thus,
h ( x ) ≥ μ 2 γ ∥ x − z ∥ ≥ μ 2 γ dist ( x , Q ) ⟹ dist ( x , Q ) ≤ 2 μ γ h ( x ) . h(x) \ge\frac{\mu}{2}\gamma\lVert x-z\rVert\ge\frac{\mu}{2}\gamma\operatorname{dist}(x,Q) \implies\operatorname{dist}(x,Q) \le\frac{2}{\mu\gamma}h(x). h ( x ) ≥ 2 μ γ ∥ x − z ∥ ≥ 2 μ γ dist ( x , Q ) ⟹ dist ( x , Q ) ≤ μ γ 2 h ( x ) .
Hence, the assertion follows with C = 2 μ γ > 0 C = \frac{2}{\mu\gamma} > 0 C = μ γ 2 > 0 .
Now, let us consider the constrained optimization problem
min f 0 ( x ) , x ∈ M , f i ( x ) ≤ 0 , i = 1 , 2 , … , m . (14) \min f_0(x), \quad x\in M,\quad f_i(x)\le0,\quad i=1,2,\ldots,m. \tag*{(14)} min f 0 ( x ) , x ∈ M , f i ( x ) ≤ 0 , i = 1 , 2 , … , m . (14)
For which we suppose that Q = { x ∈ M : f i ( x ) ≤ 0 , i = 1 , 2 , … , m } ≠ ∅ Q=\{x\in M:f_i(x)\le0,\ i=1,2,\ldots,m\}\ne\varnothing Q = { x ∈ M : f i ( x ) ≤ 0 , i = 1 , 2 , … , m } = ∅ . Define the function
f ~ ( x ) : = max 1 ≤ i ≤ m f i ( x ) . \tilde{f}(x):=\max_{1\le i\le m} f_i(x). f ~ ( x ) := 1 ≤ i ≤ m max f i ( x ) .
In this section, we present a Feasibility–Optimization Switching Stochastic Finite-Difference Method for Problem (13) and establish the corresponding convergence guarantees.
Algorithmic Scheme
The proposed method utilizes an adaptive switching mechanism that alternates between minimizing the objective function and reducing constraint violations based on an asymptotically vanishing feasibility threshold.
Algorithm 1 Feasibility–Opt Switching Stochastic Finite-Difference Method
Require:
x 0 ∈ M x^0 \in M x 0 ∈ M , ρ k = 1 k + 0.5 \rho_k = \frac{1}{\sqrt{k+0.5}} ρ k = k + 0.5 1 , α k = 1 k + 1 \alpha_k = \frac{1}{k+1} α k = k + 1 1 , R = diam ( M ) = max x , y ∈ M ∥ x − y ∥ R = \operatorname{diam}(M) = \max_{x,y\in M} \lVert x-y\rVert R = diam ( M ) = max x , y ∈ M ∥ x − y ∥ , common Lipschitz constant on Ω \Omega Ω , L Ω = max 0 ≤ i ≤ m L i > 0 L_{\Omega} = \max_{0\le i\le m} L_i > 0 L Ω = max 0 ≤ i ≤ m L i > 0 , where L i L_i L i is the Lipschitz constant of f i f_i f i on Ω \Omega Ω , and a positive lower bound on gradient norms: γ = min 0 ≤ i ≤ m min x ∈ M ∥ f i ′ ( x ) ∥ > 0 \gamma= \min_{0\le i\le m}\min_{x\in M} \lVert f_i'(x)\rVert> 0 γ = min 0 ≤ i ≤ m min x ∈ M ∥ f i ′ ( x )∥ > 0 ,
Unified scale parameter:
R ~ ≥ max { R , n L Ω , L Ω 2 γ ( n 2 L Ω 2 + 2 R 2 ln 3 + 1 ) } . \widetilde{R} \ge\max\left\{R,\ nL_{\Omega},\ \frac{L_{\Omega}}{2\gamma}\left(n^2L_{\Omega}^2+\frac{2R^2}{\ln3}+1\right)\right\}. R ≥ max { R , n L Ω , 2 γ L Ω ( n 2 L Ω 2 + ln 3 2 R 2 + 1 ) } .
for k = 0 , 1 , 2 , … k = 0,1,2,\ldots k = 0 , 1 , 2 , … do
Compute the maximum constraint violation:
f ~ ( x k ) = max 1 ≤ i ≤ m f i ( x k ) . \widetilde{f}(x^k) = \max_{1\le i\le m} f_i(x^k). f ( x k ) = 1 ≤ i ≤ m max f i ( x k ) .
if f ~ ( x k ) ≤ ρ k R ~ \widetilde{f}(x^k) \le\rho_k\widetilde{R} f ( x k ) ≤ ρ k R then
Sample a direction uniformly from the unit sphere: u k ∼ Unif ( S n − 1 ) u_k \sim\operatorname{Unif}(S^{n-1}) u k ∼ Unif ( S n − 1 ) .
Set search direction for objective minimization:
p k = g 0 ( x k , α k , u k ) . p^k = g_0(x^k,\alpha_k,u_k). p k = g 0 ( x k , α k , u k ) .
else
Identify active maximal-violation constraints:
I ( x k ) = { i ∈ { 1 , … , m } : f i ( x k ) = f ~ ( x k ) } . I(x^k) = \left\{i \in\{1,\ldots,m\}: f_i(x^k) = \widetilde{f}(x^k)\right\}. I ( x k ) = { i ∈ { 1 , … , m } : f i ( x k ) = f ( x k ) } .
Select an index ξ k \xi_k ξ k uniformly at random from I ( x k ) I(x^k) I ( x k ) .
Sample a direction uniformly from the unit sphere: u k ∼ Unif ( S n − 1 ) u_k \sim\operatorname{Unif}(S^{n-1}) u k ∼ Unif ( S n − 1 ) .
Set search direction for constraint reduction:
p k = g ξ k ( x k , α k , u k ) . p^k = g_{\xi_k}(x^k,\alpha_k,u_k). p k = g ξ k ( x k , α k , u k ) .
end if
Update the iterate via projection onto M M M :
x k + 1 = Π M ( x k − ρ k p k ) . x^{k+1} = \Pi_M(x^k-\rho_k p^k). x k + 1 = Π M ( x k − ρ k p k ) .
end for
Ensure: A sequence of iterates { x k } k ⊂ M \{x^k\}_k \subset M { x k } k ⊂ M .
Convergence Result
The main theoretical outcome establishing the rate of convergence for Algorithm 1 is formalized below.
Theorem 5. Consider the constrained optimization problem on M ⊂ R n M \subset\mathbb{R}^{n} M ⊂ R n . Assume the following conditions hold:
M ⊂ R n M \subset\mathbb{R}^{n} M ⊂ R n is a nonempty, convex, and compact set with diameter R = diam ( M ) R = \operatorname{diam}(M) R = diam ( M ) . Define the enlarged domain
Ω = M + R B 1 ( 0 ) . \Omega= M + R B_{1}(0). Ω = M + R B 1 ( 0 ) . The objective function f 0 f_{0} f 0 is quasiconvex on Ω \Omega Ω , while each constraint function f i f_{i} f i (i = 1 , … , m i = 1,\ldots,m i = 1 , … , m ) is μ \mu μ -strongly quasiconvex on Ω \Omega Ω for some μ > 0 \mu> 0 μ > 0 .
Each function f i f_{i} f i , i = 0 , … , m i = 0,\ldots,m i = 0 , … , m , has a Lipschitz-continuous gradient on Ω \Omega Ω . Consequently, each f i f_{i} f i is Lipschitz continuous on Ω \Omega Ω . We denote by L Ω > 0 L_{\Omega} > 0 L Ω > 0 a common Lipschitz constant for the functions f 0 , … , f m f_{0},\ldots,f_{m} f 0 , … , f m on Ω \Omega Ω .
Gradients do not vanish on M M M , admitting a strictly positive lower bound:
γ : = min 0 ≤ i ≤ m min x ∈ M ∥ f i ′ ( x ) ∥ > 0. \gamma:= \min_{0 \leq i \leq m} \min_{x \in M} \lVert f_{i}'(x) \rVert> 0. γ := 0 ≤ i ≤ m min x ∈ M min ∥ f i ′ ( x )∥ > 0. Let the algorithm parameters be chosen as
ρ k = 1 k + 0.5 , α k = 1 k + 1 . \rho_{k} = \frac{1}{\sqrt{k+0.5}}, \qquad\alpha_{k} = \frac{1}{k+1}. ρ k = k + 0.5 1 , α k = k + 1 1 . Then, for the sequence { x k } k \{x^{k}\}_{k} { x k } k generated by Algorithm 1, there exists a constant C > 0 C > 0 C > 0 such that, for every integer k ≥ 3 k \geq3 k ≥ 3 , one can find an index i ′ ∈ { 0 , 1 , … , k } i' \in\{0,1,\ldots,k\} i ′ ∈ { 0 , 1 , … , k } satisfying
∣ f 0 ( x i ′ ) − f 0 ( x ∗ ) ∣ ≤ A k 1 / 4 and d ( x i ′ , Q ) ≤ A k 1 / 4 , \lvert f_{0}(x^{i'}) - f_{0}(x^{*}) \rvert\leq\frac{A}{k^{1/4}}
\qquad\text{and}\qquad
d(x^{i'},Q) \leq\frac{A}{k^{1/4}}, ∣ f 0 ( x i ′ ) − f 0 ( x ∗ )∣ ≤ k 1/4 A and d ( x i ′ , Q ) ≤ k 1/4 A , where x ∗ x^{*} x ∗ is an optimal solution to the constrained problem, Q = { x ∈ M : f i ( x ) ≤ 0 , i = 1 , … , m } Q = \{x \in M : f_{i}(x) \leq0,\ i = 1,\ldots,m\} Q = { x ∈ M : f i ( x ) ≤ 0 , i = 1 , … , m } is the feasible set, and d ( x , Q ) = inf y ∈ Q ∥ x − y ∥ d(x,Q) = \inf_{y \in Q} \lVert x-y \rVert d ( x , Q ) = inf y ∈ Q ∥ x − y ∥ represents the Euclidean distance to $Q.
Proof. Let L Ω ′ L'_{\Omega} L Ω ′ denote a common Lipschitz constant for the gradients of f 0 , f 1 , … , f m f_{0},f_{1},\ldots,f_{m} f 0 , f 1 , … , f m on Ω \Omega Ω . For every k k k , define
I ( x k ) = { i ∈ { 1 , … , m } : f i ( x k ) = f ~ ( x k ) } . I(x^{k}) = \{i \in\{1,\ldots,m\} : f_{i}(x^{k}) = \widetilde{f}(x^{k})\}. I ( x k ) = { i ∈ { 1 , … , m } : f i ( x k ) = f ( x k )} .
First consider the case
f ~ ( x k ) > ρ k R ~ . \widetilde{f}(x^{k}) > \rho_{k}\widetilde{R}. f ( x k ) > ρ k R .
In this case, the algorithm selects ξ k \xi_k ξ k uniformly from I ( x k ) I(x^k) I ( x k ) , while u k u_k u k is uniformly distributed on S n − 1 S^{n-1} S n − 1 . By the representation of the stochastic finite-difference estimator, its conditional mathematical expectation with respect to x k x^k x k is the corresponding smoothed gradient. Hence
E [ p k ∣ x k ] = 1 ∣ I ( x k ) ∣ ∑ i ∈ I ( x k ) f i ′ ( x k , α k ) . \mathbb{E}[p^k \mid x^k] = \frac{1}{|I(x^k)|} \sum_{i \in I(x^k)} f_i'(x^k,\alpha_k). E [ p k ∣ x k ] = ∣ I ( x k ) ∣ 1 i ∈ I ( x k ) ∑ f i ′ ( x k , α k ) .
For every i ∈ I ( x k ) i \in I(x^k) i ∈ I ( x k ) , f i ( x k ) = f ~ ( x k ) f_i(x^k) = \tilde{f}(x^k) f i ( x k ) = f ~ ( x k ) . Then, by the smoothing estimate,
⟨ f i ′ ( x k , α k ) , x k − x ∗ ⟩ ≥ ⟨ f i ′ ( x k ) , x k − x ∗ ⟩ − L Ω ′ diam ( M ) α k . \langle f_i'(x^k,\alpha_k),x^k-x^*\rangle\geq\langle f_i'(x^k),x^k-x^*\rangle-L'_\Omega\operatorname{diam}(M)\alpha_k. ⟨ f i ′ ( x k , α k ) , x k − x ∗ ⟩ ≥ ⟨ f i ′ ( x k ) , x k − x ∗ ⟩ − L Ω ′ diam ( M ) α k .
Since x ∗ ∈ Q x^* \in Q x ∗ ∈ Q , we have f i ( x ∗ ) ≤ 0 f_i(x^*) \leq0 f i ( x ∗ ) ≤ 0 . Moreover, f i ( x k ) = f ~ ( x k ) f_i(x^k) = \tilde{f}(x^k) f i ( x k ) = f ~ ( x k ) . Hence, by the geometric inequality,
⟨ f i ′ ( x k ) , x k − x ∗ ⟩ ≥ γ L Ω ( f i ( x k ) − f i ( x ∗ ) ) ≥ γ L Ω f ~ ( x k ) . \langle f_i'(x^k),x^k-x^*\rangle\geq\frac{\gamma}{L_\Omega}(f_i(x^k)-f_i(x^*)) \geq\frac{\gamma}{L_\Omega}\tilde{f}(x^k). ⟨ f i ′ ( x k ) , x k − x ∗ ⟩ ≥ L Ω γ ( f i ( x k ) − f i ( x ∗ )) ≥ L Ω γ f ~ ( x k ) .
Consequently,
⟨ f i ′ ( x k , α k ) , x k − x ∗ ⟩ ≥ γ L Ω f ~ ( x k ) − L Ω ′ diam ( M ) α k . \langle f_i'(x^k,\alpha_k),x^k-x^*\rangle\geq\frac{\gamma}{L_\Omega}\tilde{f}(x^k)-L'_\Omega\operatorname{diam}(M)\alpha_k. ⟨ f i ′ ( x k , α k ) , x k − x ∗ ⟩ ≥ L Ω γ f ~ ( x k ) − L Ω ′ diam ( M ) α k .
This estimate holds for every i ∈ I ( x k ) i \in I(x^k) i ∈ I ( x k ) . Then, after averaging over all i ∈ I ( x k ) i \in I(x^k) i ∈ I ( x k ) , we obtain
⟨ E [ p k ∣ x k ] , x k − x ∗ ⟩ ≥ γ L Ω f ~ ( x k ) − L Ω ′ diam ( M ) α k > γ R ~ L Ω ρ k − L Ω ′ diam ( M ) α k , \langle\mathbb{E}[p^k \mid x^k],x^k-x^*\rangle\geq\frac{\gamma}{L_\Omega}\tilde{f}(x^k)-L'_\Omega\operatorname{diam}(M)\alpha_k > \frac{\gamma\widetilde{R}}{L_\Omega}\rho_k-L'_\Omega\operatorname{diam}(M)\alpha_k, ⟨ E [ p k ∣ x k ] , x k − x ∗ ⟩ ≥ L Ω γ f ~ ( x k ) − L Ω ′ diam ( M ) α k > L Ω γ R ρ k − L Ω ′ diam ( M ) α k ,
where the strict inequality follows from f ~ ( x k ) > ρ k R ~ \tilde{f}(x^k)>\rho_k\widetilde{R} f ~ ( x k ) > ρ k R .
Consider the projected iteration
x i + 1 = Π M ( x i − ρ i p i ) . x^{i+1}=\Pi_M(x^i-\rho_i p^i). x i + 1 = Π M ( x i − ρ i p i ) .
Since x ∗ ∈ M x^* \in M x ∗ ∈ M and M M M is closed and convex, the nonexpansiveness of the projection gives
∥ x i + 1 − x ∗ ∥ 2 ≤ ∥ x i − x ∗ − ρ i p i ∥ 2 = ∥ x i − x ∗ ∥ 2 − 2 ρ i ⟨ p i , x i − x ∗ ⟩ + ρ i 2 ∥ p i ∥ 2 . \|x^{i+1}-x^*\|^2\leq\|x^i-x^*-\rho_i p^i\|^2=\|x^i-x^*\|^2-2\rho_i\langle p^i,x^i-x^*\rangle+\rho_i^2\|p^i\|^2. ∥ x i + 1 − x ∗ ∥ 2 ≤ ∥ x i − x ∗ − ρ i p i ∥ 2 = ∥ x i − x ∗ ∥ 2 − 2 ρ i ⟨ p i , x i − x ∗ ⟩ + ρ i 2 ∥ p i ∥ 2 .
Since ∥ p i ∥ ≤ n L Ω \|p^i\|\leq nL_\Omega ∥ p i ∥ ≤ n L Ω , we have
∥ x i + 1 − x ∗ ∥ 2 ≤ ∥ x i − x ∗ ∥ 2 − 2 ρ i ⟨ p i , x i − x ∗ ⟩ + n 2 L Ω 2 ρ i 2 . \|x^{i+1}-x^*\|^2\leq\|x^i-x^*\|^2-2\rho_i\langle p^i,x^i-x^*\rangle+n^2L_\Omega^2\rho_i^2. ∥ x i + 1 − x ∗ ∥ 2 ≤ ∥ x i − x ∗ ∥ 2 − 2 ρ i ⟨ p i , x i − x ∗ ⟩ + n 2 L Ω 2 ρ i 2 .
Taking the conditional mathematical expectation with respect to x i x^i x i , we obtain
E [ ∥ x i + 1 − x ∗ ∥ 2 ∣ x i ] ≤ ∥ x i − x ∗ ∥ 2 − 2 ρ i ⟨ E [ p i ∣ x i ] , x i − x ∗ ⟩ + n 2 L Ω 2 ρ i 2 . \mathbb{E}\left[\|x^{i+1}-x^*\|^2\mid x^i\right]\leq\|x^i-x^*\|^2-2\rho_i\langle\mathbb{E}[p^i\mid x^i],x^i-x^*\rangle+n^2L_\Omega^2\rho_i^2. E [ ∥ x i + 1 − x ∗ ∥ 2 ∣ x i ] ≤ ∥ x i − x ∗ ∥ 2 − 2 ρ i ⟨ E [ p i ∣ x i ] , x i − x ∗ ⟩ + n 2 L Ω 2 ρ i 2 .
Put r i = ∥ x i − x ∗ ∥ r_i=\|x^i-x^*\| r i = ∥ x i − x ∗ ∥ . Let k ′ = ⌊ k / 3 ⌋ k'=\lfloor k/3\rfloor k ′ = ⌊ k /3 ⌋ and define
I k = { i ∈ { k ′ , … , k } : f ~ ( x i ) ≤ ρ i R ~ } . I_k=\{i\in\{k',\ldots,k\}:\tilde{f}(x^i)\leq\rho_i\widetilde{R}\}. I k = { i ∈ { k ′ , … , k } : f ~ ( x i ) ≤ ρ i R } .
Thus, I k I_k I k is the set of iterations at which the algorithm operates in the objective-minimization mode.
First, we prove that I k ≠ ∅ I_k \ne\varnothing I k = ∅ . Suppose, to the contrary, that I k = ∅ I_k = \varnothing I k = ∅ . Then for all i ∈ { k ′ , … , k } i \in\{k', \ldots, k\} i ∈ { k ′ , … , k } , we have f ( x i ) > ρ i R ~ f(x^i) > \rho_i \widetilde{R} f ( x i ) > ρ i R .
Summing the recurrence inequality for E [ r i + 1 2 ∣ x i ] \mathbb{E}[r_{i+1}^2 \mid x^i] E [ r i + 1 2 ∣ x i ] from i = k ′ i = k' i = k ′ to i = k i = k i = k and taking total expectations gives:
E [ r k + 1 2 ] ≤ E [ r k ′ 2 ] − ( 2 γ R ~ L Ω − n 2 L Ω 2 ) ∑ i = k ′ k ρ i 2 + 2 L Ω R ∑ i = k ′ k ρ i α i . \mathbb{E}[r_{k+1}^2] \le\mathbb{E}[r_{k'}^2] - \left(\frac{2\gamma\widetilde{R}}{L_\Omega} - n^2L_\Omega^2\right)\sum_{i=k'}^k \rho_i^2 + 2L_\Omega R\sum_{i=k'}^k \rho_i\alpha_i. E [ r k + 1 2 ] ≤ E [ r k ′ 2 ] − ( L Ω 2 γ R − n 2 L Ω 2 ) i = k ′ ∑ k ρ i 2 + 2 L Ω R i = k ′ ∑ k ρ i α i .
By the choice of R ~ \widetilde{R} R , we have
2 γ R ~ L Ω − n 2 L Ω 2 ≥ 2 R 2 ln 3 + 1. \frac{2\gamma\widetilde{R}}{L_\Omega} - n^2L_\Omega^2 \ge\frac{2R^2}{\ln3}+1. L Ω 2 γ R − n 2 L Ω 2 ≥ ln 3 2 R 2 + 1.
Furthermore, E [ r k ′ 2 ] ≤ R 2 \mathbb{E}[r_{k'}^2] \le R^2 E [ r k ′ 2 ] ≤ R 2 , and for all sufficiently large k k k ,
∑ i = k ′ k ρ i 2 ≥ ln 3 2 , ∑ i = k ′ k ρ i α i ≤ C 0 k . \sum_{i=k'}^k \rho_i^2 \ge\frac{\ln3}{2}, \qquad\sum_{i=k'}^k \rho_i\alpha_i \le\frac{C_0}{\sqrt{k}}. i = k ′ ∑ k ρ i 2 ≥ 2 ln 3 , i = k ′ ∑ k ρ i α i ≤ k C 0 .
Substituting these estimates yields
0 ≤ E [ r k + 1 2 ] ≤ R 2 − ( 2 R 2 ln 3 + 1 ) ln 3 2 + C k = − ln 3 2 + C k . \begin{aligned}
0 \le\mathbb{E}[r_{k+1}^2] \le R^2-\left(\frac{2R^2}{\ln3}+1\right)\frac{\ln3}{2}+\frac{C}{\sqrt{k}} \\
&= -\frac{\ln3}{2}+\frac{C}{\sqrt{k}}.
\end{aligned} 0 ≤ E [ r k + 1 2 ] ≤ R 2 − ( ln 3 2 R 2 + 1 ) 2 ln 3 + k C = − 2 ln 3 + k C .
Since ln 3 / 2 > 0 \ln3/2 > 0 ln 3/2 > 0 , the right-hand side is strictly negative for all sufficiently large k k k , which is a contradiction.
Thus, I k ≠ ∅ I_k \ne\varnothing I k = ∅ . Now, for i ∈ I k i \in I_k i ∈ I k , define
v i = ⟨ f 0 ′ ( x i , α i ) , x i − x ∗ ⟩ . v_i=\langle f'_0(x^i,\alpha_i),x^i-x^*\rangle. v i = ⟨ f 0 ′ ( x i , α i ) , x i − x ∗ ⟩ .
For i ∉ I k i \notin I_k i ∈ / I k , define
v ~ i = ⟨ E [ p i ∣ x i ] , x i − x ∗ ⟩ . \widetilde{v}_i=\langle\mathbb{E}[p^i\mid x^i],x^i-x^*\rangle. v i = ⟨ E [ p i ∣ x i ] , x i − x ∗ ⟩ .
Summing the conditional expectations from i = k ′ i = k' i = k ′ to i = k i = k i = k and taking total expectations gives
E [ r k + 1 2 ] + 2 ∑ i ∈ I k ρ i E [ v i ] + 2 ∑ i ∉ I k ρ i E [ v ~ i ] ≤ E [ r k ′ 2 ] + n 2 L Ω 2 ∑ i = k ′ k ρ i 2 . \mathbb{E}[r_{k+1}^2]+2\sum_{i\in I_k}\rho_i\mathbb{E}[v_i]+2\sum_{i\notin I_k}\rho_i\mathbb{E}[\widetilde{v}_i]\le\mathbb{E}[r_{k'}^2]+n^2L_\Omega^2\sum_{i=k'}^k\rho_i^2. E [ r k + 1 2 ] + 2 i ∈ I k ∑ ρ i E [ v i ] + 2 i ∈ / I k ∑ ρ i E [ v i ] ≤ E [ r k ′ 2 ] + n 2 L Ω 2 i = k ′ ∑ k ρ i 2 .
Suppose, to the contrary, that v i ≥ R ~ 2 ρ i v_i\ge\widetilde{R}^2\rho_i v i ≥ R 2 ρ i for all i ∈ I k i\in I_k i ∈ I k . Using the definition of R ~ \widetilde{R} R , the lower bound for v ~ i \widetilde{v}_i v i , and the estimates for the constraint-reduction iterations, we obtain:
1 ≥ ∑ i = k ′ k 1 i + 0.5 − 2 L Ω 2 diam ( M ) ∑ i = k ′ k ρ i α i . 1\ge\sum_{i=k'}^k\frac{1}{i+0.5}-2L_\Omega^2\operatorname{diam}(M)\sum_{i=k'}^k\rho_i\alpha_i. 1 ≥ i = k ′ ∑ k i + 0.5 1 − 2 L Ω 2 diam ( M ) i = k ′ ∑ k ρ i α i .
Since ∑ i = k ′ k 1 i + 0.5 ≥ ln 3 \sum_{i=k'}^k \frac{1}{i+0.5} \ge\ln3 ∑ i = k ′ k i + 0.5 1 ≥ ln 3 , and ∑ i = k ′ k ρ i α i ≤ C 0 k \sum_{i=k'}^k \rho_i\alpha_i \le\frac{C_0}{\sqrt{k}} ∑ i = k ′ k ρ i α i ≤ k C 0 , we conclude that 1 ≥ ln 3 − C k 1 \ge\ln3 - \frac{C}{\sqrt{k}} 1 ≥ ln 3 − k C , where C > 0 C>0 C > 0 is independent of k k k . Since ln 3 > 1 \ln3>1 ln 3 > 1 , the right-hand side is greater than 1 for all sufficiently large k k k , which is a contradiction. Therefore, there exists an index i ′ ∈ I k i' \in I_k i ′ ∈ I k such that ⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ < R ~ 2 ρ i ′ \langle f'_0(x^{i'},\alpha_{i'}),x^{i'}-x^*\rangle< \widetilde{R}^2\rho_{i'} ⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ < R 2 ρ i ′ .
First suppose that x i ′ ∈ Q x^{i'}\in Q x i ′ ∈ Q . Using the smoothing estimate and the geometric inequality for the strongly quasiconvex objective function f 0 f_0 f 0 , we obtain
R ~ 2 ρ i ′ > ⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ ≥ γ L Ω ( f 0 ( x i ′ ) − f 0 ( x ∗ ) ) − L Ω ′ diam ( M ) α i ′ . \widetilde{R}^2\rho_{i'} > \langle f'_0(x^{i'},\alpha_{i'}),x^{i'}-x^*\rangle\ge\frac{\gamma}{L_{\Omega}}(f_0(x^{i'})-f_0(x^*))-L'_{\Omega}\operatorname{diam}(M)\alpha_{i'}. R 2 ρ i ′ > ⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ ≥ L Ω γ ( f 0 ( x i ′ ) − f 0 ( x ∗ )) − L Ω ′ diam ( M ) α i ′ .
Hence,
f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ C 1 ρ i ′ + C 2 α i ′ . f_0(x^{i'})-f_0(x^*) \le C_1\rho_{i'}+C_2\alpha_{i'}. f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ C 1 ρ i ′ + C 2 α i ′ .
Since i ′ ≥ k ′ i'\ge k' i ′ ≥ k ′ and k ′ > k 3 − 1 k'>\frac{k}{3}-1 k ′ > 3 k − 1 , there exists C 3 > 0 C_3>0 C 3 > 0 such that ρ i ′ ≤ C 3 k \rho_{i'}\le\frac{C_3}{\sqrt{k}} ρ i ′ ≤ k C 3 . Then,
f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ C 4 k . f_0(x^{i'})-f_0(x^*)\le\frac{C_4}{\sqrt{k}}. f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ k C 4 .
Now consider the case x i ′ ∉ Q x^{i'}\notin Q x i ′ ∈ / Q . Let y i ′ = Π Q ( x i ′ ) y^{i'}=\Pi_Q(x^{i'}) y i ′ = Π Q ( x i ′ ) . By Lemma 4,
∥ x i ′ − y i ′ ∥ ≤ 2 μ f ~ + ( x i ′ ) . \left\|x^{i'}-y^{i'}\right\|\le\frac{2}{\sqrt{\mu}}\sqrt{\widetilde{f}^{+}(x^{i'})}. x i ′ − y i ′ ≤ μ 2 f + ( x i ′ ) .
By expanding the inner product difference, we have
⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ − ⟨ f 0 ′ ( y i ′ , α i ′ ) , y i ′ − x ∗ ⟩ = ⟨ f 0 ′ ( x i ′ , α i ′ ) − f 0 ′ ( y i ′ , α i ′ ) , x i ′ − x ∗ ⟩ + ⟨ f 0 ′ ( y i ′ , α i ′ ) , x i ′ − y i ′ ⟩ . \begin{aligned}
&\langle f'_0(x^{i'},\alpha_{i'}),x^{i'}-x^*\rangle-\langle f'_0(y^{i'},\alpha_{i'}),y^{i'}-x^*\rangle\\
&=\langle f'_0(x^{i'},\alpha_{i'})-f'_0(y^{i'},\alpha_{i'}),x^{i'}-x^*\rangle+\langle f'_0(y^{i'},\alpha_{i'}),x^{i'}-y^{i'}\rangle.
\end{aligned} ⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ − ⟨ f 0 ′ ( y i ′ , α i ′ ) , y i ′ − x ∗ ⟩ = ⟨ f 0 ′ ( x i ′ , α i ′ ) − f 0 ′ ( y i ′ , α i ′ ) , x i ′ − x ∗ ⟩ + ⟨ f 0 ′ ( y i ′ , α i ′ ) , x i ′ − y i ′ ⟩ .
Using the Lipschitz continuity of the gradient of f 0 f_0 f 0 (with constant L Ω ′ L'_{\Omega} L Ω ′ ) for the first term and the boundedness of the smoothed gradient ∥ f 0 ′ ( y i ′ , α i ′ ) ∥ ≤ L Ω \|f'_0(y^{i'},\alpha_{i'})\|\le L_{\Omega} ∥ f 0 ′ ( y i ′ , α i ′ ) ∥ ≤ L Ω for the second term, we obtain
⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ ≥ ⟨ f 0 ′ ( y i ′ , α i ′ ) , y i ′ − x ∗ ⟩ − ( L Ω ′ diam ( M ) + L Ω ) ∥ x i ′ − y i ′ ∥ ≥ ⟨ f 0 ′ ( y i ′ , α i ′ ) , y i ′ − x ∗ ⟩ − C 5 f ~ + ( x i ′ ) . \begin{aligned}
\langle f'_0(x^{i'},\alpha_{i'}),x^{i'}-x^*\rangle
&\ge\langle f'_0(y^{i'},\alpha_{i'}),y^{i'}-x^*\rangle-(L'_{\Omega}\operatorname{diam}(M)+L_{\Omega})\|x^{i'}-y^{i'}\|\\
&\ge\langle f'_0(y^{i'},\alpha_{i'}),y^{i'}-x^*\rangle-C_5\sqrt{\widetilde{f}^{+}(x^{i'})}.
\end{aligned} ⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ ≥ ⟨ f 0 ′ ( y i ′ , α i ′ ) , y i ′ − x ∗ ⟩ − ( L Ω ′ diam ( M ) + L Ω ) ∥ x i ′ − y i ′ ∥ ≥ ⟨ f 0 ′ ( y i ′ , α i ′ ) , y i ′ − x ∗ ⟩ − C 5 f + ( x i ′ ) .
Since y i ′ ∈ Q y^{i'}\in Q y i ′ ∈ Q , we may apply the estimate obtained above for the objective function. Hence,
⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ ≥ γ L Ω ( f 0 ( x i ′ ) − f 0 ( x ∗ ) ) − C 6 f ~ + ( x i ′ ) . \langle f'_0(x^{i'},\alpha_{i'}),x^{i'}-x^*\rangle\ge\frac{\gamma}{L_{\Omega}}(f_0(x^{i'})-f_0(x^*))-C_6\sqrt{\widetilde{f}^{+}(x^{i'})}. ⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ ≥ L Ω γ ( f 0 ( x i ′ ) − f 0 ( x ∗ )) − C 6 f + ( x i ′ ) .
On the other hand, by the choice of i ′ i' i ′ , we have ⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ < R ~ 2 ρ i ′ \langle f'_0(x^{i'},\alpha_{i'}),x^{i'}-x^*\rangle< \widetilde{R}^2\rho_{i'} ⟨ f 0 ′ ( x i ′ , α i ′ ) , x i ′ − x ∗ ⟩ < R 2 ρ i ′ . Then,
f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ C 7 f ~ + ( x i ′ ) + C 8 ρ i ′ . f_0(x^{i'})-f_0(x^*)\le C_7\sqrt{\widetilde{f}^{+}(x^{i'})}+C_8\rho_{i'}. f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ C 7 f + ( x i ′ ) + C 8 ρ i ′ .
Since i ′ ∈ I k i'\in I_k i ′ ∈ I k , the algorithm is in the objective-minimization mode at iteration i ′ i' i ′ . Hence, by the switching rule, f ~ ( x i ′ ) ≤ ρ i ′ R ~ \widetilde{f}(x^{i'})\le\rho_{i'}\widetilde{R} f ( x i ′ ) ≤ ρ i ′ R . Consequently,
f ~ + ( x i ′ ) ≤ R ~ ρ i ′ . \widetilde{f}^{+}(x^{i'})\le\widetilde{R}\rho_{i'}. f + ( x i ′ ) ≤ R ρ i ′ .
Since i ′ ≥ k ′ i' \ge k' i ′ ≥ k ′ , there exists C 9 > 0 C_9 > 0 C 9 > 0 such that ρ i ′ ≤ C 9 k \rho_{i'} \le\frac{C_9}{\sqrt{k}} ρ i ′ ≤ k C 9 . Then, f ~ + ( x i ′ ) ≤ C 10 k 1 / 4 \sqrt{\widetilde{f}^{+}(x^{i'})} \le\frac{C_{10}}{k^{1/4}} f + ( x i ′ ) ≤ k 1/4 C 10 .
It follows that there exists A 1 > 0 A_1 > 0 A 1 > 0 , independent of k k k , such that
f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ A 1 k 1 / 4 . f_0(x^{i'}) - f_0(x^*) \le\frac{A_1}{k^{1/4}}. f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ k 1/4 A 1 .
Moreover, for every i = 1 , … , m i = 1,\ldots,m i = 1 , … , m , we have f i ( x i ′ ) ≤ f ~ ( x i ′ ) ≤ C 11 k f_i(x^{i'}) \le\widetilde{f}(x^{i'}) \le\frac{C_{11}}{\sqrt{k}} f i ( x i ′ ) ≤ f ( x i ′ ) ≤ k C 11 . Applying Lemma 4, we obtain
dist ( x i ′ , Q ) ≤ 2 μ f ~ + ( x i ′ ) ≤ A 2 k 1 / 4 . \operatorname{dist}(x^{i'},Q) \le\frac{2}{\sqrt{\mu}}\sqrt{\widetilde{f}^{+}(x^{i'})} \le\frac{A_2}{k^{1/4}}. dist ( x i ′ , Q ) ≤ μ 2 f + ( x i ′ ) ≤ k 1/4 A 2 .
It remains to obtain a lower bound for the objective error. Since y i ′ ∈ Q y^{i'} \in Q y i ′ ∈ Q and x ∗ x^* x ∗ is an optimal solution, we have f 0 ( y i ′ ) ≥ f 0 ( x ∗ ) f_0(y^{i'}) \ge f_0(x^*) f 0 ( y i ′ ) ≥ f 0 ( x ∗ ) . Since f 0 f_0 f 0 is Lipschitz continuous on Ω \Omega Ω , we have
f 0 ( x i ′ ) − f 0 ( y i ′ ) ≥ − L Ω ∥ x i ′ − y i ′ ∥ f_0(x^{i'}) - f_0(y^{i'}) \ge-L_{\Omega}\lVert x^{i'}-y^{i'}\rVert f 0 ( x i ′ ) − f 0 ( y i ′ ) ≥ − L Ω ∥ x i ′ − y i ′ ∥
⟹ f 0 ( x i ′ ) − f 0 ( x ∗ ) ≥ − L Ω dist ( x i ′ , Q ) ≥ − A 3 k 1 / 4 . \Longrightarrow\quad f_0(x^{i'}) - f_0(x^*) \ge-L_{\Omega}\operatorname{dist}(x^{i'},Q) \ge-\frac{A_3}{k^{1/4}}. ⟹ f 0 ( x i ′ ) − f 0 ( x ∗ ) ≥ − L Ω dist ( x i ′ , Q ) ≥ − k 1/4 A 3 .
Combining this estimate with the previously obtained upper bound, we conclude that
∣ f 0 ( x i ′ ) − f 0 ( x ∗ ) ∣ ≤ A k 1 / 4 , \left|f_0(x^{i'}) - f_0(x^*)\right| \le\frac{A}{k^{1/4}}, f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ k 1/4 A ,
for some constant A > 0 A > 0 A > 0 independent of k k k . At the same time, dist ( x i ′ , Q ) ≤ A 4 k 1 / 4 \operatorname{dist}(x^{i'},Q) \le\frac{A_4}{k^{1/4}} dist ( x i ′ , Q ) ≤ k 1/4 A 4 . Thus, for every k ≥ 3 k \ge3 k ≥ 3 , there exists i ′ ∈ { 0 , … , k } i' \in\{0,\ldots,k\} i ′ ∈ { 0 , … , k } for which both estimates hold. The proof is complete. □
Remark 9. If the Slater condition is additionally imposed, then the standard linear error bound
dist ( x , Q ) ≤ C S h + ( x ) \operatorname{dist}(x,Q) \le C_S h^{+}(x) dist ( x , Q ) ≤ C S h + ( x )
allows the constraint-violation estimate in Theorem 5 to be converted into a distance-to-feasibility estimate of the same order. Moreover, under the additional estimates used in the proof of Theorem 5 , the objective-function error satisfies
∣ f 0 ( x i ′ ) − f 0 ( x ∗ ) ∣ ≤ C S ′ k , \left|f_0(x^{i'}) - f_0(x^*)\right| \le\frac{C'_S}{\sqrt{k}}, f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ k C S ′ ,
where C S ′ > 0 C'_S > 0 C S ′ > 0 is independent of k k k . Hence, to achieve
∣ f 0 ( x i ′ ) − f 0 ( x ∗ ) ∣ ≤ ε , \left|f_0(x^{i'}) - f_0(x^*)\right| \le\varepsilon, f 0 ( x i ′ ) − f 0 ( x ∗ ) ≤ ε ,
it is sufficient to take
k = O ( ε − 2 ) . k = O(\varepsilon^{-2}). k = O ( ε − 2 ) .
For comparison, Nguyen and Balasubramanian [22 ] establish an oracle complexity of order O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) in the convex setting and O ( ε − 3 ) O(\varepsilon^{-3}) O ( ε − 3 ) in the nonconvex setting, with respect to their approximate-KKT criterion. Thus, with respect to the accuracy parameter, the present Slater-based objective-value estimate has the same order O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) as their convex result.
This comparison is only at the level of the dependence on the accuracy parameter. The two results are obtained under different assumptions and convergence criteria. In particular, our objective function is assumed to be quasiconvex, whereas in [22 ] consider a different class of functionally constrained stochastic optimization problems. Moreover, their approximate-KKT guarantee does not directly imply the objective-function value estimate established in our theorem.
The Penalty Function Method
The presentation of this method is based on problem (13). We assume that all functions f i f_i f i , with i = 1 , … , m i=1,\ldots,m i = 1 , … , m , are strongly quasiconvex and locally Lipschitz continuous on R n \mathbb{R}^n R n , that the function f 0 f_0 f 0 is quasiconvex and regular, and that the feasible set M ⊂ R n M\subset\mathbb{R}^n M ⊂ R n is convex and compact.
We also assume that the minimal value
f 0 ∗ : = min x ∈ Q f 0 ( x ) , Q : = { x ∈ M : f i ( x ) ≤ 0 , i = 1 , … , m } , f_0^*:=\min_{x\in Q}f_0(x),\quad Q:=\{x\in M:f_i(x)\leq0,\ i=1,\ldots,m\}, f 0 ∗ := x ∈ Q min f 0 ( x ) , Q := { x ∈ M : f i ( x ) ≤ 0 , i = 1 , … , m } ,
is known. The goal is to generate a sequence { x k } k ⊂ M \{x^k\}_k\subset M { x k } k ⊂ M that converges to the set
Q ∗ : = { x ∈ Q : f 0 ( x ) = f 0 ∗ } Q^*:=\{x\in Q:f_0(x)=f_0^*\} Q ∗ := { x ∈ Q : f 0 ( x ) = f 0 ∗ }
of minimizers. Consider the auxiliary function,
f ~ 0 ( x ) : = max { f 0 ( x ) − f 0 ∗ , f 1 ( x ) , … , f m ( x ) } . \widetilde{f}_0(x):=\max\{f_0(x)-f_0^*,f_1(x),\ldots,f_m(x)\}. f 0 ( x ) := max { f 0 ( x ) − f 0 ∗ , f 1 ( x ) , … , f m ( x )} .
Clearly, f ~ 0 \widetilde{f}_0 f 0 is quasiconvex and Q ∗ Q^* Q ∗ is the set of minimizers of f ~ 0 \widetilde{f}_0 f 0 on Q Q Q .
The algorithm performs a sliding minimization over the family of functions
F ( x , C ) : = f ~ 0 ( x ) + C ∑ i = 1 m [ max { 0 , f i ( x ) } ] 2 , C > 0 , F(x,C):=\widetilde{f}_0(x)+C\sum_{i=1}^{m}[\max\{0,f_i(x)\}]^2,\quad C>0, F ( x , C ) := f 0 ( x ) + C i = 1 ∑ m [ max { 0 , f i ( x )} ] 2 , C > 0 ,
on M M M , incorporating a quadratic penalty.
Let the sequence of iterates be generated by
x k + 1 = Π M ( x k − α k a k ) , ∀ k = 0 , 1 , … x^{k+1}=\Pi_M\left(x^k-\alpha_k a^k\right),\quad\forall k=0,1,\ldots x k + 1 = Π M ( x k − α k a k ) , ∀ k = 0 , 1 , …
where a k ∈ ∂ F ( x k , C k ) a^k\in\partial F(x^k,C_k) a k ∈ ∂ F ( x k , C k ) and, more explicitly,
a k = a 0 k + 2 C k ∑ i = 1 m max { 0 , f i ( x k ) } a i k , a 0 k ∈ ∂ f ~ 0 ( x k ) , a i k ∈ ∂ f i ( x k ) , i = 1 , … , m . a^k=a_0^k+2C_k\sum_{i=1}^{m}\max\{0,f_i(x^k)\}a_i^k,\quad a_0^k\in\partial\widetilde f_0(x^k),\quad a_i^k\in\partial f_i(x^k),\ i=1,\ldots,m. a k = a 0 k + 2 C k i = 1 ∑ m max { 0 , f i ( x k )} a i k , a 0 k ∈ ∂ f 0 ( x k ) , a i k ∈ ∂ f i ( x k ) , i = 1 , … , m .
We impose the following conditions on the parameters
α k > 0 , ∑ k = 0 ∞ α k = + ∞ , C k → + ∞ , ∑ k = 0 ∞ α k 2 C k 2 < + ∞ , ∑ k = 0 ∞ α k C k 1 / 3 < + ∞ . \alpha_k>0,\quad\sum_{k=0}^{\infty}\alpha_k=+\infty,\quad C_k\to+\infty,\quad\sum_{k=0}^{\infty}\alpha_k^2C_k^2<+\infty,\quad\sum_{k=0}^{\infty}\frac{\alpha_k}{C_k^{1/3}}<+\infty. α k > 0 , k = 0 ∑ ∞ α k = + ∞ , C k → + ∞ , k = 0 ∑ ∞ α k 2 C k 2 < + ∞ , k = 0 ∑ ∞ C k 1/3 α k < + ∞.
For example, the previous assumptions hold when α k = 1 k \alpha_k=\frac{1}{k} α k = k 1 and C k = k 1 / 4 C_k=k^{1/4} C k = k 1/4 . We have the following convergence result.
Theorem 6. Let us consider the assumptions mentioned above on the functions f i f_i f i , with i = 0 , 1 , … , m i=0,1,\ldots,m i = 0 , 1 , … , m , and the set M M M . Assume that
0 ∉ ∂ f i ( x ) , ∀ x ∈ M , ∀ i = 0 , 1 , … , m . 0\notin\partial f_i(x),\quad\forall x\in M,\ \forall i=0,1,\ldots,m. 0 ∈ / ∂ f i ( x ) , ∀ x ∈ M , ∀ i = 0 , 1 , … , m . Then the sequence { x k } k \{x^k\}_k { x k } k generated by the above sliding minimization algorithm converges to the set Q ∗ Q^* Q ∗ .
Proof. Let x ∗ ∈ Q ∗ x^*\in Q^* x ∗ ∈ Q ∗ . Then the projection update yields
∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 − 2 α k ⟨ a k , x k − x ∗ ⟩ + α k 2 ∥ a k ∥ 2 . (15) \left\|x^{k+1}-x^*\right\|^2\leq\left\|x^k-x^*\right\|^2-2\alpha_k\langle a^k,x^k-x^*\rangle+\alpha_k^2\left\|a^k\right\|^2. \tag*{(15)} x k + 1 − x ∗ 2 ≤ x k − x ∗ 2 − 2 α k ⟨ a k , x k − x ∗ ⟩ + α k 2 a k 2 . (15)
We first estimate the middle term using Lemma 2. Let i ∈ { 1 , … , m } i\in\{1,\ldots,m\} i ∈ { 1 , … , m } be with f i ( x k ) > 0 f_i(x^k)>0 f i ( x k ) > 0 . Then by inequality (4),
f i ( x k ) − f i ( x ∗ ) ≤ L Ω ⟨ a i k ∥ a i k ∥ , x k − x ∗ ⟩ ≤ L Ω γ ~ ⟨ a i k , x k − x ∗ ⟩ , f_i(x^k)-f_i(x^*)\leq L_\Omega\left\langle\frac{a_i^k}{\left\|a_i^k\right\|},x^k-x^*\right\rangle\leq\frac{L_\Omega}{\widetilde\gamma}\left\langle a_i^k,x^k-x^*\right\rangle, f i ( x k ) − f i ( x ∗ ) ≤ L Ω ⟨ a i k a i k , x k − x ∗ ⟩ ≤ γ L Ω ⟨ a i k , x k − x ∗ ⟩ ,
where γ ~ : = min i min x ∈ M dist ( 0 , ∂ f i ( x ) ) > 0 \widetilde\gamma:=\min_i\min_{x\in M}\operatorname{dist}(0,\partial f_i(x))>0 γ := min i min x ∈ M dist ( 0 , ∂ f i ( x )) > 0 . Thus,
2 C k ∑ i = 1 m max { 0 , f i ( x k ) } ⟨ a i k , x k − x ∗ ⟩ ≥ 2 γ ~ C k L Ω ∑ i = 1 m max { 0 , f i ( x k ) } ( f i ( x k ) − f i ( x ∗ ) ) . 2C_k\sum_{i=1}^{m}\max\{0,f_i(x^k)\}\langle a_i^k,x^k-x^*\rangle\geq\frac{2\widetilde\gamma C_k}{L_\Omega}\sum_{i=1}^{m}\max\{0,f_i(x^k)\}\left(f_i(x^k)-f_i(x^*)\right). 2 C k i = 1 ∑ m max { 0 , f i ( x k )} ⟨ a i k , x k − x ∗ ⟩ ≥ L Ω 2 γ C k i = 1 ∑ m max { 0 , f i ( x k )} ( f i ( x k ) − f i ( x ∗ ) ) .
Since f ~ 0 ( x ∗ ) = 0 \widetilde f_0(x^*)=0 f 0 ( x ∗ ) = 0 and f ~ 0 ( x k ) > 0 \widetilde f_0(x^k)>0 f 0 ( x k ) > 0 , we have
⟨ a 0 k , x k − x ∗ ⟩ ≥ γ ~ L Ω ( f ~ 0 ( x k ) − f ~ 0 ( x ∗ ) ) . \left\langle a_0^k,x^k-x^*\right\rangle\geq\frac{\widetilde\gamma}{L_\Omega}\left(\widetilde f_0(x^k)-\widetilde f_0(x^*)\right). ⟨ a 0 k , x k − x ∗ ⟩ ≥ L Ω γ ( f 0 ( x k ) − f 0 ( x ∗ ) ) .
Combining these, we obtain
⟨ a k , x k − x ∗ ⟩ ≥ 2 γ ~ L Ω ( F ( x k , C k ) − F ( x ∗ , C k ) ) . \left\langle a^k,x^k-x^*\right\rangle\geq\frac{2\widetilde\gamma}{L_\Omega}\left(F(x^k,C_k)-F(x^*,C_k)\right). ⟨ a k , x k − x ∗ ⟩ ≥ L Ω 2 γ ( F ( x k , C k ) − F ( x ∗ , C k ) ) .
Next, we estimate the difference F ( x k , C k ) − F ( x ∗ , C k ) F(x^k,C_k)-F(x^*,C_k) F ( x k , C k ) − F ( x ∗ , C k ) using Lemma 4. Note that F ( x , C k ) = f ~ 0 ( x ) F(x,C_k)=\tilde f_0(x) F ( x , C k ) = f ~ 0 ( x ) for all x ∈ Q x\in Q x ∈ Q . Hence,
F ∗ ( C k ) : = inf x ∈ M F ( x , C k ) ≤ inf x ∈ Q F ( x , C k ) = f ~ 0 ∗ . F^*(C_k):=\inf_{x\in M}F(x,C_k)\le\inf_{x\in Q}F(x,C_k)=\tilde f_0^*. F ∗ ( C k ) := x ∈ M inf F ( x , C k ) ≤ x ∈ Q inf F ( x , C k ) = f ~ 0 ∗ .
For x ∈ M ∖ Q x\in M\setminus Q x ∈ M ∖ Q , we have for any y ∈ Q y\in Q y ∈ Q that
f ~ 0 ( x ) ≥ f ~ 0 ( y ) − L ∥ x − y ∥ ≥ f ~ 0 ∗ − L ( dist ( x , Q ) ) . \tilde f_0(x)\ge\tilde f_0(y)-L\lVert x-y\rVert\ge\tilde f_0^*-L(\operatorname{dist}(x,Q)). f ~ 0 ( x ) ≥ f ~ 0 ( y ) − L ∥ x − y ∥ ≥ f ~ 0 ∗ − L ( dist ( x , Q )) .
Moreover, by Lemma 4,
C k ∑ i = 1 m [ max { 0 , f i ( x ) } ] 2 ≥ C k μ 2 8 ( dist ( x , Q ) ) 4 . C_k\sum_{i=1}^{m}[\max\{0,f_i(x)\}]^2\ge\frac{C_k\mu^2}{8}(\operatorname{dist}(x,Q))^4. C k i = 1 ∑ m [ max { 0 , f i ( x )} ] 2 ≥ 8 C k μ 2 ( dist ( x , Q ) ) 4 .
Combining the above estimates, there exists a constant A > 0 A>0 A > 0 such that
f ~ 0 ∗ − F ( x , C k ) ≤ A C k 1 / 3 . \tilde f_0^*-F(x,C_k)\le\frac{A}{C_k^{1/3}}. f ~ 0 ∗ − F ( x , C k ) ≤ C k 1/3 A .
Since the subgradients a k a^k a k are bounded on the compact set M M M , there exists B > 0 B>0 B > 0 such that ∥ a k ∥ ≤ B C k \lVert a^k\rVert\le BC_k ∥ a k ∥ ≤ B C k . Substituting these bounds into (14) gives
∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 + α k A γ ~ L Ω C k 1 / 3 + B 2 C k 2 α k 2 . (16) \lVert x^{k+1}-x^*\rVert^2\le\lVert x^k-x^*\rVert^2+\alpha_k\frac{A\tilde\gamma}{L_\Omega C_k^{1/3}}+B^2C_k^2\alpha_k^2. \tag*{(16)} ∥ x k + 1 − x ∗ ∥ 2 ≤ ∥ x k − x ∗ ∥ 2 + α k L Ω C k 1/3 A γ ~ + B 2 C k 2 α k 2 . (16)
Since, by assumptions, the series ∑ k = 0 ∞ ( α k C k 1 / 3 + α k 2 C k 2 ) < + ∞ \sum_{k=0}^{\infty}\left(\frac{\alpha_k}{C_k^{1/3}}+\alpha_k^2C_k^2\right)<+\infty ∑ k = 0 ∞ ( C k 1/3 α k + α k 2 C k 2 ) < + ∞ , thus dist ( x k , Q ∗ ) \operatorname{dist}(x^k,Q^*) dist ( x k , Q ∗ ) is convergent. Furthermore, from (15) there exists a subsequence { x k j } j \{x^{k_j}\}_j { x k j } j such that
F ( x k j , C k j ) = f ~ 0 ( x k j ) + C k j ∑ i = 1 m ( max { 0 , f i ( x k j ) } ) 2 → f ~ 0 ∗ . F(x^{k_j},C_{k_j})=\tilde f_0(x^{k_j})+C_{k_j}\sum_{i=1}^{m}\left(\max\{0,f_i(x^{k_j})\}\right)^2\to\tilde f_0^*. F ( x k j , C k j ) = f ~ 0 ( x k j ) + C k j i = 1 ∑ m ( max { 0 , f i ( x k j )} ) 2 → f ~ 0 ∗ .
Since this subsequence lies in the compact set M M M , we may assume it converges to some x ∗ ∗ ∈ M x^{**}\in M x ∗∗ ∈ M . Then, ∑ i = 1 m [ max { 0 , f i ( x ∗ ∗ ) } ] 2 = 0 \sum_{i=1}^{m}[\max\{0,f_i(x^{**})\}]^2=0 ∑ i = 1 m [ max { 0 , f i ( x ∗∗ )} ] 2 = 0 and f ~ 0 ( x ∗ ∗ ) = f ~ 0 ∗ \tilde f_0(x^{**})=\tilde f_0^* f ~ 0 ( x ∗∗ ) = f ~ 0 ∗ , so that x ∗ ∗ ∈ Q ∗ x^{**}\in Q^* x ∗∗ ∈ Q ∗ . Hence, dist ( x k j , Q ∗ ) → 0 \operatorname{dist}(x^{k_j},Q^*)\to0 dist ( x k j , Q ∗ ) → 0 . Since the sequence dist ( x k , Q ∗ ) \operatorname{dist}(x^k,Q^*) dist ( x k , Q ∗ ) is convergent, it follows that dist ( x k , Q ∗ ) → 0 \operatorname{dist}(x^k,Q^*)\to0 dist ( x k , Q ∗ ) → 0 , which completes the proof. □
We conclude this paper with a numerical illustration of the finite difference stochastic method (Algorithm 1).
Example 1. Consider the constrained optimization problem
f 0 ( x 1 , x 2 ) = x 1 + x 2 + 0.01 ( x 1 2 + x 2 2 ) → min (17) f_0(x_1,x_2)=x_1+x_2+0.01(x_1^2+x_2^2)\to\min \tag*{(17)} f 0 ( x 1 , x 2 ) = x 1 + x 2 + 0.01 ( x 1 2 + x 2 2 ) → min (17) subject to
f 1 ( x 1 , x 2 ) = 0.8 x 1 2 + 0.4 x 2 2 − 1 0.8 x 1 2 + 0.4 x 2 2 + 10 − 1 ≤ 0 , ( x 1 , x 2 ) ∈ M = B 0.45 ( 1 , 1 ) . (18) f_1(x_1,x_2)=0.8x_1^2+0.4x_2^2-\frac{1}{0.8x_1^2+0.4x_2^2+10}-1\leq0,\quad(x_1,x_2)\in M=B_{0.45}(1,1). \tag*{(18)} f 1 ( x 1 , x 2 ) = 0.8 x 1 2 + 0.4 x 2 2 − 0.8 x 1 2 + 0.4 x 2 2 + 10 1 − 1 ≤ 0 , ( x 1 , x 2 ) ∈ M = B 0.45 ( 1 , 1 ) . (18) The objective f 0 f_0 f 0 is strongly convex (hence quasiconvex), and f 1 f_1 f 1 is strongly quasiconvex by Remark 1(ii).
With diameter R = diam ( M ) = 0.9 R=\operatorname{diam}(M)=0.9 R = diam ( M ) = 0.9 , let Ω = M + R B 1 ( 0 ) = B 1.35 ( 1 , 1 ) \Omega=M+RB_1(0)=B_{1.35}(1,1) Ω = M + R B 1 ( 0 ) = B 1.35 ( 1 , 1 ) (n = 2 n=2 n = 2 ). The gradient bounds over Ω \Omega Ω are γ 0 ≈ 1.4335 \gamma_0\approx1.4335 γ 0 ≈ 1.4335 , L 0 ≈ 1.4695 L_0\approx1.4695 L 0 ≈ 1.4695 , and for the constraint f 1 f_1 f 1 , numerical estimates yield γ 1 ≈ 1.1552 \gamma_1\approx1.1552 γ 1 ≈ 1.1552 , L 1 ≈ 3.8754 L_1\approx3.8754 L 1 ≈ 3.8754 . Setting γ = min { γ 0 , γ 1 } ≈ 1.1552 \gamma=\min\{\gamma_0,\gamma_1\}\approx1.1552 γ = min { γ 0 , γ 1 } ≈ 1.1552 and L Ω = max { L 0 , L 1 } ≈ 3.8753 L_\Omega=\max\{L_0,L_1\}\approx3.8753 L Ω = max { L 0 , L 1 } ≈ 3.8753 , we choose the unified scale parameter R ~ = 105 \widetilde{R}=105 R = 105 .
Parameters are ρ k = 1 / k + 0.5 \rho_k=1/\sqrt{k}+0.5 ρ k = 1/ k + 0.5 , α k = 1 / ( k + 1 ) \alpha_k=1/(k+1) α k = 1/ ( k + 1 ) , with initial point x 0 = ( 1.3 , 0.7 ) x^0=(1.3,0.7) x 0 = ( 1.3 , 0.7 ) (f 0 ( x 0 ) = 2.0218 f_0(x^0)=2.0218 f 0 ( x 0 ) = 2.0218 , f 1 ( x 0 ) ≈ 0.4614 > 0 f_1(x^0)\approx0.4614>0 f 1 ( x 0 ) ≈ 0.4614 > 0 , thus infeasible).
The global minimizer is x ∗ ≈ ( 0.6818 , 0.6818 ) x^*\approx(0.6818,0.6818) x ∗ ≈ ( 0.6818 , 0.6818 ) with f 0 ( x ∗ ) ≈ 1.3729 f_0(x^*)\approx1.3729 f 0 ( x ∗ ) ≈ 1.3729 and f 1 ( x ∗ ) ≈ − 0.5369 < 0 f_1(x^*)\approx-0.5369<0 f 1 ( x ∗ ) ≈ − 0.5369 < 0 . The feasible set is Q = M ∩ { x : 2 x 1 2 + x 2 2 ≤ 2.7254 } Q=M\cap\{x:2x_1^2+x_2^2\leq2.7254\} Q = M ∩ { x : 2 x 1 2 + x 2 2 ≤ 2.7254 } .
Numerical Results: After 5000 iterations of Algorithm 1 implemented in Python (using a fixed random seed), the results are:
x 5000 ≈ ( 0.6813 , 0.6823 ) , f 0 ( x 5000 ) ≈ 1.372902 , f 1 ( x 5000 ) ≈ − 0.5372 < 0. x^{5000}\approx(0.6813,0.6823),\quad f_0(x^{5000})\approx1.372902,\quad f_1(x^{5000})\approx-0.5372<0. x 5000 ≈ ( 0.6813 , 0.6823 ) , f 0 ( x 5000 ) ≈ 1.372902 , f 1 ( x 5000 ) ≈ − 0.5372 < 0. The errors are ∥ x 5000 − x ∗ ∥ ≈ 0.00071 \lVert x^{5000}-x^*\rVert\approx0.00071 ∥ x 5000 − x ∗ ∥ ≈ 0.00071 and ∣ f 0 ( x 5000 ) − f 0 ( x ∗ ) ∣ ≈ 8.04 × 10 − 7 \lvert f_0(x^{5000})-f_0(x^*)\rvert\approx8.04\times10^{-7} ∣ f 0 ( x 5000 ) − f 0 ( x ∗ )∣ ≈ 8.04 × 1 0 − 7 . The objective-minimization phase remained active throughout, while constraint-reduction was inactive.
Figure 1. Feasible region Q Q Q , initial point x 0 x^0 x 0 , exact solution x ∗ x^* x ∗ , and final iterate x 5000 x^{5000} x 5000 .
Figure 2. Convergence of the objective function f 0 ( x k ) f_0(x^k) f 0 ( x k ) over 5000 iterations.
Remark 13 (Practical performance and adaptive switching ). In practical ap- plications, estimating the problem-dependent constants L Ω L_{\Omega} L Ω and γ \gamma γ may be challenging, leading to conservative theoretical bounds for the parameter R ~ \widetilde{R} R , such as R ~ ≥ 105 \widetilde{R} \ge105 R ≥ 105 . We therefore examine the empirical behavior of Algorithm 1 for a moderate value of R ~ = 1.0 \widetilde{R} = 1.0 R = 1.0 .
For an initial constraint shift yielding f ~ ( x 0 ) ≈ 2.4614 \widetilde{f}(x^{0}) \approx2.4614 f ( x 0 ) ≈ 2.4614 , the algorithm is run for N = 1000 N = 1000 N = 1000 iterations. During iterations k = 0 , … , 17 k = 0,\ldots,17 k = 0 , … , 17 , the condition f ~ ( x k ) > ρ k R ~ \widetilde{f}(x^{k}) > \rho_{k}\widetilde{R} f ( x k ) > ρ k R holds, and the algorithm selects the constraint-reduction direction p k = g ξ k ( x k , α k , u k ) p^{k} = g_{\xi_{k}}(x^{k},\alpha_{k},u_{k}) p k = g ξ k ( x k , α k , u k ) . Starting at iteration k = 18 k = 18 k = 18 , the condition f ~ ( x k ) ≤ ρ k R ~ \widetilde{f}(x^{k}) \le\rho_{k}\widetilde{R} f ( x k ) ≤ ρ k R is satisfied, triggering a switch to the objective-minimization direction p k = g 0 ( x k , α k , u k ) p^{k} = g_{0}(x^{k},\alpha_{k},u_{k}) p k = g 0 ( x k , α k , u k ) .
After N = 1000 N = 1000 N = 1000 iterations, the algorithm yields x 1000 ≈ ( 0.6815 , 0.6821 ) x^{1000} \approx(0.6815,0.6821) x 1000 ≈ ( 0.6815 , 0.6821 ) , with f 0 ( x 1000 ) ≈ 1.3730 f_{0}(x^{1000}) \approx1.3730 f 0 ( x 1000 ) ≈ 1.3730 and f 1 ( x 1000 ) ≈ − 0.5370 f_{1}(x^{1000}) \approx-0.5370 f 1 ( x 1000 ) ≈ − 0.5370 . These results illustrate the adaptive switching mechanism and demonstrate that the algorithm attains a feasible point in this numerical experiment, despite using a value of R ~ \widetilde{R} R substantially below the theoretical bound.
Declarations
Author Contributions
Both authors contributed equally to the study conception, design and implementation and wrote and corrected the manuscript.
Competing Interests
There are no conflicts of interest or competing interests related to this manuscript.
Funding
This research was partially supported by ANID–Chile under project Fondecyt Regular 1241040.
Acknowledgements
The authors wish to thanks the reviewers for their comments and remarks that helped to improve the quality of the paper.
References