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

2025/10/18 by Serge Gratton, Philippe L. Toint, Gratton, Serge +1 · 1 citation
Computer Science · Mathematics · #49M37 #65K05 #65Y20 #Advanced Optimization Algorithms Research #F.2.1 #FOS: Mathematics #G.1.6 #Iterative Methods for Nonlinear Equations #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2510.16390

openalex publication_date 2025/10/18 · openalex created_date 2025/10/22 · openalex updated_date 2026/07/28

Abstract

A very simple first-order algorithm is proposed for solving nonlinear optimization problems with deterministic 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 O(1/sqrtk), 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.

Citations

• A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity
• S2MPJ and CUTEst optimization problems for Matlab, Python and Julia
• Sequential Quadratic Optimization for Stochastic Optimization with Deterministic Nonlinear Inequality and Equality Constraints
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems
• Complexity of a Class of First-Order Objective-Function-Free\n Optimization Algorithms
• Complexity and performance for two classes of noise-tolerant first-order algorithms
• Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization
• A Simple Convergence Proof of Adam and Adagrad
• Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimization
• CUTEst: a Constrained and Unconstrained Testing Environment with safe threads for mathematical optimization
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares

Cited by

• Adaptive directional decomposition methods for nonconvex constrained optimization

Related

• Optimistic Noise-Aware Sequential Quadratic Programming for Equality Constrained Optimization with Rank-Deficient Jacobians
• A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians
• An Inexact First-order Method for Constrained Nonlinear Optimization
• A New Lagrangian-Based First-Order Method for Nonconvex Constrained Optimization
• Nonsmooth exact penalty methods for equality-constrained optimization: complexity and implementation