
\documentstyle[12pt]{article}

\pagestyle{empty}
\newcommand{\textspace}{\openup 3\jot\relax}
\textspace
\renewcommand{\arraystretch}{1.4}
\input{macros}

\begin{document}

\begin{enumerate}

\item
Consider the following problem
\probmin{}{c^Tx}{\sum_{j=1}^n a_jx_j = b \\ l_j \le x_j \le u_j, j=1,\ldots,n}
where $l$ and $u$ are finite, and $b$, $a_j$ and $c_j$ are all positive numbers.
\begin{enumerate}
\item If $\tilde{x}$ is an optimal solution for this problem, prove
that there exists $\tilde{\pi}$ such that $\tilde{\pi} a_j < c_j$ implies
$\tilde{x}_j = l_j$, 
$\tilde{\pi} a_j > c_j$ implies $\tilde{x}_j = u_j$, and
$l_j < \tilde{x}_j < u_j$ implies $\tilde{\pi} a_j = c_j$.
\item Suppose the variables are listed in the problem so that
\[ (c_1/a_1) < (c_2/a_2) < \ldots < (c_n/a_n) \]
Prove that if a feasible solution exits, then there is an optimal
solution $\bar{x}$ satisfying the property that for some $s$:
$\bar{x}_j = u_j$, $j=1$ to $s-1$,
$l_s \le \bar{x}_s \le u_s$, and
$\bar{x}_j = l_j$, $j=s+1$ to $n$.
\end{enumerate}

\pagebreak

\item Let $\function{g}{\real^n}{\real}$ be the quadratic function
$g(x) = \frac{1}{2} x^TAx - b^Tx + c$, where $A \in \real^{n\times n}$ is
symmetric and positive definite.  For arbitrary $x^0 \in \real^n$
and linearly independent vectors $p^0, \ldots, p^{k-1}$, let
\[ V_k = \set{x \in \real^n}{ x = x^0 + \sum_{i=0}^{k-1} \alpha_i p^i, 
\forall \alpha_i \in \real} \]
Show that the unique minimizer of the restriction of $g$ to $V_k$ is
given by
\[ x^0 + P_k \inv{(P_k^T A P_k)} P_k^T (b - Ax^0) \]
where $P_k$ is the matrix with columns $p^0, \ldots, p^{k-1}$.

Suppose the conjugate gradient method is applied to minimize $g$, 
that is 
\[ x^{k+1} = x^k - \alpha_k p^k, k = \oneto{n} \]
where 
\[ \alpha_k = \frac{(Ax^k - b)^T p^k}{(Ap^k)^T p^k} \]
and $p^0, \ldots, p^{n-1}$ are A--conjugate, that is 
$(Ap^i)^T p^j = 1$ if $i=j$ and $0$ otherwise.
Show that
\[ g(x^k) = \min \set{g(x)}{x \in V_k}, k = \oneto{n} \]
\end{enumerate}

\end{document}

