From @VM1.MCGILL.CA:MA56@MUSICA.MCGILL.CA Mon Jul 26 13:10:08 1993
Date:        Mon, 26 Jul 93 13:46:22 EDT
From: MA56000 <MA56@MUSICA.MCGILL.CA>
To: <4er@iems.nwu.edu>, <akgul%TRBILUN.BITNET@VM1.MCGILL.CA>, <bixby@rice.edu>,
        <boggs@cam.nist.gov>, <borchers@nmt.edu>, <CIP@ren.IR.Miami.EDU>,
        <clovis.gonzaga@inria.fr>, <clyde@flash.bellcore.com>,
        <cottle@sierra.stanford.edu>, <dmg@research.att.com>,
        <ebarnes@isye.gatech.edu>, <goldfarb@namaste.cc.columbia.edu>,
        <harker@WILMA.WHARTON.UPENN.EDU>, <hf.gls@forsythe.stanford.edu>,
        <HOFFA%YKTVMV.BITNET@VM1.MCGILL.CA>, <ilan@frodo.berkeley.edu>,
        <irv@jazz.princeton.edu>, <jcl@research.att.com>,
        <jpvial@uni2a.unige.ch>, <kanstrei@scout-po.biz.uiowa.edu>,
        <kojima@msa.is.titech.ac.jp>, <kort@icaen.uiowa.edu>,
        <kturner@cc.usu.edu>, MA56000 <MA56%mcgilla.BITNET@VM1.MCGILL.CA>,
        <megiddo@almaden.ibm.com>, <mehrotra@iems.nwu.edu>,
        <mgcr@research.att.com>, <mhw@research.att.com>,
        <mike@sol-michael.stanford.edu>, <mitchj@rpi.edu>,
        <peg@optimal.ucsd.edu>, <puett@math.uni-wuppertal.de>, <rat@RICE.EDU>,
        <res@rstone.mn.org>, <rvdb@princeton.edu>, <shawdx@ecn.purdue.edu>,
        <tone@poli-sci.saitama-u.ac.jp>, <walter@SOL-WALTER.STANFORD.EDU>,
        <zhang@math12.math.umbc.edu>, <aslewis@orion.uwaterloo.ca>,
        <bbuyin@vaxa.weeg.uiowa.edu>, <cmcd@stats.ox.ac.uk>, <dennis@RICE.EDU>,
        <djensen%yktvmx.BITNET@VM1.MCGILL.CA>, <dwagner@ONR-HQ.NAVY.MIL>,
        <ferris>, <fpotra@umaxa.weeg.uiowa.edu>, <guler@math15.math.umbc.edu>,
        <hwolkowi@orion.uwaterloo.ca>, <illest@ludens.elte.hu>,
        <imai@is.s.u-tokyo.ac.jp>, <karmar@research.att.com>,
        <klee@math.washington.edu>, <ltuncel@watdragon.uwaterloo.ca>,
        <mcshane@cs.cornell.edu>, <miketodd@cs.cornell.edu>,
        <mizuno@cs.cornell.edu>, <msc_wjp@jhuvms.hcf.jhu.edu>,
        <nazareth@amath.washington.edu>, <nesterov@divsun.unige.ch>,
        <noma@msa.is.titech.ac.jp>, <olvi>, <pardalos@math.ufl.edu>,
        <polyak@watson.ibm.com>, <renegar@orie.cornell.edu>,
        <renu@sie.arizona.edu>, <rfreund@sloan.mit.edu>,
        <rmarsten@gitvm1.gatech.edu>, <roos@dutiosa.twi.tudelft.nl>,
        <rothblum@cancer.rutgers.edu>, <rsaigal@engin.umich.edu>,
        <rvdb@macbeth.princeton.edu>, <shanno%zodiac.BITNET@VM1.MCGILL.CA>,
        <sonnevend@ludens.elte.hu>, <tomlin@almaden.ibm.com>,
        <tseng@math.washington.edu>, <vaidya@cs.uiuc.edu>,
        <wright@mcs.anl.gov>, <yufei@cs.cornell.edu>, <nocedal@eecs.nwu.edu>,
        <kingaj@yktvmv.watson.ibm.com>, <boyd@isl.stanford.edu>,
        <lemarech@lagrange.inria.fr>, <clovis%lncc.BITNET@VM1.MCGILL.CA>,
        <jrbirge@engin.umich.edu>, <dab@yktvmz.vnet.ibm.com>,
        <pht@math.fundp.ac.be>, <Jochem.Zowe@uni.bayreuth.de>
Subject: 

Dear friends and colleagues
Here follows a LATEX file of a working paper
                                   #93-06-07
                                   Faculty of Management
                                   McGill University

%
%Luo and Ye's souped-up paper (may 31 1993)
%
\documentstyle[12pt,twoside]{article}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\topmargin}{0pt}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6in}
%%%%%%%%%%%%%%%%%%%%%% remove for final copy
%\parskip 0.1in
%\renewcommand{\baselinestretch}{1.4}
%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newcommand{\newsection}{\setcounter{equation}{0}\section}
\newcommand{\nn}{\nonumber}
\newcommand{\IR}{\makebox{\sf I \hspace{-9.5 pt} R \hspace{-7.0pt} }}
%
%
\def \bn {\hfill \\ \smallskip\noindent}
\def\proof{\bn {\bf Proof.} }
\def\QED{\hfill{\bf QED}}
\def\interior{\rm int}

%% PUT YOUR TITLE PAGE INFORMATION HERE %%%
\begin{flushleft}
{\Large{\bf
On the Complexity of a Column Generation
Algorithm
for  Convex or Quasiconvex Feasibility Problems}}
\footnote{
The research of the first author is supported
by the Natural Sciences and Engineering
Research Council of Canada, grant number OPG0004152 and by the FCAR of
Quebec;
the research of the second author is supported
by the Natural Sciences and Engineering
Research Council of Canada, grant number OPG0090391;
the research of the third
author is supported by NSF grant DDM-9207347.}\\

\vspace{0.8cm}
Jean-Louis GOFFIN\\
{\em Faculty of Management, McGill University, 1001 Sherbrooke W,
Montreal, Quebec, H3A 1G5, Canada}\\
Zhi-Quan LUO\\
{\em Department of Electrical and Computer
Engineering, McMaster University, Hamilton, On\-ta\-rio,
L8S 4L7, Canada}\\
and\\
Yinyu YE\\
{\em Department of Management Sciences, The University of Iowa,
            Iowa City, Iowa 52242, USA.}\\
{June 3, 1993; revised June 14, 1993}\footnote{
This is a revised version of GERAD report 93-17.\\
To appear in
{\em Large Scale Optimization: State of the Art},
W. W. Hager, D. W. Hearn and P.M. Pardalos, Editors,
1993 Kluwer Academic Publishers B.V.
}

\end{flushleft}
\vspace{0.6cm}
\begin{quote}
\begin{flushleft}


{\bf Abstract}
\end{flushleft}


{\small
We analyze the convergence and the complexity of a potential reduction
column generation algorithm
for solving general convex or quasiconvex
feasibility problems defined
by a separation oracle. The oracle is called at the analytic
center of the set given by the intersection of the linear inequalities
which are the previous answers of the oracle.
We show that the algorithm converges in finite time and is in fact
a fully polynomial approximation algorithm,
provided that the feasible region has an nonempty interior.
This result is based on the works of Ye \cite{Ye1} and Nesterov
\cite{Nes1}.


{\bf Keywords}: Convex feasibility problem, potential reduction,
column generation, cutting planes.
}

\end{quote}




\newpage
%%SO MUCH FOR THE TITLE PAGE
\newsection{Introduction}
We consider the problem of finding an interior point in a convex set
$S\subset\IR^m$, where $S$ is contained in the cube
$\Omega^0=\{y\in\IR^m:0\leq y\leq e\}=[0,1]^m$.
The feasible set $S$ contains a full dimensional ball of radius
$\epsilon$;
clearly $\epsilon\leq\frac{1}{2}$.

The set $S$ is defined implicitly by a {\bf separating oracle}
which for every
$\bar y\in \Omega^0$  either answers that
$\bar y$ belongs to  $\interior(S)$
or generates
a separating hyperplane
$\{y\in\IR^m:a^Ty\leq a^T \bar y\}\supset S$, where $a$ is scaled so
that $\Vert a\Vert =1$.

Note that the oracle is not required to give a strict separation between
$\bar y$ and $S$ as the cut goes through $\bar y$
 and that it gives a separation even if $\bar y$ belongs to the
boundary of $S$.

The problem of finding an interior point to a convex set defined by
a system (finite or infinite) of convex inequalities
\[S =\{y\in \IR^m: f_i(y)\le 0,\quad i=1,2,...\}\]
where each $f_i:\IR^m\mapsto\IR$ is convex can be cast in this manner,
if $a$ is selected to be ${g_i}/{\Vert g_i\Vert}$ and $g_i$
is an arbitrary
subgradient of any of the functions $f_i$ that satisfies $f_i(\bar y)
\geq 0$, i.e. $g_i\in\partial f_i(\bar y)$ the subdifferential of $f_i$.
The subdifferential of a convex function $f_i$ at $\bar y$
is defined as
$\partial f_i(\bar y)=\{g_i\in\IR^n:f_i(y)\geq
f_i(\bar y)+g_i^T(y-\bar y),
\forall\ y\in\IR^n\}$.
Note that for any $g_i\in\partial f_i(\bar y)$,
$f_i(y)\leq f_i(\bar y) \Rightarrow g_i^T(y-\bar y)\leq 0$
and thus if $f_i(\bar y)\geq 0$,  $f_i(y)\leq 0 \Rightarrow
g_i^T(y-\bar y)\leq 0$.

In fact, the requirement that $f_i(\bar y)$ be computed exactly
and that $g_i\in\partial f_i(\bar y)$
can be significantly relaxed.
All that
is required from the oracle is that the following query be answered:
find any $i$ such that $f_i(\bar y)\geq 0$, and $a$ such that
$a^T(y-\bar y)\leq 0$ for all $y\in \{y\in \IR^m:f_i(y)\leq 0\}$.


This very same approach applies if the  functions $f_i$
are pseudoconvex, with
$a=g_i/\Vert g_i\Vert$, where $g_i=\nabla f_i(\bar y)$ is the gradient of
any $f_i$ such that $f_i(\bar y)\geq 0$.
A function $f_i$ is quasiconvex if it is differentiable
and $f_i(y)<f_i(\bar y) \Rightarrow \nabla f_i(\bar y)^T(y-\bar y)<0$.


The problem under investigation may be cast as that of finding the
solution to an infinite system of linear inequalities, which is
defined implicitly by the oracle. The classical centering methods
that have
been suggested for this type of problem include
the center of gravity method of
Levin \cite{Lev}, the largest sphere method of Elzinga and
Moore \cite{Elmo}, the ellipsoid method of Yudin
and Nemirovskii \cite{Arik,Khacian,Shor},
the maximum volume ellipsoid method of Tarasov, Khacian and Erlich
\cite{Taras,Todk} and the method
of volumetric centers of Vaidya \cite{Vaidya}, among others.
The relaxation method of Agmon, Motzkin and Schoenberg
\cite{Agmon,Mots,Goffin}, and the projection methods on the solution set
of the system of inequalities generated so far
need to be modified somewhat as the current point $\bar y$ is feasible
and on the boundary of that set -- the algorithms proposed by
Lemar\'echal, Nemirovskii and Nesterov \cite{Lnn} may be viewed as
such a modification.

Sonnevend \cite{Sonn},
Goffin, Haurie and Vial \cite{Ghv} and Ye \cite{Ye1} proposed a column
generation -- or cutting plane -- algorithm that computes
$\bar y$ as the analytic center of the system of inequalities generated
so far.
In \cite{Ye1}, Ye showed that it is a potential-reduction
algorithm for solving the linear feasibility problem where
$S=\{y\in \IR^m:
A^Ty\le c\}$ for some $A\in \IR^{m\times d}$ and $c\in \IR^d$.
If $d$ is finite, the algorithm finds a
feasible solution in polynomial-time of $n$ and $d$.
When $d$ is infinite, this algorithm was
developed and tested for a variety of  problems, where they
performed quite well (see, for example, Burke et al \cite{Burke},
Goffin, Haurie and Vial \cite{Ghv} and Mitchell \cite{Mitchell});
but proofs of convergence and of
complexity were hard to come by.

Recently Atkinson and Vaidya developed a modified version of the
algorithm
that uses a column elimination scheme and proved a polynomial
complexity result \cite{Atkiv1}; Nesterov \cite{Nes1} proved
a complexity result for the minimization of
a convex function
using a variant of the algorithm which uses
a potential function which includes the logarithm of
a quadratic term which represents the initial set of localization,
which is assumed to be a sphere.

In this note, we show that for any given convex or quasiconvex
feasibility problem
with nonempty interior, the algorithm of \cite{Ghv,Ye1} is
a fully polynomial approximation scheme for the original
variant of the algorithm that uses only linear
inequalities to approximate the solution set
and does not use  column elimination.





\newsection{The Cutting Plane Method from Analytic Centers}

Let the solution set $S$ be contained in
$\Omega^0=\{y\in\IR^m:0\leq y\leq e\}$,
and $\interior(S)$ contain a full dimensional closed ball
with $\epsilon<\frac{1}{2}$
radius.
We also assume that there exists an oracle which for every
$\bar y\in \Omega^0$ either returns that $\bar y\in \interior(S)$
or generates
a separating hyperplane
$ \{y:a^Ty\leq a^T \bar y\}\supset S$, with $\Vert a\Vert =1$
being assumed.

The column
generation -- or cutting plane -- algorithm
\cite{Sonn,Ghv,Ye1} from exact analytic centers is as follows:

\begin{itemize}

\item{\bf Step 0}

Let
\[
A^0=(I,-I)\in \IR^{m\times 2m},\nn\]
\begin{eqnarray}
c^0=
\left(
\begin{array}{c}
e \\
0
\end{array}
\right)
\in \IR^{2m}\nn
\end{eqnarray}
\[ y^0=\frac{1}{2}e\in\IR^m\nn\]
and
\[
s^0=c^0-(A^0)^Ty^0=\frac{1}{2}e\in\IR^{2m}\nn
\]
\item{\bf Step 1}

Let $y^k$ be the analytic center of
$\Omega^k=\{y\in\IR^m:c^k-(A^k)^Ty\geq 0\}$.

Check the oracle to see if $y^k\in \interior(S)$ or not.

If yes, stop;
otherwise generate a hyperplane
$ \{y:a^T_{k+1}y\leq a^T_{k+1}y^k\} \supset S$
with $\Vert a_{k+1}\Vert =1,$
and let
\[
\Omega^{k+1}=\{y\in\IR^m:c^{k+1}-(A^{k+1})^Ty\geq 0\}
\nn\]
where
\[
A^{k+1}=(A^k,a_{k+1})
\nn\]
and

\[
c^{k+1}=
\left(
\begin{array}{c}
c^k\\
a^T_{k+1}y^k
\end{array}
\right)
\nn\]

\item{\bf Step 2}
Set $k:=k+1$ and return to Step 1.
\end{itemize}


This is a description of the algorithm that uses exact analytic centers.
Clearly approximate centers can be used instead of exact analytic
centers -- this is necessary to make the algorithm implementable
\cite{Ghv,Ye1}.

\newsection{Convergence and Complexity}
Let
\[ P(\Omega^k)=\sum_{j=1}^{2m+k}\ln(c^k-(A^k)^Ty^k)_j.\nn\]
Ye (Theorem 2 of \cite{Ye1}) showed that the sets of the sequence
 $\{\Omega^k\}$
satisfy
the following relations:

\begin{enumerate}
\item
\begin{equation}
 S\subset\Omega^k\,\quad \forall k
\label{assum1}
\end{equation}

\item
\begin{equation}
 P(\Omega^{k+1})\leq P(\Omega^k)+\frac{1}{2}\ln(r^k)^2
-(1.5-\ln 4)
\label{assum2}
\end{equation}
where
\[
(r^k)^2=a_{k+1}^T(A^k(S^k)^{-2}(A^k)^T)^{-1}a_{k+1}
\nn\]
and
\[
s^k=c^k-(A^k)^Ty^k,\; S^k={\rm\ diag(s^k)}.
\nn\]
where ${\rm\ diag}$ denotes the diagonal matrix whose
diagonal elements are the
corresponding elements of a vector.
\end{enumerate}
Using these two relations and a recent result of Nesterov \cite{Nes1},
we show that this column generation algorithm is a fully
polynomial approximation scheme. More specifically, the algorithm
stops as soon as:
\[
\frac
{2m+k}
{\frac{1}{2}+2m\ln(1+\frac{k}{8m^2})}
\geq
\frac{m}{\epsilon^2}.
\]


\begin{lemma}
\label{lobpot}
For all $k\geq 0$,
\[
P(\Omega^k)\geq(2m+k)\ln \epsilon.\nn\]
\end{lemma}

\proof

>From \ref{assum1}, $S\subset \Omega^k$. Thus
$\Omega^k$ contains a full
dimensional ball with $\epsilon$ radius.
Let the center of the ball be
$\bar y$.

Then $c^k-(A^k)^T\bar y\geq\epsilon e$;
thus
\[
P(\Omega^k)=
\sum_{j=1}^{2m+k}\ln(c^k-(A^k)^T y^k)_j\geq
\sum_{j=1}^{2m+k}\ln(c^k-(A^k)^T\bar y)_j
\geq
\sum_{j=1}^{2m+k}\ln\epsilon
\]
where $y^k$ denotes the analytic center of $\Omega^k$.
\QED

\begin{lemma}
\label{sbound}
Let $s=c^k-(A^k)^Ty$ for any $y\in\Omega^0$.
Then
\begin{enumerate}
\item $0\leq s_j\leq 1,\quad j=1,\ldots,2m$

\item $0\leq s_j\leq \sqrt{m},\quad j=2m+1,\ldots,2m+k.$
\end{enumerate}
\end{lemma}
\proof

For $j=1,\ldots,m$,\  $s_j=1-y_{j}$; since
$0\leq y_j\leq 1$, $0\leq s_j\leq 1$.

For $j=m+1,\ldots,2m$,\  $s_j=y_{j-m}$; since
$0\leq y_{j-m}\leq 1$, $0\leq s_j\leq 1$.

For $j=2m+1,\ldots,2m+k$,
\[ s_j=a_{j-2m}^Ty^{j-2m}-a_{j-2m}^Ty
\leq
\Vert a_{j-2m}\Vert\ \Vert y^{j-2m}-y\Vert
=
\Vert y^{j-2m}-y\Vert\leq\sqrt{m}
\]
The last inequality is due to the fact that
$0\leq y^{j-2m}\leq e$
and
$0\leq y\leq e$
or $y^{j-2m}\in\Omega^0$ and $y\in \Omega^0$.
\QED


\begin{lemma}
\label{AB}

Let $B^0=8I$,
$B^{k+1}=B^k+\frac{1}{m}a_{k+1}a_{k+1}^T$.
Then
\[A^k(S^k)^{-2}(A^k)^T\succeq B^k;\]
that is,
\[A^k(S^k)^{-2}(A^k)^T-B^k\] is positive definite.

\end{lemma}
\proof
Let $Y^k={\rm\ diag(y^k)}$. Then
\begin{eqnarray}
A^k(S^k)^{-2}(A^k)^T
&=&(Y^k)^{-2}+(I-Y^k)^{-2}
+\sum_{j=1}^k\frac{a_ja_j^T}{(s_{2m+j}^k)^2}\nn\\
&\succeq&
(Y^k)^{-2}+(I-Y^k)^{-2}
+\frac{1}{m}\sum_{j=1}^k a_ja_j^T\,\quad( {\rm by\ lemma\
\ref{sbound}})
\nn\\
&\succeq&
8I+\frac{1}{m}\sum_{j=1}^k a_ja_j^T\,
\quad( {\rm as}\ 0\leq y^k\leq e)\nn\\
&=&B^k\nn
\end{eqnarray}
\QED

Let $(\omega^k)^2=a_{k+1}^T(B^k)^{-1}a_{k+1}$, then
Lemma \ref{AB} indicates that
\begin{equation}
(\omega^k)^2\geq
a_{k+1}^T(A^k(S^k)^{-2}(A^k)^T)^{-1}a_{k+1}=(r^k)^2.
\label{omr}
\end{equation}

\begin{lemma}[Nesterov]\label{locknes}
\[ \sum_{j=0}^k (\omega^j)^2
\leq
2m^2\ln(1+\frac{k+1}{8m^2}).
\]
\end{lemma}
\proof

Note that
\[
\det B^{k+1}=
\det(B^k+\frac{1}{m}a_{k+1}a_{k+1}^T)
=(1+\frac{(\omega^k)^2}{m})\det B^k.
\]
Thus
\[\ln\det B^{k+1}=\ln\det B^k+
\ln(1+\frac{(\omega^k)^2}{m}).
\]
But
\[
\frac{(\omega^k)^2}{m}
\leq
\frac{1}{8}a_{k+1}^Ta_{k+1}=\frac{1}{8};
\]
hence
\begin{eqnarray}
\ln(1+\frac{(\omega^k)^2}{m})
&\geq&
\frac{(\omega^k)^2}{m}
-\frac{(\frac{(\omega^k)^2}{m})^2}{2(1-\frac{(\omega^k)^2}{m})}\nn\\
&=&
\frac{(\omega^k)^2}{m}(1
-\frac{\frac{(\omega^k)^2}{m}}{2(1-\frac{(\omega^k)^2}{m})})\nn\\
&\geq&
\frac{(\omega^k)^2}{2m}.\nn
\end{eqnarray}

Thus we have
\[
\ln\det B^{k+1}\geq
\ln\det B^0+
\sum_{j=0}^k\frac{(\omega^j)^2}{2m}
=m\ln 8 +\sum_{j=0}^k\frac{(\omega^j)^2}{2m}.
\]
But
\[
\frac{1}{m}\ln\det B^{k+1}\leq \ln\frac{{\rm trace}\ B^{k+1}}{m}
=\ln(8+\frac{k+1}{m^2}).
\]

Thus
\[
\sum_{j=0}^k\frac{(\omega^j)^2}{2m}
\leq
m\ln(8+\frac{k+1}{m^2})-m\ln 8
\]
or
\[
\sum_{j=0}^k(\omega^j)^2\leq
2m^2\ln(1+\frac{k+1}{8m^2}).
\]
\QED

\begin{theorem}\label{nice}
For all $k\geq 1$:
\[
\frac{2m+k}
{\frac{1}{2}+2m\ln(
1+\frac{k}{8m^2})}\leq\frac{m}{\epsilon^2}.
\]
\end{theorem}
\proof
>From relation (\ref{assum2}) and Lemma \ref{lobpot},
\begin{eqnarray}
(2m+k+1)\ln\epsilon
&\leq&
P(\Omega^{k+1})\nn\\
&\leq& P(\Omega^0)
+\frac{1}{2}\sum_{j=0}^k\ln(r^j)^2
-(k+1)(1.5-\ln 4)\nn\\
&=&2m\ln\frac{1}{2}
+\frac{1}{2}\sum_{j=0}^k\ln(r^j)^2
-(k+1)(1.5-\ln 4)\nn\\
&\leq&
2m\ln\frac{1}{2}+\frac{1}{2}\sum_{j=0}^k\ln(r^j)^2.\nn
\end{eqnarray}
Thus
\begin{eqnarray}
\ln\epsilon
&\leq&\frac{1}{2(2m+k+1)}
\left[2m\ln\frac{1}{4}+\sum_{j=0}^k\ln(r^j)^2\right]\nn\\
&\leq&\frac{1}{2}\ln
\frac
{2m\frac{1}{4}+\sum_{j=0}^k (r^j)^2}
{2m+k+1}\quad({\rm from\ the\ concavity\ of\ \ln})\nn\\
&\leq&\frac{1}{2}\ln
\frac
{\frac{m}{2}+\sum_{j=0}^k(\omega^j)^2}
{2m+k+1}\;\quad({\rm  from \ (\ref{omr})})\nn\\
&\leq&
\frac{1}{2}
\ln
\frac{
\frac{m}{2}
+2m^2\ln(1+\frac{k+1}{8m^2})}
{2m+k+1}\;\quad({\rm  from\ Lemma\ \ref{locknes}})\nn
\end{eqnarray}
or
\[
\frac{\epsilon^2}{m}\leq
\frac{
\frac{1}{2}+2m\ln(1+\frac{k+1}{8m^2})}
{2m+k+1}.
\]
\QED

Theorem \ref{nice} implies that the column generation scheme stops
as soon as
\[
\frac{2m+k}{
\frac{1}{2}+2m\ln(1+\frac{k}{8m^2})}\geq
\frac{m}{\epsilon^2}.\]

This complexity readily extends to the case where
$\hat y^k$ is an approximate analytic center of $\Omega^k$;
the analysis given by Ye \cite{Ye1} carries through, and shows
that the number of recentering Newton steps required
to go from one approximate analytic center to the next one
is $O(1)$.


\newpage


\begin{thebibliography}{99}


\bibitem{Agmon}
 S.  Agmon,  "The  relaxation method for linear
inequalities", Canadian Journal of Mathematics, 6 (1954), 382-392.

\bibitem{Atkiv1}
D.~S. Atkinson and P.~M. Vaidya, "A cutting plane algorithm
that uses analytic
 centers",
  University of
  Illinois at Urbana--Champaign, Urbana, IL~61820, USA, June 1992.

\bibitem{Burke}
J.~V. Burke, A.~A. Goldstein, P. Tseng, and Y. Ye,
 ``Translation cuts for minimization,''
Complexity in Numerical Optimization (Editor: P.M. Pardalos), World
Scientific (1993), pp. 57-73.



\bibitem{Danw1}
G. B. Dantzig and P. Wolfe,  "The decomposition algorithm for linear
 programming", {\it Econometrica}
{\bf 29} (1961) 767--778.

\bibitem{Elmo}
J. Elzinga and T. Moore,
"A central cutting plane algorithm for convex programming",
Mathematical Programming 8 (1975) 134-145.


\bibitem{Goffin}
 J.L. Goffin, "The relaxation method for solving systems of linear
    inequalities,"  Mathematics of Operations Research 5 (1980)  388-
    414.


\bibitem{Ghv}
J.-L. Goffin, A.~Haurie, and J.-P. Vial, "Decomposition and
nondifferentiable
 optimization with the
projective
  algorithm", {\it Management Science} {\bf 38} (1992) 284--302.




\bibitem{Kell}
J. E. Kelley,  "The cutting plane method for solving
convex programs", {\it Journal of the SIAM } {\bf 8} (1960) 703--712.

\bibitem{Khacian}
 L.G.  Khacian, "Polynomial algorithms in linear programming," Zh.
     vychisl.  Mat.  mat.  Fiz,  20, No. 1 (1980) 51-68; translated in
     USSR Computational Mathematics and Mathematical Physics,  20, No.
     1 (1980) 53-72.

\bibitem{Todk}
L. G. Khacian and M. J. Todd,
"On the complexity of approximating the maximal inscribed
ellipsoid for a polytope", Tech. Report No. 893,
SORIE, Cornell University, February 1990.

\bibitem{Lnn}
C. Lemar\'echal, A. Nemirovskii and Y. Nesterov,
"New variants of bundle methods" to appear in
Mathematical Programming, series B,
"Nondifferentiable and Large Scale
Optimization" J.-L. Goffin and J.-P. Vial, editors.


\bibitem{Lev}
A. Levin,
" An algorithm of minimization of convex
functions",
Soviet Math. Doklady, v.160 (1965), 6, 1244-1247.

\bibitem{Mitchell}
J.~E. Mitchell,
\newblock ``Karmarkar's algorithm and combinatorial
optimization problems,''
\newblock Ph.D. Thesis, Department of ORIE,
Cornell University (Ithaca, NY,
1988).

\bibitem{Mots}
  T.  Motzkin and I.J. Schoenberg, "The relaxation method for linear
     inequalities," Canadian Journal of Mathematics 6 (1954) 393-404.


\bibitem{Arik}
A. Nemirovsky and D. Yudin,
"Problem complexity
and method efficiency in Optimization", Wiley-Interscience, NY 1983.

\bibitem{Nes1}
Y. Nesterov, "Cutting plane algorithms from analytic centers:
efficiency
estimates",  University of Geneva, Geneva, Switzerland,
December 1992.


\bibitem{Ren}
J. Renegar, ``A polynomial-time algorithm based on Newton's
method for linear
 programming", {\it
Mathematical Programming } {\bf 40} (1988) 59--94.


\bibitem{Shor}
N. Z. Shor,  "Minimization Methods for Non-Differenti\-able
Functions",
 Spr\-inger-Ver\-lag, Ber\-lin, Hei\-del\-berg (1985).



\bibitem{Sonn}
G.~Sonnevend, "New algorithms in convex programming based
on a notion of  ''centre''
  (for systems of analytic inequalities) and on rational
extrapolation", in  K.~H. Hoffmann, J.~B.
Hiriat-Urruty, C.~Lemarechal, and J.~Zowe,
  editors, {\it Trends in Mathematical Optimization: Proceedings
of the 4th  French--German Conference on Optimization
in Irsee, West--Germany, April
  1986}, volume~84 of {\it International Series of
Numerical Mathematics},
  pages 311--327. Birkh{\"a}user Verlag, Basel, Switzerland, 1988.

\bibitem{Taras}
S. Tarasov, L.G.  Khachiyan, I. Erlich,
"The method of inscribed ellipsoids", Soviet Math. Doklady,
v.37 (1988).


\bibitem{Vaidya}
P. Vaidya, " A new algorithm for minimizing
convex functions over convex sets" 1989, to appear in Mathematical
Programming.


\bibitem{Ye1}
Y.~Ye, "A potential reduction algorithm allowing column generation",
{\it SIAM  Journal on
Optimization} {\bf  2} (1992) 7--20.


\bibitem{Ye2}
Y. Ye,
``Convergence of a Potential-Reduction and Column-Generation
Algorithm for
Convex Feasibility Problems,''
Working Paper, Department of Management Sciences,
The University of Iowa, Iowa City, Iowa 52242, USA.


\end{thebibliography}
\end{document}

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
Jean-Louis Goffin                                        |
Faculty of Management, McGill University                 |
1001 Sherbrooke West , Montreal, PQ, H3A 1G5, CANADA.    |
e-mail: MA56@MUSICA.MCGILL.CA                            |
Phone: 514-398-4003   FAX: 514-398-3876                  |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


