Note: (10-27-06) You will want to use qrinsert, qrdelete, and qrupdate in your feasible point method.

Known typos:

Question: (10-29-06) For the afiro test problem, please explain the data vectors.

Answer: A * x0 = b, x0 > 0, A'*lambda0 + s0 = c, s0 > 0 The true solution is x.

Question: (10-29-06) How do we express work per iteration. Is O(...) enough?

Answer: No, compute the constant in front of the high order term.

Question: (10-30-06) For the IPM:

1. How should we choose sigma and alpha?
2. When do we stop the iteration?
3. How do we solve for the step?

Answer:

1. sigma is between 0 and 1. Choose 1/2, or your favorite number.
alpha is often chosen so that you step 95% of the way to the boundary.

2. (See p. 6 of Unit 3 Part 4 notes) Stop when x^T z < epsilon, where epsilon is perhaps 10^{-4} or so.

3. Use the normal equations.

Question: (10-30-06) For the IPM: Is it efficient to use "X\e"?

Answer:

No. When working with X and Z, note, for example, that X\e is equivalent to 1./x, and it is much more efficient to work with the vector rather than the matrix.

Question: (11-01-06) What is the operations count for qrinsert and qrdelete?

Answer:

In Matlab, say "type qrinsert" to see the code, and make the operations count from that. Similarly for qrdelete.

Question: (11-01-06) How can we update the matrix in the IPM method?

Answer:

This is possible (as mentioned briefly in class) but complicated. For this assignment, at each iteration, just refactor the matrix for the normal equations. You do not need to try to update a factorization.