GGGeovani Nunes Grapiglia

Geovani Nunes Grapiglia

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Geovani Nunes Grapiglia has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    An adaptive line-search-free multiobjective gradient method and its iteration-complexity analysis

    by Max L. N. Gonçalves, Geovani N. Grapiglia, Jefferson G. Melo

    This work introduces an adaptive line-search-free multiobjective gradient (AMG) method for solving smooth multiobjective optimization problems. The proposed approach automatically adjusts stepsizes based on steepest descent directions, promoting robustness with respect to stepsize choice while maintaining low computational cost. The method is specifically tailored to the multiobjective setting and does not rely on function evaluations, making it well-suited for this scenario. The proposed algorithm admits two variants: (i) a conservative variant, in which the stepsize is monotonically decreasing; and (ii) a flexible variant, which allows occasional increases in the stepsize. From a theoretical standpoint, under standard Lipschitz continuity assumptions on the gradients, we establish iteration-complexity bounds for achieving a Pareto critical point for both variants in the nonconvex setting. In the convex setting, we further derive improved iteration-complexity bounds for the conservative AMG variant. From a practical standpoint, the numerical experiments demonstrate that the flexible AMG performs favorably compared to the steepest descent method with either a fixed stepsize or Armijo line search.

  • Open Access

    On the complexity of lower-order implementations of higher-order methods

    by Nikita Doikov, Geovani Nunes Grapiglia

    In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous p th-order derivatives, starting from $$p \ge 1$$ p ≥ 1 . The method, however, only requires derivative information up to order $$(p-1)$$ ( p - 1 ) , since the p th-order derivatives are approximated via finite differences. To ensure oracle efficiency, instead of recomputing a finite-difference approximation of the p th-order derivative at every iteration, we attempt to reuse each approximation for m consecutive iterations before recomputing it, with $$m \ge 1$$ m ≥ 1 as a key parameter. As a result, we obtain an adaptive method of order $$(p-1)$$ ( p - 1 ) that requires no more than $$\mathcal {O}(\epsilon ^{-\frac{p+1}{p}})$$ O ( ϵ - p + 1 p ) iterations to find an $$\epsilon $$ ϵ -approximate stationary point of the objective function and that, for the choice $$m=(p-1)n + 1$$ m = ( p - 1 ) n + 1 , where n is the problem dimension, takes no more than $$\mathcal {O}(n^{1/p}\epsilon ^{-\frac{p+1}{p}})$$ O ( n 1 / p ϵ - p + 1 p ) oracle calls of order $$(p-1)$$ ( p - 1 ) . This improves previously known bounds for tensor methods with finite-difference approximations in terms of the problem dimension.

  • Enhancing finite-difference-based derivative-free optimization with machine learning

    by Timothé Taminiau, Geovani N. Grapiglia, Estelle Massart

  • Open Access

    Riemannian optimization with finite-difference gradient approximations

    by Timothé Taminiau, Estelle Massart, Geovani Nunes Grapiglia

    Derivative-free Riemannian optimization (DFRO) aims to minimize an objective function using only function evaluations, under the constraint that the decision variables lie on a Riemannian manifold. The rapid increase in problem dimensions over the years calls for computationally cheap DFRO algorithms, that is, algorithms requiring as few function evaluations and retractions as possible. We propose a novel DFRO method based on finite-difference gradient approximations that relies on an adaptive selection of the finite-difference accuracy and stepsize that is novel even in the Euclidean setting. When endowed with an intrinsic finite-difference scheme, that measures variations of the objective in tangent directions using retractions, our proposed method requires $O(dε^{-2})$ function evaluations and retractions to find an $ε$-critical point, where $d$ is the manifold dimension. We then propose a variant of our method when the search space is a Riemannian submanifold of an $n$-dimensional Euclidean space. This variant relies on an extrinsic finite-difference scheme, approximating the Riemannian gradient directly in the embedding space, assuming that the objective function can be evaluated outside of the manifold. This approach leads to worst-case complexity bounds of $O(dε^{-2})$ function evaluations and $O(ε^{-2})$ retractions. We also present numerical results showing that the proposed methods achieve superior performance over existing derivative-free methods on various problems in both Euclidean and Riemannian settings.

  • Open Access

    A Finite-Difference Trust-Region Method for Convexly Constrained Smooth Optimization

    by Dânâ Davar, Geovani Nunes Grapiglia

    We propose a derivative-free trust-region method based on finite-difference gradient approximations for smooth optimization problems with convex constraints. The proposed method does not require computing an approximate stationarity measure. For nonconvex problems, we establish a worst-case complexity bound of $\mathcal{O}\!\left(n\left(\tfrac{L}σε\right)^{-2}\right)$ function evaluations for the method to reach an $\left(\tfrac{L}σε\right)$-approximate stationary point, where $n$ is the number of variables, $L$ is the Lipschitz constant of the gradient, and $σ$ is a user-defined estimate of $L$. If the objective function is convex, the complexity to reduce the functional residual below $(L/σ)ε$ is shown to be of $\mathcal{O}\!\left(n\left(\tfrac{L}σε\right)^{-1}\right)$ function evaluations, while for Polyak-Lojasiewicz functions on unconstrained domains, the bound further improves to $\mathcal{O}\left(n\log\left(\left(\frac{L}σε\right)^{-1}\right)\right)$. Numerical experiments on benchmark problems and a model-fitting application demonstrate the method's efficiency relative to state-of-the-art derivative-free solvers for both unconstrained and bound-constrained problems.

  • Open Access

    On the Complexity of Lower-Order Implementations of Higher-Order Methods

    by Nikita Doikov, Geovani Nunes Grapiglia

    In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous $p$th-order derivatives, starting from $p \geq 1$. The method, however, only requires derivative information up to order $(p-1)$, since the $p$th-order derivatives are approximated via finite differences. To ensure oracle efficiency, instead of computing finite-difference approximations at every iteration, we reuse each approximation for $m$ consecutive iterations before recomputing it, with $m \geq 1$ as a key parameter. As a result, we obtain an adaptive method of order $(p-1)$ that requires no more than $O(ε^{-\frac{p+1}{p}})$ iterations to find an $ε$-approximate stationary point of the objective function and that, for the choice $m=(p-1)n + 1$, where $n$ is the problem dimension, takes no more than $O(n^{1/p}ε^{-\frac{p+1}{p}})$ oracle calls of order $(p-1)$. This improves previously known bounds for tensor methods with finite-difference approximations in terms of the problem dimension.

  • Open Access

    A Riemannian AdaGrad-Norm Method

    by Glaydston de C. Bento, Geovani N. Grapiglia, Mauricio S. Louzeiro, Daoping Zhang

    We propose a manifold AdaGrad-Norm method (\textsc{MAdaGrad}), which extends the norm version of AdaGrad (AdaGrad-Norm) to Riemannian optimization. In contrast to line-search schemes, which may require several exponential map computations per iteration, \textsc{MAdaGrad} requires only one. Assuming the objective function $f$ has Lipschitz continuous Riemannian gradient, we show that the method requires at most $\mathcal{O}(\varepsilon^{-2})$ iterations to compute a point $x$ such that $\|\operatorname{grad} f(x)\|\leq \varepsilon$. Under the additional assumptions that $f$ is geodesically convex and the manifold has sectional curvature bounded from below, we show that the method takes at most $\mathcal{O}(\varepsilon^{-1})$ to find $x$ such that $f(x)-f_{low}\leqε$, where $f_{low}$ is the optimal value. Moreover, if $f$ satisfies the Polyak--Łojasiewicz condition globally on the manifold, we establish a complexity bound of $\mathcal{O}(\log(\varepsilon^{-1}))$, provided that the norm of the initial Riemannian gradient is sufficiently large. For the manifold of symmetric positive definite matrices, we construct a family of nonconvex functions satisfying the PL condition. Numerical experiments illustrate the remarkable performance of \textsc{MAdaGrad} in comparison with Riemannian Steepest Descent equipped with Armijo line-search.

  • Open Access

    Active-set Newton-MR methods for nonconvex optimization problems with bound constraints

    by Ernesto G. Birgin, Geovani N. Grapiglia, Diaulas S. Marcondes

    This paper presents active-set methods for minimizing nonconvex twice-continuously differentiable functions subject to bound constraints. Within the faces of the feasible set, we employ descent methods with Armijo line search, utilizing approximated Newton directions obtained through the Minimum Residual (MINRES) method. To escape the faces, we investigate the use of the Spectral Projected Gradient (SPG) method and a tailored variant of the Cubic Regularization of Newton's method for bound-constrained problems. We provide theoretical guarantees, demonstrating that when the objective function has a Lipschitz continuous gradient, the SPG-based method requires no more than $\mathcal{O}(nε^{-2})$ oracle calls to find $ε$-approximate stationary points, where $n$ is the problem dimension. Furthermore, if the objective function also has a Lipschitz continuous Hessian, we show that the method based on cubic regularization requires no more than $\mathcal{O}\left(n|\log_{2}(ε)|ε^{-3/2}\right)$ oracle calls to achieve the same goal. We emphasize that, under certain hypotheses, the method achieves $O(ε^{3/2})$ descent within the faces without resorting to cubic regularization. Numerical experiments are conducted to compare the proposed methods with existing active-set methods, highlighting the potential benefits of using MINRES instead of the Conjugate Gradient (CG) method for approximating Newton directions.