Homework 3
Gradients, Jacobians, and positive definiteness
\[ \def\argmin{\operatorname*{argmin}} \def\argmax{\operatorname*{argmax}} \def\Ball{\mathbf{B}} \def\bmat#1{\begin{bmatrix}#1\end{bmatrix}} \def\Diag{\mathbf{Diag}} \def\half{\tfrac12} \def\int{\mathop{\rm int}} \def\ip#1{\langle #1 \rangle} \def\maxim{\mathop{\hbox{\rm maximize}}} \def\maximize#1{\displaystyle\maxim_{#1}} \def\minim{\mathop{\hbox{\rm minimize}}} \def\minimize#1{\displaystyle\minim_{#1}} \def\norm#1{\|#1\|} \def\Null{{\mathbf{null}}} \def\proj{\mathbf{proj}} \def\R{\mathbb R} \def\Re{\mathbb R} \def\Rn{\R^n} \def\rank{\mathbf{rank}} \def\range{{\mathbf{range}}} \def\sign{{\mathbf{sign}}} \def\span{{\mathbf{span}}} \def\st{\hbox{\rm subject to}} \def\T{^\intercal} \def\textt#1{\quad\text{#1}\quad} \def\trace{\mathbf{trace}} \def\xbar{\bar x} \]
- See the syllabus for the due date
- Follow the homework submission instructions
1 Optimality
- Beck, Exercise 2.20(v)
- Beck, Exercise 2.25. (Note, you must argue in both directions.)
2 Directional derivative
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). \]
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.
Compute the gradient of \(f(x)\) at an arbitrary point \(x\in\Rn\).
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.
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\).