A Simple First-Order Algorithm for Full-Rank Equality Constrained Optimization

Serge Gratton; Philippe Toint

A Simple First-Order Algorithm for Full-Rank Equality Constrained Optimization

Serge Gratton
, Philippe Toint

Namur Institute for Complex Systems

Research output: Working paper

4 Downloads (Pure)

Abstract

A very simple first-order algorithm is proposed for solving
nonlinear optimization problems with
nonlinear equality constraints. This algorithm
adaptively selects steps in the plane tangent to the constraints or
steps that reduce infeasibility, without using a merit function or
filter. The tangent steps are based on the AdaGrad method for
unconstrained minimization. The objective function is never evaluated
by the algorithm, making it suitable for noisy problems. Its
worst-case evaluation complexity is analyzed, yielding a global convergence
rate in lO(1/\sqrt{k}), which matches the best
known rate of first-order methods for unconstrained
problems. Numerical experiments are presented suggesting that the
performance of the algorithm is comparable to that of first-order
methods for unconstrained problems, and that its reliability is
remarkably stable in the presence of noise on the gradient.

Original language	English
Place of Publication	2510-16390
Publisher	Arxiv
Publication status	Published - Oct 2025

Access to Document

arXiv-2510-16390Other version, 4.06 MBLicence: Unspecified

3 Article
1 Preprint
1 Working paper

An objective-function-free algorithm for general smooth constrained optimization
Bellavia, S., Gratton, S., Morini, B. & Toint, P., 2 Feb 2026, Arxiv.
Research output: Working paper › Preprint

File
A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity
Gratton, S., Jerad, S. & Toint, P., Mar 2025, In: Open Journal of Mathematical Optimization. 6, 5, 32 p., 5.
Research output: Contribution to journal › Article › peer-review

Open Access
File
47 Downloads (Pure)
Complexity and performance for two classes of noise-tolerant first-order algorithms
Gratton, S., Jerad, S. & Toint, P., 2025, (Accepted/In press) In: Optimization Methods and Software.
Research output: Contribution to journal › Article › peer-review

File
110 Downloads (Pure)

2 Active

Complexity in nonlinear optimization
Toint, P. (CoI), Gould, N. I. M. (CoI) & Cartis, C. (CoI)
1/11/08 → …
Project: Research
ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization
Sartenaer, A. (CoI) & Toint, P. (CoI)
1/01/87 → …
Project: Research Axis

1 Invited talk

Stochastic ADAGRAD with bounds, curvature (and problem structure)
Toint, P. (Speaker)
Jan 2026 → 9 Jan 2026
Activity: Talk or presentation types › Invited talk

Cite this

@techreport{ff8ccd0c393c448285c1eb7f2bf7571d,

title = "A Simple First-Order Algorithm for Full-Rank Equality Constrained Optimization",

abstract = "A very simple first-order algorithm is proposed for solving nonlinear optimization problems with nonlinear equality constraints. This algorithm adaptively selects steps in the plane tangent to the constraints or steps that reduce infeasibility, without using a merit function or filter. The tangent steps are based on the AdaGrad method for unconstrained minimization. The objective function is never evaluated by the algorithm, making it suitable for noisy problems. Its worst-case evaluation complexity is analyzed, yielding a global convergence rate in lO(1/\textbackslash{}sqrt\{k\}), which matches the best known rate of first-order methods for unconstrained problems. Numerical experiments are presented suggesting that the performance of the algorithm is comparable to that of first-order methods for unconstrained problems, and that its reliability is remarkably stable in the presence of noise on the gradient.",

author = "Serge Gratton and Philippe Toint",

year = "2025",

month = oct,

language = "English",

publisher = "Arxiv",

type = "WorkingPaper",

institution = "Arxiv",

}

TY - UNPB

T1 - A Simple First-Order Algorithm for Full-Rank Equality Constrained Optimization

AU - Gratton, Serge

AU - Toint, Philippe

PY - 2025/10

Y1 - 2025/10

N2 - A very simple first-order algorithm is proposed for solving nonlinear optimization problems with nonlinear equality constraints. This algorithm adaptively selects steps in the plane tangent to the constraints or steps that reduce infeasibility, without using a merit function or filter. The tangent steps are based on the AdaGrad method for unconstrained minimization. The objective function is never evaluated by the algorithm, making it suitable for noisy problems. Its worst-case evaluation complexity is analyzed, yielding a global convergence rate in lO(1/\sqrt{k}), which matches the best known rate of first-order methods for unconstrained problems. Numerical experiments are presented suggesting that the performance of the algorithm is comparable to that of first-order methods for unconstrained problems, and that its reliability is remarkably stable in the presence of noise on the gradient.

AB - A very simple first-order algorithm is proposed for solving nonlinear optimization problems with nonlinear equality constraints. This algorithm adaptively selects steps in the plane tangent to the constraints or steps that reduce infeasibility, without using a merit function or filter. The tangent steps are based on the AdaGrad method for unconstrained minimization. The objective function is never evaluated by the algorithm, making it suitable for noisy problems. Its worst-case evaluation complexity is analyzed, yielding a global convergence rate in lO(1/\sqrt{k}), which matches the best known rate of first-order methods for unconstrained problems. Numerical experiments are presented suggesting that the performance of the algorithm is comparable to that of first-order methods for unconstrained problems, and that its reliability is remarkably stable in the presence of noise on the gradient.

M3 - Working paper

BT - A Simple First-Order Algorithm for Full-Rank Equality Constrained Optimization

PB - Arxiv

CY - 2510-16390

ER -

A Simple First-Order Algorithm for Full-Rank Equality Constrained Optimization

Abstract

Access to Document

Fingerprint

Research output

An objective-function-free algorithm for general smooth constrained optimization

A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

Complexity and performance for two classes of noise-tolerant first-order algorithms

Projects

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

Activities

Stochastic ADAGRAD with bounds, curvature (and problem structure)

Cite this