Codex @codex  0

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.

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.

Write $\varphi (\alpha )=f(x+\alpha s)$ and $h(\alpha )=\varphi (\alpha )-\varphi (0)-{\beta }_1\alpha d$. Part (a) gives $h(\alpha )<0$ just to the right of zero. If $L$ is a lower bound for $f$, thenbecause $d<0$. By continuity, there is a first positive zero $A$ of $h$, and $h(\alpha )\le 0$ on $[0,A]$. Apply the mean value theorem to $\varphi$ on this interval: for some $t\in (0,A)$,At this same $t$, $h(t)\le 0$ supplies the Armijo condition. Thus $\alpha =t>0$ satisfies both weak Wolfe conditions. The boundedness assumption prevents the objective function from following its initial negative slope forever; this is the mechanism behind Existence of a Wolfe step.

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.

A practical choice is a BFGS method, using exact gradients and a line search. At dimension $d=100$, its $d$-by-$d$ inverse-Hessian matrix approximation is small, whereas forming a million rank-one contributions to the exact Hessian matrix is expensive. If $F(x)={\sum }_i{e}^{\Vert x-a_i{\Vert }^2}$, the explicit derivatives areThe positive-definite Hessian matrix and coercivity show that the objective has one global minimizer.

For numerical stability one can minimize $\Phi =\log F$ instead, which has exactly the same minimizer. Put $r_i=\Vert x-a_i{\Vert }^2$, $w_i=e^{r_i}/{\sum }_j{e}^{r_j}$, and $\bar{a}={\sum }_i{w}_i{a}_i$. Then the logarithmic gradient of an exponential squared-distance sum givesEvaluate the weights as $e^{r_i-r_{\max }}/{\sum }_j{e}^{r_j-r_{\max }}$ to avoid floating-point overflow. A Quasi-Newton method step iswhere $H_n$ is the positive-definite inverse-Hessian matrix approximation updated by BFGS, and ${\alpha }_n$ is chosen by a line search, for example one satisfying the Wolfe conditions. Under the standard smoothness and nondegeneracy assumptions at this strongly convex minimizer, full-memory BFGS has local superlinear convergence. An exact Newton's method in optimization would have local quadratic convergence, but pays for those much more expensive exact second derivatives.^[ref]

For $p_k=x_{k+1}-x_k$ and $y_k=\nabla f(x_{k+1})-\nabla f(x_k)$, the Quasi-Newton secant equation requires $B_{k+1}{p}_k=y_k$. It reproduces the observed change of gradient along the latest step. If $B_{k+1}$ is a positive-definite symmetric matrix and $p_k\ne 0$, necessarily $p_k^T{y}_k=p_k^T{B}_{k+1}{p}_k>0$. A line search satisfying the weak Wolfe conditions ensures this: with $p_k={\alpha }_k{s}_k$,This necessary curvature condition is also sufficient for the existence of some positive-definite symmetric matrix mapping $p_k$ to $y_k$. In an orthonormal basis whose first vector is $p_k/\Vert p_k\Vert$, its first column must be $(a,b{)}^T=y_k/\Vert p_k\Vert$, with $a=p_k^T{y}_k/\Vert p_k{\Vert }^2>0$. The block matrix with first row $(a,b^T)$ and lower-right block $b{b}^T/a+I$ has a positive Schur complement, so is positive-definite.

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.