\documentclass{amsart}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}



\topmargin 0pt
%\advance \topmargin by -\headheight
%\advance \topmargin by -\headsep
\advance \topmargin by -.4in
     
\textheight 8.9in
%\textheight 9.8in
     
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
     
%\textwidth 6in
\textwidth 7in

\input{macros}

%\newcommand{\R}{I\!\!R}
%\newcommand{\Rn}{\R^n}
\newcommand{\by}{{\bar y}}
%\newcommand{\tcone}[2]{T(#1\mid #2 )}
%\newcommand{\Rm}{\R^m}
%\newcommand{\Rnn}{\R^{n\times n}}
%\newcommand{\Rmn}{\R^{m\times n}}
%\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{\blam}{\bar \lambda}
\newcommand{\Span}{\mbox{Span}}
%\newcommand{\ip}[2]{\left\langle #1 ,#2\right\rangle}
\newcommand{\uball}{I\!\!B}
\newcommand{\polar}[1]{{#1}^\circ}
\newcommand{\duball}{\polar{\uball}}
\newcommand{\cQ}{{\mathcal{Q}}}
\newcommand{\cF}{{\mathcal{F}}}
\newcommand{\diag}[1]{\mbox{diag}\,(#1)}

\begin{document}
\centerline{\bf \Large MATH 516}
\medskip

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

%\noindent Home Due Friday, June 2.
%\bigskip

\begin{enumerate}
\item
Program the {\it practical} infeasible interior point algorithm
described in the notes and test it on the following test problems.

\noindent
\underline{Test Problems:}
\begin{center}
\parbox{5.8in}{
The matrix $M$ is computed as follows:
Let $A,B\in \R^{n\times n}$ and $q, d\in \R^n$ be randomly generated
such that $a_{ij}, b_{ij}\in (-5,5), q_i\in(-500,500),d_i\in(0.0, 0.3)$.
 Define $M=A^TA+\half (B-B^T)+\diag{d}$.
Generate ten problems in this way
for each of the dimensions $n=50,\ 100,\ 150,\ 200$.
Report the maximum, average, and minimum number of iterations needed by the
algorithm to solve these problems.
Also report back graphs of per--iteration data on a random problem
that allow you to
discuss the performance of the algorithm.
Can you improve the performance of the algorithm by changing some
of the parameters appearing in the algorithm?
}\end{center}
\medskip

\item In this problem we study the theory and algorithmic implications
for an interior point approach to the {\it horizontal linear
complementarity problem}. In what follows we assume
that the matrix
$Q\in\R^{p\times p}$ is symmetric and positive semi-definite
and that $c\in\R^p$, $A\in\R^{m\times p}$,
$E\in\R^{k\times p}$, $d\in\R^k$, and $b\in\R^m$.
\begin{enumerate}
\item
Assume that $\mbox{Nul}\,(E^T)=\{0\}$ and consider the QP
$$
\begin{array}{lll}
{\mathcal{Q}}_2&\mbox{minimize}&\half u^TQu-c^tu\\
&\mbox{subject to}&Au\le b,\ Eu=d,\ 0\le u\ .
\end{array}
$$
Related to ${\mathcal{Q}}_2$ is the so-called {\it horizontal LCP}
\smallskip

\noindent
\underline{The Horizontal LCP (HLCP)}

\noindent
Given $M\in\R^{n\times n}$, $G\in \R^{k\times n}$, $h\in\R^k$,
and $q\in\R^n$,
find $x\in\R^n$, $z\in\R^k$, and $y\in \R^n$ such that
$$
Mx+G^Tz+q=y,\ Gx=h,\ 0\le x,\ 0\le y,\ \mbox{and}\ x^Ty=0\ .
$$
\smallskip

\begin{enumerate}
\item
Write the KKT conditions for ${\mathcal{Q}}_2$.
\item
Show that the KKT conditions for ${\mathcal{Q}}_2$ are an instance
of the HLCP by specifying $M,\ G,\ h$, and $q$ in terms
of $Q,\ A,\ E,\ c,\ b,$ and $d$.
\item
Show that under this specification $\mbox{Nul}\,(E^T)=\{0\}$
if and only if $\mbox{Nul}\,(G^T)=\{0\}$.
\item
Again, show that under this specification the positive semi-definiteness
of $Q$ implies that $M$ is positive semi-definite.
\end{enumerate}

\item
Define
$$
F(x,z,y)=\left[\begin{array}{c}
Mx+G^Tz-y+q\\ Gx-h \\ XYe\end{array}\right]\ .
$$
\begin{enumerate}
\item
Show that $(x,z,y)$ solves the HLCP if and only if
$F(x,z,y)=0$ and $0\le x,y$.
\item
Assume that $M$ is positive semi-definite
and $\mbox{Nul}\,(G^T)=\{0\}$. Show that $F'(x,z,y)$
is nonsingular whenever $0<x$ and $0<y$.
\item
Define
$$
{\mathcal{F}}_+=\{(x,z,y)\, :\, Mx+G^Tz+q=y,\ Gx=h, \ 0< x,\ 0<y\}.
$$
Under the assumption that $M$ is positive semi-definite,
$\mbox{Nul}\,(G^T)=\{0\}$, and ${\mathcal{F}}_+\ne \emptyset$,
show that the set
$$
{\mathcal{F}}(t)=\{ (x,z,y)\, :\, Mx+G^Tz+q=y,\ Gx=h, \ 0\le x,\ 0\le y,\
x^Ty\le t\}
$$
is compact for all $t\ge 0$.

\noindent
({\it Hint}: There are a number of ways to show this. The best
way to start is to first show that for all $(x,z,y)\in {\mathcal{F}}(t)$
$(x,y)$ is bounded in 1-norm. This is done using exactly the same
kind of argument as is used in the LCP case. To show that the
$z$ component is also bounded there are again a number of possible
arguments. The most direct argument uses the fact that the
matrix $GG^T$ is invertible (Why?).)
\end{enumerate}
\item 
Define $$\hat{\mathcal{F}}_+ =\{ (x,y)\, :\, \exists z\in\R^k\ \mbox{such that}\
(x,z,y)\in {\mathcal{F}}_+\}.$$
Assume that $M$ is positive semi-definite and
$\mbox{Nul}\,(G^T)=\{0\}$, and $\hat{\mathcal{F}}_+ \ne \emptyset$.
Consider the mapping $\map{u}{\hat{\mathcal{F}}_+}{\mbox{int}\,(\R^n_+)}$
given by $$u(x,y)=XYe$$. 
\begin{enumerate}
\item 
Show that to each $(x,y)\in \hat{\mathcal{F}}_+$ there exists a unique
$z\in\R^k$ such that $(x,z,y)\in {\mathcal{F}}_+$.
\item
Show that for every $a\in \mbox{int}\,(\R^n_+)$ there exists a
unique $(x,y)\in \hat{\mathcal{F}}_+$ such that $u(x,y)=a$. Using this
fact one can show that $u$ defines a diffeomorphism between
$\hat{\mathcal{F}}_+$ and $\mbox{int}\,(\R^n_+)$.  
\item
Define a notion of {\it central path} for the HLCP and use the
previous result to show that it exists under the given hypotheses.
\item Show that a solution the the HLCP exists.
\end{enumerate}
\end{enumerate}

\end{enumerate}


\end{document}
