Unconstrained Optimization

Resources

• Kiyani, Elham, Khemraj Shukla, Jorge F. Urbán, Jérôme Darbon, and George Em Karniadakis. 2025. “Which Optimizer Works Best for Physics-Informed Neural Networks and Kolmogorov-Arnold Networks?” arXiv. https://doi.org/10.48550/arXiv.2501.16371.

Related

• Optimization
• Constrained Optimization
• Multi-Objective Optimization
• Adam

Main Idea

Solve

Iterative methods are used most commonly. The general form for updating iteration $k$ includes a step size or learning rate ${\alpha }_k\ge 0$, and a direction ${\mathbf{p}}_k$:

Using ${\mathbf{p}}_k=-\mathrm{\nabla }f(x_k)$ gives Gradient Descent, which can be related to Ordinary Differential Equations through the Gradient Flow Equation.

Supposedly, second-order methods (using ${\mathrm{\nabla }}^{2}f$ information) are categorized as either line-search methods or trust-region methods, by restricting ${\mathbf{p}}_k$ or ${\alpha }_k$ first.

Line-search Methods

After determining ${\mathbf{p}}_k$, ${\alpha }_k$ is determined based on the 1-dimensional problem,

Usually, this is solved approximately, by an inexact line search.

Wolfe Conditions

The Armijo rule is

In short, for a descent method, this condition requires that $f$ is reduced "enough", based on $\mathrm{\nabla }f({\mathbf{x}}_k)$ and ${\mathbf{p}}_k$. For instance, if both of those are very large and in the same direction, then we should be able decrease $f$ more substantially than if they are small, or do not agree with one another. Based on this, it is also referred to as the sufficient decrease rule.

The curvature rule is

We can rearrange to reveal a term resembling $\mathrm{\nabla }f({\mathbf{x}}_k+{\alpha }_k{\mathbf{p}}_k)-\mathrm{\nabla }f({\mathbf{x}}_k)$, which is part of the numerator of a forward difference approximating the Hessian along ${\mathbf{p}}_k$. The direction of the inequality corresponds to positive concavity. To further understand this rule, suppose ${\alpha }_k=0$, then

If ${\mathbf{p}}_k$ is a descent direction, then ${\mathbf{p}}_k^T\mathrm{\nabla }f({\mathbf{x}}_k)<0$, so this would require

yet, we often take $c_2=0.9$, so this condition would be violated.

The strong Wolfe condition on curvature extends this idea, requiring

Suppose $\mathrm{\nabla }f({\mathbf{x}}_k)=-{\mathbf{p}}_k$ and $\mathrm{\nabla }f({\mathbf{x}}_k+{\alpha }_k{\mathbf{p}}_k)={\mathbf{p}}_k$, in other words, ${\alpha }_k$ would be so aggressive that the slope becomes the opposite. The (weak) condition on curvature would have:

which is satisfied for the usual $c_2=0.9$. However, the strong version would require $|-1|=1\le c_2$, thus rejecting this step. Thus, to summarize, the strong Wolfe condition prevents not only small steps but also those that are too aggressive.

Quasi-Newton Methods

Newton's Method computes the update as

Near the solution, this has quadratic convergence, but further away, it may not even be a descent method. Further, computing the Hessian is expensive, especially as the size of $\mathbf{x}$ grows.

Quasi-Newton methods approximate the Hessian with an iteratively updated ${\mathbf{B}}_k.$ This must satisfy the secant equation:

Note that ${\mathbf{B}}_k$ depends on ${\mathbf{x}}_k$, (not ${\mathbf{x}}_{k+1}$), and ${\mathbf{B}}_{k+1}$ is used to find ${\mathbf{x}}_{k+2}$. We can view this as a backward Finite Difference approximation of the Hessian, along the axis aligning with ${\mathbf{x}}_{k+1}-{\mathbf{x}}_k$. In 1D this gives a single formula,

There are multiple unique ways of constructing ${\mathbf{B}}_k$, thus differentiating Symmetric Rank 1 (SR1) from Broyden-Fletcher-Goldfarb-Shanno (BFGS) methods.

BFGS methods take ${\mathbf{H}}_k={\mathbf{B}}_k^{-1}$, and

where taking the update to the approximated Hessian is specified as

Instead of computing ${\mathbf{B}}_{k+1}^{-1}$, we can use the Sherman-Morrison formula to update the inverse from the previous step, as this is a rank 1 (?) update.

AdaGrad

AdaGrad adds a preconditioner that is based on the gradient history, weighting updates to commonly updated parameters less than infrequently updated parameters.
Denoting $g_k=\mathrm{\nabla }f(x_k)$ as the gradient at step $k$,

The update is then given as

In other words, the preconditioner for parameter $j$ divides by the sum of the ${\ell }^2$ Norm of the history of updates (a vector with $k$ entries, not $n$).