Multiple Cuts in the Analytic Center Cutting Plane Method.
We analyze the multiple cut generation scheme in the analytic center cutting plane method. We propose an optimal primal and dual updating direction when the cuts are central. The direction is optimal in the sense that it maximizes the product of the new dual slacks and of the new primal variables within the trust regions defined by Dikin's primal and dual ellipsoids. The new primal and dual directions use the variance-covariance matrix of the normals to the new cuts in the metric given by Dikin's ellipsoid.We prove that the recovery of a new analytic center from the optimal restoration direction can be done in O(plog (p+1)) damped Newton steps, where p is the number of new cuts added by the oracle, which may vary with the iteration. The results and the proofs are independent of the specific scaling matrix---primal, dual, or primal-dual---that is used in the computations.The computation of the optimal direction uses Newton's method applied to a self-concordant function of p variables.The convergence result of [Ye,  Math. Programming, 78 (1997), pp. 85--104] holds here also: the algorithm stops after $O^*(\frac{\bar p^2n^2}{\varepsilon^2})$ cutting planes have been generated, where $\bar p$ is the maximum number of cuts generated at any given iteration.
Introduction
The analytic center cutting plane (ACCPM) algorithm [5, 19] is an efficient
algorithm in practice [2, 4]. The complexity of related algorithms was given in
[1, 13], and subsequently in [6]. Extensions to deep cuts were given in [7] and
to very deep cuts in [8]. The method studied in [8] corresponds to the practical
implementation of ACCPM [11] with a single cut.
In practice, it often occurs that the oracle in the cutting plane scheme generates
multiple cuts. The papers [12, 20, 17] show that it is possible to handle
several cuts at a time provided they are central [20] or moderately shallow [12].
Although these analyses show how one can recover feasibility after introducing
multiple cuts, there is no clear argument as to the choice of a feasibility restoration
direction. Intuitive, but well justified, arguments about how to introduce
multiple cuts were given in [2] in the context of a primal projective algorithm
and two cuts (one shallow, one deep) and in [10] with an infeasible primal-dual
approach to the introduction of several cuts in general position.
The case of two central cuts was analyzed in [9]. It was shown that there exist
explicit primal and dual directions which allow a best move towards primal and
dual feasibility. An argument using the primal, dual and primal-dual potentials
at this new optimal primal and dual point proves that O(1) damped Newton
steps are enough to recover centrality. The updating direction depends on the
cosine in the metric of Dikin's ellipsoid of the normals to the cuts.
In this paper, we analyze the multiple cut generation scheme in the analytic
center cutting plane method. We propose an optimal updating direction when
the cuts are central. The direction is optimal in the sense that it maximizes the
product of the new slacks within the trust region defined by Dikin's ellipsoid.
The new primal and dual directions use the variance-covariance matrix of the
normals to the new cuts in the metric given by Dikin's ellipsoid.
We prove that the recovery of a new analytic center from the optimal restoration
point can be done in O(p log(p+1)) damped Newton steps, where p is the number
of new cuts added by the oracle. The results and the proofs are independent of
the specific scaling matrix -primal, dual or primal-dual- that is used in the
computations.
The computation of the optimal direction uses Newton's method applied to a
self-concordant function of p variables. This could be very advantageous in
practice if the number of cuts p is a small multiple of n, the dimension of the
space.
The convergence result of [20] holds here also: the algorithm stops after O
cutting planes have been generated.
Analytic center cutting plane method
2.1 Cutting planes
The problem of interest is that of finding a point in a convex set C ae IR n . We
make the following assumptions.
Assumption 2.1 The set C is convex, contains a ball of radius " ? 0 and is
contained in the cube 0 - y - e.
Assumption 2.2 The set C is described by an oracle. That is, the oracle either
confirms that y 2 C, or answers at least one cutting plane that contains C and
does not contain y in its interior.
A cut at -
takes the form
a T y - a T -
fl:
the cut is deep; if -
the cut is shallow; if - the cut passes
through -
y, and is thus a central cut.
The algorithm may generate multiple cuts at a time. They take the form
a T
We define the matrix B by
Assumption 2.3 All the cutting planes generated have been scaled so that
We also assume that the cuts are central, that is -
A cutting plane algorithm constructs a sequence of query points fy k g. The
answers of the oracle to the queries, together with the cube 0 - y - e, define a
polyhedral outer approximation
of C. Since A contains the identity matrix associated with the cube, A has
full row rank. Therefore there is a one-to-one correspondence between points
and the slack y, leading to the equivalent definition of FD
The number of columns in A is denoted as m and is equal to 2n plus the number
of cutting planes generated until the k th iteration.
The analytic center cutting plane method chooses as a query point an approximate
analytic center of FD .
2.2 Analytic center
The analytic center of FD is the unique point maximizing the dual potential
log s i
with formally introduce the optimization problem
and the associated first order optimality conditions
where x is a vector in R m . The notation xs indicates the Hadamard or componentwise
product of the two vectors x and s.
The analytic center can alternatively be defined as the optimal solution of
where
log x i
denotes the primal potential. One easily checks that problem (2) shares with
(1) the same first order optimality conditions.
At this stage it is convenient to introduce the primal-dual potential
and an associated duality relationship.
Lemma 2.4 Let x 2 intF P and s 2 intF D . Then 'PD (x; s) - \Gammam; with
equality if and only if
Proof
Consider the simple inequality
log
with equality if and only if Apply (3) with
By summing the resulting inequalities, one gets
log
log
with equality if and only if xs = e. Therefore,
with equality if and only if
Finally, we define approximate centers by relaxing the condition in the
first order optimality conditions. Formally, any solution (x; s) of
defines a pair of '-approximate centers, or '-centers in short.
2.3 Analytic center cutting plane method
ACCPM can be shortly stated as follows.
Initialization Let F 0
fy eg be the unit cube and y
e be its
center. The centering parameter is
Basic Step y k is a '-center of F k
the total number
hyperplanes describing F k
D .
1. The oracle returns the cuts amk+j , k , at y k .
2. Update
g.
3. Compute a '-center of F k+1
D .
The computation of a new '-center after adding new cuts will be discussed in a
further section.
3 Some useful properties
The literature on interior point methods essentially proposes three approaches
for computing analytic centers. All of them are based on Newton's method. The
primal (resp. dual) Newton direction is initiated at an interior primal (resp.
dual) feasible point; it involves the scaling matrix
(We recall the standard notation X which denotes the diagonal matrix diag(x).)
The primal-dual direction is initiated at an interior primal-dual feasible pair,
involves the scaling matrix
Let us shortly recall the formulas. The primal direction is given by
xp(x) with
The dual direction is given by \Deltas = sq(s) with
Finally the primal dual direction is
\Deltas and
3.1 Properties of the Newton step
There are two basic properties, a local one in the vicinity of the analytic center,
and a global one. Since the results are well-known we state them without proofs.
Missing proofs can be found in the books [18] or [21].
Let us start with the local properties. Proximity to analytic center is measured
with the quantity sxk. In this definition, either
Note that if
and case). The Newton step defines a pair
Theorem 3.1 Assume
3 . Let be the point resulting
from a Newton step (primal, dual, or primal-dual). Then,
intF D \Theta intF P .
In the primal and dual cases, the theorem holds with any 0 ! ' ! 1.
One can derive from the above theorem a useful corollary that yields lower
bounds on the potentials near the analytic center. Let be the pair of
exact analytic centers. Denote ' c
Corollary 3.2 Assume (5)-(7) at (x; s). Then
1. ' c
2. ' c
3. \Gammam - 'PD (x; s) - \Gammam
Let us now consider the global properties of a damped Newton step. The properties
are consequences of the well-known inequality on the logarithm function
Lemma 3.3 Let h be any point in R m such that khk ! 1. Then,
The main result bounds the variation of the potentials after a damped Newton
step.
Theorem 3.4 Assume
s+ff\Deltas. (\Deltax and \Deltas may be the primal, dual or primal-dual directions.) Then,
there exists a step size ff ? 0 and absolute constants oe P , oe D and oe PD such that
1. 'P
2. 'D (x(ff)) - 'D
3. 'PD (x(ff);
In the primal and dual cases the constants are oe '). The
above result allows to design a potential increase algorithm based on damped
Newton steps. The convergence estimate is given by the following theorem.
Theorem 3.5 Let x potential increase algorithm
(primal, dual, primal-dual) produces an interior feasible pair such that
a number of iterations not greater than
oe
with or oe PD , depending on which approach (primal, dual or primal-
dual) is taken.
3.2 Dikin's ellipsoids
. From the observation that x \Deltax such that
1, we can define an ellipsoidal neighborhood of x that is entirely
contained in FP . Formally,
We shall be particularly concerned with ellipsoids around a '-center.
We can extend the definition of Dikin ellipsoid to include a different scaling.
Lemma 3.6 Let (x; s) be a pair of '-centers.
1. If
2. If
Proof
For the dual scaling the proof follows from
and
For the primal-dual scaling the proof follows from
and
We can similarly define Dikin's ellipsoids in the dual. Let s 2 intF D . The dual
ellipsoid is
The extension of Dikin's ellipsoid to a different scaling at a '-center is given by
Lemma 3.7 1. If
2. If
The proof is the same as for Lemma 3.6.
It is well-known that an homothety of Dikin's ellipsoid contains the feasible set.
We shall use this property in the restricted context of the set FD .
Lemma 3.8 Let (x; s) be a '-centered feasible pair. Then
ae
oe
Proof
s) be a '-centered feasible pair and ~
point of FD . Since are orthogonal,
Since ~
one has x T s -
thus obtain the weak bound
Finally, from kD(~s \Gamma s)k -
Hence,
ae
oe
4 Multiple central cuts
We assume now that a '-center (x; s; y) has been computed, i.e.,
The cuts are
a T
We define
The new cuts lead to two new sets:
e
or
e
and
e
We shall use the notation
so
After adding the cuts, one has
~
FD
and
~
Let us introduce the notation
The primal and dual potentials at the new points (-x; fi) and (-s; fl) are:
~
log -
log
log
and
~
log -
log
log
The points lie on the boundary of the primal and dual sets respectively. To
recover the new analytic center, one has to increase the components fi and fl.
Since the terms
log fi i and
log fl i are dominant near
maximizing those terms while limiting the variation on 'P and 'D is likely to
produce a good step towards the solution.
This approach requires the knowledge of the level sets of the potential, something
that we don't have, but that can be approximated by Dikin's ellipsoids.
Therefore, we are interested in solving the following problems
log
and
log
\Deltay
Here D is one of the scaling matrices X
depending whether the
computations are done with the primal, the dual or the primal-dual algorithm.
Let show here that the above problems are well-defined and have a finite optimum

Lemma 4.1 Under Assumptions 2.1 and 2.2, Problems (11) and (12) are well
defined and have a finite optimum that is uniquely defined by the first order
optimality conditions.
Proof Both problems have a strictly concave objective. Their optimum, if it
exists, is unique in fi (resp., fl).
By Assumptions 2.1 and 2.2, there exists a -
\Deltay such that B T -
Problem (12) is well-defined. Since \Deltay is bounded, fl is bounded and the
feasible set is compact. Since the objective tends to \Gamma1 close to the boundary,
the problem has a finite solution that is uniquely defined by the set of first order
optimality conditions.
To show that Problem (11) is also well-defined, we note that the equation A\Deltax+
has a solution for any fi ? 0 since A has full row rank. Let us show
that the feasible set is bounded. Indeed, let fi - 0 and
\Deltay
Recalling that A has full row rank,
we conclude from A\Deltax
fi is bounded, since \Deltax is bounded by
Problem (11) is thus
well-defined and has a finite optimum.
The solutions of Problems (11) and (12) define the primal dual pair of rays
fffiA
and
\Deltay
ffflA
~
FP and ~ s(ff) 2 int ~
The following positive semidefinite matrix
plays a fundamental role in the analysis. V can be interpreted as variance-covariance
matrix between the vectors (a m+j in the metric induced
by the matrix (AD 2 A
Theorem 4.2 The solution of Problems (11) and (12) is given by
and
with fi defined as the unique solution of
log
and
Proof Let - 2 R n and oe 2 be the multipliers associated with the constraints of
Problem (11). The optimality conditions are
?From the definition of \Deltax, one immediately sees that A\Deltax Letting
This proves the second relation. To prove the first relation, we shall use the
optimality condition for Problem (13). However, we must check first that (13)
has a bounded optimum. In Lemma 4.1 we proved that
nonegative solution. Thus, for all fi - 0, fi 6= 0, one has
This proves that the objective \Gamma p
log fi i is bounded above and Problem
has a unique optimum.
The optimality condition for Problem (13) is
Replacing fi \Gamma1 by pV fi we get the identity
It remains to check that
and
Let us now consider Problem (12). The optimality conditions are
\Deltay
are the multipliers associated with the two constraints

We want to show that are the optimal multipliers, where fi
is the optimal solution of Problem (13). Solving for \Deltay, one gets:
Now
Remembering the optimality condition for fi, one may replace
thus check that the first optimality condition holds.
Finally,
\Deltay
proves that with our choice of multipliers, the last optimality condition also
holds.
Remark 4.1 If V is nonsingular, fl is also the unique solution of
log
We can now give an explicit formula for the restoration direction. Noting that
we have the new primal-dual pair
~
and
~
Remark 4.2 We note a significant dissymmetry between the primal and dual
directions:
1. any positive value of fi, say primal feasible direction
2. but fi ? 0 does not guarantee
then taking a feasible dual direction.
Different stepsizes (ff could be used in the primal and dual space.
Note that, by construction,
D\Deltas. At the optimum direction, one has
The computation of fi requires solving the nonlinear optimization problem (13).
Since the function F
log
self-concordant, it can easily
be minimized by classical Newton schemes. We postpone to a later section the
discussion on the complexity estimate for getting approximate solutions.
For the sake of a simpler presentation we shall assume in our analysis of ACCPM
that the minimizers are exact. However, this is not the case in practice and we
must be concerned with the impact of errors on fi and fl on the performance
of ACCPM. This discussion is also postponed to a later section. Below, we
sketch the result that enables an easy extension of our analysis of ACCPM with
multiple cuts in the case of inexact computations of fi and fl.
The convergence analysis of section 5 relies on the following properties:
e:
If we can guarantee that the solutions satisfy pfifl - e and 1
then the convergence result on ACCPM is essentially unaffected, while
the proofs need only minor adjustments.
We give here a theorem that stipulates the condition that must be met by fi and
fl to carry the analysis with inexact minimizers. In a later section we shall show
that classical interior point schemes make it possible to meet the condition.
Theorem 4.3 Assume fi ? 0 and kpfi(V fi) \Gamma ek - j. Let
and
In particular,
Proof
The first set of inequalities follows directly from the assumption and the definition
of fl. These inequalities also imply that
Multiplying these inequalities by e T one gets
5 Convergence analysis
We now assume that (x; s) is a pair of '-centers and that \Deltax and \Deltas are
computed as in Section 4 with fi and fl being the exact minimizers of problems
and (14). We assume that the computations are done with either the
primal, the dual of the primal-dual scaling.
Lemma 5.1 Independently of the specific scaling matrix D (primal, dual or
primal-dual), one has, for any ff
Proof
By construction
1. From Lemma 3.6, for any primal,
dual or primal-dual scaling D, we have
The proof is the same in the dual case.
Remark 5.1 The above result can be sharpened by considering separately the
three different scaling matrices D. However, we prefer the weaker result since
it allows a single formulation for the three cases.
Lemma 5.2 The following inequalities hold:
and
je
Proof
?From \GammaA\Deltax, one has
Thus,
To prove the second statement, we note that x T
je
In view of the above lemmas, we can bound the potentials e
'P and e
'D at the
new pair of points (~x(ff); ~ s(ff)).
Lemma 5.3 For any 0 ! ff the new potentials satisfy
e
log
e
log
and
e
Proof
Let us prove first the inequality on the primal potential. At the updated point
~
x(ff) the potential is
e
log x
log
log x
log
log
1. We can apply Lemma 3.3 to get
Then, by Lemma 5.2
ffe
decreasing, we can bound khP k
e
log
Let us prove now the dual case. We have
e
log s
log
log
\Deltas. By Lemma 5.1 khD k ! 1. We can apply Lemma 3.3 to get
Since by Lemma 5.2
we obtain, by putting the inequalities together, the same result as in the primal
case
e
log
To conclude the proof of the theorem, we just sum the inequalities on ~
'P and
~
'D and use
e to get
e
5.1 Recovering the new analytic center
Theorem 5.4 The number of Newton steps to compute the updated '-analytic
center is bounded by
oe
where
and, depending on the Newton scheme,
Proof
To bound the number of Newton steps, we compute the optimality gap
for the sum of the primal and dual potentials. On the one hand,
~
On the other hand, we can write
e
Finally,
Hence
e
Thus
Using theorem 3.4 and the above bound on the potential variation we conclude
the proof of the theorem.
5.2 Convergence of ACCPM with multiple cuts
The next lemma is a first step on bounding the number of calls to the oracle.
Theorem 5.5 For all
~
log
with
Proof
The first inequality uses ~
'P (~x(ff)), the duality on potential and Lemma
2.4 to yield
log
We now need to deal with the contribution of the new variables
log
Since fi solves (13), we have fi T V
log
f
log
log
for any arbitrary fi 0 .
Let us define the vector - by
a T
Note that - while the off-diagonal terms of V are
The off-diagonal elements
Those properties are typical of a variance-covariance matrix. Let us choose
Then
The correlation matrix: all its coefficient
are bounded in absolute value by 1, and
Thus
log
log
log
log
Using corollary 3.2 we have
Putting together (21), (22) and (23) yields
~
ff
ff
log
The bound
ff
can be analyzed by selecting, somewhat arbitrarily,
guaranteeing
ff
which is exactly the same result as in [20], but with a rather different derivation,
as we show that this inequality is actually achieved at the iterate obtained by
the restoration step.
Remark 5.2 If the p cuts generated are identical, then the correlation matrix
R is the rank-one matrix ee T . Otherwise for the optimal fi
log fi
log
may be significantly greater than 0 and speed the convergence in practice, even
though this does not appear to affect the worst case complexity bound.
5.3 Convergence of ACCPM
The convergence analysis uses the proof given in [20], for the case of multiple
cuts.
Denote
and let P k be the same value after k calls to the oracle, that is, after adding
denotes the number of cuts added at iteration
j. By Theorem 5.5 and the observation (24) the following inequality holds
log
Theorem 10 of [20] can be used here, with p - n denotes the maximum number
of cuts generated by any call to the oracle.
Theorem 5.6 The algorithm stops with a solution as soon as k satisfies:
Furthermore the number of damped Newton steps per call to the oracle is O(p log(p+
1)). The number of cutting planes generated is at most O
The assumption that p - n is not required in the proof of [20], and in fact
would still lead to O
cutting planes (this would only impact
the constant).
6 Computing the optimal direction of restora-
tion
The restoration direction requires the solution of the concave problem
log
We note that in the computation of the restoration direction a significant absence
of symmetry occurs: it is easy to give a feasible value for fi, say
or
that gives a feasible solution to the problem of finding a feasible
direction, but, in general, this is not the case for the dual side.
If V is invertible, then the dual direction could also be computed by maximizing
log
1 The notation O   indicates that lower order terms are ignored.
A good starting value for fl could also be given, say
or
, with - 2
D being the diagonal of V \Gamma1 .
The following bounds on F (fi) will be useful in the computation of complexity
estimate of a Newton method to solve (13).
Theorem 6.1 For
log
and
Proof
The inequality on F (fi 0 ) was derived in the proof of theorem 5.5. (See (22).)
Let us construct an upper bound on F (fi   ) where fi   denotes the optimal solution
of problem (13), and fl  . From the optimality condition
log
log(fi
Hence,
F (fi
log
By Lemma 3.8, an homothety of Dikin's ellipsoid contains the current set of
localization, i.e.,
ae
oe
By assumption (2.1) and the fact that the algorithm has not terminated, a
sphere of radius " is contained in FD . Hence,
contains a sphere of radius "(1\Gamma')
(m+1)(1+') . Denoting by y c the center of this sphere,
and selecting one has
log
with
And thus
If V is invertible, one can derive alternative upper bounds on F (fi   ) as follows.
Using
we have
log
(setting
If instead of
log(- D
The bounds on F (fi 0 ) and F (fi   ) are used to derive a complexity estimate for
the computation of an approximate optimal solution. Using the fact that the
function F is self-concordant [15], we can resort to a potential increase scheme.
The scheme uses the Newton direction
\Gamma[F
Let us denote kuk
the norm of an arbitrary vector u in the metric
induced by the positive definite matrix H . The norm
a critical role in the analysis. The potential increase scheme is based on an
extension of lemma 3.3. The proof can be found in the unpublished lecture
notes [14]. (The proof is also made available in [16].)
Lemma 6.2 Let \Deltafi be such that k\Deltafik [F 00 (fi)]
with
Assume now
and satisfies the condition of the above
lemma. Thus,
easily shows that
is bounded from below by an absolute constant.
The complexity estimate for the potential increase scheme follows directly from
the above analysis and a bound on the achievable potential increase
Theorem 6.3 Let fi
. The potential increase algorithm applied
to the maximization of F produces a point fi such that
in a number of iterations not greater than6 6 6
Remark 6.1 The total number of Newton steps involved in the computation
of all the approximate optimum directions can easily bounded by m k   log(1="),
using theorem (6.3), where k   is the number of calls to the oracle at termination,
long step argument similar to the one given in [20] could
most likely be used to reduce this bound.
Looking at every iteration individually, and using the fact that A T y - c contains
the cutting planes 0 - y - e, we can assert that
and hence
This indicates that, in practice, the number of iterations needed at each iteration
to compute the optimal fi should not increase with the number of cutting planes.
It remains to prove that the potential increase scheme yields a solution fi that
meets the proximity condition kpfi(V used in Theorem 4.3. In other
words, we must show that for j small enough the condition
implies To this end, we adapt some results and proofs of [3]
developed for quadratic programming.
We then relate a few critical norms.
Lemma 6.4 Let
The following inequality holds
Proof
Since
This proves the left-hand side inequality.
As V is positive semidefinite, one has
Therefore
We can now prove the main result of the section.
Lemma 6.5 Assume
Proof
Since
over,
we get
We conclude that
The above lemma shows that once the condition
met, one more Newton step is enough to generate point satisfying
and thus, by Theorem 4.3, a point
7 Conclusion
In this paper, we defined an efficient direction to restore primal and dual feasibility
and centrality after adding p new central cuts simultaneously. The direction
is efficient in the sense that it maximizes the the product of the new variables
brought into the primal or the dual potentials, under the constraints that the
other variables remains within the Dikin ellipsoid. The computation of the optimal
direction takes place in a space of dimension p equal to the number of cuts
added at a given iteration. If p is sufficiently smaller than n, then significant
gains in efficiency can be expected.
The analysis has been derived under the assumption that the cuts are central. If
deep cuts are present, which is to be expected in practice, primal feasibility can
always be recovered but dual feasibility appears difficult to achieve in general,
except by the use of a primal Newton method. One could then extend the long
step argument of [8] in the case of one deep cut to multiple deep cuts.
The implementation of ACCPM [11] uses
e. Other choices using the
variance-covariance matrix V , if it is invertible, have been proposed in [10], and
the analysis of this paper actually strengthens that line of thinking.
Both the heuristic and optimal choices for fi and fl need to be tested in practice,
and rigorous extensions to multiple deep cuts deserve a more thorough study.



--R

"A cutting plane algorithm that uses analytic centers"
"A Cutting Plane Method from Analytic Centers for Stochastic Programming"
Interior Point Approach to Linear
"Solving Non-linear Multicommodity Flows Problems by the Analytic Center Cutting Plane Method"
"Decomposition and non-differentiable optimization with the projective algorithm"
"Complexity analysis of an interior cutting plane for convex feasibility problems"
"Using the Primal Dual Infeasible Newton Method in the Analytic Center Method for Problems Defined by Deep Cutting Planes"
"Shallow, deep and very deep cuts in the analytic center cutting plane method"
"A two-cut approach in the analytic center cutting plane method"
"Warm start of the Primal-Dual Method Applied in the Cutting Plane Scheme"
"ACCPM - A Library for Convex Optimization Based on an Analytic Center Cutting Plane Method"
"Analysis of a Cutting Plane Method That Uses Weighted Analytic Center and Multiple Cuts"
"Cutting plane algorithms from analytic centers: efficiency estimates"
Introductory lectures on Convex Optimization.
Interior Point Polynomial Algorithms in Convex Programming
Homogeneous Analytic Center Cutting Plane Methods for Convex Problems and Variational Inequalities
"On Updating the Analytic Center after the Addition of Multiple Cuts,"
Theory and Algorithms for Linear Optimization: An Interior point Approach
"A potential reduction algorithm allowing column genera- tion"
"Complexity Analysis of the Analytic Center Cutting Plane Method That Uses Multiple Cuts"
Interior Point Algorithms: Theory and Analysis.
--TR

--CTR
Olivier Pton , Jean-Philippe Vial, Multiple Cuts with a Homogeneous Analytic Center Cutting Plane Method, Computational Optimization and Applications, v.24 n.1, p.37-61, January
Fernanda Raupp , Clvis Gonzaga, A Center Cutting Plane Algorithm for a Likelihood Estimate Problem, Computational Optimization and Applications, v.21 n.3, p.277-300, March 2002
Shu-Cherng Fang , Soon-Yi Wu , Jie Sun, An Analytic Center Cutting Plane Method for Solving Semi-Infinite Variational Inequality Problems, Journal of Global Optimization, v.28 n.2, p.141-152, February 2004
cutting plane method;self-concordance;primal Newton algorithm;interior-point methods;analytic center;multiple cuts