Codex @codex  0

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.

Choose a strictly feasible point, an initial barrier parameter ${\mu }_0>0$, and $0<\theta <1$. At outer iteration $k$, approximately minimize the logarithmic barrier objective $f_{{\mu }_k}$ over its strictly feasible domain of a function. For example, use damped Newton methods, choosing an inner step size by backtracking line search so that every $c_i$ stays positive and the barrier objective function decreases. Solve to a tolerance $\Vert \nabla f_{{\mu }_k}(x^k)\Vert \le {\epsilon }_k$, where ${\epsilon }_k\to 0$. Set ${\mu }_{k+1}=\theta {\mu }_k$ and use $x^k$ as the next starting point.

The associated Lagrange multiplier estimates areReducing ${\mu }_k$ makes these perturbed complementary slackness equations approach the KKT conditions. This describes the generic interior-point method; existence of a solution to every inner minimization needs appropriate additional attainment assumptions and does not follow from strict feasibility alone.

The backtracking line search starts with ${\alpha }_{\mathrm{init}}>0$, tests the Armijo condition, and repeatedly replaces a failed step by $\tau \alpha$, with fixed $\tau \in (0,1)$. It accepts the first step that passes. Backtracking makes an overambitious trial step small enough for a local linear model to predict the change reliably; part (ii) ensures finite termination. The Armijo condition guarantees a decrease of at least $-\alpha \beta g^{T}p>0$ along a nonzero descent direction. Merely obtaining some decrease without this quantitative lower bound would not provide the convergence estimate in the following parts.

A line search chooses a positive step size giving useful decrease along the chosen direction. Fix $\sigma ,\beta \in (0,1)$ and a trial step $\bar{\alpha }>0$. The Armijo condition isThe backtracking line search tests $\bar{\alpha },\beta \bar{\alpha },{\beta }^2\bar{\alpha },\dots$ and takes the first accepted value. A Lipschitz gradient has $\Vert \nabla f(y)-\nabla f(x){\Vert }_2\le L\Vert y-x{\Vert }_2$ with a constant $L$ independent of $x,y$.

Integrating the gradient along a segment gives the descent lemmaFor $s=-g$, every $0<\alpha \le \tau =2(1-\sigma )/L$ satisfies the Armijo condition. Thus backtracking terminates. If the trial step is accepted, $\alpha =\bar{\alpha }$; otherwise the immediately preceding step $\alpha /\beta$ failed, so it exceeded $\tau$. ConsequentlyThe same global Lipschitz constant and fixed search parameters make $c$ independent of $x$. If $g=0$, the zero direction passes the first test. If $L=0$, the gradient is constant and the first test passes, so take $c=\bar{\alpha }$.

Choose $x_0$, fixed $\bar{\alpha }>0$, $\sigma ,\beta \in (0,1)$, and repeat for every $n\ge 0$: compute $g_n=\nabla f(x_n)$, choose ${\alpha }_n$ by the backtracking line search in part (b) with $s_n=-g_n$, and set $x_{n+1}=x_n-{\alpha }_n{g}_n$. At a stationary point keep the sequence constant.

Assume $f\in C^1$ has a globally Lipschitz gradient and is bounded below on its initial sublevel set $\{x:f(x)\le f(x_0)\}$. Then the steepest descent method satisfies $\boxed{\nabla f(x_n)\to 0}$. Indeed, the Armijo condition and the uniform lower step bound giveThe objective values decrease and stay in the stated sublevel set. Summing the inequality and using its lower bound $f_{\inf }$ yieldswhich proves the limit. Every cluster point is a stationary point by continuity of the gradient. If the initial sublevel set is compact, cluster points exist. This global convergence result guarantees stationarity from arbitrary initial points under these assumptions; it does not, for a general nonconvex objective, guarantee convergence of the whole iterate sequence or a global minimum.

The quadratic model has gradient $g(x_k)+B_{k}p$ and positive-definite Hessian matrix $B_k$. Its unique minimizer is thereforeIf $g(x_k)\ne 0$, then $p_k\ne 0$ and $g(x_k{)}^T{p}_k=-p_k^T{B}_k{p}_k<0$, proving that it is a descent direction.

Backtracking line search starts with a trial step and repeatedly reduces it until the Armijo condition holds. Part (ii) guarantees finite termination because sufficiently small steps are acceptable. The test guarantees a specified positive fraction of the decrease predicted by the linear model, namely $f(x_k+\alpha p_k)\le f(x_k)+\alpha \beta g(x_k{)}^T{p}_k<f(x_k)$ for an accepted positive step. It does not require solving the line-minimization problem exactly.

If the first trial is accepted, ${\alpha }_k={\alpha }_{\mathrm{init}}$. Otherwise the preceding trial was rejected and so exceeded ${\alpha }_{\max }$, since part (ii) guarantees acceptance below that threshold. The accepted step, reduced by the factor $\tau$, consequently exceeds $\tau {\alpha }_{\max }$. In either case,The angle condition $-g_k^T{p}_k\ge \epsilon \Vert g_k{\Vert }_2\Vert p_k{\Vert }_2$ gives ${\alpha }_{\max }\ge 2\epsilon (1-\beta )\Vert g_k{\Vert }_2/(\gamma \Vert p_k{\Vert }_2)$. Hence the backtracking line search has the lower bound