Homework 7, due Apr 20.

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.

Do problems 16.1 and 16.2 on p.266.

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

Then dx, dy, etc are obtained by

dx = d(1:n);
dy = d(n+1:n+m)
etc.

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