From @VM1.MCGILL.CA:MA56@MUSICA.MCGILL.CA Thu Dec  2 19:51:49 1993
Date:        Thu, 02 Dec 93 20:45:49 EST
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>,
        <clyde@flash.bellcore.com>, <cottle@sierra.stanford.edu>,
        <dmg@research.att.com>, <ebarnes@isye.gatech.edu>,
        <goldfarb@cunixb.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@titisna.is.titech.ac.jp>,
        <kort@icaen.uiowa.edu>, <kturner@cc.usu.edu>,
        MA56000 <MA56@musica.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>,
        <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>, <noma@titisna.is.titech.ac.jp>,
        <olvi>, <pardalos@math.ufl.edu>, <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>, <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>,
        <jrbirge@engin.umich.edu>, <pht@math.fundp.ac.be>,
        <Jochem.Zowe@uni-bayreuth.de>, <nesterov@core.ucl.ac.be>,
        <eva@gallai.elte.hu>, <patricem@CRT.UMontreal.CA>,
        <gossisks@cs.aston.ac.uk>, <c.gonzaga@twi.tudelft.nl>,
        <numikm@vm.uni-c.dk>, <uffe@math.kth.se>, <magnanti@MIT.EDU>,
        <HEARN@ise.ufl.edu>, <nimp@unidhp.uni-c.dk>,
        <gilbert@CRT.UMontreal.CA>, <irv@dizzy.cplex.com>, <el@fusl.ac.be>,
        <gaur@cs.uiuc.edu>, <luozq@mcmail.cis.mcmaster.ca>,
        <atkinson@yertle.cc.uiuc.edu>, <angm026@vax.rz.uni-wuerzburg.dbp.de>,
        <kiwiel@ibspan.waw.pl>, <tind@mi.aau.dk>, <averick@mcs.anl.gov>,
        <behrman@sccm.stanford.edu>, <bertseka@lids.mit.edu>,
        <jerome@sona3.vc50.edu>, <chakrapa@ams.sonysb.edu>, <chen@ise.ufl.edu>,
        <gchen@math13.umbc.edu>, <arconn@watson.ibm.com>, <joe_dunn@ncsu.edu>,
        <eckstein@think.com>, <floudas@zeus.princeton.edu>,
        <andersf@math.kth.se>, <fuku@kuamp.kyoto-u.ac.jp>,
        <skywalker!blood!ericg@texsun.sun.com>, <hager@math.ufl.edu>,
        <art@iems.nwu.edu>, <infanger@or.stanford.edu>, <tim_kelley@ncsu.edu>,
        <akuwahat@msm.epri,com>, <bgkq312@utxvm.bitnet>, <4076p@navpgs>,
        <mwl@sdna3.ucsd.edu>, <rrm>, <more@mcs.anl.gov>, <mulvey@macbeth.pri
Subject: paper

\documentstyle[11pt]{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\theequation {\thesection.\arabic{equation}}
\def\pn {\par\smallskip\noindent}
\def \bn {\hfill \\ \smallskip\noindent}
\def\proof{\bn {\bf Proof.} }
\def\QED{\hfill{\bf Q.E.D.}}
\def\interior{\rm int}

%% PUT YOUR TITLE PAGE INFORMATION HERE %%%
\begin{flushleft}
{\Large{\bf
Further Complexity Analysis of a Primal-Dual 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 GERAD, 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.}\\
{November, 1993}

\end{flushleft}
\vspace{0.6cm}
%\begin{quote}
\begin{flushleft}
{\bf Abstract}
\end{flushleft}
{\small
We further analyze the convergence and the complexity of a primal-dual
column generation algorithm for solving general convex or quasiconvex
feasibility problems defined by a separation oracle. The oracle is
called at an {\it approximate} 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.}
\begin{flushleft}
{\bf R\'esum\'e}
\end{flushleft}
{\small Nous \'etudions la convergence et la  complexit\'e d'un
algorithme primal dual  g\'en\'erant des colonnes
appliqu\'e \`a la r\'esolution du probl\`eme de la
r\'ealisibilit\'e d'un syst\`eme
d'in\'equa\-tions convexes ou qausiconvexes
d\'efinies par un oracle de s\'eparation.
Cet oracle est consult\'e \`a un centre analytique {\it approch\'e}
de l'ensemble d\'efini par l'intersection des in\'egalit\'es
lin\'e\-aires qui repr\'e\-sen\-tent les r\'epon\-ses de l'oracle.
L'algorithm converge en temps fini et est en fait
un algorithme d'ap\-pro\-xi\-ma\-tion polynomial,
pourvu que la r\'egion admissible ait un int\'erieur.}



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

{\bf AMS subject classification}: 90C25, 90C26, 90C60.
%\end{quote}
\newpage
%%SO MUCH FOR THE TITLE PAGE
\newsection{Introduction}\label{intro}
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 linear inequalities generated
so far; a new column is then generated at $\bar y$ and added to the system
of linear inequalities. Mitchell \cite{Mitchell}
and Mitchell and Todd \cite{Mitodd} also applied a column
generation interior-point method to solving combinatorial optimization
problems. Goffin, Luo and Ye \cite{GLY} recently analyzed the iteration
complexity for this algorithm, based on several results of Nesterov
\cite{Nes1} and Ye \cite{Ye1}. Their analysis relies on using the
exact analytic center to generate a cut.

In \cite{Ye1}, Ye showed that how to use an approximate center to generate
cut for solving a finite linear feasibility problem. In this note, we show
that for any given convex or quasiconvex
feasibility problem with nonempty interior, the algorithm that uses an
approximate center to generate cut is a fully polynomial approximation
scheme.  To update an approximate analytic center, the algorithm uses
a constant number of primal-dual Newton iterations.

The problem studied is that of finding an interior point in a convex set
$\Gamma\subset\IR^m$ assumed to have a nonempty interior, and
where $\Gamma$ is contained in the cube
$\Omega^0=\{y\in\IR^m:0\leq y\leq e\}=[0,1]^m$.

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


The problem of finding an interior point to a convex set defined by
a system (finite or infinite) of convex or pseudoconvex inequalities
can be cast in this manner.

\newsection{Preliminaries}

Before we use approximate analytic centers, we need to
develop some technical results to be used in the subsequent analysis.
We start with a measure of proximity to the analytic center.
Again, let $\Omega$ be a (bounded) polytope in $\Re^m$ defined by $n\ (>m)$
linear inequalities, i.e.,
\[\Omega=\{ y\in \IR^m: c-A^Ty\ge 0 \}.\]
Recall that for a point $y$ in the interior of $\Omega$, the potential function
\[\phi(y):=\sum_{j=1}^n\ln s_j\]
where
\[s=c-A^Ty,\]
and the max-potential of $\Omega$ is defined as
\[P(\Omega):=\max_{y\in\Omega}\phi(y).\]

Consider a normalized gradient vector of $\phi$ at $y$
\[\Delta s(y)=S^{-1}A^T(AS^{-2}A^T)^{-1}\nabla\phi(y)
=-S^{-1}A^T(AS^{-2}A^T)^{-1}AS^{-1}e\]
and
\[\delta(y)=\|\Delta s(y)\|=
\|S^{-1}A^T(AS^{-2}A^T)^{-1}AS^{-1}e\|,\]
or
\[\delta(y)^2=e^TS^{-1}A^T(AS^{-2}A^T)^{-1}AS^{-1}e.\]
Note that $AS^{-2}A^T$ is symmetric positive semi-definite. Thus, this quantity
 is
a norm of the gradient vector. Let
\[x(y)=S^{-1}(I-S^{-1}A^T(AS^{-2}A^T)^{-1}AS^{-1})e\]
we have
\[\Delta s(y)=Sx(y)-e\quad\mbox{and}\quad \delta(y)=\|Sx(y)-e\|.\]

Another measure would explicitly use the primal variable $x\ge 0$ and $Ax=0$,
the Lagrangean multiplier for $\Omega$, where $\Omega$ is usually called the
dual system. For a primal feasible $x$, a residual is defined as
\[\eta(x,y)=\|X(c-A^Ty)-e\|=\|Xs-e\|.\]
We now establish some interesting inequalities relating $\delta(y)$ to
 $\eta(x,y)$.
Some of these inequalities will be used in the subsequent analysis.
Most results of this lemma were proved in Gonzaga \cite{Gon} or
den Hertog et al \cite{dHRV}.

\begin{lemma}\label{lemma3:1} Let $(y,s)$ be an interior point in $\Omega$.
\pn
i$)$ If there is $x\ge 0$ with $Ax=0$ such that $\eta(x,y) < 1$ then
\[\delta(y) \le \eta(x,y);\]
Conversely, if $\delta(y)<1$ then there is $x\ge 0$ with $Ax=0$ such that
\[\eta(x,y)= \delta(y).\]
\pn
ii$)$ Let $\Delta (y)=(AS^{-2}A^T)^{-1}\nabla\phi(y)$ and let
$y^+=y+\Delta (y)$. Then
if $\delta(y) < 1$,
\[\delta(y^+)\le \delta(y)^2.\]
\pn
iii$)$ Let $\bar y$ be the analytic center of $\Omega$. Then,
if $\delta(y) < 1$,
\[\phi(\bar y)-\phi(y)\le {\delta(y)^2\over 1-\delta(y)^2}\]
or
\[P(\Omega)-\phi(y)\le {\delta(y)^2\over 1-\delta(y)^2}.\]
\pn
iv$)$ Let $\bar s=c-A^T\bar y$ where $\bar y$ is the analytic center of
 $\Omega$.
Then, if $\delta(y) < 1$,
\[\|S^{-1}\bar s-e\|\le {\delta(y)\over 1-\delta(y)}.\]
\end{lemma}

\noindent {\bf Proof}.

\pn
i) Given $(y,s)$ in the interior of $\Omega$, we can
verify that $\delta(y)$ is the minimal value and $x(y)$ is the minimal solution
of the least squares problem

\[
  \begin{array}{lll}
   & \mbox{minimize} &\|Sx-e\|\\
            & \mbox{subject to} &Ax=0.
  \end{array}
\]
Since $x$ in $\eta(x,y)$ is a feasible point for this problem, we must have
\[\delta(y)\le \eta(x,y).\]
Conversely, let $x=x(y)$. Then, we have $Ax=0$ and $\eta(x,y)=\delta(y)$.
Moreover, $x>0$ since $\delta(y)<1$.

\pn
ii) Note that from the proof of (i)
\[\delta(y^+)=\|S^+x(y^+)-e\|\le \|S^+x(y)-e\|.\]
But
\begin{eqnarray*}
  \|S^+x(y)-e\|^2
     & =&  \|(2S-S^2X(y))x(y)-e\|^2 \\
     & =  &\sum_{j=1}^n(s_jx(y)_j-1)^4\\
     &\le &(\sum_{j=1}^n(s_jx(y)_j-1)^2)^2\\
     & =  &\|Sx(y)-e\|^4\\
     & =  &\delta(y)^4.
\end{eqnarray*}

iii) Let $y^+$ be generated in (ii). Since $\phi$ is a concave function
\[\phi(y^+)-\phi(y)\le \nabla\phi(y)(y^+-y)=\delta(y)^2.\]
Consider the sequence generated by this process
with $y^0=y$ and $y^{k+1}=y^k+\Delta(y^k)$, then from (ii),
$y^k\rightarrow \bar y$ and from the above relation
\[\phi(y^{k+1})-\phi(y^k)\le \delta(y^k)^2.\]
Thus, for any $k\ge 1$ we have
\[\phi(y^k)-\phi(y^0)\le \sum_{j=1}^k\delta(y)^{2^j}\le
\sum_{j=1}^k(\delta(y)^2)^j\le {\delta(y)^2\over 1-\delta(y)^2}.\]

iv) Let $y^0=y$ and the sequence $\{y^k,s^k\}$ be generated by the process in
(iii). Then, we show by induction that
\[\|(S^0)^{-1}s^k-e\|\le \sum_{j=1}^{2^k-1}\delta(y)^j.\]
Obviously, this relation is true for $k=1$. Now assuming it is true for $k$.
Note that
\[s^{k+1}=s^k-S^{k}(S^kx(y^k)-e),\]
we have
\begin{eqnarray*}
\|(S^0)^{-1}(s^{k+1}-s^k)\|
   &= &  \|(S^0)^{-1}S^{k}(S^kx(y^k)-e)\|\\
   &\le& \|(S^0)^{-1}S^{k}\|\|S^kx(y^k)-e\|\\
   &\le &\left(\sum_{j=0}^{2^k-1}\delta(y)^j\right)\|S^kx(y^k)-e\|\\
   &\le &\left(\sum_{j=0}^{2^k-1}\delta(y)^j\right)\delta(y)^{2^k}.
\end{eqnarray*}
Thus,
\begin{eqnarray*}
\|(S^0)^{-1}s^{k+1}-e)\|
   &\le &\|(S^0)^{-1}s^{k}-e)\|+\|(S^0)^{-1}(s^{k+1}-s^k)\|\\
   &\le &\sum_{j=1}^{2^k-1}\delta(y)^j+
        \left(\sum_{j=0}^{2^k-1}\delta(y)^j\right)\delta(y)^{2^k}\\
   &= &\sum_{j=1}^{2^{k+1}-1}\delta(y)^j.
\end{eqnarray*}
This proves (iv). \QED

\newsection{Primal-dual Newton Procedure}
\label{priduN}
In this section, we briefly review the primal-dual Newton iteration for
finding the analytic center. Given an interior point $y\in \IR^m$ and a
primal feasible $x\in \IR^n$ satisfy
\begin{equation}\label{3:1}
\|Xs-e\|\le \eta<1,
\end{equation}
we can apply the primal-dual Newton method to generate a new iterate $x^+$ and
$(y^+,s^+)$ as follows.

Solve for $d_x$, $d_y$ and $d_s$ from the system of linear equations:
\begin{equation} \label{3:2}
  \begin{array}{rcl}
    S d_x + X d_s & = &  \frac{x^Ts}{n}e - X s, \\
    A d_x & = & 0,    \\
    A^T d_y + d_s & = & 0.
  \end{array}
\end{equation}
Then, let
\[x^+=x+d_x,\quad y^+=y+d_y,\quad s^+=s+d_s.\]

We have a lemma for the residual at $(x^+,y^+,s^+)$.

\begin{lemma}\label{lemma3:2}
Let $(x^+,y^+,s^+)$ be generated as above. Then,
\[\|X^+s^+-e\|\le {\sqrt{2}\eta^2\over 4(1-\eta)}.\]
\end{lemma}

\noindent{\bf Proof}. See Mizuno \cite{MIZUNO}.

\newsection{Max-Potential Reduction}\label{maxpot}

Now, we use an approximate center $y^k$ to generate a cut, where
$(y^k,s^k)$ is an interior point in $\Omega$ and
there is $x^k>0$ with $Ax^k=0$ such that
\begin{equation}
\label{eta}
\|X^ks^k-e\|\le \eta\end{equation}
for some $0<\eta<1$. Let us place a cut exactly at $y^k$, that is, we add a new
 inequality
$a^Ty\le a^Ty^k$ to $\Omega$, and consider the new set
\[\Omega^+=\{y: A^Ty\le c,\quad a^Ty\le a^Ty^k\}.\]
We remark that our definition of $\Omega^+$ is different from that of [7] which
 requires
the new inequality to be $a^Ty\le a^T y^k+\beta r$, for some $0<\beta<1$,
 where
 \[r=\sqrt{a^T(A(S^k)^{-2}A^T)^{-1}a}.\]
Thus, ``more" is cut away from $\Omega$ in the current definition of
$\Omega^+$. This deep cut was first developed by Nesterov in his cutting
plane method \cite{Nes1}.

We now prove a lemma resembling Theorem 2 of Ye \cite{Ye1}.
\begin{lemma}\label{potin}
Let $(\bar y,\bar s)$ be the analytic center of $\Omega$ and
let
\[\bar r=\sqrt{a^T(A\bar S^{-2}A^T)^{-1}a}.\]
Then
\[P(\Omega^+)\le P(\Omega)+\ln(\bar r)-\alpha\]
for some constant $\alpha$. Moreover, if $0<\eta<1/100$, then we have
 $\alpha>0$.

\end{lemma}

\noindent {\bf Proof}. Let $\bar y$ and $\bar y^+$ be the analytic centers for
$\Omega$ and $\Omega^+$, respectively.
Let $\bar s^+=c-A^T\bar y^+>0$ and $\bar s^+_{n+1}=a^Ty^k-a^T\bar y^+$.
Then we have
\begin{eqnarray*}
\bar s^+_{n+1}
      &=& a^T(y^k - \bar y^+)\\
      &= &a^T(A\bar S^{-2}A^T)^{-1}(A\bar S^{-2}A^T)(y^k -\bar y^+)\\
      &= &a^T(A\bar S^{-2}A^T)^{-1}A\bar S^{-2}(A^Ty^k - A^T\bar y^+)\\
      &= &a^T(A\bar S^{-2}A^T)^{-1}A\bar S^{-2}(-c+A^Ty^k +c- A^T\bar y^+)\\
      &= & a^T(A\bar S^{-2}A^T)^{-1}A\bar S^{-2}(\bar s^+-s^k)\\
      &= &a^T(A\bar S^{-2}A^T)^{-1}A\bar S^{-1}(\bar S^{-1}\bar s^+-
         \bar S^{-1}s^k)\\
      &\le &\|a^T(A\bar S^{-2}A^T)^{-1}A\bar S^{-1}\|
         \|\bar S^{-1}\bar s^+-\bar S^{-1}s^k\|\\
      &=  & \bar r\|\bar S^{-1}\bar s^+-e+e-\bar S^{-1}s^k\|\\
      &\le &\bar r(\|\bar S^{-1}\bar s^+-e\|+\|e-\bar S^{-1}s^k\|)\\
      &\le &\bar r(\|\bar S^{-1}\bar s^+-e\|+{\eta\over 1-2\eta})
\quad (\mbox{from Lemma \ref{lemma3:1}}).
\end{eqnarray*}
Thus,
\begin{eqnarray*}
{\exp {P(\Omega^+)}\over \bar r\exp {P(\Omega)}}
    &=   &{\bar s^+_{n+1}\over \bar r}\prod_{j=1}^n{\bar s^+_j\over \bar s_j}\\
    &\le &(\|\bar S^{-1}\bar s^+-e\|+{\eta\over 1-2\eta})
         \prod_{j=1}^n{\bar s^+_j\over \bar s_j}.
\end{eqnarray*}
Note that we still have
\[e^T\bar S^{-1}\bar s^+=n.\]
Thus, from the proof of Theorem 2 of \cite{Ye1}
\[(\|\bar S^{-1}\bar s^+-e\|+{\eta\over 1-2\eta})
         \prod_{j=1}^n{\bar s^+_j\over \bar s_j}\le
  4\exp({8\eta-3\over 2(1-2\eta)}).\]
Thus,
\[P(\Omega^+)-P(\Omega) \le \ln(\bar r)+\ln(4)+{8\eta-3\over 2(1-2\eta)}.\]
Let
\[\alpha=-\ln(4)-{8\eta-3\over 2(1-2\eta)}.\]
Let $\eta=1/100$. Then we must have $\alpha>0$.
Thus, we have desired result. \QED

\newsection{Update to a New Approximate Center}\label{update}

In this section, we show how to construct a pair $(x,y,s)$ from
$(x^k,y^k,s^k)$, such that
$(A,a)x=0$ with $x>0$, $(y,s)$ is in the interior of $\Omega^+$, and
\[\|Xs-e\|<\gamma < 1.\]
Suppose a pair $(x^k,y^k,s^k)$ is given which satisfies (\ref{eta}),
we use the primal-dual scaling for the construction of $(x,y,s)$.
Let
\begin{eqnarray*}
r^k&=&\sqrt{a^T(A(X^k)^{2}A^T)^{-1}a},\\
\Delta y&=& -(\beta/r^k)(A(X^k)^{2}A^T)^{-1}a,\\
\Delta s&=& (\beta/r^k)A^T(A(X^k)^{2}A^T)^{-1}a,\\
\Delta x&=&-(\beta/r^k)(X^k)^2A^T(A(X^k)^2A^T)^{-1}a.
\end{eqnarray*}
Then we set
\[y=y^k+\Delta y\]
and
\[x=
\left[
\begin{array}{c}
x^k+\Delta x \\
\beta/r^k
\end{array}
\right]=
\left[
\begin{array}{c}
x^k-(\beta/r^k)(X^k)^2A^T(A(X^k)^2A^T)^{-1}a \\
\beta/r^k
\end{array}
\right].\]
It can be readily verified that
\[s=\left[\begin{array}{c} c-A^T(y^k+\Delta y)\\ a^Ty^k-a^T(y^k+\Delta y)
\end{array}\right]=
\left[
\begin{array}{c}
s^k+\Delta s \\
\beta r^k
\end{array}
\right]=
\left[
\begin{array}{c}
s^k+(\beta/r^k)A^T(A(X^k)^2A^T)^{-1}a \\
\beta r^k
\end{array}
\right]\]
First, we have
\[(A,a)x=Ax^k-(\beta/r^k)a+(\beta/r^k)a=0.\]
Second, we have
\[s^k+(\beta/r^k)A^T(A(X^k)^{2}A^T)^{-1}a=
  (X^k)^{-1}(X^kS^ke+p^k)\]
and
\[x^k-(\beta/r^k)(X^k)^{2}A^T(A(X^k)^{2}A^T)^{-1}a=
  X^k(e-p^k),\]
where
\[p^k=(\beta/r^k)X^kA^T(A(X^k)^{2}A^T)^{-1}a.\]
Note that we have
\begin{equation}\label{beta}
\|p^k\|=\beta.
\end{equation}
On the other hand, we have
\[x^k_js^k_j\ge 1-\eta.\]
Thus, if we select $\eta$ and $\beta$ such that
\begin{equation} \label{bound}
1-\eta-\beta>0,\end{equation}
then both
\[s=
\left[
\begin{array}{c}
(X^k)^{-1}(X^kS^ke+p^k)\\
\beta r^k
\end{array}
\right]>0\]
and
\[x=
\left[
\begin{array}{c}
X^k(e-p^k)\\
\beta/r^k
\end{array}
\right]>0.\]
A simple calculation yields
\[Xs-e=
\left[
\begin{array}{c}
X^ks^k-e \\ 0
\end{array}
\right]
-\left[
\begin{array}{c}
 -(p^k)^2\\
1-\beta^2
\end{array}
\right]
-\left[
\begin{array}{c}
(X^kS^k-I) p^k\\
0
\end{array}
\right]\]
where the vector
\[(p^k)^2=((p^k_1)^2,(p^k_2)^2,...(p^k_n)^2)^T.\]
Therefore, we have
\begin{eqnarray*}
\|Xs-e\| &\le
 &\|X^ks^k-e\|+\sqrt{\|(p^k)^2\|^2+(1-\beta^2)^2}+\|X^ks^k-e\|\|p^k\|\\
&  \le & \eta+\sqrt{\beta^4+(1-\beta^2)^2}+\eta \beta
\end{eqnarray*}
where the last step follows from (\ref{eta}) and (\ref{beta}).
Let $\beta=1/\sqrt{2}$ and $\eta=0.15$, then
\[\|Xs-e\|\le \gamma=0.15+1/\sqrt{2}+0.15/\sqrt{2}<1.\]
Or, we can let
\[\eta=1/100,\quad\mbox{and have}\quad\gamma:=1/100+1.01/\sqrt{2}<1.\]
Furthermore, it can also be easily verified that (\ref{bound}) holds.

Hence, using this $(x,y,s)$ as a starting pair, we can apply the primal-dual
Newton procedure of Section 2 to generate a pair $(x^{k+1},s^{k+1})$ such that
\begin{eqnarray*}
(A,a)x^{k+1}&=&0,\quad x^{k+1}>0,\\
s^{k+1}&=&(c^T,a^Ty^k)^T-(A,a)^Ty^{k+1}>0
\end{eqnarray*}
and
\[\|X^{k+1}s^{k+1}-e\|\le \eta.\]
By Lemma \ref{lemma3:2} and the above given values of $\gamma$ and
$\eta$, this can be accomplished in $4$ primal-dual Newton steps.
This column generation process can be repeated, and from Lemma \ref{potin}
the nested sequence of polyhedral sets $\Omega^k$ generated by the algorithm
satisfies
\begin{equation}\label{key}
P(\Omega^{k+1})\le P(\Omega^k)+\ln(\bar r^k)-\alpha\end{equation}
where $\alpha$ is some constant,
\[\bar r^k=\sqrt{a_{k+1}^T(A(\bar S^k)^{-2}A^T)^{-1}a_{k+1}}\]
$(\bar y^k,\bar s^k)$ is the analytic center of $\Omega^k$, and
$a_{k+1}$ is the cut generated at the $k$th iteration.
Note that $(\bar y^k,\bar s^k)$ is solely used for analysis, and the
algorithm does not need any knowledge of $(\bar y^k,\bar s^k)$.

We remark that, instead of using the primal-dual Newton iterations of Section 2,
one can use the updating scheme prescribed by Lemma 2.1 (ii) to
obtain an approximate analytic center. Such updating
procedure works with the dual variables only.


\newsection{The Cutting Plane Method from Analytic Centers:
Convergence and Complexity}

The analysis  of Goffin et al. \cite{GLY} relies on two things: (i) a bound
identical
to (\ref{key}); (ii) the assumption that the original feasibility problem has
an interior
point.
Using the analysis above, we show that
the technical results of  \cite{GLY}
hold without much change for the algorithm using approximate centers.
Thus, we derive the identical
iteration complexity for the algorithm, and each iteration uses a constant
number of primal-dual Newton steps. We extend here the proof of \cite{GLY}
for completeness.



Let the solution set $\Gamma$ be contained in
$\Omega^0=\{y\in\IR^m:0\leq y\leq e\}$,
and $\interior(\Gamma)$ 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(\Gamma)$
or generates
a separating hyperplane
$ \{y:a^Ty\leq a^T \bar y\}\supset \Gamma$, with $\Vert a\Vert =1$
being assumed.

The primal-dual column
generation -- or cutting plane -- algorithm
\cite{Sonn,Ghv,Ye1} from approximate  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\]
\[
s^0=c^0-(A^0)^Ty^0=\frac{1}{2}e\in\IR^{2m},\nn
\]
\[ x^0=2e\in\IR^{2m}\nn\]
and
\[k=1.\nn\]
\item{\bf Step 1}

Compute $(y^k,s^k,x^k)$ with $y^k$
an $\eta$-approximate analytic center of
$\Omega^k=\{y\in\IR^m:c^k-(A^k)^Ty\geq 0\}$, using the
primal-dual method of section \ref{priduN} with the
updating scheme of section \ref{update} starting at
$(y^{k-1},s^{k-1},x^{k-1})$,  an $\eta$-approximate "primal-dual"
center of $\Omega^{k-1}$.

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

If yes, stop;
otherwise generate a hyperplane
$ \{y:a^T_{k+1}y\leq a^T_{k+1}y^k\} \supset \Gamma$
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}


Let the potential function computed at
the {\bf exact} analytic center $\bar y^k$ be:
\[ P(\Omega^k)=\sum_{j=1}^{2m+k}\ln(c^k-(A^k)^T\bar y^k)_j.\nn\]
Clearly the following relations hold, provided that termination has not
occurred:

\begin{enumerate}
\item
\begin{equation}
 \Gamma\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(\bar r^k)^2
-\alpha {\ \ \rm \ (by \ Lemma \ \ref{potin})}
\label{assum2}
\end{equation}

where
\[
(\bar r^k)^2=a_{k+1}^T(A^k(\bar S^k)^{-2}(A^k)^T)^{-1}a_{k+1}
\nn\]
and
\[
\bar s^k=c^k-(A^k)^T\bar y^k,\; \bar S^k={\rm\ diag}(\bar s^k).
\nn\]
\end{enumerate}


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

\proof

{From} \ref{assum1}, $\Gamma\subset \Omega^k$. Thus
$\Omega^k$ contains a full
dimensional ball with $\epsilon$ radius.
Let the center of this 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 \bar 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 $\bar 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 See \cite{GLY}.
\QED

Lemma \ref{lobpot} indicates that in order
to prove finite convergence,
one needs
to show that $P(\Omega^k)$ grows more slowly than
$2m+k$. By Lemma \ref{potin},
this means finding upper bounds on $\bar r^k$. In the following Lemma
this is achieved by using a construction due to Nesterov \cite{Nes1}
which uses a matrix $B^k$
which is a lower bound on \[A^k(\bar S^k)^{-2}(A^k)^T,\]
and which is simple enough to handle.

\begin{lemma}
\label{AB}

Let  $s=c^k-(A^k)^Ty$ for any $y\in\Omega^0$ and $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

\begin{lemma}\label{omr}

Let  $\bar s^k=c^k-(A^k)^T\bar y^k$ be the
slacks at the analytic center $\bar y^k$ of $\Omega^k$ and
$(\omega^k)^2=a_{k+1}^T(B^k)^{-1}a_{k+1}$, then
\begin{equation}
(\omega^k)^2\geq
a_{k+1}^T(A^k(\bar S^k)^{-2}(A^k)^T)^{-1}a_{k+1}=(\bar r^k)^2.
\end{equation}
\end{lemma}
\begin{proof}
Using Lemma \ref{AB}
\begin{equation}
(\omega^k)^2=a_{k+1}^T(B^k)^{-1}a_{k+1}\geq
a_{k+1}^T(A^k(\bar S^k)^{-2}(A^k)^T)^{-1}a_{k+1}=(\bar r^k)^2.
\end{equation}
\QED
\end{proof}


This implies that upper bounds on the series of $(\omega^k)^2$ will
lead to upper bounds on the series $(\bar r^k)^2$.

The following lemma adapts a result of Nesterov \cite{Nes1} to the
technical hypotheses of this paper.

\begin{lemma}\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}
The column generation scheme  stops with a feasible solution as soon as
$k$ satisfies:
\[
\frac{\epsilon^2}{m}\geq
\frac{
\frac{1}{2}+2m\ln(1+\frac{k+1}{8m^2})}
{2m+k+1}e^{-2\alpha\frac{k+1}{k+1+2m}}.
\]
\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(\bar r^j)^2
-(k+1)\alpha\nn\\
&=&2m\ln\frac{1}{2}
+\frac{1}{2}\sum_{j=0}^k\ln(\bar r^j)^2
-(k+1)\alpha.\nn
\end{eqnarray}
Thus
\begin{eqnarray}
\ln\epsilon+\frac{k+1}{2m+k+1}\alpha
&\leq&\frac{1}{2(2m+k+1)}
\left[2m\ln\frac{1}{4}+\sum_{j=0}^k\ln(\bar r^j)^2\right]\nn\\
&\leq&\frac{1}{2}\ln
\frac
{2m\frac{1}{4}+\sum_{j=0}^k  (\bar 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 \  Lemma\ \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}e^{-2\alpha\frac{k+1}{k+1+2m}}.
\]
\QED

Theorem \ref{nice} implies that the complexity of the
column generation scheme, counted by the calls to the oracle
is $O^*(\frac{m^2}{\epsilon^2})$; the notation $O^*$ means that
lower order terms are ignored.




\begin{theorem}\label{verynice}
The complexity of the approximate analytic center algorithm,
which uses the
updating scheme of section \ref{update}, and the primal-dual method of
section \ref{priduN}, measured by the number of Newton steps or
by the number of factorizations, is, for
appropriate values of $\eta$ and $\beta$ (say $\eta=1/100$ and
$\beta=1/\sqrt{2}$),
\[O^*(\frac{m^2}{\epsilon^2}).\]
\end{theorem}
\proof
For the prescribed values of $\eta$ and $\beta$, the number of
primal-dual Newton steps is at most 4. One additional
factorization is required for the updating procedure.
\QED

The largest value of $\eta$ that guarantees $\alpha>0$ and
$\gamma^{16}\le\eta$ (so that 4 primal-dual steps
are enough to recenter) is about $\eta=.09$ with $\beta=.691$.

\begin{thebibliography}{99}

\bibitem{dHRV}
D. den Hertog, C.Roos and J. Ph. Vial,
``A complexity reduction for the long-step path-following algorithm for
linear programming",
{\it SIAM  Journal on
Optimization} {\bf  2} (1992) 71--87.


\bibitem{GLY}
J.-L. Goffin, Z. Luo, and Y. Ye, ``On the complexity of a column generation
algorithm for convex or quasiconvex feasibility problems",
Working Paper 93-06-07, Faculty of Management, McGill University, Montreal,
Canada, June 1993, to appear in "Large Scale Optimization: State of
the Art", W.W. Hager, D.W. Hearn and P.M. Pardalos, editors,
Kluwer Academic Publishers.

\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{Gon}
C. C. Gonzaga, ``Path-following methods for linear programming",
{\it SIAM Review} {\bf 34} (1992) 167-224.

\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{Mitodd}
J.~E. Mitchell and M.~J. Todd,
\newblock ``Solving combinatorial
optimization problems using Karmarkar's algorithm ''
\newblock {\it Mathematical Programming} {\bf 56} (1992) 245--284.

\bibitem{MIZUNO}
S. Mizuno, ``A new polynomial time method for a linear complementarity problem",
Technical Report 16, Department of IE and Management, Tokyo Institute of
Technology, Tokyo, Japan, Feb. 1989.

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

\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{Ye1}
Y.~Ye, ``A potential reduction algorithm allowing column generation",
{\it SIAM  Journal on
Optimization} {\bf  2} (1992) 7--20.


\end{thebibliography}

\end{document}


