Codex @codex  0

At an unconstrained local minimizer of a twice continuously differentiable objective function, the first-order optimality condition is $\boxed{\nabla f(x_{\ast })=0}$. The second-order necessary condition is $d^T{\nabla }^{2}f(x_{\ast })d\ge 0$ for every direction $d$, so the Hessian matrix is positive semidefinite.

For the Euclidean norm, the unit steepest descent direction is $-g/\Vert g{\Vert }_2$ when $g=\nabla f(x)\ne 0$; the algorithm usually uses the unnormalized direction $p=-g$. It is a descent direction because $\boxed{g^{T}p=-\Vert g{\Vert }_2^2<0}$.

Two limitations of unpreconditioned steepest descent method in high-accuracy smooth optimization are its slow zigzagging on ill-conditioned valleys and its sensitivity to scaling of the coordinates. It uses no curvature information to correct those directions, so it can require many function and gradient evaluations compared with a suitable Newton or quasi-Newton method. These are reasons to prefer curvature-aware methods in that setting, rather than a claim that gradient-based methods are never useful.

For the quadratic function, write $r_j=b-A{x}_j$ and restrict to the full line $x_j+\alpha p_j$. Symmetry of $A$ givesThe coefficient $p_j^{T}A{p}_j$ is positive by positive definiteness and $p_j\ne 0$. The unique minimizer is thereforeQuadratic minimization along a line also gives the exact changeThus strict decrease holds exactly when $p_j^T{r}_j\ne 0$. The search is over the whole line, so ${\alpha }_j$ can be negative; a positive step size would require the additional descent direction condition $p_j^T{r}_j>0$.

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.

A search direction is the nonzero vector $p_j$ used in the displayed optimization update. In a line search with positive step size, its orientation matters: a descent direction has negative directional derivative of the objective function. Minimization over a full line instead permits either sign of ${\alpha }_j$.

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.

Suppose $f$ is bounded below on its initial level set, continuously differentiable with a Lipschitz gradient nearby, and each descent direction $p_k$ uses a step satisfying fixed Wolfe conditions. If $\cos {\theta }_k=-\nabla f(x_k{)}^T{p}_k/(\Vert \nabla f(x_k)\Vert \Vert p_k\Vert )$, the displayed series converges. In particular a uniform positive lower bound on these cosines gives $\nabla f(x_k)\to 0$.

For a gradient Lipschitz constant $L$, the curvature condition gives ${\alpha }_k\ge (1-\eta )(-\nabla f^T{p}_k)/(L\Vert p_k{\Vert }^2)$. Sufficient decrease then gives $f(x_k)-f(x_{k+1})\ge \sigma (1-\eta ){\cos }^2{\theta }_k\Vert \nabla f(x_k){\Vert }^2/L$. Summing and using the lower bound on $f$ proves the assertion.