Planar methods and grossone for the Conjugate Gradient breakdown in nonlinear programming

Abstract

This paper deals with an analysis of the Conjugate Gradient (CG) method (Hestenes and Stiefel in J Res Nat Bur Stand 49:409–436, 1952), in the presence of degenerates on indefinite linear systems. Several approaches have been proposed in the literature to issue the latter drawback in optimization frameworks, including reformulating the original linear system or recurring to approximately solving it. All the proposed alternatives seem to rely on algebraic considerations, and basically pursue the idea of improving numerical efficiency. In this regard, here we sketch two separate analyses for the possible CG degeneracy. First, we start detailing a more standard algebraic viewpoint of the problem, suggested by planar methods. Then, another algebraic perspective is detailed, relying on a novel recently proposed theory, which includes an additional number, namely grossone. The use of grossone allows to work numerically with infinities and infinitesimals. The results obtained using the two proposed approaches perfectly match, showing that grossone may represent a fruitful and promising tool to be exploited within Nonlinear Programming.

Appendix

Proof of Proposition 2.1

Recalling that $n= P+N$, let us consider for $\tilde{A}^{-1}$ the positive definite matrix

$$\begin{aligned} \tilde{A}^{-1} = \sum _{i=1}^{P} \frac{1}{p_{i}^{T}Ap_{i}}p_{i}p_{i}^{T} - \sum _{i=P+1}^{P+N} \frac{1}{p_{i}^{T}Ap_{i}}p_{i}p_{i}^{T}; \end{aligned}$$

then (ii)–(iii) follow from the conjugacy of the directions $p_1, \ldots ,p_{n}$ with respect to A. Moreover, we have after a brief arrangement

$$\begin{aligned} \tilde{A}^{-1} = V \left( \begin{array}{c|c} {\displaystyle {\mathrm{diag}}_{p_{i} \in P1}} \left\{ \frac{1}{p_{i}^{T}Ap_{i}} \right\} &{} \emptyset \\ \hline \emptyset &{} - \ {\mathrm{diag}}_{p_{i} \in P2} \left\{ \frac{1}{p_{i}^{T}Ap_{i}} \right\} \end{array} \right) V^{T}, \end{aligned}$$

(6.1)

being

$$\begin{aligned} V = \left( p_1 \ \vdots \ \cdots \ \vdots \ p_{P} \ \vdots \ p_{P+1} \ \vdots \ \cdots \ \vdots \ p_{P+N} \right) \in \mathbb {R}^{n \times n} \end{aligned}$$

a nonsingular matrix. Then, by (6.1) we obtain

$$\begin{aligned} \tilde{A} = V^{-T} \left( \begin{array}{c|c} {\mathrm{diag}}_{p_{i} \in P1} \{p_{i}^{T}Ap_{i}\} &{} \emptyset \\ \hline \emptyset &{} - \ {\mathrm{diag}}_{p_{i} \in P2} \{p_{i}^{T}Ap_{i}\} \end{array} \right) V^{-1} \end{aligned}$$

hence

$$\begin{aligned} V^{T} \tilde{A} V = \left( \begin{array}{c|c} {\mathrm{diag}}_{p_{i} \in P1} \left\{ p_{i}^{T}Ap_{i} \right\} &{} \emptyset \\ \hline \emptyset &{} - \ {\mathrm{diag}}_{p_{i} \in P2} \left\{ p_{i}^{T}Ap_{i} \right\} \end{array} \right) , \end{aligned}$$

(6.2)

showing that (iv) holds. Finally, by Table 1 and the properties of the CG, let us consider the expression of the coefficients

$$\begin{aligned} \alpha _{i} = \frac{\Vert r_{i}\Vert ^2}{p_{i}^{T}Ap_{i}} = \frac{r_0^{T}p_{i}}{p_{i}^{T}Ap_{i}} = \frac{b^{T}p_{i}}{p_{i}^{T}Ap_{i}}, \qquad i \ge 1. \end{aligned}$$

Then, (6.2) implies

$$\begin{aligned} \left\{ \begin{array}{lcl} p_{i}^{T} \tilde{A} p_{i} = p_{i}^{T}Ap_{i}, &{} \qquad &{} \forall p_{i} \in P1, \\ p_{i}^{T} \tilde{A} p_{i} = -p_{i}^{T}Ap_{i}, &{} \qquad &{} \forall p_{i} \in P2. \end{array} \right. \end{aligned}$$

(6.3)

Now, to prove (v) it suffices to show that the condition $\tilde{A} (d_{P}+d_{N})=b$ holds, i.e.

$$\begin{aligned} \tilde{A} (d_{P}+d_{N})=b \quad \Longleftrightarrow \quad \left[ b - \tilde{A} (d_{P}+d_{N}) \right] ^{T}p_{i}=0, \quad i=1, \ldots ,P+N. \end{aligned}$$

The result follows by (6.3), being either

$$\begin{aligned} \begin{array}{lcl} &{}&{} \left[ b - \tilde{A} (d_{P}+d_{N}) \right] ^{T}p_{i} = b^{T}p_{i} - \alpha _{i} p_{i}^{T} \tilde{A} p_{i} = b^{T}p_{i} \\ &{}&{} -\, \displaystyle \frac{b^{T}p_{i}}{p_{i}^{T} \tilde{A} p_{i}} p_{i}^{T} \tilde{A} p_{i} = 0, \quad \forall i=1, \ldots ,P, \end{array} \end{aligned}$$

or

$$\begin{aligned} \begin{array}{lcl} &{}&{} \left[ b - \tilde{A} (d_{P}+d_{N}) \right] ^{T}p_{i} = b^{T}p_{i} + \alpha _{i} p_{i}^{T} \tilde{A} p_{i} = b^{T}p_{i} \\ &{}&{} +\, \displaystyle \frac{b^{T}p_{i}}{-p_{i}^{T} \tilde{A} p_{i}} p_{i}^{T} \tilde{A} p_{i} = 0, \quad \forall i=P+1, \ldots ,P+N. \end{array} \end{aligned}$$

$\square$