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

We further assume that is a symmetric positive definite matrix.

Let’s say that we have an iterative algorithm to find the solution of problem . The algorithm works by selecting a “good” direction at iteration and then walk some amount in that direction.

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

A necessary condition for the latter minimization problem is to have:

The question that it poses now is: How to choose the next direction ? Let’s be audacious and assume that somehow we can take the best direction possible, i.e., the direction that leads us to the optimal solution:

Obviously we don’t know the optimal solution and we need to find some condition on that doesn’t depend on . Fortunately such condition exists.

Hence,

Hum… So we pick the next direction such that Note that doesn’t mean , but it seems a good criteria to use in order to chose where to go next, as the best direction respects the same condition. One can show the following proposition:

**Proposition**: Let to be a sequence of directions such that . Then .

A set in which is said to be –*conjugated *(It is a generalization of the notion of orthogonality. One can recover usual orthogonality between vectors by setting ). At this point, we conclude that our mock-algorithm works with -conjugated directions. Let’s check on another property of -conjugated directions.

**Proposition**: Let to be symmetric definite positive and to be a set of at most -conjugated directions. Then are linear independent.

*Proof. *Set and suppose are not LI. Then there exists , not all zero, such that

.

Choose and multiply the last expression by . Then,

.

But we know as is definite positive. The last expression is valid for all , and then we conclude that , which is a contradiction

We can apply the trick of multiplying by one more time. Since there are at most -conjugated directions, one can write the optimal solution as:

Multiplying by in both sides for some :

.

Thus, it is easy to see that:

Hence, the optimal solution can be computed using our mock-algorithm if one has the -conjugated directions. The question now is how to get -conjugated directions? The answer comes in a future post.

**Further Reference**

- David G. Luenberger and Yinyu Ye. 2015.
*Linear and Nonlinear Programming*. Springer Publishing Company, Incorporated [Chapter 9]. - Alexey Izmailov and Mikhail Solodov. 2012.
*Otimização Volume II – Métodos Computacionais*. IMPA [Section 3.4].