A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization

The paper extends the analysis of the Gradient-Eigenstep Algorithm by Goyens et al. for solving nonconvex equality-constrained optimization problems. The contributions are twofold. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher’s augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.

The paper begins by introducing the problem of nonlinear equality-constrained continuous optimization and discusses penalty methods, specifically Fletcher’s augmented Lagrangian function, which is both exact and smooth. The Gradient-Eigenstep method from [9] is based on minimizing this function and only requires a linear system solve in each iteration. The paper’s first contribution is proving that if an initial point is sufficiently close to a strong second-order stationary point satisfying a regularity condition, and if the penalty parameter is sufficiently large and step sizes are sufficiently small, then gradient descent applied to minimize Fletcher’s augmented Lagrangian can achieve a linear rate of decrease in the norm of the gradient, yielding a more accurate approximate strong second-order stationary point. The second contribution applies this result to prove strong worst-case complexity properties for a progressive sampling method for solving equality-constrained problems where objective and constraint functions are formed by large-scale sample average approximations.

The paper is organized as follows: Section 2 proves the local-linear convergence of the Gradient-Eigenstep method in the neighborhood of certain second-order stationary points. Section 3 applies this result to prove strong worst-case complexity properties of a progressive sampling method. Section 4 provides a summary and concluding remarks.

In Section 2, the paper establishes several assumptions and definitions. Assumption 2.1 states that the objective function f and constraint function c are twice-continuously differentiable. Assumption 2.2 assumes the existence of a positive real number R such that the set CR:= x ∈ Rn: ∥c(x)∥ ≤ R is compact. Assumption 2.3 assumes there exists δ ∈ R>0, a bounded open set CˆR containing CR + v ∈ Rn: ∥v∥ ≤ δ, and a positive real number σmin such that for any x ∈ CˆR, the constraint Jacobian has σm (∇c(x)T) ≥ σmin. Assumption 2.4 assumes that the least-squares Lagrange multiplier function y defined by (4) is twice-continuously differentiable over CˆR, and that the Hessian functions of f + cT y and ∥c∥2 are Lipschitz continuous over CˆR with constants Mf and Mc, respectively.

The paper defines an (ϵ, ζ)-stationary point in Definition 2.1 as a point x for which there exists ŷ such that ∥∇L(x, ŷ)∥ ≤ ϵ and dT ∇2xx L(x, ŷ)d ≥ −ζ∥d∥2 for all d ∈ Null(∇c(x)T). The least-squares Lagrange multiplier function y(x) is defined in (3) and (4) as y(x) = −∇c(x)† ∇f (x). Fletcher’s augmented Lagrangian is defined in Definition 2.2 as Fρ (x) = f (x) + c(x)T y(x) + ρ∥c(x)∥2.

Lemma 2.1 provides uniform bounds on various quantities and states useful properties of Fρ at approximate second-order stationary points. It shows that under Assumptions 2.1-2.4, there exists κ ∈ R>0 such that the norms of ∇f (x), y(x), ∇y(x), ∇c(x), ∇2 f (x), ∇2 [y]j (x), and ∇2 [c]j (x) are bounded by κ over CR. It also shows that for any ρ ∈ R>0, λR,ρ:= sup λ1 (∇2 Fρ (x)) 0, if x satisfies (7), then for any ρ ∈ R>0 and with ωρ:= 1 + κ + 2ρκ and ηρ:= √(2 mκ)/σmin + mκ + 2mρκ, one finds that ∥c(x)∥ ≤ R, ∥∇Fρ (x)∥ ≤ ωρ ϵ, and λn (∇2 Fρ (x)) ≥ min β − ηρ ϵ, 2ρσmin squared − (κ + mκ 2) − ηρ ϵ.

The proof of Lemma 2.1 involves expressing the Hessian of Fρ in an equivalent form involving a decomposition into orthogonal spaces defined by the constraint Jacobian. The paper derives an expression for ∇y(x)∇c(x)T by differentiating the linear system that defines y(x). It then combines this with the definition of the Hessian to obtain a lower bound on the smallest eigenvalue of ∇2 Fρ (x). The proof uses norm inequalities, the triangle inequality, and the fact that the spectral norm of the pseudoinverse of a matrix is at most the reciprocal of the matrix’s smallest singular value.

Theorem 2.1 is the main theorem of Section 2. It states that under Assumptions 2.1-2.4, if the penalty parameter ρ satisfies (25), the initial point x satisfies (7), the tolerance ϵ satisfies (26), and the step size t satisfies (27), then the Gradient-Eigenstep method [9, Algorithm 1] with parameters (28) reduces to applying gradient descent with constant step size t to minimize Fρ with initial point x. The theorem provides an upper bound on the number of iterations T in (29) and shows that the method gives a point satisfying (7) with (ϵ, β) replaced by (ϵ′, β ′), where β ′ is defined in (30).

The proof of Theorem 2.1 involves showing that the conditions in (26) imply positivity of various quantities, including the upper bound for the step size. It then considers gradient descent applied to minimize Fρ from x with step size t and shows that the iterates remain in CR, the gradient norms decrease linearly, and the smallest eigenvalue of the Hessian of Fρ remains bounded below. The proof uses induction and employs [9, Corollary 2.7] to show that the iterates remain in CR. It also shows that the line-search termination condition in [9, Algorithm 2] is satisfied at each iteration, so the algorithm reduces to gradient descent with a fixed step size.

In Section 3, the paper applies Theorem 2.1 to prove strong worst-case complexity properties for a progressive sampling method. The SAA problem is written as (48), where the objective and constraint functions are defined as averages over N terms. The progressive sampling strategy, given as Algorithm 1, solves a sequence of subproblems (49) with increasing sample sizes. Algorithm 2 is a simplified statement of [9, Algorithm 1] used as the subproblem solver.

The paper makes several assumptions in this section. Assumption 3.1 states that the objective and constraint functions are twice-continuously differentiable with bounded gradients and Hessians. Assumption 3.2 provides bounds on the differences between the component functions and their averages. Assumptions 3.3-3.5 extend Assumptions 2.2-2.4 to any sample problem. Assumption 3.6 states that problem (48) is (α, β)-strongly Morse, meaning that for any x with ∥∇L(x, y(x))∥ ≤ α, one has dT ∇2xx L(x, y(x))d ≥ β∥d∥2 for all d ∈ Null(∇c(x)T).

Lemma 3.1 shows that under Assumptions 3.1-3.5, for a given sample set S1 and initial point x0, there exists ρ̂1 such that the requirements of [9, Theorem 3.5] hold for all ρ1 ≥ ρ̂1. Consequently, Algorithm 2 with appropriate tolerances terminates in a number of iterations at most TS1 = max uS1,1 ϵ−2 1, uS1,2 ζ1−3 and produces an (ϵ̄, ζ̄)-stationary point.

Lemma 3.2 is [1, Lemma 3.6], which shows that the strong Morse property extends from the full-sample problem to any sampled problem as long as the sample size is sufficiently large. Lemma 3.3 shows that if the achieved termination tolerances for a sample problem are set appropriately, then the initial point for the next sample problem satisfies certain critical bounds. The proof of Lemma 3.3 involves bounding the difference between the gradients of the Lagrangians for consecutive sample problems and using the strong Morse property.

Lemma 3.4 establishes monotonicity properties of the tolerance ϵρ (b, κ) defined in (84). It shows that ϵρ (b, κ) is nondecreasing in b and nonincreasing in each of κ and ρ. Consequently, for every ρ ∈ (ρβ, ρmax], κ ∈ (0, κ̄], and b ∈ [β/2, β], one has that ϵ∗ ≤ ϵρ (b, κ), and for any ϵ ∈ (0, ϵρ (b, κ)], the step size tρ (b, κ) equals 1/λ̄.

Theorem 3.1 is the main theorem of Section 3. It has two parts. Part (a) considers the case where p1 = N, meaning the full sample is used directly. In this case, Algorithm 1 with appropriate tolerances requires O(N ⌈max ϵ−2, ζ −3 ⌉) individual objective gradients and individual constraint Jacobians until termination, yielding an (ϵ, ζ)-stationary point. Part (b) considers the case where p1 < N and the sample size increases progressively. Under appropriate parameter choices, Algorithm 1 terminates with xK satisfying ∥∇L(xK, y(xK))∥ ≤ ϵ and dT ∇2xx L(xK, y(xK))d ≥ 12 β∥d∥2 for all d ∈ Null(∇c(xK)T), so xK is (ϵ, ζ ′)-stationary for every ζ ′ ∈ R≥0. The total number of individual objective gradients and individual constraint Jacobians computed before termination is at most the bound in (90), which is O(p1 C1 + T θ(N − p1)/(θ − 1) + N logB (3√5ωϵc /ϵ)), where the first two terms are independent of ϵ and ζ.

The proof of Theorem 3.1 involves verifying the conditions of Theorem 2.1 for each subproblem. For k = 1, Lemma 3.1 is used to show that Algorithm 2 terminates in at most C1 iterations. For k ∈ 2,..., K − 1, the paper proves by induction that the initial point xk−1 satisfies (92), and then Theorem 2.1 applies with ϵ′ = ϵ̂k, showing that Algorithm 2 returns xk in at most T̄ iterations and xk is (ϵ̂k, ζ̂k)-stationary. For k = K, Theorem 2.1 applies with ϵ′ = ϵ, showing that Algorithm 2 returns xK in at most ⌈logB (3√5ωϵc /ϵ)⌉ iterations and xK satisfies the desired stationarity conditions.

The paper concludes in Section 4 with a summary of the contributions. It states that the Gradient-Eigenstep algorithm reduces to a local-linearly convergent gradient-descent method in the vicinity of certain approximate second-order stationary points when the step size is sufficiently small and the penalty parameter is sufficiently large. It also states that the progressive sampling strategy can obtain an improved worst-case sample complexity bound as compared to an approach that solves a full-sample problem directly.

Based on the paper, here are the specific improvements you can make to AI systems:

1. Improved Optimization for Nonconvex Equality-Constrained Problems

• Implement the Gradient-Eigenstep algorithm as a subproblem solver in AI systems that handle constrained optimization (e.g., reinforcement learning with safety constraints, robotics motion planning).

• The system can now achieve local linear convergence to strong second-order stationary points (not just first-order) when initialized near a good solution, with explicit step-size and penalty parameter tuning rules (Equations 25-27).

2. Sample-Efficient Learning with Progressive Sampling

• Build AI systems that solve optimization problems where objective/constraints are defined by large datasets (e.g., empirical risk minimization, system identification).

• Use the progressive sampling strategy (Algorithm 1) to start with a small sample, solve the subproblem, then increase sample size geometrically. This reduces worst-case sample complexity from O(N·max ε−2, ζ−3) to O(p1·C1 + T·θ(N−p1)/(θ−1) + N·log B(3√5ωε c/ε)), where the first two terms are independent of accuracy ε and ζ.

• This means the AI system can achieve high-accuracy solutions with significantly fewer total gradient/Jacobian evaluations compared to solving the full-sample problem directly.

3. Automatic Parameter Adaptation for Stable Convergence

• The paper provides explicit conditions (Assumptions 2.1–2.4, Lemma 2.1) for choosing penalty parameter ρ and step size t to guarantee linear convergence.

• An AI system can now automatically verify these conditions (e.g., checking Lipschitz constants, singular value lower bounds) and select parameters that ensure the algorithm reduces to simple gradient descent, avoiding line-search overhead and improving iteration efficiency.

4. Guaranteed Stationarity with Second-Order Verification

• The system can now certify that its output is an (ε, ζ)-stationary point, meaning both gradient norm and Hessian curvature in the null space of constraints are controlled.

• This is critical for AI systems in safety-critical applications (e.g., optimal control, resource allocation) where first-order stationarity is insufficient and second-order conditions (e.g., avoiding saddle points) are required.

5. Robustness to Sample Noise in Stochastic Settings

• The strong Morse property (Assumption 3.6) and the tolerance propagation lemmas (Lemmas 3.2–3.4) allow the AI system to handle noisy objective/constraint estimates from finite samples.

• The system can adapt its termination tolerances (ε̂ k, ζ̂ k) per subproblem to ensure the final solution meets the desired accuracy, even when sample sizes increase progressively.

6. Reduced Computational Overhead in Large-Scale Problems

• Each Gradient-Eigenstep iteration only requires a linear system solve (not a full Hessian inversion), making it scalable to high-dimensional AI models.

• The local linear convergence rate means fewer iterations are needed near the optimum, reducing wall-clock time for fine-tuning AI systems (e.g., hyperparameter optimization, neural network training with constraints).

Improved AI System Capabilities:

• Constrained RL agents that learn policies with safety constraints (e.g., collision avoidance) using fewer environment samples.

• Large-scale parameter estimation systems that handle millions of data points with provably lower sample complexity.

• Optimization solvers that automatically switch between progressive sampling and full-sample refinement, balancing speed and accuracy.

• Certified optimization tools that output both a solution and a certificate of second-order stationarity, useful for verification in autonomous systems.