\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.20in
\textheight=8.5in 
\textwidth=6.5in 
\oddsidemargin=-0.10in

\begin{document}

\noindent{\bf Math 273} \ \ \ {\bf Homework \#4, due on Wednesday, December 4th} 

\medbreak 

\noindent{\bf [1]} Consider the quadratic program 
$$\min_{x} q(x)=\frac{1}{2}x^T G x+x^Td,\mbox{ subject to } Ax=b,$$
where $G\in\R^{n\times n}$ is a symmetric matrix, $A\in \R^{m\times n}$. Assume that $A$ has full row rank $m$. 

(a) Express the first order necessary conditions for $x_*$ to be a solution in the form of a linear matrix equation in the unknown $(x_*\ \ \lambda^*)^T$.

(b) Express in (a) $x_*$ by $x+p$, with $x$ some fixed feasible estimate and unknown $p\in Null(A)$. Re-write the matrix equation now in the unknown $(-p\ \ \lambda^*)^T$.

(c) Assume in addition that the reduced-Hessian $Z^T G Z$ is positive definite. Show that the coefficient matrix in (b) is non-singular, thus there is a unique vector pair $(x_*,\lambda^*)$ satisfying the matrix equation in (a). 

\medbreak 

\noindent{\bf [2]} Show that $(0,-1)^T$ is a local minimizer for the problem 

Minimize \ $f(x)=2x_1^2+x_2$ \ subject to 

$x_2\geq x_1^2-1$ 

$x_1\geq x_2$. 

\medbreak

\noindent{\bf [3]} The problem of finding the shortest distance from a point $x_0$ to the hyperplane $\{x:\ Ax=b\}$ where $A$ has full row rank can be formulated as the quadratic program 
$$\min \frac{1}{2}(x-x_0)^T(x-x_0),\ \ \mbox{ s.t. } Ax=b.$$ 

(i) Show that the optimal multiplier is $\lambda^*=(AA^T)^{-1}(b-Ax_0)$, and that the solution is $x_*=x_0+A^T(AA^T)^{-1}(b-Ax_0)$. 

(ii) Show that in the special case where $A$ is a row vector, the shortest distance from $x_0$ to the solution set of $Ax=b$ is $\frac{|b-Ax_0|}{\|A\|}$. 

\medbreak 

\noindent{\bf [4]} Repeat problem [3], Hw \#3 using now Newton's method, and compare the two methods. Give details about your implementation (such as computation of gradient, of Hessian, of inverse, about $\alpha$, about your stopping criterion), and include your code. 

\medbreak 

 \noindent{\bf [5]} Let $V$ be a real vector space and $F:V\rightarrow \overline{\R}$ be a convex function, thus for every $u,v\in V$, we have $F(\lambda u+(1-\lambda)v)\leq \lambda F(u)+(1-\lambda)F(v)$, $\forall\lambda\in [0,1]$, whenever the RHS is defined (the RHS is not defined when $F(u)=-F(v)=+\infty$ or $F(u)=-F(v)=-\infty$). 

(a) If $F$ is convex, show that for every $u_1,...,u_n$ of points of $V$ and for every family $\lambda_1,...,\lambda_n$, $\lambda_i\geq0$, $\sum_{i=1}^n\lambda_i=1$, we have 
$$F(\sum_{i=1}^n\lambda_i u_i)\leq\sum_{i=1}^n\lambda_iF(u_i).$$ 

(b) If $F:V\rightarrow \overline{\R}$ is convex, show that the sections 
$\{u: \ F(u)\leq a\}$ and $\{u: \ F(u)<a\}$ are convex sets. 
Show that the converse is not true. 

\medbreak 

\noindent{\bf [6]} The {\it epigraph} of a function $F:V\rightarrow \R$ is the 
set 
$$\mbox{epi}F=\{(u,a)\in V\times \R|\ f(u)\leq a\},$$
where $V$ is a normed vector space.
Show that the function $F$ is convex if and only if its epigraph is convex.


\end{document} 

