Homework 7, due Apr 20. Do problems 16.1 and 16.2 on p.266.
Please do this homework now even if you have not yet completed the
earlier ones: the program here is quite easy to implement.
Please be ready to report on the results in class on Apr 20.
Email me or phone me if you have problems.
What is the relationship between the Hessian of the primal barrier
function B(x,w) and the Hessian of the dual barrier function D(z,y) on
the central path? (Originally I wrote D(y,z), sorry.)
Implement an inefficient version of the primal dual interior point
algorithm given in Figure 17.1 on p. 274 of the text. This is very
easy. You need to write two functions, one called pd_int (the main
routine) and one called pd_ls (to compute the step length theta).
The main work in the algorithm is the computation of dx, dy, dw, dz,
defined by the equations after "solve". As discussed in class, these
equations may be written as a block matrix equation, which can be solved
simply (though inefficiently) by
d = -J\F
where F is the vector at the top of p.272, and
J (for Jacobian) is the square matrix F' underneath it.
The vector F and the matrix J are set up by statements like:
F = zeros(n+m,1);
F(1:m) = phi; % phi is the primal infeasiblity vector Ax + w - b
J = zeros(2*(n+m), 2*(n+m)); % zero the block matrix
J(1:m,1:n) = A; % top left block
Then dx, dy, etc are obtained by
dx = d(1:n);
dy = d(n+1:n+m)
Do not be confused by the strange "carot" notation in the definition
of theta: it simply means
theta = min(r*alpha, 1)
where 1/alpha is the max of the negative ratios.
Choose a stopping criterion for the while loop and justify your
choice. You cannot expect the optimality conditions to be exactly
Test the code on some of the same test problems you used for the
simplex method. Subsequent assignments
will ask you to modify this program to make it more efficient.