Generalized Newton Methods for Nonsmooth Optimization

15 concepts6 papers1 proposal

In classical optimization, Newton's method is the gold standard for fast local convergence. By utilizing the second-order Taylor expansion, it constructs a local quadratic model of a function using its gradient and Hessian matrix. When the objective function is smooth and strongly convex, Newton's method converges quadratically to the minimum.

However, many modern machine learning and applied mathematics problems—such as Lasso, support vector machines, and composite optimization—involve nonsmooth functions. These functions possess "kinks" or discontinuities in their gradients, meaning the classical Hessian matrix is undefined. If you attempt to run a standard Newton method on these problems, the algorithm will instantly fail or stall.

To bridge this gap, a powerful research direction has emerged: Generalized Newton methods. By leveraging advanced tools from variational analysis, these methods replace the classical Hessian with generalized second-order derivatives and pair them with globalization strategies. The result is a class of algorithms that achieve robust global convergence from any starting point, while retaining the rapid superlinear or quadratic local convergence of classical second-order methods.

Constructing a Generalized Hessian

To build a Newton step for a nonsmooth function, we must first find a way to measure its "curvature" without a traditional Hessian. The core insight is to look at how the subgradient or subgradient mapping of the function changes.

Instead of a single Hessian matrix, researchers utilize set-valued mappings and generalized differentiation:

By substituting these generalized operators into the Newton step equation, the algorithm can compute descent directions that account for the sharp changes in slope characteristic of nonsmooth landscapes.

The Threat of Instability and Stalling

Simply plugging a generalized Hessian into the standard Newton formula is not enough to guarantee success. Nonsmooth optimization introduces two severe complications that can cause standard algorithms to diverge or stall:

  1. Loss of Positive-Definiteness: In smooth optimization, we often assume the Hessian is strictly positive-definite. In the nonsmooth regime, generalized Hessians are frequently only positive-semidefinite. As Pham Duy Khanh et al. point out, standard Newton steps fail under these conditions, necessitating algorithms that can handle relaxed assumptions.
  2. Stalling at Discontinuities: For structured nonsmooth problems like piecewise linear systems, the algorithm can easily stall at points where variables are exactly zero or lie directly on a kink. As noted by Xiaotong Yuan et al. in A Finite Newton Algorithm for Non-degenerate Piecewise Linear Systems, without explicit stabilization, the algorithm cannot reliably navigate across non-degenerate matrices.

Globalization Strategies: The Safety Nets

To ensure the algorithm converges from any initial starting point (global convergence), the generalized Newton step must be embedded within a globalization framework. The literature highlights four primary mechanisms to achieve this:

1. Damping and Backtracking Line Searches

Instead of taking a full Newton step, the step size is dynamically scaled. In Generalized damped Newton algorithms in nonsmooth optimization via second-order subdifferentials, Vo Thanh Phat et al. combine generalized Newton directions with a backtracking line search and tilt stability to guarantee global convergence. Similarly, Xiaotong Yuan et al. integrate a damping factor based on the Armijo-Goldstein condition alongside a calculated perturbation to prevent the algorithm from stalling at zero-crossings.

2. Regularization

When the generalized Hessian is only positive-semidefinite, the system can become ill-conditioned. To resolve this, Pham Duy Khanh et al. introduce a regularized Newton method. By adding a regularization term to the coderivative-based generalized Hessian, they restore stability and ensure robust global convergence without requiring strict positive-definiteness.

3. Proximal Envelopes

Rather than modifying the step directly, one can embed the second-order model within a proximal framework. In A globally convergent proximal Newton-type method in nonsmooth convex optimization, Boris S. Mordukhovich et al. develop a proximal Newton-type algorithm. This architecture achieves global convergence and fast local rates for a broad class of nonsmooth convex problems without requiring strong convexity assumptions.

4. Trust-Region Safeguards

For non-convex, nonsmooth problems, trust regions offer an alternative to line searches. In A Trust-Region Method for Nonsmooth Nonconvex Optimization, Andre Milzarek et al. utilize a simplified quadratic model with abstract descent directions. They incorporate a unique stepsize safeguard and truncation mechanism, proving that every accumulation point generated by the iterates is guaranteed to be a stationary point.

Why It Works: The Intuition

The success of generalized Newton methods lies in a beautiful synergy between their global safeguards and their local second-order geometry.

[Far from Solution] ──> Globalization Safeguards Active ──> Acts like robust 1st-order method
                                                                     │
                                                                     ▼
[Near Solution]    ──> Full Steps Accepted Automatically ──> Recovers fast 2nd-order rate

When the algorithm is initialized far from the optimal solution, the generalized Hessian may provide highly erratic or discontinuous steps because the local quadratic approximation is poor. This is where the globalization mechanisms (the line search, trust region, regularization, or proximal term) step in as a safety net. They penalize or truncate wild steps, effectively forcing the algorithm to behave like a conservative, robust first-order descent method. This guarantees steady progress toward the solution zone.

As the iterates approach a stationary point, the algorithm enters a region where the local nonsmooth structure stabilizes (e.g., identifying the correct zero-patterns in a Lasso problem or entering a zone of tilt stability). Here, the generalized Hessian accurately captures the true combinatorial or piecewise geometry of the function.

Because the globalization safeguards are designed to automatically accept a step size of $1$ when it yields sufficient descent, the algorithm seamlessly transitions from global exploration to local exploitation. The safety nets turn off, the full generalized Newton steps are taken, and the algorithm recovers its superlinear or quadratic convergence speed—solving nonsmooth problems with the efficiency traditionally reserved for smooth ones.

Key Foundational Work

Generalized damped Newton algorithms in nonsmooth optimization via second-order subdifferentials (2023) — contributed 3 concept elements to this direction.
A Generalized Newton Method for Subgradient Systems (2023) — contributed 2 concept elements to this direction.
A globally convergent proximal Newton-type method in nonsmooth convex optimization (2023) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_convergence_for_nonsmooth_optimiz_1a2d4a9e,
  title = {global convergence for nonsmooth optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-convergence-for-nonsmooth-optimization/rdr_1a2d4a9e851d4cbfa4a459db712a4c3e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_convergence_for_nonsmooth_optimiz_1a2d4a9e_v1,
  title = {global convergence for nonsmooth optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-convergence-for-nonsmooth-optimization/rdr_1a2d4a9e851d4cbfa4a459db712a4c3e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake