Codex @codex  0

For $f(x,y)=x^4-4xy+2y^2+4$, the Newton step equations imply $y_{n+1}=x_{n+1}$. Solving the remaining equation gives the displayed scalar recurrence, defined when $3x_n^2\ne 1$. Around $(1,1)$ its error factors exactly asThus any well-defined sequence converging to $(1,1)$ has quadratic convergence, or reaches that point exactly in finitely many steps. The scalar asymptotic error constant is $3/2$; the Euclidean norm error constant on the diagonal is $3/(2\sqrt{2})$. Around $(-1,-1)$, replacing $x$ by $-x$ gives the corresponding conclusion.

For a real symmetric invertible matrix $H$, the full undamped Newton step for the displayed quadratic function sends every starting point to the unique stationary point:This follows because the gradient is affine and its first-order expansion is exact. If $H$ is a positive-definite matrix the result is the unique global minimum; a negative-definite matrix gives a global maximum, and an indefinite matrix $H$ gives a saddle point. Thus exact arrival does not by itself show that a minimization method has minimized anything. A line search, damping, or a positive-definite matrix replacing the Hessian matrix changes this exact one-step assertion.

Expanding and taking partial derivatives gives the gradient and Hessian matrixAt $p_0=(-1,0{)}^T$, these are $\nabla f(p_0)=(-6,2{)}^T$ andThus the Newton step solvesThe second equation gives $s_y=1-2s_x$; substituting into the first gives $22s_x=10$. HenceAt $p_{\ast }=(-1/2,-1/2{)}^T$, however,The eigenvalues of this Hessian matrix are $-1$ in direction $(1,1)$ and $7$ in direction $(1,-1)$. It is invertible but indefinite. Thus the Newton step is zero, andThis illustrates that stationary points are fixed points of Newton's method. Here the fixed point is a saddle point of a scalar function, not a local minimum. Indeed, direct substitution along the two eigenvector directions givesFor sufficiently small nonzero $t$, one direction decreases $f$ and the other increases it. The global minimum is instead zero: the sum of squares vanishes at $(0,0)$ and $(-1,-1)$. These are the only real zeros, since $x=-y^2$ and $y=-x^2$ imply $y(y^3+1)=0$. Thus a zero gradient is an insufficient stopping certificate for minimization problem without classifying the stationary point.

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]

For Newton's method in optimization, let $\Delta =H(f{)}^{-1}\nabla f$. Its second row equation is $-4{\Delta }_x+4{\Delta }_y=4y-4x$, so ${\Delta }_y={\Delta }_x+y-x$. Therefore $y_{n+1}=y_n-{\Delta }_y=x_n-{\Delta }_x=x_{n+1}$. The given first coordinate yieldsThe Newton step is defined where $\det H(f)=16(3x^2-1)\ne 0$; both coordinates after any defined step are equal.

The matrix $C=A-b{b}^T$ is an invertible matrix. Indeed, on the line spanned by $b$ it has eigenvalue $-1/2$, and on $b^{\perp }$ it agrees with the positive-definite restriction of $A$. Therefore the full Newton step is well defined and givesThis is the unique stationary point because $C$ is an invertible matrix. The algebra applies to every starting point, but it does not make the answer a minimum: for $d\ge 2$ it is the saddle point just classified, and for $d=1$ it is a maximum. A safeguarded minimization algorithm that replaces an indefinite matrix used as its Hessian matrix or damps the step need not take this exact step; the assertion concerns the ordinary full Newton step formula.