On the truncated conjugate gradient method (Q1575075)

Trust region algorithms for the unconstrained optimization problem \(\min_{x\in\mathbb{R}^n} f(x)\), where the function \(f(x)\) is continuously differentiable, often need to solve the following subproblem \[ \min_{d\in\mathbb{R}^n} g^Td+ d^TBd/2\quad\text{subject to }\|d\|\leq \Delta, \] where \(\Delta> 0\) is a trust region bound, \(g\in \mathbb{R}^n\) is the gradient of the objective function \(f(x)\) at the current iterate, and \(B\in\mathbb{R}^{n\times n}\) symmetric is an approximation to the Hessian of \(f(x)\). At each iteration of a trust region algorithm, the subproblem has to be solved exactly or inexactly to obtain a trial step. The author shows in the paper that if \(B\) is positive definite, the function reduction obtained by truncated conjugate gradient method is at least half of the reduction obtained by exact solution. Numerical tests are not given.