Homework 3

Gradients, Jacobians, and positive definiteness

Homework submission instructions

1 Optimality

  1. Beck, Exercise 2.17(iii)
  2. Beck, Exercise 2.19. (Note, you must argue in both directions.)

2 Directional derivative

  1. Prove that the directional derivative (when it exists) of a function \(f:\Rn\to\R\) is positively homogeneous of degree one, that is, show that for all \(\alpha\ge0\), \[ f'(x;\alpha d) = \alpha f'(x;d). \]

  2. Which unit-norm direction minimizes the directional derivative, i.e., which direction provides the largest instantaneous decrease in \(f\) at the point \(x\)?

3 Nonlinear least squares (source localization)

The source localization problem can be formulated as the optimization problems \[ \min_{x\in\Rn} \left\{ f(x):=\sum_{i=1}^m(\|x-c_i\|^2-d_i^2)^2 \right\}, \] where \(c_i\in\Rn\) are the coordinates of the \(i\)th sensor and \(d_i\in\R\) is the distance from the \(i\)th sensor to a source of unknown position. The function \(f\) is a nonlinear least squares objective. Here we assume that \(n=2\) (i.e., the source is in the plane).

In this homework, you will analyze the gradient and Jacobian of this function. In the next homework you will implement a solver for this problem.

  1. Compute the gradient of \(f(x)\) at an arbitrary point \(x\in\Rn\).

  2. Rewrite the problem as a nonlinear least squares problem in “standard form”, i.e., \[ \min_{x\in\Rn} \left\{ g(x):=\half\|r(x)\|^2 \right\}, \] where \(r(x):\Rn\to\R^m\) is the vector of residual functions. Compute also the Jacobian of \(r(x)\), given by \[ J(x) = \begin{bmatrix} \nabla r_1(x)\T\\ \vdots\\ \nabla r_m(x)\T \end{bmatrix}, \] which is an \(m\times n\) matrix.

  3. Show that as long as the sensor positions \(c_1,\ldots,c_m\) are not all colinear (that is, arrayed on a line), that the Jacobian \(J(x)\) has full rank for all \(x\in\Rn\).

4 Positive definiteness

Suppose that \(A\) is block diagonal, e.g.,

\[ A = \begin{bmatrix} A^{(1)} & 0 & \cdots & 0 \\ 0 & A^{(2)} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots &A^{(l)} \end{bmatrix}. \]

Prove that \(A\succeq 0\) if and only if each block \(A^{(k)} \succeq 0\) for all \(k\), and \(A\succ 0\) if and only if \(A^{(k)} \succ 0\) for all \(k\).