- 1.
- Compare and contrast the line search and trust region methods of
globalizing a quasi-Newton method. Your discussion should touch on the
following points:
- (a)
- The cost of taking a step (that is, of solving the line search subproblem and trust region subproblem), and the complexity of the algorithms.
- (b)
- Dealing with nonconvexity.
- (c)
- Convergence theorems.

- 2.
- Derive the BFGS update used for approximating the Hessian of the objective function in an unconstrained minimization problem. Explain the rationale for the steps in the derivation.
- 3.
- (a)
- State carefully and prove the first-order necessary condition
for
to have a local minimum at
*x*=*x*^{*}. - (b)
- Give an example to show that the first-order condition is only necessary, not sufficient.
- (c)
- State carefully and prove the second-order necessary condition
for
to have a local minimum at
*x*=*x*^{*}. - (d)
- Give an example to show that the second-order condition is only necessary, not sufficient.

- 4.
- (a)
- Let
be a sequence in
,
and suppose

Define `` q-quadratically.'' - (b)
- Let
be given. Newton's method for minimizing
*f*is locally q-quadratically convergent. State carefully and prove this theorem.

- 5.
- Suppose
is convex.
- (a)
- State and prove a theorem indicating that the usual first-order necessary condition is, in this case, a sufficient condition.
- (b)
- Prove that every local minimum of
*f*is, in fact, a global minimum.

- 6.
- Consider the equality-constrained problem

where and are smooth functions.- (a)
- Explain how to apply the quadratic penalty method to (). How does one obtain an estimate of the Lagrange multiplier?
- (b)
- Explain how to apply the augmented Lagrangian method to (). How does one obtain an estimate of the Lagrange multiplier?

- 7.
- Recall that the
norm of
is defined by

Derive the formula for the corresponding induced matrix norm of , and prove that it is correct. - 8.
- (a)
- What is the condition number of a matrix ?
- (b)
- Explain how this condition number is related to the problem of
computing the solution
*x*to*Ax*=*b*, where*b*is regarded as the data of the problem, and*A*is regarded as being known exactly.

- 9.
- Consider the least-squares problem
*Ax*=*b*, where ,*m*>*n*, and are given, and*x*is to be determined.- (a)
- Assume that
*A*has full rank. Explain how to solve the least-squares problem using:- i.
- the normal equations;
- ii.
- the QR factorization of
*A*; - iii.
- the SVD of
*A*.

- (b)
- Discuss the advantages and disadvantages of each of the above methods. Which is the method of choice for the full rank least-squares problem?

- 10.
- (a)
- Give a simple example to show that Gaussian elimination without partial pivoting is unstable in finite-precision arithmetic. (Hint: The example can be as small as .)
- (b)
- Using the concept of backward error analysis, explain the conditions under which Gaussian elimination with partial pivoting can be unstable in finite-precision arithmetic. (Note: This question does not ask you to perform a backward error analysis. Rather, you can quote standard results in your explanation.)
- (c)
- Give an example to show that Gaussian elimination with partial pivoting can be unstable.

- 11.
- (a)
- Suppose that
has eigenvalues

Explain how to perform the power method, and under what conditions it converges to an eigenvalue. - (b)
- Explain the idea of simultaneous iteration.
- (c)
- Explain the QR algorithm and its relationship to simultaneous iteration.

- 12.
- Suppose that
is invertible,
*B*is an estimate of*A*^{-1}, and*AB*=*I*+*E*. Show that the relative error in*B*is bounded by (using an arbitrary matrix norm). - 13.
- Show that if A is symmetric positive definite and
*banded*, say*a*_{ij}= 0 for |*i*-*j*| >*p*, then the Cholesky factor*B*of*A*satisfies*b*_{ij}= 0 for*j*>*i*or*j*<*i*-*p*. - 14.
- Suppose that Gaussian elimination (without partial pivoting) is
applied to a symmetric positive definite matrix
*A*. Write

where each*E*_{j}is an elementary (lower triangular) matrix (left-multiplication by*E*_{j}accomplishes the*j*th step of Gaussian elimination). None of the*E*_{j}s is a permutation matrix, that is, no row interchanges are performed. The purpose of this exercise is to prove that this is possible (i.e. that Gaussian elimination can be applied without row interchanges) and to prove the following inequality:

Do this by proving the following three lemmas:- (a)
- Let
*B*be a symmetric positive definite matrix. Then*b*_{ii}> 0for and the largest entry of*B*(in magnitude) occurs on the diagonal. - (b)
- Let
*A*be a symmetric positive definite matrix, and suppose one step of Gaussian elimination is applied to*A*to obtain

Then is also symmetric positive definite. - (c)
- Using the notation of the previous lemma,

- 15.
- Let
have SVD
*A*=*USV*^{T}, where and are orthogonal and*S*is diagonal (*S*_{ij}=0 if ). Define*S*^{(k)}by

and define*A*^{(k)}by

*A*^{(k)}=*US*^{(k)}*V*^{T}.

What is , where is the matrix norm induced by the Euclidean () vector norm? Prove your answer.