math.OCMar 30, 2026

Yau's Affine Normal Descent: Algorithmic Framework and Convergence Analysis

Authors: Yi-Shuai Niu, Artan Sheshmani, Shing-Tung Yau

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We propose Yau's Affine Normal Descent (YAND), a geometric framework for smooth unconstrained optimization in which search directions are defined by the equi-affine normal of level-set hypersurfaces. The resulting directions are invariant under volume-preserving affine transformations and intrinsically adapt to anisotropic curvature. Using the analytic representation of the affine normal from affine differential geometry, we establish its equivalence with the classical slice-centroid construction under convexity. For strictly convex quadratic objectives, affine-normal directions are collinear with Newton directions, implying one-step convergence under exact line search. For general smooth (possibly nonconvex) objectives, we characterize precisely when affine-normal directions yield strict descent and develop a line-search-based YAND. We establish global convergence under standard smoothness assumptions, linear convergence under strong convexity and Polyak-Lojasiewicz conditions, and quadratic local convergence near nondegenerate minimizers. We further show that affine-normal directions are robust under affine scalings, remaining insensitive to arbitrarily ill-conditioned transformations. Numerical experiments illustrate the geometric behavior of the method and its robustness under strong anisotropic scaling.

Figures & tables

Figure 1. Geometric comparison between the Euclidean and affine normals
Figure 2. Disconnected inward slices for f(x,y)=x2(x2−1)(x2−4)(x2−9)−yf(x,y)=x^{2}(x^{2}-1)(x^{2}-4)(x^{2}-9)-y at z=(0,0)z=(0,0) . The red curve is the zero level set f(x,y)=f(z)f(x,y)=f(z) , and the green set is a representative slice SCS_{C} for some C<0C<0 . Under the inward convention, the centroid direction remains inward/descent, but the slice is disconnected and thus ceases to be a faithful local geometric proxy for the analytic affine normal.
Figure 3. Normal–aligned frame at xkx_{k} illustrating three typical constructions of dkd_{k} . The analytic affine normal dAN(xk)d_{\mathrm{AN}}(x_{k}) is represented in the frame {e1,…,en,en+1}\{e_{1},\dots,e_{n},e_{n+1}\} with its (n+1)(n+1) -st component normalized to −1-1 . Case 1: the affine normal is already a descent direction ( ⟨∇f(xk),dAN(xk)⟩<0\langle\nabla f(x_{k}),d_{\mathrm{AN}}(x_{k})\rangle<0 ), hence dk=dAN(xk)d_{k}=d_{\mathrm{AN}}(x_{k}) . Case 2: the affine normal points uphill ( ⟨∇f(xk),dAN(xk)⟩>0\langle\nabla f(x_{k}),d_{\mathrm{AN}}(x_{k})\rangle>0 ), so we flip the sign and set dk=−dAN(xk)d_{k}=-d_{\mathrm{AN}}(x_{k}) . Case 3: the affine normal is orthogonal to the gradient ( ⟨∇f(xk),dAN(xk)⟩=0\langle\nabla f(x_{k}),d_{\mathrm{AN}}(x_{k})\rangle=0 ); in this degenerate case we revert to the steepest–descent direction dk=−∇f(xk)/∥∇f(xk)∥d_{k}=-\nabla f(x_{k})/\|\nabla f(x_{k})\| .
Figure 4. YAND on the well-conditioned quadratic ( 10.1 ) with three different line-search strategies. Each panel shows (from left to right) the YAND trajectory on level sets, the function value f(xk)−f⋆f(x_{k})-f^{\star} (log scale), and the gradient norm ∥∇f(xk)∥2\|\nabla f(x_{k})\|_{2} (log scale).
Figure 5. Optimization trajectories in the original xx -coordinates for fγ(x)=12(x12+γ2x22)f_{\gamma}(x)=\tfrac{1}{2}(x_{1}^{2}+\gamma^{2}x_{2}^{2}) with γ=1,102,104\gamma=1,10^{2},10^{4} . As γ\gamma increases, the level sets become increasingly elongated. YAND-Exact and Newton remain essentially one-step methods, while the behavior of gradient descent depends more strongly on the step-size rule. In particular, GD-Fixed becomes substantially slower as the anisotropy increases, whereas GD-Exact remains convergent on this diagonal quadratic.
Figure 6. YAND trajectories after normalization y=Bγxy=B_{\gamma}x for γ=1,102,104\gamma=1,10^{2},10^{4} . After mapping to the intrinsic coordinates of ϕ(y)=12∥y∥2\phi(y)=\tfrac{1}{2}\|y\|^{2} , the trajectories collapse onto nearly identical paths, illustrating the affine invariance predicted by the theory.
Figure 7. YAND on the smooth convex polynomial ( 10.2 ). Each panel shows the optimization trajectory together with the semilog plots of f(xk)−f⋆f(x_{k})-f^{\star} and ∥∇f(xk)∥2\|\nabla f(x_{k})\|_{2} .
Figure 8. YAND on the ill-conditioned convex inverse barrier problem ( 10.3 ). The initial point x0=(0.01,0.98)⊤x_{0}=(0.01,0.98)^{\top} lies extremely close to the affine boundary x1+x2=1x_{1}+x_{2}=1 .
Figure 9. YAND on the Rosenbrock function ( 10.4 ) starting from x0=(−1.2,1.0)⊤x_{0}=(-1.2,1.0)^{\top} .
Figure 10. Gradient descent on the Rosenbrock function ( 10.4 ) with strong Wolfe line search.
Figure 11. Damped Newton on the Rosenbrock function ( 10.4 ) with strong Wolfe line search.
Figure 12. YAND on the tilted ring-shaped valley ( 10.5 ).
Figure 13. YAND on the saddle-type polynomial ( 10.6 ).
Figure 14. YAND on the four-well quartic ( 10.7 ).
More in this topic

Nonconvex Optimization

Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.

See all 145 papers

Explore similar work

CardsList

  1. An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent

    Apr 4, 2026Anja Surina, Arun Suggala, George Tsoukalas +5Last-Iterate ConvergenceMin-Max Optimization

    Google DeepMind

  2. A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad, Shampoo and Muo

    Apr 19, 2026S. Gratton, Ph. L. TointMomentum MethodsNonconvex Stochastic Optimization

    Université de Toulouse, INP, IRIT, Toulouse, France. · Université de Toulouse, INP, IRIT, Toulouse, France, and NAXYS, University of Namur, Namur, Belgium.

  3. A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity

    Apr 15, 2026Damek Davis, Dmitriy DrusvyatskiyGradient DescentAdaptive Gradient Methods

    Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA 19104