Conjugated Directions Methods – Part I

Let’s say we have the following unrestricted quadratic problem to solve:

\displaystyle \min_{x}{x^TQx - b^Tx} \quad \quad (P)

We further assume that Q \in \mathbb{R}^{n+1} is a symmetric positive definite matrix.

Let’s say that we have an iterative algorithm to find the solution x^\star of problem (P). The algorithm works by selecting a “good” direction d_k at iteration k and then walk some amount \alpha _k in that direction.

x_{k+1} = x_k + \alpha _k d_k.

Moreover, let’s say that we know how to compute \alpha _k in order to minimize the problem:

\displaystyle f(x_{k+1}) = \min_{\alpha _k}{f(x_k + \alpha _k d_k)}.

Continue reading