Homework 4
Assigned Mon Mar 30, due Thurs Apr 9 (any time)

The Primal Barrier Method
1. Write a Matlab function to implement the primal barrier method for minimizing a convex function subject to convex inequality constraints, that is (11.1) with no equality constraints. The first parameter should be an anonymous function funs which, when it is called, will provide the name of a routine that computes the objective function, the inequality constraints, and their gradients and Hessians. Use cell arrays to represent the constraints, their gradients and their Hessians: thus, for example, congrad{k} and conhess{k} could return the kth constraint gradient and Hessian respectively. Other parameters needed by the barrier method are the initial value for the barrier parameter, the scalar mu, the initial guess x0, the target for the final duality gap, a maximum number of iterations, and several parameters to pass to your code newtmeth: the line search parameters &alpha and &beta and a tolerance telling it to terminate when the Newton decrement is sufficiently small (you will need to add this capability to newtmeth.)

New: It was pointed out to me by a couple of students that, given the limitations of Matlab's anonymous functions, your existing newtmeth code can't be conveniently used to minimize a barrier function based on funs. The easiest solution seems to be to create a specialized Newton barrier minimization method newtmethbarrier which has parameters that include the barrier parameter t, the anonymous function funs described above, and the starting point x0. Also, you should change the call to chol to return a second argument that is nonzero if the matrix is not numerically positive definite, so you can print an informative message and terminate instead of incurring an error if this happens - which it may when the barrier parameter is sufficiently large.

New: Even if Cholesky reports that the Hessian is positive definite, the full Newton step (initial step 1) may be infeasible. If you just go ahead and evaluate the log barrier function at an infeasible point, you will get the log of a negative number which gives a complex number which is totally irrelevant. There is an easy fix: the barrier function should be defined as:
• B = tf0(x) - sum log -fi(x) if x is feasible
• B = inf (&infin) otherwise
By simply using the perfectly good floating point number inf in this way the line search will reject the step of 1 and try 1/2, 1/4 etc until it finds a feasible point.