The method of ellipcenters with momentum and relaxation for convex quadratic minimization
Abstract
The method of ellipcenters (ME) is a recent technique developed for unconstrained minimization. Its iteration relies only on first order information and consists of building a suitable two-dimensional ellipse that tries to capture intrinsic ill-conditioning of the problem. The center of the ellipse is taken as the next iterate, which justifies the name of the method. ME was already shown to converge linearly when the objective function is smooth and strongly convex. The special case when the objective is quadratic was studied in the first paper on ME and is also the subject of our work here. In this paper, we propose two variants of ME: RelaxME which adds in ME an additional relaxation step at each iteration and MomME which embeds momentum in ME. We prove linear convergence of RelaxME and MomME and, in particular, we show convergence of RelaxME and MomME (and also of ME) in one iteration when the matrix of the quadratic form has only two distinct eigenvalues. Finally, we provide the results of numerical experiments which compare on five optimization problems (and different combinations of parameters defining these problems) ME, RelaxME, and MomME, with 3 other optimizers: the conjugate gradient method [10], Barzilai and Borwein gradient method with long step [2], and the gradient method with adaptive spectral step length [7]. On most instances, MomME provides the smallest number of iterations and conjugate gradient and MomME provide the smallest CPU times and similar CPU times. This opens optimistic possibilities for ME with momentum in broader settings.
Related
- The Method of Ellipcenters for strongly convex minimization
- A method for global minimization of nonconvex quadratic functions
- An Improved Minimization Method: Eliminating Shift and Variance Inflation While Maintaining Marginal Balance
- On the Ω(n) SDP relaxation gap for Submodular Box-Constrained Quadratic Programming
- A projected descent method for minimization of weakly semismooth functions over polyhedral sets
BibTeX
@misc{behling2026method,
title = {{The method of ellipcenters with momentum and relaxation for convex quadratic minimization}},
author = {Roger Behling and Vincent Guigues and Harry Oviedo},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29454},
eprint = {2608.29454},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29454},
}
RIS
TY - UNPB
TI - The method of ellipcenters with momentum and relaxation for convex quadratic minimization
AU - Roger Behling
AU - Vincent Guigues
AU - Harry Oviedo
PY - 2026
DA - 2026/08/29
PB - arXiv
DO - 10.48550/arxiv.2608.29454
UR - https://arxiv.org/abs/2608.29454
AB - The method of ellipcenters (ME) is a recent technique developed for unconstrained minimization. Its iteration relies only on first order information and consists of building a suitable two-dimensional ellipse that tries to capture intrinsic ill-conditioning of the problem. The center of the ellipse is taken as the next iterate, which justifies the name of the method. ME was already shown to converge linearly when the objective function is smooth and strongly convex. The special case when the objective is quadratic was studied in the first paper on ME and is also the subject of our work here. In this paper, we propose two variants of ME: RelaxME which adds in ME an additional relaxation step at each iteration and MomME which embeds momentum in ME. We prove linear convergence of RelaxME and MomME and, in particular, we show convergence of RelaxME and MomME (and also of ME) in one iteration when the matrix of the quadratic form has only two distinct eigenvalues. Finally, we provide the results of numerical experiments which compare on five optimization problems (and different combinations of parameters defining these problems) ME, RelaxME, and MomME, with 3 other optimizers: the conjugate gradient method [10], Barzilai and Borwein gradient method with long step [2], and the gradient method with adaptive spectral step length [7]. On most instances, MomME provides the smallest number of iterations and conjugate gradient and MomME provide the smallest CPU times and similar CPU times. This opens optimistic possibilities for ME with momentum in broader settings.
ER -