
\documentstyle[11pt]{article}
%\input psfig
\newtheorem{lemma}{Lemma}[section]
\newtheorem{prop}[lemma]{Proposition}
\newtheorem{thm}[lemma]{Theorem}
\newtheorem{conj}[lemma]{Conjecture}
\newtheorem{cor}[lemma]{Corollary}
\newtheorem{alg}[lemma]{Algorithm}
\newtheorem{defn}[lemma]{Definition}
\newtheorem{exam}[lemma]{Example}
\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\catcode`\@=11
\renewcommand{\section}{
        \setcounter{equation}{0}
        \@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
        -.2ex}{2.3ex plus .2ex}{\Large\bf}
}
\catcode`\@=12
\newcommand{\pref}[1]{(\ref{#1})}
\newenvironment{pf}{~ \\[0.1in] {\bf Proof.} }{\hfill $\Box$ \bigskip}
\newenvironment{npf}[2]{~ \\[0.1in] {\bf Proof of #1~\ref{#2}.} }{\hfill
$\Box$
\bigskip}
\newenvironment{prob}{~ \\[0.1in] {\bf Problem:} \em}{\bigskip}
\newenvironment{remark}{~ \\[0.1in] {\bf Remark:} }{\bigskip}
\newenvironment{remarks}{~ \\[0.1in] {\bf Remarks:} }{\bigskip}
\newenvironment{ack}{~ \\[0.1in] {\bf Acknowledgement:} }{\bigskip}

\newcommand{\beqn}[1]{\begin{equation}\label{#1}}
\newcommand{\eeqn}{\end{equation}}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\bpr}{{\bf Proof.} \hspace{1 em}}
\newcommand{\epr}{~~\\ \hspace*{4.5in}  $\Box$}
\def\then {\Longrightarrow}
\def\iff {\Longleftrightarrow}
\def\eig {\mbox{\em Eig}}
\begin{document}
(Reference: ``A variation on Karmarkar's algorithm for solving linear
programming problems'', Earl R. Barnes, Mathematical Programming 36
(1986) 174-182.)

Consider the LP problem
\beqn{eq:LP}
\begin{array}{cc}
\mbox{minimize}&c^Tx \\
\mbox{subject to}&Ax=b \\
 & x\geq 0,
\end{array}
\eeqn
where $c,x \in \Re^n$, $b\in \Re^m$, and $A$ is $m \times n$ matrix. The
dual program is
\beqn{eq:DP}
\begin{array}{cc}
\mbox{maximize}&b^Ty \\
\mbox{subject to}&A^Ty\leq c
\end{array}
\eeqn

Let $z\in \Re^n$ be a feasible solution of \req{eq:LP} satisfying $z_j
>0,~i=1,\ldots,n.$ If $0 < R < 1,$ and $x_i \leq 0,$ for some $i$, then
\[ \sum_j^n 
\frac {(x_j-z_j)^2}{z_j^2} \geq
\frac {(x_j-z_j)^2}{z_j^2} \geq 1 > R^2.
\]
Therefore, the ellipsoid
\beqn{eq:ellipsoid}
 \sum_j^n 
\frac {(x_j-z_j)^2}{z_j^2} \leq R^2
\eeqn
lies in the interior of the positive orthant in $\Re^n.$ Therefore we
can obtain a feasible solution for \req{eq:LP} by solving the problem:
\beqn{eq:minellips}
\begin{array}{cc}
\mbox{minimize}&c^Tx \\
\mbox{subject to}&Ax=b \\
 \sum_j^n 
\frac {(x_j-z_j)^2}{z_j^2} \leq R^2.
\end{array}
\eeqn
the nonnegativity constraint $x \geq 0$ has been replaced by the
ellipsoidal constraint.

To solve \req{eq:minellips} define the diagonal matrix $D= \Diag (z).$
$D$ is a nonsingular diagonal matrix. Then for any $x$ satisfying
$Ax=b$, we have, by the Cauchy-Schwartz inequality,
\beqn{eq:cauchyS}
\begin{array}{rcl}
c^Tz-c^Tx &=& \{c-A^ty\}^T(y-x)=\left[D(c-A^Ty)\right]^TD^{-1}(x-y) \\
 &\leq& ||D(c-A^ty)|| ||D^{-1}(x-y)||\leq ||D(c-A^ty)||R.
\end{array}
\eeqn
Equality holds throughout \req{eq:cauchyS} if
\beqn{eq:equality}
D(c-A^ty)= \gamma D^{-1}(x-y)
\eeqn
for some constant $\gamma,$ and if
\[
||D^{-1}(x-y)||=R.
\]
This implies that
\[
\gamma = \frac{||D(c-A^ty)||}R.
\]
Substituting in \req{eq:equality} gives
\beqn{eq:step}
 x=z-R\frac {D^2(c-A^ty)}{D(c-A^ty)||}.
\eeqn
The conditions that $Ax=Az=b$ imply that
$AD^2(c-A^ty)=0$, or
\beqn{eq:vary}
 y=(AD^2A^T)^{-1}AD^2c.
\eeqn
We can write \req{eq:cauchyS} as
\beqn{eq:improve}
c^Tx \geq c^Tz -R||D(c-A^ty)||.
\eeqn
Combining the above, we get the following algorithm:
\begin{alg}
Let $x^0 > 0$ satisfying $Ax^0 = b$ be given. In general, if $x^k$ is
known, define
\[ D_k = \Diag (x^k) \]
and compute
\beqn{eq:xk1}
 x^{k+1}=x^{k}-R\frac {D^2(c-A^ty^k)}{D(c-A^ty^k)||},
\eeqn
where
\beqn{eq:dualk}
 y^k=(AD_k^2A^T)^{-1}AD_k^2c.
\eeqn
\end{alg}

%\bibliographystyle{plain}
%\bibliography{.psd,.master,.publs}
\end{document}
