betaFeedback

WorksMathematics

Subgradient and Stochastic Finite-Difference Methods for Constrained Strongly Quasiconvex Optimization

Abstract

We propose a projected subgradient method for solving quasiconvex minimization problems. By employing the Clarke subdifferential, we prove that the sequence generated by the proposed algorithm converges to a solution of the minimization problem when the objective function is locally Lipschitz continuous and strongly quasiconvex in the sense of Polyak, under the same assumptions required for convex functions with the convex subdifferential. Moreover, we derive explicit convergence rate estimates for both the iterates and objective function values. In particular, compared with the corresponding results for nonsmooth, locally Lipschitz, strongly convex optimization, our analysis replaces strong convexity with strong quasiconvexity while preserving the order of the convergence rate, thereby extending the guarantees to a class of possibly nonconvex objective functions. In addition, we investigate a stochastic finite-difference scheme for minimizing a strongly quasiconvex function subject to inequality constraints defined by strongly quasiconvex functions, and establish a convergence rate of order O(k−1/4)O(k^{-1/4}), consistent with known complexity bounds for stochastic zeroth-order methods.

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∈Ifi(x)f(x) = \max_{i \in I} f_i(x), where each fif_i is quasiconvex with Lipschitz-continuous gradient on a convex compact set, obtaining an O(1/k)O(1/\sqrt{k}) convergence rate. However, the feasible set there is a plain set constraint x∈Mx \in M; no inequality constraints fi(x)≤0f_i(x) \le0 with quasiconvex fif_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}) 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 Rn\mathbb{R}^{n} and the Euclidean norm are denoted by ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle and ∥⋅∥\lVert\cdot\rVert, respectively. The closed ball with center at x0∈Rnx_{0}\in\mathbb{R}^{n} and radius ε>0\varepsilon>0 is denoted by Bε(x0)B_{\varepsilon}(x_{0}).

Given any extended-valued function h:Rn→R‾h:\mathbb{R}^{n}\to\overline{\mathbb{R}}, the effective domain of hh is defined by dom⁡h:={x∈Rn:h(x)<+∞}\operatorname{dom}h:=\{x\in\mathbb{R}^{n}:h(x)<+\infty\}.

A function hh with convex domain is said to be:

  • (a) (strongly) convex on dom⁡h\operatorname{dom}h, if there exists μ≥0\mu\geq0 such that, for all x,y∈dom⁡hx,y\in\operatorname{dom}h and all λ∈[0,1]\lambda\in[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)}
  • (b) (strongly) quasiconvex on dom⁡h\operatorname{dom}h, if there exists μ≥0\mu\geq0 such that, for all x,y∈dom⁡hx,y\in\operatorname{dom}h and all λ∈[0,1]\lambda\in[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)}

A function is strongly convex (resp. quasiconvex) when μ>0\mu> 0, and convex (resp. quasiconvex) when μ=0\mu= 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 ff is called regular in the sense of Clarke on MM if, for every x∈Mx \in M and every v∈Rnv \in\mathbb{R}^{n}, the ordinary directional derivative exists and satisfies

f′(x;v)=f∘(x;v).f^{\prime}(x;v)=f^{\circ}(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→Rf : \mathbb{R} \to\mathbb{R} be the function given by

f(x)=max⁡{f1(x),f2(x)},f(x)=\max\{f_{1}(x),f_{2}(x)\},

where f1(x)=max⁡{0,x}+∣x∣2f_{1}(x)=\max\{0,x\}+|x|^{2} and f2(x)=x2+2sin⁡2(x)f_{2}(x)=x^{2}+2\sin^{2}(x).

Here, f1f_{1} is strongly convex, thus strongly quasiconvex with modulus μ1=2\mu_{1}=2. The function f2f_{2} is also strongly quasiconvex with modulus μ2=12\mu_{2}=\frac{1}{2} (see [16, Example 30]).

Since the maximum of strongly quasiconvex functions is again strongly quasiconvex [27 Corollary 2], it follows that ff is strongly quasiconvex on the whole domain with modulus μ:=min⁡{μ1,μ2}=12\mu:=\min\{\mu_{1},\mu_{2}\}=\frac{1}{2}.

On the other hand, note that ff is locally Lipschitz as the maximum of two locally Lipschitz functions, it is not differentiable at points where f1(x)=f2(x)f_{1}(x)=f_{2}(x), and it is not convex due to f2f_{2}.

(ii) Let h:Rn→Rh : \mathbb{R}^{n} \to\mathbb{R} be a strongly convex (possible nonsmooth) and positive function. Let us show that the function

f(x)=h(x)−1h(x)+a,a>0,f(x)=h(x)-\frac{1}{h(x)+a}, \qquad a>0,

is strongly quasiconvex. Indeed, let us define the functions:

h1(x)=h(x),h2(x)=−1h(x)+a.h_{1}(x)=h(x), \qquad h_{2}(x)=-\frac{1}{h(x)+a}.

Note that h2h_{2} is quasiconvex since its sublevel sets are convex. Now, take xx, yy, and define z:=(1−λ)x+λyz:=(1-\lambda)x+\lambda y with λ∈[0,1]\lambda\in[0,1]. Suppose without loss of generality that h1(x)≤h1(y)h_{1}(x)\le h_{1}(y). This implies h2(x)≤h2(y)h_{2}(x)\le h_{2}(y). By quasiconvexity of h2h_{2}, we get h2(z)≤h2(y)h_{2}(z)\le h_{2}(y). Thus,

h(z)=h1(z)+h2(z)≤max⁡{h1(x),h1(y)}+h2(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}

Therefore, hh is strongly quasiconvex with modulus μ>0\mu>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⊂RnM \subset\mathbb{R}^{n}, for arbitrary x,y∈M⊂Rnx,y \in M \subset\mathbb{R}^{n} and g(x)∈∂f(x)g(x) \in\partial f(x) with g(x)≠0g(x) \ne0, we introduce the auxiliary quantity

vf(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)}

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∈Mx \in M to the distance from that xx to the unique minimizer x∗x^*.

Lemma 1. Let M⊂RnM \subset\mathbb{R}^{n} be a closed convex set, and let f:Rn→Rf:\mathbb{R}^{n} \to\mathbb{R} be a locally Lipschitz continuous, regular, and strongly quasiconvex function with modulus μ>0\mu> 0 on MM. Then, for all x∈Mx \in 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),

where x∗x^* is the unique minimizer of ff on MM.

Proof. Since x∗x^* is a global minimizer of ff on MM, we have f(x∗)≤f(x)f(x^*) \le f(x) for all x∈Mx \in M. Using this and the strong quasiconvexity of ff, we have for every t∈[0,1]t \in[0,1] that

f(x+t(x∗−x))≤f(x)−μ2t(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.

Dividing by t>0t>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.

Letting t↓0t \downarrow0 and using the regularity of ff, 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.

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.

Taking d=x∗−xd=x^*-x, we have

References

  1. [3]J. Choque, F. Lara, R.T. Marcavillaca, A subgradient projection method for quasiconvex minimization, Positivity, 28, article 64, 2024.DOI
  2. [4]F.H. Clarke, Generalized gradients and applications, Trans. Amer. Math. Soc., 205, 247–262, 1975.DOI
  3. [5]A. Gasnikov, M. Alkousa, A. Lobanov, Y. Dorn, F. Stonyakin, I. Kuruzov, S. Singh, On quasiconvex smooth optimization problems by a comparison oracle, arXiv:2411.16745, 2024.
  4. [6]S.M. Grad, F. Lara, R.T. Marcavillaca, Strongly quasiconvex functions: what we know so far, J. Optim. Theory Appl., 205, Article 38, 2025.arxiv.org/abs/2410.23055
  5. [8]N. Hadjisavvas, F. Lara, Characterizations of strongly quasiconvex functions, J. Global Optim., 94, 997–2003, 2026.
  6. [9]N. Hadjisavvas, F. Lara, R.T. Marcavillaca, P.T. Vuong, Heavy ball and Nesterov accelerations with Hessian-driven damping for nonconvex optimization, Applied Math. Optim., 93, Article 63, 2026.
  7. [10]M. Jovanovic, A note on strongly convex and quasiconvex functions, Math. Notes, 60, 584–585, 1996.DOI
  8. [11]A. Kabgani, F. Lara, Strong subdifferentials: theory and applications in nonconvex optimization, J. Global Optim., 84(2), 349–368, 2022.DOI
  9. [12]H. Karimi, J. Nutini, M. Schmidt, Linear convergence of gradient and proximal-gradient methods under the Polyak-Lojasiewicz condition, Machine Learning and Knowledge Discovery in Databases, 795–811, 2016.DOI
  10. [13]R.A. Khachatryan, Stochastic finite-difference schemes for nondifferentiable quasiconvex optimization: convergence rate, Vestnik Rossiiskikh Universitetov. Matematika, 31, 154, 168–185, 2026.DOI
  11. [14]D. Kozak, C. Molinari, L. Rosasco, L. Tenorio, S. Villa, Zeroth order optimization with orthogonal random directions, Math. Program., 199(1–2), 1179–1219, 2023.arxiv.org/abs/2107.03941
  12. [15]F. Lara, On strongly quasiconvex functions: existence results and proximal point algorithm, J. Optim. Theory Appl., 192, 891–911, 2022.DOI
  13. [16]F. Lara, R.T. Marcavillaca, P.T. Vuong, Characterizations, dynamical systems and gradient methods for strongly quasiconvex functions, J. Optim. Theory Appl., 206, Article 60, 2025.arxiv.org/abs/2410.03534
  14. [17]Z. Li, P.-Y. Chen, S. Liu, S. Lu, Y. Xu, “Zeroth-Order Optimization for Composite Problems with Functional Constraints,” Proc. AAAI Conf. on Art. Intel., 36(7), 7453–7461, 2022.arxiv.org/abs/2112.11420
  15. [18]Yu.E. Nesterov, Minimization methods for non-smooth convex and quasi-convex functions, Matekon, 29, 519–531, 1984.
  16. [19]Yu.E. Nesterov, Efficient Methods in Nonlinear Programming, Moscow, Radio i Svyaz, 1989.
  17. [20]Yu.E. Nesterov, Introduction to Convex Optimization, Moscow, MCCME, 2010 (in Russian).
  18. [21]Yu.E. Nesterov, V.G. Spokoiny, Random gradient-free minimization of convex functions, Found. Comput. Math., 17, 527–566, 2017.
  19. [22]A. Nguyen, K. Balasubramanian, Stochastic zeroth-order functional constrained optimization: oracle complexity and applications, INFORMS Journal on Optim., 5(3), 256–272, 2023.arxiv.org/abs/2210.04273
  20. [23]B.T. Polyak, Existence theorems and convergence of minimizing sequences in extremum problems with restrictions, Soviet Math., 7, 72–75, 1966.
  21. [24]R.T. Rockafellar, Monotone operators and proximal point algorithms, SIAM J. Control Optim., 14, 877–898, 1976.DOI
  22. [25]A.G. Sukharev, A.V. Timokhov, V.V. Fedorov, Course of Optimization Methods, Nauka, Moscow, 1986.
  23. [26]J.P. Vial, Strong convexity of sets and functions, J. Math. Econ., 9, 187–205, 1982.
  24. [27]A.A. Vladimirov, Yu.E. Nesterov, Yu.N. Chekanov, On uniformly quasi-convex functionals, Mosc. Univ. Comput. Math. Cybern., 1978, no. 4, 19–30; translation from Vestn. Mosk. Univ., Ser. XV, 1978, no. 4, 18–27.

Paper details

vlnc:W_g89e89nx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 10

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents