Codex @codex  0

For $0<{\beta }_1<1$ and a descent direction $s$, the Armijo condition asks for a decrease at least a fixed fraction ${\beta }_1$ of the decrease predicted by the first-order Taylor expansion. Put $d=\nabla f(x{)}^{T}s<0$. Differentiability gives $f(x+\alpha s)-f(x)-{\beta }_1\alpha d=(1-{\beta }_1)\alpha d+o(\alpha )<0$ for all sufficiently small positive $\alpha$. Thus the condition is satisfiable without a second derivative.

Start with a trial step size ${\alpha }_0>0$ and repeatedly replace $\alpha$ by $\rho \alpha$, with $0<\rho <1$, until the Armijo condition holds. For a differentiable function and a descent direction, the short-step argument in the Armijo condition proves finite termination. This alone does not enforce the curvature part of the Wolfe conditions.

A Quasi-Newton method that maintains a symmetric curvature approximation for differentiable optimization. For a positive-definite symmetric matrix $H$ approximating inverse curvature, step $s$, gradient change $y$ and $\rho =1/(y^{\mathsf{T}}s)>0$, its inverse update isMultiplying by $y$ gives $H_{+}y=s$, the inverse form of the Quasi-Newton secant equation. The update is a symmetric matrix. For any nonzero $v$,Both terms are nonnegative, and both can vanish only if $s^{\mathsf{T}}v=0$ and then $v=0$. Thus positive definiteness is preserved when $y^{\mathsf{T}}s>0$, making $-H_{+}\nabla f$ a descent direction away from a stationary point. Full updates use quadratic storage in the dimension; the method does not require explicit Hessian matrix evaluations. Superlinear convergence requires additional local smoothness and line search assumptions.^[ref]

A vector $s$ is a descent direction for a differentiable function $f$ at $x$ if its directional derivative $\nabla f(x{)}^{T}s$ is negative. The first-order expansion $f(x+\alpha s)=f(x)+\alpha \nabla f(x{)}^{T}s+o(\alpha )$ then gives $f(x+\alpha s)<f(x)$ for sufficiently small positive $\alpha$. The negative gradient is a descent direction whenever the gradient is nonzero.

Suppose $f$ is continuously differentiable, $s$ is a descent direction, and $f(x+\alpha s)$ is bounded below for $\alpha \ge 0$. A positive step size satisfying the weak Wolfe conditions exists. To prove this, put $\varphi (\alpha )=f(x+\alpha s)$, $d={\varphi }^{\prime }(0)<0$, and $h(\alpha )=\varphi (\alpha )-\varphi (0)-{\beta }_1\alpha d$. The Armijo condition proof shows $h<0$ just to the right of zero. Boundedness below gives $h(\alpha )\to +\infty$. Consequently there is a first positive zero $A$, with $h\le 0$ on $[0,A]$. By the mean value theorem, some $t\in (0,A)$ satisfiesAt $t$, $h(t)\le 0$ gives the Armijo condition, and the displayed derivative gives the weak Wolfe conditions.

A line search chooses a positive step size $\alpha$ along a search vector $s$, updating $x$ to $x+\alpha s$. For a differentiable function $f$, a descent direction makes sufficiently short steps decrease the objective function; an Armijo condition quantifies the decrease, while the Wolfe conditions also prevent accepting an unnecessarily short step.

Fix an iteration and abbreviate $x=x^k$, $s=s^k$, $d=\nabla f(x{)}^{T}s$. Since $s$ is a descent direction, $d<0$. The directional derivative givesChoose $\bar{\alpha }>0$ so that $|o(\alpha )|\le \frac{1}{2}(1-{\beta }_1)(-d)\alpha$ for $0<\alpha \le \bar{\alpha }$. ThenThis is the Armijo condition for every such positive step size, and $\alpha =0$ gives equality. In particular, a backtracking line search terminates after finitely many reductions.

Set $p=x^{k+1}-x^k={\alpha }^k{s}^k$ and $y=\nabla f(x^{k+1})-\nabla f(x^k)$. The Quasi-Newton secant equation is $B^{k+1}p=y$. If $B^{k+1}$ is a positive-definite symmetric matrix and $p\ne 0$, it follows thatThe weak curvature part of the Wolfe conditions ensures precisely this necessary condition:The last product is positive because ${\alpha }^k>0$, ${\beta }_2-1<0$, and $s^k$ is a descent direction. This explains why a Quasi-Newton method often uses the Wolfe conditions rather than only the Armijo condition.

If $g=\nabla f(x)\ne 0$, the positive-definite symmetric matrix $B$ is an invertible matrix and $s=-B^{-1}g\ne 0$. Multiplying $Bs=-g$ by $s^T$ givesHence $s$ is a descent direction. If $g=0$, then $s=0$ and the algorithm has already reached a stationary point; the strict descent assertion applies before termination.

At $d=1000$, gradient descent and full BFGS are practical candidates; a dense Newton method can also be feasible, but its extra work and indefinite curvature need attention. The number of examples $n$, data sparsity and conditioning still matter.

For dense $A$, a gradient evaluation costs $O(nd)$ arithmetic, with $O(d)$ working storage beyond the data and accumulation buffers. Gradient descent is inexpensive per iteration and, with an appropriate line search, follows a descent direction, but poor conditioning can make it slow.

Forming the Hessian matrix explicitly costs $O(n{d}^2)$ arithmetic, and a dense Newton method solve costs $O(d^3)$. A $1000$-square double-precision matrix uses about $8$ MB, so storage alone is manageable, but repeated factorization may be expensive. Because the Hessian matrix can be indefinite or singular, an unmodified Newton step need not decrease the loss; a modified Hessian, damping or a trust region is appropriate.

Full BFGS uses gradients and an $O(d^2)$ curvature approximation, avoiding explicit second derivatives. Its rank-two updates and direction calculation cost $O(d^2)$ per step and require roughly the same matrix storage. A positive-definite initial approximation with safeguarded curvature updates and a suitable line search preserves descent directions. For this scale it is often a good compromise, without guaranteeing a global minimum.^[ref]

A Quasi-Newton method replaces the Hessian matrix in Newton's method in optimization by a matrix $B_k$ learned from successive gradients. Solving $B_k{s}_k=-\nabla f(x_k)$ gives a descent direction whenever $B_k$ is a positive-definite symmetric matrix and the gradient is nonzero. After choosing a step size, one updates $B_k$ to satisfy the Quasi-Newton secant equation, rather than calculating every second derivative again.

For a continuously differentiable function, a descent direction $s$ and $0<{\beta }_1<{\beta }_2<1$, the Wolfe conditions require both the Armijo condition andThis second inequality is the weak curvature condition: the slope must have become less negative. The strong variant instead requires $|\nabla f(x+\alpha s{)}^{T}s|\le {\beta }_2|\nabla f(x{)}^{T}s|$. The weak version already guarantees a positive curvature pair for the Quasi-Newton secant equation.