Stat 310, 2020, Homework 2. Due at the beginning of the class, Wednesday, January 22.
Problem 1: (40 points)
An essential part of optimization (as it will turn out later) is to efficiently determine the inertia of a symmetric matrix that is, the number of positive, negative, and zero eigenvalues. An inertia matrix is a matrix that has only 1,0 and -1 on the diagonal.
I.
f) Propose a way that is guaranteed to terminate in a finite number of operations, and that computes the inertia (the number of zero eigenvalues, positive eigenvalues and negative eigenvalues) of a symmetric matrix A. What seems to be the asymptotic effort of doing so for the matrix W(n) in Problem 2, if we do sparse calculations?
Problem 2: (computation; Newton’s method, 30 points)
Implement Newton’s method ((3.38) in Nocedal and Wright, or from lecture notes). Allow the number of iterations to be a parameter.
a) A matrix A is said to be congruent with a matrix B if there exists an invertible S such that A= SBST
b) Show that if A is congruent with B then B is congruent with A and if A is congruent with B and B is congruent with C then A is congruent with C.
c) Show that any symmetric matrix A is congruent with an inertia matrix N,
d) Let N1 and N2 be 2 inertia matrices that are congruent. Prove that their
number of zeros are equal (hint: find a 1 to 1 mapping between their null
spaces, based on their congruence relationship).
e) (the hard part). Show that if N1 and N2 are 2 congruent inertia matrices
then their number of positive entries is also equal to each other. (Hint: Suppose N = ST N S is the congruence relationship. Without loss of
21
generality we can assume that the matrix S is such that the first entries in N1
and N2 are positive, the following group are the negative ones, and the last
group is made of the zero entries. Otherwise the matrix S can be multiplied by the proper permutations that ensures that to be the case. Suppose now that s is the number of positive entries in N1 and that t is the number of
positive entries in N2 and that s < t . Show then that there exists a vector 0≠x∈n suchthat x =x =...x =0andthat (Sx) =(Sx) =...=(Sx) =0.
t+1t+2n 12s Forthisvector,showthat xTN x>0, (Sx)T N(Sx)≤0whichisa
21 contradiction). Then prove that N1 = N2
II. Apply the method to the following function (Fenton’s function);
ì222ü
ï 1+x xx +100ïæ1ö
f(x)=12+x2+ 2+12 í12 4ýç÷
î x þ10 ï 1 (x1x2) ïè ø
If you code the derivatives by hand, then implement the function (in Matlab) [f,g,H]=fentonfgH(x), where x is the point of function, gradient, and Hessian evaluation.
III. Initialize the method at x = [3,2]. Describe what you observe.
IV. Initialize the method at x=[3,4]. Describe what you observe.
V. For the cases where the method converges, estimate the order of convergence numerically.
VI. Submit your code to the Matlab submission folder as follows. Implement a function whose name is hwk2p2.m in Matlab, that should take in the initial point and the number of iterations, and return the final point. In Matlab, the calling sequence should be: [x]=hwk2p2(x0,n).