Peter Zhang

CS 61C

From univariate to multivariate:

  • Derivative -> Gradient
  • Second Derivative -> Hessian
  • Taylor Series…
\[f(x + \Delta) = f(x) + \grad f(x) \Delta + 1/2 \Delta^T \gradient^2f(x) \Delta + O(||\Delta||^3)\]

To cut the tail without error, use the mid-value theorem. Given some \(x\) and \(\delta\):

  1. There exists \(z\) on the segment \([x, x+\delta]\) such that \(f(x + \delta) = f(x) + \grad f(z) \delta\).
  2. There exists some \(z'\) on the segment \([x, x+ \delta]\) such that \(f(x + \delta) = f(x) + \grad f(x) \delta + 1/2 \delta^T \grad f(z') \delta\).

The segment connecting \(x\) to \(x + \delta\) has dimension 1. The neighborhood around a given point forms a set. A sphere is ‘hollow’, a ball is solid. With an open ball, there is no way to reach the boundary; those points are excluded from the set. A closed set contains the boundary. A neighborhood is an open set that contains the point and an open ball. Equivalently, a set of a neighborhood of a point if the point is interior.

A local minimum will have \(\grad = 0\) because otherwise, we would have \(f(x_* + \Delta) < f_(x_*)\). To generalize minimization:

n=1 n>1
\(f' = 0\) \(\grad f = 0\)
\(f'' > 0\) \(\grad^2 f \succcurlyeq 0\)

After computing the gradient and setting it equal to 0, there are any number of potential solutions. A symmetric (Hessian) matrix has \(n\) eigenvalues \(\lambda 1, \lambda_2, \lambda_3, ...\) such that: \(Hy = \lambda y\) which are computed by setting $det(\lambda I - H) = 0$. The matrix \(H\) is positive semidefinite (PSD, \(H \succcurlyeq 0\)) if all the eigenvalues are positive. One property is that \(H \succcurlyeq 0 \equiv \forall \Delta: \Delta^T H \Delta > 0\). To prove that \(H\) is sign indefinite, it suffices to show that: \(\exist y, z \in \mathbb{R}^n \text{ s.t. } y^THy.> 0, z^T H z < 0\) To show that a Hessian is PSD or NSD, compute the determininat or compute the eigenvalues. To show that it is sign indefinite, show that the determinant is zero,

Built with Jekyll on the Swiss theme.