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.
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.
- 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].