
\documentclass{amsart}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm,amssymb}


\topmargin 0pt
%\advance \topmargin by -\headheight
%\advance \topmargin by -\headsep
\advance \topmargin by -1in

\textheight 10in
%\textheight 9.8in

\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in

%\textwidth 6in
\textwidth 6.8in


%\input{macros}

\newcommand{\R}{\mathbb{R}}
\newcommand{\bS}{\mathbb{R}}
\newcommand{\Sn}{\bS^n}
\newcommand{\bE}{\mathbb{E}}
\newcommand{\Rn}{\R^n}
\newcommand{\Rm}{\R^m}
\newcommand{\map}[3]{#1:#2\mapsto #3}
\newcommand{\dd}[3]{#1'(#2:#3)}
\newcommand{\norm}[1]{|\!| #1 |\!|}
\newcommand{\abs}[1]{|#1|}
\newcommand{\tpose}[1]{#1^{\scriptscriptstyle T}}
\newcommand{\e}{\hbox{e}}
\newcommand{\grad}{\nabla}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\bx}{\bar x}
\newcommand{\cP}{{\cal P}}
\newcommand{\cl}{\mbox{\, \rm cl}}
\newcommand{\tp}{{\scriptscriptstyle T}}
\newcommand{\Span}{\mbox{Span}}
\newcommand{\ip}[2]{\left\langle #1 ,#2\right\rangle}
\newcommand{\tcone}[2]{T_{#2}(#1)} 
\newcommand{\set}[2]{\left\{ #1\,\left|\, #2\right.\right\}}
\newcommand{\dist}[2]{\mathrm{dist}\left( #1\, \left|\, #2\right.\right)}
\newcommand{\lev}[2]{\mathrm{lev}_{#2}(#1)}

\def\lam{\lambda}
\def\eps{\epsilon}
\def\alf{\alpha}
\def\cA{\mathcal{A}}

\begin{document}
\small
\centerline{\bf \Large MATH/AMATH 516}
\medskip

\centerline{\bf \Large  THIRD HOMEWORK SET}
\bigskip

%\noindent Homework Due Friday, April 22. 
%Please leave time for the programming assigment in problem 4.

\bigskip


\begin{enumerate}
\item
Let $\Omega\subset\Rn$ and $x\in\Omega$. The tangent cone
to $\Omega$ at $x$ is given by
\[
\tcone{x}{\Omega}:=\set{u}{\exists\, \{x^k\}\subset\Omega,\ x^k\rightarrow x,\ t_k\downarrow 0
\mbox{ with } t_k^{-1}(x^k-x)\rightarrow u}.
\]
\begin{enumerate}
\item
Show that
\[
\tcone{x}{\Omega}:=\set{tu}{t\ge 0 \mbox{ and }\exists\, \{x^k\}\subset\Omega,\ x^k\rightarrow x,
\mbox{ with } \frac{(x^k-x)}{\norm{x^k-x}}\rightarrow u}.
\]
\item
Show that $\tcone{x}{\Omega}$ is a cone, i.e. $\lam \tcone{x}{\Omega}\subset \tcone{x}{\Omega}$
for all $t\ge 0$.
\end{enumerate}
\item Let $A\in\R^{s\times n}$, $a\in\R^{s}$, 
$B\in\R^{r\times n}$, and $b\in\R^r$. Consider the set
$\Omega:=\set{x}{Ax\le b,\ Bx=b}$, where we write $u\le v$ for $u,v\in \R^m$
if and only if $v-u\in\R^m_+:=\set{y\in\Rm}{y_i\ge 0, \ i=1,\dots,m}$,
or equivalently, $u_i\le v_i,\ i=1,\dots,m$.   
The set $\Omega$ is a convex polyhedron.
\begin{enumerate}
\item Show that $\Omega$ is a closed convex set.
\item Let $\bx\in \Omega$, show that
\[
\tcone{\bx}{\Omega}=\set{v}{\ip{A_{i\cdot}}{v}\le 0\ \forall\ i\in \cA(\bx),\ Bv=0},
\]
where $\cA(\bx):=\set{i\in\{1,\dots,s\}}{\ip{A_{i\cdot}}{\bx}=b_i}$ and
$A_{i\cdot}$ is the $i^{th}$ row of the matrix $A$, $i=1,\dots,s$.
\item If $b=0$, show that $\Omega$ is a closed convex cone.
\item Show that the closed set $K\subset \bE$ is a convex cone if and only if
$K+K\subset K$ and $tK\subset K$ for all $t\ge 0$.
\end{enumerate} 
\item Let $\map{f_i}{\Rn}{\R}$ be $C^1$-smooth for $i=1,\dots,m$, and let $s$ be an
integer such that $1<s<m$.
consider the set
\[
\Omega:=\set{x\in\Rn}{f_i(x)\le 0,\, i=1,\dots,s,\ f_i(x)=0,\ i=s+1,\dots, m}.
\]
\begin{enumerate}
\item
Show that, for $x\in \Omega$,
\begin{equation}\label{eq:1}\tag{$\star$}
\tcone{x}{\Omega}\subset\set{v\in\Rn}{\ip{\nabla f_i(x)}{v}\le 0,\ i\in \cA(x),\ 
\ip{\nabla f_i(x)}{v}= 0,\ i=s+1,\dots,m},
\end{equation}
where $\cA(x):=\set{i\in\{1,\dots,s\}}{f_i(x)=0}$.
\item Suppose $n=2$ and $s=2=m$ so that there are no equalities, and let
$f_1(x_1,x_2):=x_2-x_1^3$ and $f_2(x_2,x_2):=-(x_2+x_1^3)$. First graph
the region $\Omega$ and then show that the inclusion in \eqref{eq:1} is strict.
\end{enumerate}
%\item Given $\map{f}{\Rn}{\R}$ we define the directional derivative of $f$ in the direction
%$d\in\Rn$ to be the following limit when it exists:
%\[
%\dd{f}{x}{d}:=\lim_{t\downarrow 0}\frac{f(x+td)-f(x)}{t}.
%\]
%\begin{enumerate}
%\item If $f$ is $C^1$-smooth show that $\dd{f}{x}{d}=\ip{\nabla f(x)}{d}$.
%\item If $n=1$ and $f_i(x):=(-1)^i|x|$, show that $\dd{f_1}{0}{1}=-1=\dd{f_1}{0}{-1}$
%and $\dd{f_2}{0}{1}=1=\dd{f_2}{0}{-1}$.
%\end{enumerate}	
\item Let $\map{f}{\Rn}{\R}$. We say that $f$ is $p$-coercive for $p\ge 0$ if
\[
\lim_{\norm{x}\to\infty}\frac{f(x)}{\norm{x}^p}=+\infty.
\] 
Note that if $f$ is $p_0$-coercive, then $f$ is $p$-coercive for all $0\le p\le p_0$.
Define the $\alf$-lower level set of $f$ to be the set
\[
\lev{\alf}{f}:=\set{x\in\Rn}{f(x)\le\alf}.
\]
Given $Q\in\Sn$ and $b\in\Rn$, set $h(x):=\half x^TQx-\ip{b}{x}$.
\begin{enumerate}
\item If $\map{f}{\Rn}{\R}$ is $p$-coercive for any $p\ge 0$, 
show that $\lev{\alf}{f}$ is a compact for all $\alf\in\R$.
\item If $f$ is $p$-coercive and continuous on a nonempty closed set $\Omega\subset \Rn$,
show that there must exist a solution to the problem $\min_{\Omega}f$.
\item Show that
\[
((1-\lam)x+\lam y)^TQ((1-\lam)x+\lam y) +\lam(1-\lam)(x-y)^TQ(x-y)=(1-\lam)x^TQx+\lam y^TQy
\]
ofr all $x,y\in\Rn$ and $\lam\in\R$.
\item For what values of $p$ and under what conditions, 
if any, is the quadratic function $h$ a $p$-coercive function?
\item Under what conditions does there exist a solution to $\min_{x\in\Rn}h(x)$?
\item If there does not exist a solution to $\min_{x\in\Rn}h(x)$,
show that the optimal value must be $-\infty$.
\end{enumerate}
\item Let $\Omega$ be a nonempty closed convex subset of $\Rn$, and let
$K\subset\Rn$ be a non-empty, closed, convex, cone.
\begin{enumerate}
\item
Show that the projection onto $\Omega$, $P_\Omega$, is 1-Lipschitz.
\item Show that $\phi(x):=\dist{x}{K}$ is positively homogeneous and subadditive, i.e.,
$$
\alpha \dist{x}{K}=\dist{\alf x}{K}\quad
\mbox{and}\quad \dist{x+y}{K}\leq \dist{x}{K}+\dist{y}{K}
$$
for all
$\alpha\geq 0$ and $x,y\in\Rn$.
\item Show that $P_K$ is positively homogeneous.
%\item $P_K(x+y)=x$ and $P_{\polar{K}}(x+y)=y$ if and only if
%$x\in K,\ y\in\polar{K},$ and $\ip{x}{y}=0$.
\end{enumerate}
\end{enumerate}


\end{document}

