\documentclass[11pt]{article}
\usepackage{verbatim}
\usepackage{amsmath,amsfonts}
\usepackage[mathscr]{eucal}
\usepackage{amssymb,amsmath}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{amsthm}
\newcommand {\C}{\mathbb {C}}
\newcommand {\R}{\mathbb {R}}
\newcommand {\T}{\mathbb {T}}
\newcommand {\D}{\mathcal {D}}
\newcommand {\I}{\mathcal {I}}
\newcommand {\G}{\mathcal {G}}
\newcommand {\N}{\mathcal {N}}
\newcommand {\Z}{\mathbb {Z}}
\topmargin=-0.5in
\textheight=9.0in
\oddsidemargin=-0.10in
\textwidth=6.75in
\begin{document}
\noindent {\bf Math 273}: {\bf Homework \#3, due on Friday, November 14}
\bigbreak
\noindent{\bf [1]} (This problem is related with [2] from Hw \#2)
Let $u(x,y,t)$ be a smooth solution of the time-dependent PDE
$$\frac{\partial u}{\partial t}=\frac{\partial}{\partial x} L_{u_x}(P)+\frac{\partial}{\partial y}L_{u_y}(P)-L_u(P),$$
with $u(x,y,0)=u_0(x,y)$ in $\Omega$ and $u(x,y,t)=g(x,y)$ for $(x,y)\in \partial\Omega$ and $t\geq 0$ (recall that $P$ is a notation for $(x,y,u(x,y),u_x(x,y),u_y(x,y))$).
Show that the function $E(t)=F(u(\cdot,\cdot,t))$ is decreasing in time, where
$F(u)=\int_{\Omega}L(x,y,u,u_x,u_y)dxdy.$
\bigbreak
\noindent{\bf [2]} Let $\Omega$ be an open and bounded domain in $\R^2$, with
ufficiently smooth boundary $\partial\Omega$. Consider the minimization problem
in two dimensions
$$\inf_{u}F(u)=\int_{\Omega} (Ku-u_0)^2dxdy+\alpha\int_{\Omega}f(\nabla u)dxdy,$$
with $u_0\in L^2(\Omega)$ a given square-integrable function, and $f$ a smooth function on $\R^2$ with real values. Here
$K:L^2(\Omega)\rightarrow L^2(\Omega)$ is a linear and continuous operator, and its adjoint is $K^*$ (thus $K^*$ has the property $\int_{\Omega}(Ku)v dxdy =\int_{\Omega}u (K^*v)dxdy\
$).
Obtain, as before, the Euler-Lagrange equation associated with the
minimization problem that is formally satisfied by a sufficiently smooth
optimal $u$. No explicit boundary conditions are imposed, thus you have to
deduce implicit (or natural) boundary conditions on $\partial\Omega$.
\bigbreak
\noindent{\bf [3]} Apply the gradient descent method described in class to the
two-dimensional diffusion problem
$$F(u)=\sum_{1\leq i,j\leq n}\Big[(u_{i+1,j}-u_{i,j})^2+(u_{i,j+1}-u_{i,j})^2
+\lambda(u_{i,j}-f_{i,j})^2\Big],$$
where $f_{i,j}$ is given for $0\leq i,j\leq n+1$, and with boundary
conditions $u_{i,j}=f_{i,j}$ if $i=0$ or $i=n+1$ or $j=0$ or $j=n+1$ (chosen for simplicity). Here $\lambda>0$ is a tunning parameter.
Choose a function $f$ of your choice (for example an image). If you do not have
one, you can create a synthetic image. Test various values of the parameter
$\lambda$ and observe the properties of your implementation. Give your choice of the stopping criterion and also plot the value of the objective function versus iterations. Plot the data $f$, your starting point and your final result,
as 2D images.
\bigbreak
\noindent{\bf [4]} Recall the BFGS update formula for the Hessian approximation:
$$B_{k+1}=B_k-\frac{B_ks_ks_k^tB_k}{s_k^tB_ks_k}+\frac{y_ky_k^t}{y_k^ts_k}$$
(where $B_k$ is symmetric and positive definite), and the formula to directly update the inverse of Hessian approximation:
$$H_{k+1}=(I-\rho_ks_ky_k^t)H_k(I-\rho_ky_ks_k^t)+\rho_ks_ks_k^t$$
(where $H_k$ is symmetric and positive definite, as inverse of $B_k$, and $\rho_k=\frac{1}{y_k^ts_k}$).
Using the following Sherman-Morrison-Woodbury formula, show that $H_{k+1}$ is the inverse of $B_{k+1}$.
(SWM) If $A$ is an $n\times n$ nonsingular matrix, and $a,b$ vectors in $\R^n$, let $\overline{A}=A+ab^t$, then the following (SMW) formula holds:
$$\overline{A}^{-1}=A^{-1}-\frac{A^{-1}ab^tA^{-1}}{1+b^tA^{-1}a}.$$
\bigbreak
\noindent{\bf [5]} Consider the constrained optimization problem
$$\min_{x\in \R^n} f(x),\ \ \mbox{ subject to }Ax=b,$$
where $A\in \R^{m\times n}$ has full row rank, $m\leq n$, $b\in \R^m$. Tranform the problem into an unconstrained minimization problem by one of the methods discussed in class.
\bigbreak
\noindent{\bf [6]} Verify that the KKT conditions (1st order optimality conditions) for the bound-constrained problem
$$\min_{x\in \R^n} \phi(x),\mbox{ subject to } l\leq x\leq u,$$
are equivalent to the compactly stated condition
$P_{[l,u]}\nabla \phi(x)=0,$
where the projection operator $P_{[l,u]}$ of a vector $g\in \R^n$ onto the
rectangular box $[l,u]$ is defined by
$$
(P_{[l,u]}g)_i=\left\{
\begin{array}{ll}
min(0,g_i), & \mbox{ if } x_i=l_i,\\
g_i, & \mbox{ if } x_i\in (l_i,u_i), \mbox{ for all } i=1,2,...,n\\
max(0,g_i), & \mbox{ if } x_i=u_i.
\end{array}
\right.
$$
\end{document}