betaFeedback

WorksMathematics

First-order characterizations of strong quasiconvexity with the exact modulus

Abstract

In this paper, we study first-order characterizations of strong quasiconvexity for functions defined on convex subsets of real normed spaces. For functions that are continuous along segments, an inequality involving the lower Dini derivative is a known necessary condition for strong quasiconvexity with a given modulus, whereas the established converse guarantees only half of that modulus. By means of a one-dimensional lemma, we prove that this inequality, and even its weaker version with the upper Dini derivative, ensures strong quasiconvexity with the same modulus, without requiring the domain to be open; this answers a question raised in the recent literature. The main result leads to a characterization with the same modulus in terms of the Clarke subdifferential for locally Lipschitz functions on Banach spaces, which answers another open question, and to a formula for the exact modulus of radial functions defined on Hilbert spaces. We also present some consequences in optimization, such as an optimality condition without Clarke regularity, an error bound with optimal constant and, for the projected subgradient method, the same convergence rate as in the strongly convex case, together with the exponential convergence of the associated flow. Finally, we show that the converse of a relation between proximal points and strong subdifferentials fails in general, but holds for a truncation of the function.

Introduction

One of the most natural extensions of strong convexity to nonconvex optimization is the class of strongly quasiconvex functions, introduced by Polyak [22] as a particular case of uniformly quasiconvex functions, see [8 Section 1]. Let XX be a real normed space and let C⊆XC \subseteq X be a convex set. In the form in which it is currently used, cf. [8], a function h:C→Rh:C \to\mathbb{R} is strongly quasiconvex with modulus γ>0\gamma> 0 if

h(x+t(y−x))≤max⁡{h(x),h(y)}−γ2t(1−t)∥y−x∥2for all x,y∈C, t∈[0,1].(1)h(x+t(y-x)) \leq\max\{h(x),h(y)\}-\frac{\gamma}{2}t(1-t)\lVert y-x\rVert^2 \quad\text{for all } x,y\in C,\ t\in[0,1]. \tag*{(1)}

If CC has more than one point and hh satisfies (1) with some modulus, then the set of admissible moduli is an interval of the form (0,γ∗](0,\gamma^*], with γ∗<∞\gamma^*<\infty, and γ∗\gamma^* is called the exact modulus of hh on CC (see also the notion of exact modulus of quasiconvexity in [28 Definition 1]).

Every strongly convex function with modulus γ\gamma satisfies (1), but the class is broader and contains functions that are neither convex nor locally Lipschitz (see Example 3.5). When X=RnX=\mathbb{R}^n, these functions are 2-supercoercive and, if CC is closed and hh is lower semicontinuous, then hh has exactly one minimizer on CC [15 Theorem 1 and Corollary 3]. For this reason, they constitute a natural setting for proximal, gradient and subgradient methods beyond convexity [4, 15, 16].

The first-order characterization of this class goes back to Vladimirov, Nesterov and Chekanov [28 Theorems 1 and 6] (see also [10 Theorem 1]), according to whom, for a function hh of class C1C^1, strong quasiconvexity with modulus γ\gamma implies

h(x)≤h(y)⟹⟨∇h(y),y−x⟩≥γ2∥y−x∥2for all x,y∈C,(2)h(x)\leq h(y)\Longrightarrow\langle\nabla h(y),y-x\rangle\geq\frac{\gamma}{2}\lVert y-x\rVert^2 \quad\text{for all } x,y\in C, \tag*{(2)}

and, conversely, (2) implies strong quasiconvexity with modulus γ2\frac{\gamma}{2}. The equivalence with the same modulus γ\gamma in both directions was established by Bao and Nam [3 Theorem 3.2] for Gâteaux differentiable functions on open sets.

2020 Mathematics Subject Classification. 90C26, 49J52, 26B25, 26A24, 65K10, 34A60.

Key words and phrases. Strongly quasiconvex functions, Dini derivatives, Clarke subdifferential, exact modulus, subgradient method.

Corresponding author: Lizet Santa Cruz Calderón ([email protected]).

More recently, in the nonsmooth setting, Hadjisavvas and Lara [9 Theorem 6(b)] showed that, for hh continuous along segments of an open convex set, strong quasiconvexity with modulus γ\gamma implies

h(x)≤h(y)⟹h−′(y;y−x)≥γ2∥y−x∥2,(3)h(x) \le h(y) \Longrightarrow h'_{-}(y;y-x) \ge\frac{\gamma}{2}\lVert y-x\rVert^{2}, \tag*{(3)}

where h−′(y;v):=lim inf⁡t→0h(y+tv)−h(y)th'_{-}(y;v) := \liminf_{t\to0} \frac{h(y+tv)-h(y)}{t} is the lower Dini derivative of hh at yy in the direction vv, and that the converse holds with modulus γ2\frac{\gamma}{2}. The same factor 12\frac{1}{2} appears in [9 Theorem 4 and Corollary 8], for a condition involving only values of hh and for Gâteaux differentiable functions. Bao and Nam [3 Section 5] asked whether the modulus γ\gamma can be recovered in this setting. The loss of the factor 12\frac{1}{2} has a quantitative effect, since quadratic growth constants, error bounds and convergence rates depend on the modulus, and obtaining it only up to the factor 12\frac{1}{2} leads to less sharp guarantees.

In another direction, the survey [8] collects results on the Clarke subdifferential of these functions, obtained by Vial [27 Lemma 1 and Theorems 2 and 3] and by Dudov and Osiptsev [7 Lemma 2.1 and Corollaries 2.1 and 3.1], and records two open questions: one concerning the converse of Vial’s inequality for Clarke subgradients [8 Remark 49], and another concerning the converse of an inclusion between proximal points and strong subdifferentials [8 Remark 38].

In this work, we answer these three questions. The main contribution is Theorem 3.3, according to which, for hh continuous along segments of a convex set CC, not necessarily open, condition (3) with constant γ\gamma is equivalent to strong quasiconvexity with modulus γ\gamma, even when the lower Dini derivative is replaced by the upper one. Thus, the exact modulus persists in the nonsmooth setting, and the converses mentioned above hold with the modulus γ\gamma itself. The proof relies on a one-dimensional lemma (Lemma 3.1), which extends [3 Lemma 3.1] to functions that are merely continuous, and the result of Bao and Nam is recovered as a particular case (Corollary 3.8). As an application, we obtain a formula for the exact modulus of radial functions on Hilbert spaces (Corollary 3.4), which shows that the moduli of ∥x∥α\lVert x\rVert^\alpha that can be extracted from [19] are exact (Example 3.5), and we verify that the quadratic growth constant γ4\frac{\gamma}{4} of [9 Corollary 9] is optimal (Remark 3.7).

The second contribution concerns the Clarke subdifferential. For locally Lipschitz functions on open convex subsets of Banach spaces, we prove that strong quasiconvexity with modulus γ\gamma is equivalent to Vial’s inequality with the same modulus, that is, to the inclusion of the Clarke subdifferential in the strong sublevel subdifferential ∂1,γh\partial_{1,\gamma}h of [11] (Theorem 3.10). This answers the question on Vial’s inequality in the affirmative and extends [27 Theorem 2] from Rn\mathbb{R}^{n} to Banach spaces. In Rn\mathbb{R}^{n}, the same holds with the limiting subdifferential (Corollary 3.12). It also follows that the classes of strongly quasiconvex functions of order 2 considered in [1, 25] coincide with the class defined by (1) (Remark 3.13).

The third contribution concerns optimization. The direct implication of Theorem 3.10 yields an optimality condition that generalizes [7 Corollaries 2.1 and 3.1] to functions that are not necessarily Clarke regular (Corollary 4.1), an error bound with optimal constant (Corollary 4.2), the rate O(1k)O\left(\frac{1}{k}\right) for the squared distance to the minimizer in the projected subgradient method, which is the same as in the strongly convex case (Theorem 4.4), and the exponential convergence of the Clarke subgradient flow, which extends [16 Theorem 15(b),(c)] to locally Lipschitz functions (Proposition 4.6). The method uses only Clarke subgradients, which can be obtained through the usual calculus rules, and thus complements the method of [4], which is based on strong subdifferentials. Moreover, Proposition 4.9 answers the question on proximal points, since it shows that the converse of [11 Proposition 36] fails even for the strongly convex function h(y)=y2h(y)=y^{2}, and that this converse holds for the truncation max⁡{h,h(x)}\max\{h,h(x)\}.

The paper is organized as follows. In § 2, we gather the definitions and facts used on Dini derivatives and the Clarke subdifferential, including a monotonicity lemma. In § 3, we prove the one-dimensional lemma and, from it, the characterization of strong quasiconvexity via Dini derivatives, with its consequences for radial and differentiable functions, as well as the characterization via Clarke subgradients. In § 4, we derive an optimality condition, an error bound and the convergence of the projected subgradient method and of the associated flow, and we study the relation between proximal points and strong subdifferentials. Finally, § 5 presents the conclusions.

Preliminaries

Throughout the text, XX denotes a real normed space, X∗X^* its topological dual, ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle the pairing between X∗X^* and XX, which coincides with the inner product when XX is a Hilbert space, and B(x,r)B(x,r) the open ball with center xx and radius rr. We now recall the definitions and auxiliary results used throughout the paper.

Dini derivatives

Let C⊆XC\subseteq X be convex and let h:C→Rh:C\to\mathbb{R} be a function. For x∈Cx\in C and a∈Xa\in X such that x+ta∈Cx+ta\in C for all sufficiently small t>0t>0, the upper and lower Dini derivatives of hh at xx in the direction aa are given by

h+′(x;a)=lim sup⁡t↓0h(x+ta)−h(x)t,h−′(x;a)=lim inf⁡t↓0h(x+ta)−h(x)t.h'_+(x;a)=\limsup_{t\downarrow0}\frac{h(x+ta)-h(x)}{t},\qquad h'_-(x;a)=\liminf_{t\downarrow0}\frac{h(x+ta)-h(x)}{t}.

For a function ψ:I→R\psi:I\to\mathbb{R} defined on an interval I⊆RI\subseteq\mathbb{R}, we use the same notation ψ±′(s;r)\psi'_\pm(s;r) for s∈Is\in I and r∈Rr\in\mathbb{R} such that s+tr∈Is+tr\in I for all sufficiently small t>0t>0, and we write ψ±′(s):=ψ±′(s;1)\psi'_\pm(s):=\psi'_\pm(s;1), that is,

ψ+′(s)=lim sup⁡t↓0ψ(s+t)−ψ(s)t,ψ−′(s)=lim inf⁡t↓0ψ(s+t)−ψ(s)t.\psi'_+(s)=\limsup_{t\downarrow0}\frac{\psi(s+t)-\psi(s)}{t},\qquad\psi'_-(s)=\liminf_{t\downarrow0}\frac{\psi(s+t)-\psi(s)}{t}.

These derivatives may take the values ±∞\pm\infty and satisfy the following properties, which follow directly from the definitions.

(P1) Positive homogeneity, that is,

h±′(x;λa)=λh±′(x;a)for all λ>0.h'_\pm(x;\lambda a)=\lambda h'_\pm(x;a)\quad\text{for all }\lambda>0.

In particular, ψ±′(s;r)=∣r∣ψ±′(s;sgn⁡r)\psi'_\pm(s;r)=|r|\psi'_\pm(s;\operatorname{sgn}r) for r≠0r\ne0.

(P2) h−′(x;a)≤h+′(x;a)h'_-(x;a)\leq h'_+(x;a).

(P3) Let x0∈Cx_0\in C, d∈Xd\in X and ψ(s)=h(x0+sd)\psi(s)=h(x_0+sd) for ss in the interval I:={s∈R:x0+sd∈C}I:=\{s\in\mathbb{R}:x_0+sd\in C\}, which is an interval containing 00, since CC is convex. Then ψ±′(s;r)=h±′(x0+sd;rd)\psi'_\pm(s;r)=h'_\pm(x_0+sd;rd) whenever one of the two sides is defined. In particular, with X=RX=\mathbb{R} and d=−1d=-1, the function χ(σ):=ψ(−σ)\chi(\sigma):=\psi(-\sigma) satisfies χ±′(−s)=ψ±′(s;−1)\chi'_\pm(-s)=\psi'_\pm(s;-1).

We say that hh is continuous along segments of CC if, for all x,y∈Cx,y\in C, the function s↦h(x+s(y−x))s\mapsto h(x+s(y-x)) is continuous on [0,1][0,1]. This is the hypothesis of [9 Theorems 4 and 6].

The following result is part of Dini’s theorem on the Dini derivatives of continuous functions [24 Chapter VI, p. 204]. Since it is short, we include the proof, which follows Saks’ argument.

References

  1. [1]P. Arora, G. Bhatia, and A. Gupta. Characterizations of the solution sets and sufficient optimality criteria via higher-order strong convexity. In Topics in Nonconvex Optimization: Theory and Applications, pages 231–242. Springer, 2011.DOI
  2. [2]J.-P. Aubin and A. Cellina. Differential inclusions: set-valued maps and viability theory, volume 264. Springer-Verlag, Berlin, 1984.DOI
  3. [3]N. X. D. Bao and N. M. Nam. First-order characterizations of strong quasiconvexity and a quasimonotonicity gap. arXiv preprint arXiv:2511.11384, 2025.arxiv.org/abs/2511.11384
  4. [4]J. Choque, F. Lara, and R. T. Marcavillaca. A subgradient projection method for quasiconvex minimization. Positivity, 28(5):64, 2024.DOI
  5. [5]F. H. Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
  6. [6]A. Daniilidis and D. Drusvyatskiy. Pathological subgradient dynamics. SIAM Journal on Optimization, 30(2):1327–1338, 2020.arxiv.org/abs/1910.13604
  7. [7]S. I. Dudov and M. A. Osiptsev. Sufficient conditions for a minimum of a strongly quasiconvex function on a weakly convex set. Mathematical Notes, 111(1):33–46, 2022.DOI
  8. [8]S.-M. Grad, F. Lara, and R. T. Marcavillaca. Strongly quasiconvex functions: what we know (so far). Journal of Optimization Theory and Applications, 205(2):38, 2025.arxiv.org/abs/2410.23055
  9. [9]N. Hadjisavvas and F. Lara. Characterizations of strongly quasiconvex functions. Journal of Global Optimization, 94(4):997–1003, 2026.
  10. [10]M. Jovanovic. Strongly quasiconvex quadratic functions. Publ. Inst. Math. Nouv. Sér, 53:153–156, 1993.
  11. [11]A. Kabgani and F. Lara. Strong subdifferentials: theory and applications in nonconvex optimization. Journal of Global Optimization, 84(2):349–368, 2022.DOI
  12. [12]P. Q. Khanh and F. Lara. Star quasiconvexity: a unified approach for linear convergence of first-order methods beyond convexity. arXiv preprint arXiv:2510.24981, 2025.arxiv.org/abs/2510.24981
  13. [13]K. C. Kiwiel. Convergence and efficiency of subgradient methods for quasiconvex minimization. Mathematical programming, 90(1):1–25, 2001.DOI
  14. [14]S. Lacoste-Julien, M. Schmidt, and F. Bach. A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method. arXiv preprint arXiv:1212.2002, 2012.
  15. [15]F. Lara. On strongly quasiconvex functions: existence results and proximal point algorithms. Journal of Optimization Theory and Applications, 192(3):891–911, 2022.DOI
  16. [16]F. Lara, R. T. Marcavillaca, and P. T. Vuong. Characterizations, dynamical systems and gradient methods for strongly quasiconvex functions. Journal of Optimization Theory and Applications, 206(3):60, 2025.arxiv.org/abs/2410.03534
  17. [17]F. Lara and A. Ramos. On optimality conditions for mathematical programming problems based on strong subdifferentials. Set-Valued and Variational Analysis, 34(2):17, 2026.
  18. [18]V. S. Melnik and J. Valero. On attractors of multivalued semi-flows and differential inclusions. Set-Valued Analysis, 6(1):83–111, 1998.DOI
  19. [19]N. M. Nam and J. J. Sharkansky. On strong quasiconvexity of functions in infinite dimensions. Optimization Letters, 20(4):815–840, 2026.arxiv.org/abs/2409.17450
  20. [20]Y. Nesterov. Lectures on Convex Optimization. Springer, Berlin, 2018.DOI
  21. [21]N. H. Nguyen, T. Q. Trinh, and P. T. Vuong. The projected heavy-ball method for quasar-monotone variational inequalities and quasar-convex optimization. Journal of Optimization Theory and Applications, 208(2):83, 2026.DOI
  22. [22]B. T. Polyak. Existence theorems and convergence of minimizing sequences in extremum problems with restrictions. Soviet Math. Dokl., 7:72–75, 1966.
  23. [23]R. T. Rockafellar and R. J. Wets. Variational analysis. Springer, 1998.DOI
  24. [24]S. Saks. Theory of the Integral. Dover Publications, New York, second edition, 1964.
  25. [25]S. K. Singh, A. Shahi, and S. Kant Mishra. On strong pseudomonotone and strong quasimonotone maps. In International Conference on Mathematics and Computing, pages 13–22. Springer, 2018.DOI
  26. [26]S. K. Singh, A. Shahi, and S. Kant Mishra. Strong pseudoconvexity and strong quasiconvexity of non-differentiable functions. In Recent Trends in Mathematical Modeling and High Performance Computing: M3PHCST-2020, Ghaziabad, India, January 9-11, 2020, pages 195–205. Springer, 2021.DOI
  27. [27]J.-P. Vial. Strong convexity of sets and functions. Journal of Mathematical Economics, 9(1-2):187–205, 1982.
  28. [28]A. A. Vladimirov, Y. E. Nesterov, and Y. N. Chekanov. On uniformly quasi-convex functionals. Vestn. Mosk. Univ, 4:18–27, 1978.

Paper details

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

views · 10

downloads · 0

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

  • Mathematics

Claude (Anthropic)

View statement
Looking for related papers…
Contents