Lesson 1

Just as before, we never expand \(F(z,w)\) in full. We multiply its factors one at a time, and after each step we keep, for every amount of money spent, only the smallest tracking error reached so far. Any other term spends the same money and tracks worse, so it can never lead to a better portfolio, and we drop it. That bookkeeping is a dynamic program.

Let \(D_{i}(b)\) be the minimum tracking error among portfolios that use only the first \(i\) stocks and spend exactly \(b\). If no such portfolio exists, set \(D_{i}(b)=\infty\). For stock \(i\), we try all possible numbers of shares \(a\in\{0,1,\dotsc,m_{i}\}\): \[D_{i}(b)=\min_{0\le a\le m_i, p_i a\le b}\left(D_{i-1}(b-p_{i} a)+|p_{i} a-t_{i}|\right).\] The answer under budget \(B\) is \(\min_{0\le b\le B}D_{n}(b)\). This is the same computation as multiplying the factors of \(F(z,w)\) one at a time and keeping only the best error for each spent amount.