A Cubic Regularization Method for Multiobjective Optimization
Douglas S. Gonçalves, Max L. N. Gonçalves, Jefferson G. Melo · 2025
Read A Cubic Regularization Method for Multiobjective Optimization by Douglas S. Gonçalves, Max L. N. Gonçalves, Jefferson G. Melo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08181.txt.
Introduction
Balancing several goals at once in optimization gets a new method from Douglas Goncalves, Max Goncalves, and Jefferson Melo in a 2025 paper. Their method builds a cubic-corrected model of each goal at every step and minimizes the joint model. Slope and curvature estimates must meet set accuracy bars.
A key trait is that the correction strength and estimate accuracy are tuned together by a flexible line search. Versions that use only function values to guess derivatives are covered. Under smooth curvature assumptions, the step count to reach a near-Pareto point is bounded tightly. Multi-goal design, from engineering to portfolios, gains a method with firm speed promises.
Catalog record
| CREATOR | Douglas S. Gonçalves, Max L. N. Gonçalves, Jefferson G. Melo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-08181
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Cubic Regularization Method for Multiobjective Optimization Thanks: Submitted to the editors DATE. Douglas S. Gonçalves, Max L. N. Gonçalves, Jefferson G. Melo Abstract This work introduces a new cubic regularization method for solving nonconvex unconstrained multiobjective optimization problems. At each iteration of the method, a model associated with the cubic regularization of each component of the objective function is minimized. This model allows approximations for the first- and second-order derivatives, which must satisfy suitable error conditions. One interesting feature of the proposed algorithm is that the regularization parameter of the model and the accuracy of the derivative approximations are jointly adjusted using a nonmonotone line search criterion. Implementations of the method, where derivative information is computed using finite difference strategies, are discussed. From a theoretical perspective, it is shown that, under the assumption that the Hessians of the components of the multiobjective function are globally Lipschitz continuous, the method requires at most 𝒪 ( C ϵ − 3 / 2 ) \mathcal{O}(C\epsilon^{-3/2}) iterations to generate an ϵ \epsilon -approximate Pareto critical, where C C is related to the Lipschitz constant and the inexactness parameters. In particular, if the first- and second-order derivative information is computed using finite differences based solely on function values, the method requires at most 𝒪 ( n 1 − β ϵ − 3 / 2 ) \mathcal{O}(n^{1-\beta}\epsilon^{-3/2}) iterations, corresponding to 𝒪 ( m n 3 − β ε − 3 2 ) \mathcal{O}\left(mn^{3-\beta}\varepsilon^{-\frac{3}{2}}\right) function evaluations, where n n is the dimension of the domain of the objective function, m m is the number of objectives, and β ∈ [ 0 , 1 ] \beta\in[0,1] is a constant associated with the stepsize used in the finite-difference approximation. We further discuss the global convergence and local convergence rate of the method. Specifically, under the local convexity assumption, we show that the method achieves superlinear convergence when the first derivative is computed exactly, and quadratic convergence when both first- and second-order derivatives are exact. From a practical perspective, numerical experiments are presented to illustrate the behavior of the proposed method and compare it with a multiobjective Newton method. keywords Cubic regularization method; iteration-complexity analysis; convergence rate; Pareto optimality; multiobjective problem. Funding. This work was funded by FAPESC (Fundação de Amparo à Pesquisa e Inovação do Estado de Santa Catarina) [grant number 2024TR002238]. † † runningheads: A Cubic Regularization Method for Multiobjective Optimization / Douglas S. Gonçalves, Max L. N. Gonçalves, Jefferson G. Melo MSC 49M15, 65K05, 90C26, 90C29. 1 Introduction Consider the unconstrained multiobjective optimization problem \min_{x\in\mathbb{R}^{n}}F(x),\\ (1) where \allowbreak F\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} is twice continuously differentiable. Our analysis will be conducted under the following assumptions: for every j\in\mathcal{J}:=\{1,\ldots,m\} , (A1) the Hessian of F_{j} is L_{j} -Lipschitz continuous, i.e., \|\nabla^{2}F_{j}(y)-\nabla^{2}F_{j}(z)\|\leq L_{j}\|y-x\|,\quad\forall y,z\in\mathbb{R}^{n}; (For convenience, we denote L:=\max_{j\in\mathcal{J}}L_{j}. ) (A2) there exists F_{j}^{*}\in\mathbb{R} such that F_{j}(y)\geq F_{j}^{*} for all y\in\mathbb{R}^{n} . In multiobjective optimization, the concept of optimality is replaced by Pareto optimality or efficiency. A point x^{\ast}\in\mathbb{R}^{n} is considered Pareto optimal or efficient if there is no other point x\in\mathbb{R}^{n} such that F(x)\leq F(x^{\ast}) and F(x)\neq F(x^{\ast}) , where the inequality \leq is understood component-wise. Similarly, a point x^{\ast}\in\mathbb{R}^{n} is called weakly Pareto optimal or weakly efficient if there is no point x\in\mathbb{R}^{n} such that F(x)<F(x^{\ast}) . A point x^{\ast}\in\mathbb{R}^{n} is locally Pareto optimal (or locally weakly Pareto optimal) if there is a neighborhood V\subset\mathbb{R}^{n} around x^{\ast} where x^{\ast} is Pareto optimal (or weakly Pareto optimal) for F restricted to V . A necessary condition for local Pareto optimality of x^{\ast}\in\mathbb{R}^{n} is given by: {\max_{j\in\mathcal{J}}\langle\nabla F_{j}(x^{*}),y-x^{*}\rangle\geq 0,\quad\forall y\in\mathbb{R}^{n}.} (2) A point x^{\ast}\in\mathbb{R}^{n} that satisfies this condition is called Pareto critical or stationary. Consequently, if a point x is not Pareto critical, there exists a vector y\in\mathbb{R}^{n} such that y-x is a descent direction for F at x , meaning that there exists \varepsilon>0 such that F(x+t(y-x))<F(x) for any t\in(0,\varepsilon] . In this work, we propose and analyze a multiobjective cubic regularization method (M-CRM) for solving ( 1 ). Basically, at each iteration of the method, a model associated with the cubic regularization of each component of the objective function is minimized. More specifically, the next iterate (x^{+},\gamma^{+},\lambda^{+})\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{m}_{+} is an approximate KKT point of the following smooth optimization problem with cubic objective function and quadratic constraints \begin{array}[]{cl}\displaystyle\min_{(y,\gamma)\in\mathbb{R}^{n}\times\mathbb{R}}&\;\gamma+\frac{\sigma}{6}\|y-x\|^{3}\\ \mbox{s. t.}&\langle{\nabla\bar{F}_{j}(x)},{y-x}\rangle+\displaystyle\frac{1}{2}\langle{\nabla^{2}\bar{F}_{j}(x)(y-x)},{y-x}\rangle\leq\gamma,\quad\forall j\in\mathcal{J},\end{array} (3) where x\in\mathbb{R}^{n} , \sigma>0 is a regularization parameter, and \nabla\bar{F}_{j}(x) and \nabla^{2}\bar{F}_{j}(x) are approximations to the gradient \nabla F_{j}(x) and the Hessian \nabla^{2}F_{j}(x) , respectively. Note that, this smooth problem is equivalent to the non-smooth scalar-value one \min_{y\in\mathbb{R}^{n}}M_{x,\sigma}(y):=\max_{j\in\mathcal{J}}M_{x,\sigma}^{j}(y), (4) where M_{x,\sigma}^{j}(y):=\langle\nabla\bar{F}_{j}(x),y-x\rangle+\dfrac{1}{2}\langle\nabla^{2}\bar{F}_{j}(x)(y-x),y-x\rangle+\dfrac{\sigma}{6}\|y-x\|^{3},\;\forall j\in\mathcal{J}. (5) It is worth pointing out that the exact conditions for the derivative approximations in the M-CRM, specifically the inequalities ( 16 ) below, depend only on the previous information, and hence they are implementable; for further discussion on this issue in the scalar case, see, for example, [ 26 , 32 , 24 ] . Implementations of the method, where information about derivatives are computed through finite difference strategies, are presented. One interesting feature of the M-CRM is that the regularization parameter \sigma and the accuracy of the derivative approximations are jointly adjusted using a nonmonotone line search criterion. From a theoretical perspective, it is shown that the M-CRM requires at most \mathcal{O}(C\epsilon^{-3/2}) iterations to generate an \epsilon -approximate Pareto critical point, where C is related to the Lipschitz constant L , the values F^{*}_{j}, the initial points and the inexactness parameters. In particular, if the gradients are exact and the Hessians are computed by finite differences based on gradient values, the M-CRM requires at most \mathcal{O}\left(n^{(1-2\beta)/2}\varepsilon^{-\frac{3}{2}}\right) iterations, and \mathcal{O}\left(mn^{(3-2\beta)/2}\varepsilon^{-\frac{3}{2}}\right) function and gradient evaluations, to generate an \varepsilon -approximate Pareto critical point for problem ( 1 ) (see Definiton ( 1 )), where \beta\in[0,1/2] is a constant associated with the stepsize used in the finite-difference approximation. Additionally, if the first- and second-order derivative information is computed using finite differences based solely on function values, the method requires at most \mathcal{O}(n^{1-\beta}\epsilon^{-3/2}) iterations, corresponding to \mathcal{O}\left(mn^{3-\beta}\varepsilon^{-\frac{3}{2}}\right) function evaluations, where \beta\in[0,1] . We further discuss the global convergence and local convergence rate of the method. Specifically, under local convexity assumption, we show that the method achieves superlinear convergence when the first derivatives are computed exactly, and quadratic convergence when both first- and second-order derivatives are exact. From a practical perspective, numerical experiments on standard test sets from the literature are presented to illustrate the behavior of the approach, with comparisons to the multiobjective Newton method with safeguards from [ 22 ] . As is well-known in the scalar context (i.e., m=1 in problem ( 1 )), the CRM is a globally convergent variant of Newton method for the unconstrained minimization of twice continuously differentiable functions [ 25 , 29 ] (see also [ 9 , 24 , 26 , 32 , 4 , 12 , 3 , 21 , 13 , 27 ] for some recent variants of the CRM). In the multiobjective setting, a p -order regularization framework for constrained multiobjective optimization was introduced in [ 11 ] . Iteration-complexity results were established under the assumption that the p -th derivatives of the objective components satisfy Hölder continuity conditions. However, it is important to note that the M-CRM does not fall within the scope of