Optimization 2 - Homework 2

Homework Problems

#2

Let be an arbitrary matrix, and let be itโ€™s symmetric counterpart. Show for all if and only if is positive definite.

  • WTS is positive definite
  • Suppose is positive definite
    • Then for all (defn of positive definite)
    • Then (rewrite )
    • Because , eigenvalues of are positive (property of positive definite)
    • Then the eigenvalues of either or are positive
    • Eigenvalues of are the eigenvalues of (property of eigenvalues)
    • Then the eigenvalues of and must both be positive
    • Because the eigenvalues of are positive, (property of positive definite)
    • Then (definition of positive definite)
    • Done
  • suppose
    • Then is positive definite
    • Then the eigenvalues of (and simmilarly ) are positive (property of positive definite)
    • Then the eigenvalues of and are positive (property of eigenvalues)
    • Then the eigenvalues of are positive (property of eigenvalues)
    • Then the eigenvalues of are positive (rewrite )
    • Then is positive definite (property of positive definite)
    • Done
  • Then is positive definite
  • Done

#3

Let be a symmetric matrix. Assume that there exist a matrix such that .

Show that is positive semidefinite.

  • The eigenvalues of are non-negative, as for each eigenvalue
  • Non-negative eigenvalues implies (property of positive semidefinite)
  • Done

Show that if has full column-rank, then is positive definite.

  • Suppose has full column-rank
  • Then the columns of are linearly independent (defn of full column-rank)
  • Then is nonsingular (property of symmetric matrices)
  • Then has nonzero eigenvalues (property of nonsingular matrices)
  • Because is positive semi-definite, it has non-negative eigenvalues.
  • Then the eigenvalues of must be strictly positive.
  • Then is positive definite (property of positive definite)
  • Done

#4

Let be a symmetric matrix. If are the (real) eigenvalues of , show that the Rayleigh Quotient satisfies for and

  • Eigenvectors corresponding to distinct eigenvalues of A are orthogonal to each other (property of symmetric matrices)
  • Write
  • Write
  • Write
  • Write
  • Then

Show that the quadratic form is coercive if and only if A is positive definite.

  • A quadratic form is coercive if there exists a constant such that for all
  • WTS is positive definite is coercive
  • Suppose is coercive
    • Then there exists such that for all
    • Then for all (divide both sides by )
    • From before, we know is greater than or equal to the smallest eigenvalue of .
    • Then the smallest eigenvalue of must be positive
    • Then all eigenvalues of must be positive
    • Then is positive definite
  • Suppose is positive definite
    • Then the eigenvalues of are positive
    • From before, we know is greater than or equal to the smallest eigenvalue of .
    • let represent the smallest eigenvalue of
    • Then for all (multiply both sides by )
    • Because is positive definite, is positive
    • Then is coercive with positive

Show that if and , then the quadratic function is coercive if and only if is positive definite.

  • A scalar function is coercive if

#5

To approximate a function over an interval by a polynomial of degree n we minimize the integral where . Find the equations satisfied by the optimal coefficients to minimize . Write your answer in terms of matrix , vector , and scalar given by

, ,

  • WTS a system of equations to solve for involving , and
  • The optimal is such that
  • Then the optimal derivatives of the value of with respect to is
  • Note that
  • Then we have
  • Note that
  • Then
  • Then Ac = b
  • done