Towards a Practical Volumetric Cutting Plane Method for Convex Programming.
We consider the volumetric cutting plane method for finding a point in a convex set ${\cal C}\subset\Re^n$ that is characterized by a separation oracle. We prove polynomiality of the algorithm with each added cut placed directly through the current point and show that this "central cut" version of the method can be implemented using no more than 25n constraints at any time.
Introduction
Let C ae ! n be a convex set. Given a point -
separation oracle for C either reports
that -
returns a separating hyperplane a 2 ! n such that a T x ? a T - x for every x 2 C.
The convex feasibility problem is to use such an oracle to find a point in C, or prove that
the volume of C must be less than that of an n-dimensional sphere of radius 2 \GammaL , for given
It is well known [9] that a variety of convex optimization problems can be cast as instances
of the convex feasibility problem, and moreover the problem plays a fundamental role the
complexity analysis of many combinatorial optimization problems. For many years the
standard approach to the convex feasibility problem has been the ellipsoid algorithm; see for
example [5] or [9]. In [14], Vaidya proposed an alternative algorithm for the convex feasibilty
problem based on a new barrier for a polyhedral set, the volumetric barrier. On each iteration
algorithm has a point x a polyhedral set P
where A k is a m k \Theta n matrix. For each k the set P k is bounded, is an
approximation of the volumetric center of P k , the minimizer of the volumetric barrier (see
Section 2). The algorithm then either deletes one constraint that defines P k , or calls the
separation oracle to see if x k 2 C. If not, the oracle returns a separating hyperplane which is
used to add a constraint to P k . After the addition or deletion of a constraint, the algorithm
takes a number of Newton, or Newton-like, steps for the volumetric barrier to obtain a new
point x k+1 which is an approximation of the volumetric center of the new polyhedron P k+1 .
Let T represent the cost, in numerical operations, of a call to the separation oracle.
fundamental result is that the complexity of his volumetric cutting plane algorithm
for the convex feasibility problem is O(nLT +n 4 L) operations, compared to O(n 2 LT +n 4 L)
operations for the ellipsoid algorithm. (In theory, the complexity of Vaidya's method can be
further reduced through the use of "fast matrix multiplication," which cannot be applied to
the ellipsoid algorithm.) Although Vaidya's result is theoretically significant, the algorithm
of [14] does not appear to very practical. In particular, the analysis of [14] requires that the
polyhedral sets P k have up to 10 7 n constraints, and the algorithm might require thousands
of Newton-like steps following the addition or deletion of a constraint.
In [3], Anstreicher describes a strengthened version of Vaidya's volumetric cutting plane
algorithm for the convex feasibility problem. The algorithm of [3] reduces the maximum
number of constraints to 200n, while requiring no more than 5 Newton steps following a
constraint addition or deletion. Although these figures represent a substantial improvement
over [14], the algorithm of [3] is still not fully practical. In particular:
i. For reasonable n, 200n constraints is still quite large, given that least-squares systems
with this number of rows must be repeatedly solved on each iteration.
ii. The algorithm of [3] uses true Newton steps, which in practice are expensive to compute
compared to the Newton-like steps used in [14].
iii. As in [14], the algorithm of [3] cannot place a new constraint directly through the
current point, but must rather "back off" each separating hyperplane to generate a
shallow cut.
Ramaswamy and Mitchell [13] describe a "central cut" version of the volumetric cutting
plane algorithm that allows for the placement of each new constraint through the current
point, and uses Newton-like steps following constraint additions and deletions. (The algorithm
of [13] actually solves the problem of minimizing a linear function over a convex set C
using a separation oracle, but most of the analysis is very similar to that required to solve the
convex feasibility problem.) Unfortunately [13], which uses many results from [14], requires
that the algorithm maintain up to 10 8 n constraints.
The purpose of this paper is to develop a central cut volumetric cutting plane algorithm
that also improves on the 200n constraints required by the algorithm of [3]. As in [13],
the algorithm uses an "affine" step to move off of a cut placed through the current point.
The use of such a step in the context of a cutting plane method based on analytic centers
is well known [7]. (See [4], [8], [10], [11], [12], and [15] for other results on analytic center
cutting plane methods.) In fact the affine step we use is based on that of [7], rather than the
step used in [13]. Our analysis uses a number of results from [2] and [3], and an improved
second-order expansion of the volumetric barrier, to improve upon the analysis of [13]. As
in [13], the method described here requires O(
n) Newton-like steps following the addition
or deletion of a constraint, compared to O(1) Newton, or Newton-like, steps in [14] and [3].
Although this is certainly a disadvantage from the standpoint of theoretical complexity, the
fact that the O(
n) bound arises from a worst-case analysis of descent in the volumetric
barrier suggests that in practice far fewer steps would likely be required. Our final result is
a central cut volumetric cutting plane method that requires no more than 25n constraints
at any time.
In

Table

1 we summarize important attributes of four papers (including this paper) on
volumetric cutting plane methods. These features are the placement of added cuts (shallow
or central), the number of Newton or Newton-like steps required after a constraint addition
or deletion, the maximum number of constraints required, and the value of a scalar \DeltaV ,
defined as the difference between the mimimal increase in the volumetric barrier following a
constraint addition, and the maximal decrease following a constraint deletion (see Section 3).
For all four algorithms the number of oracle calls is O(nL), with a constant that is inversely
proportional to \DeltaV (see for example the proof of [3, Theorem 3.2]).
Reference Placement Steps after Number of \DeltaV
of cut addition/deletion constraints
Anstreicher [3] Shallow O(1) 200n 3:7 \Theta 10 \Gamma4
Ramaswamy and Mitchell [13] Central O(
This Paper Central O(
n) 25n 1:4 \Theta 10 \Gamma3

Table

1: Attributes of volumetric cutting plane methods
2 The Volumetric Barrier
In this section we collect a number of properties of the volumetric barrier V (\Delta) which will be
used in the subsequent analysis. To start, let A is an m \Theta n
. Whenever we refer to P, we are implicitly refering to the constraint
system [A; b] which defines it. The volumetric barrier for P is the function
x be a point having
denote the vector equal to the diagonal of the projection
In other words oe m. It is easy to show (see for example the Appendix of
[1]) that 0 - oe - e, e T is the vector with each component equal to one.
The gradient and Hessian of V (\Delta) at x are then given by
denotes the Schur, or Hadamard product of P with itself:
ij . Let good approximation of H(x), in that
where - denotes the ordering for positive semi-definite matrices defined by A - B ()
A is positive semidefinite. See for example the Appendix of [1] for a derivation of (1)
and a proof of (2); these and other properties of V (\Delta) are originally due to Vaidya [14].
In the sequel we will often be interested in the behavior of V (\Delta) for a step of the form
1. For such an -
Q(-x). The proof of the following is very straightforward; see for example [14, Lemma
5] or [1, Lemma 2.2].
Proposition 2.1 Let -
It follows immediately from Proposition 2.1 that if -
Using a Taylor series expansion, (2), and (3), it is easy to show that
The bounds in (4) have been used in [1], [13], and [14]. The following theorem provides a
strengthening of (4) that will be used throughout the paper.
Theorem 2.2 Suppose that -
Proof: We have
dff
To prove the lemma we will obtain lower and upper bounds on the final term in (5). We
begin with the lower bound. Using (2) and (3), we have
and therefore
But it is straightforward to compute that
d
and therefore
Substituting (8) into (7), we obtain
Z 1ff
An integration by parts shows that
Z 1ff
and substituting (10) into (9) produces the lower bound of the lemma. The proof of the
upper bound is similar. Again using (2) and (3), we have
and therefore
But
d
and therefore
Substituting (12) into (11), we obtain
Z 1ff
Another integration by parts shows that
Z 1ff
and substituting (14) into (13) produces the upper bound of the lemma. 2
Since the bounds in Lemma 2.2 involve both k-k
to consider how these two quantities are related. For x with
g. Note that oe min ? 0 under the trivial assumption that A contains no zero
row. Define
In the following lemma we give two bounds for kS \Gamma1 A-k1 in terms of k-k Q ; one involving
-, and therefore oe min , and the other independent of oe.
Theorem 2.3 Let x have
2. kS
m)=2] 1=2 k-k Q .
Proof: See [1, Theorem 3.3] for the proof of 1, and [3, Lemma 2.3] for the proof of 2. 2
Motivated by Theorem 2.3, we define
It then follows from Theorem 2.3 that
The fundamental proximity criterion that we employ throughout the paper is -
this quantity is "large" (that
is,\Omega\Gamma,/23 we will take a damped Newton-like step in an effort to
reduce V (\Delta), and thus move closer to !, the volumetric center of P. When -
we will be close enough to ! to adequately control the effect of adding or deleting a constraint,
as required. The following theorem and corollary obtain a simple condition on -
suffices to demonstrate the boundedness of P.
Theorem 2.4 Let where the columns of A are independent. Let x have
g. Suppose that kS
Proof: P is bounded if and only if
6 9x 6= 0, Ax - 0. Since the columns of A are independent,
ve T
where the third equivalence uses a standard "Theorem of the Alternative" for systems of
linear inequalities. But is exactly A T S \Gamma2
can be written
A
It follows that if kS
is bounded. 2
Corollary 2.5 Let where the columns of A are independent. Let x have
suppose that -
Proof: This follows from Theorem 2.4, (17), and the fact that show that if -
sufficiently small, then we can bound the possible
remaining decrease in V (\Delta). The proximity allowed in Theorem 2.6, -
weaker than in previous, similar results in [14], [2], and [3].
Theorem 2.6 Let x have
where ! is the minimizer of V (\Delta), and
Proof: Assume that -
1. Then there is a -,
has -
from (17), we have
d
dff
where the inequality uses (6), and the final equality uses (8), both with 1. Using the
fact that jg T
we then obtain
d
dff
where the last inequality uses and the assumption that -
V (\Delta) is strictly convex, it follows that V (!) ? V (-x), which is a contradiction. Therefore
1, from (17), so Theorem 2.2 implies that
where the second inequality uses jg T -j - kgk Q and the final inequality uses -
1, and the assumption that -
In the corollary below we use Theorem 2.6 to establish bounds on V for two
values of the parameter fl which are useful in the sequel.
Corollary 2.7 Let x have
Proof: For is straightforward to show that the minimum in (20), for 0 - ff - 1,
occurs at
2. Substituting this value of ff into (20), and simplifying, then implies
that
It is also easy to show that for fl - 4=27, the right-hand side in (20) is monotonically
decreasing for 0 - ff - 1. Substituting
final topic that we consider in this section is that of reducing V (\Delta) when -
\Omega\Gamma/54 To accomplish this we use a Newton-like step of the form
for some ff ? 0. When -
=\Omega\Gamma338 it can be shown that ff may be
chosen in (21) so that an
m) reduction is obtained in V (\Delta). In the following lemma
we give a result for a particular value of fl used in the sequel.
Lemma 2.8 Suppose that x has
x(ff) be as in (21).
m.
Proof: Let construction we have -
by (17). Applying Theorem 2.2, we obtain
Substituting using -
. Finally from (16), -
m)=2 -
m. 2
3 The Algorithm and its Complexity
In this section we describe the central-cut volumetric cutting plane method, and establish its
complexity using results from the two following sections. At the start of each iteration k - 0,
we have an interior point x k of a bounded polyhedron P k oe C, where
and A k is an m k \Theta n matrix with independent columns. We assume that C is contained in
the hypercube kxk1 - 1, and set P is straightforward to
show that x 0 is the volumetric center of P 0 .) The algorithm to be analyzed is as follows:
Central-Cut Volumetric Cutting Plane Algorithm
1. Go to Step 1.
Step 1. If V k
Else go to Step 2.
Step 2. If oe k
min - ffl, go to Step 3. Else go to Step 4.
Step 3. (Constraint Addition) Call the oracle to see if x k 2 C. If so, STOP. Otherwise
the oracle returns a vector a 2 ! n such that a T x ? a T x k for all x 2 C. Let
be an augmented constraint system having a k+1
ff ? 0. Go to Step 5.
Step 4. (Constraint Deletion) Suppose that oe k
be the reduced
constraint system obtained by removing the j'th row of
Go to Step 5.
Step 5. (Centering Steps) Take a sequence of damped Newton-like steps of the form -
-x J ). Let x
to Step 1.
In Step 1 of the algorithm, the value of V k
max is such that V
proves that the
volume of P k , and therefore also C ae P k , is less than that of an n-dimensional sphere of
radius 2 \GammaL . An explicit value for
is given in Lemma 3.1, below. A suitable steplength
ff in Step 3 is given in Theorem 4.6. Note that by construction each P k is bounded, by
Corollary 2.5, since -
each k. In addition, the fact that a constraint
is only added if oe k
For the Newton-like steps in Step 5, we assume that the steplengths ff are chosen so that
each step produces an
n) decrease in V k (\Delta). That this is always possible follows from
\Omega\Gamma17 (see for example Lemma 2.8), and the fact that m k -
O(n).
Lemma 3.1 Consider the volumetric cutting plane algorithm with fl - :03. Assume that
termination in Step 1 proves that the volume
of C is less than that of an n-dimensional sphere of radius 2 \GammaL .
Proof: See [3, Lemma 3.1]. 2
Next we consider the issue of how many iterations might be required for the algorithm
to terminate. Assume that each time a constraint is added the algorithm achieves
while each time a constraint is deleted it is assured that
. The following theorem provides a complexity result for the
algorithm under simple assumptions regarding \DeltaV and the number of
Newton-like steps taken in Step 5.
Theorem 3.2 Assume that the iterates of the volumetric cutting plane algorithm, using fl -
:03, satisfy (23) and (24) on iterations where a constraint is added or deleted, respectively.
Assume further that \DeltaV + is O(1),
is\Omega\Gamma/4 , and the number of
Newton-like steps in Step 5 of the algorithm is always O(
n). Then for L
=\Omega\Gamma47 (n)) the
algorithm terminates in O(nL) iterations, using a total of O(nLT +n 4:5 L) operations, where
T is the cost of a call to the separation oracle.
Proof: See the proof of [3, Theorem 3.2]. 2
Compared to the algorithms of [14] and [3], Theorem 3.2 demonstrates that the central cut
method of this paper has the same order number of oracle calls, O(nL), but performs more
non-oracle work; O(n 4:5 L) versus O(n 4 L) operations. The reason for this is the larger number
of centering steps, O(
n) versus O(1), required after a constraint addition or deletion. Using
results from the next two sections, we now show that the assumptions of Theorem 3.2 hold
for certain choices of the parameters ffl and fl.
Theorem 3.3 Let :01. Then the central-cut volumetric cutting plane method
satisfies the assumptions of Theorem 3.2, with
Proof: First consider an iteration where a cut is added. In Theorem 4.6, it is shown that
for a particular choice of ff in Step 3 it is assured that
where we are using the fact that kg k k (Q
In addition, in Theorem
4.5 it is shown that for kg k k (Q
is the volumetric center of P k+1 . Combining (25) and (26) we obtain
Next, in Lemma 2.8 it is shown that if -
in Step 5, then a steplength
ff may be chosen so that
together imply that after
n)
steps we must obtain -
x J having -
Finally, V k+1
implies that
Next consider an iteration where a constraint is deleted. In Lemma 5.2 it is shown that
dropping constraint i to obtain a new
polyhedron P k+1 results in V k+1 Arguing exactly as above, it
follows that after
n) steps in Step 5, we must obtain - x J with -
In addition, in Lemma 5.2 it is shown that V k+1 (! k+1 must
have
The assumptions of Theorem 3.2 thus hold with
The value demonstrated in Theorem 3.3 may seem relatively small, but it
should be noted that this is the largest value of \DeltaV to date for a volumetric cutting plane
algorithm; see Table 1 in Section 1.
4 Adding a Central Cut
Let x be an interior point of P. In this section we consider augmenting the constraint system
defining P by imposing a central cut through x, to obtain a new polyhedron ~
b; a T ~
x - a T xg. Let ~
V (\Delta) be the volumetric barrier for ~
! the volumetric center. Note
that for any -
x with -
x ? a T x, we have
~
(a T -
I
(a T -
(a T -
We will first use (29) to establish a lower bound on ~
a cut is added through
x. We will obtain two versions of this result. The first, using produces a relatively
simple bound for the fundamental quantity ~
(!). Although this bound may be
of some independent interest, in practice it cannot be used since
Therefore we will also obtain a lower bound using x in a certain neighborhood of !. We
begin with a series of lemmas. Throughout we let
Lemma 4.1 Assume that -
x ? a T x, and k -
a T
(a T -
Proof: Consider the problem
a T -
Letting -
can be written as
a T -
the solution of which is
a T
with solution value equal to ae
a T
It follows that
a T
(a T -
- a T
ae 2 a T
:Lemma 4.2 Assume that -
and -r - 1. Then
a T
(a T -
immediately implies that
oe min
and also, from Lemma 2.3, that
From (32) and Proposition 2.1 it follows that
Then (31) and (33) together imply that
oe min
and the lemma follows from Lemma 4.1. 2
Lemma 4.3 Assume that -
Proof: This follows immediately from (32), and the lower bound of Lemma 2.2. 2
Now let the volumetric center of P. We will use Lemmas 4.2 and 4.3 to establish
a lower bound on ~
P is obtained by placing a central cut through !.
Theorem 4.4 Suppose that ! is the volumetric center of P,
~
!g. Let ~
V (\Delta) be the volumetric barrier for ~
! the volumetric
center. Then ~
assume for the moment that
-(!). Using (29), Lemmas 4.2 and 4.3, and the fact that
~
Next we use the fact that ln(1 to obtain
where the second inequality uses - 1, and
and the final inequality uses Substituting (35) into (34) then gives
~
A straightforward differentiation shows that the minimum of the right-hand side of (36), for
occurs at From (36) we then have
Next assume that r ? 1=-. Then there is an ff 2 (0; 1) so that -
1=-. From the convexity of V (\Delta), and Lemma 4.3, we obtain
and (29) certainly implies that ~
It follows that ~
oe min )=8. 2
It is worthwhile to mention that the analysis in [13, Section 4.1] actually shows that
~
oe min ), although the authors of [13] do not note this fact. In practice
the added cut a T ~ x - a T x cannot be passed through as in Theorem 4.4, but rather
through a point x which is close to ! in some sense. As a result the lower bound of Theorem
4.4 must be modified to account for the use of x 6= !. In the next theorem we give a result
based on particular parameter choices used throughout the paper.
Theorem 4.5 Let x have
~
V (\Delta) be the volumetric barrier for ~
! the volumetric
center. Then ~
assume for the moment that
Proceeding as in the proof of Theorem 4.4, but including the effect of
~
where the second inequality uses the fact that jg T We distinguish
two cases.
Case 1: oe min - :04725. Note that 1=-
monotonically increasing
in oe min , so oe min - :04 implies that 1=- 2 - 2
In addition, - 2 oe
oe min =(2
monotonically increasing in oe min , so oe min - :04 also implies that
Finally oe min - :04725 implies that - (2
1:606. Using these facts in (37), and the assumption that kgk Q
~
It can be verified numerically that the minimum of the right-hand side in (38), for
occurs at approximately with value greater than :0340. (See Figure 1, Case 1 for a
plot of the right-hand side of (38), for
Case 1
Case 2

Figure

1: Lower bound on ~
Case 2: oe min - :04725. In this case we have 1=-
Using these facts in (37), with - 1
and the assumption that kgk Q
~
It can be verified numerically that the minimum of the right-hand side in (39), for
occurs at approximately with value greater than :0340. (See Figure 1, Case 2 for a
plot of the right-hand side of (38), for
This completes the proof under the assumption that r - 1=-. However, arguing as at
the end of Theorem 4.4, it is easy to show that if k~! \Gamma xkQ ? 1=-, then
~
:For the final topic of the section, we consider moving off of the cut a T ~
x - a T x to a
new point -
x having a T -
x ? a T x. Our goal is to obtain an upper bound for the quantity
~
Consider a point of the form
a T
1. Note that -
x in (40) is based on A T S \Gamma2 A, the Hessian of the logarithmic
barrier at x, and not Q as used in [13, Section 4.1.2].
Theorem 4.6 Suppose that x has
x - a T xg,
and let ~
V (\Delta) be the volumetric barrier for ~
P. Then using
x having
~
Proof: By construction we have a T - x \Gamma a T
a T
It follows that
a T
(a T -
where the last inequality uses (41) and Proposition 2.1. Let -
x. Then from (41) and
Lemma 2.2 we have
where the last inequality uses the facts that Q - A T S \Gamma2 A, and - T A T S \Gamma2 Combining
(29), (42), and (43), we obtain
~
The proof is completed by substituting
5 Dropping a Constraint
In this section we consider the effect of dropping a constraint, as in Step 4 of the algorithm.
For simplicity we assume that oe
P be the new constraint system obtained
by deleting the mth constraint in the original system [A; b] defining P. Throughout we use
the tilde (~) notation to denote quantities related to the reduced constraint system [ ~
Theorem 5.1 Suppose that x has
P is obtained by deleting
the mth constraint defining P. Then
1. ~
2. oe i - ~
3. k~gk ~
Proof: See [3, Lemma 5.1, Lemma 5.2, and Theorem 5.3]. 2
We will use Theorem 5.1 to bound the change in our fundamental proximity measure
following the deletion of a constraint. We use - ~
-(x) to denote the value of -
with respect to the reduced constraint system [ ~
Theorem 5.2 Assume that x has
Let ~
P be obtained by deleting the mth constraint defining P. Then ~
P is bounded, ~
~
! is the volumetric center of ~
P.
Proof: Note that - ~
-, from part 2 of Theorem 5.1, and the fact that ~
Applying part 3 of Theorem 5.1, we obtain
-k~gk ~
min
where the second inequality uses the assumption that -
It is clear that the
right-hand side of (45) is increasing in oe min , and substituting oe results in
-k~gk ~
Assume for the moment that - ~
- :833-. Then (46) implies that - ~
-k~gk ~
~
from Corollary 2.7. Alternatively assume that - ~
- :833-. Since in any case - ~
implies that - ~
-k~gk ~
In addition, oe min - :04 implies - (2
From Corollary 2.7 we then have
~
so in all cases ~
as claimed. In addition, we have
~
and part 1 of Theorem 5.1 gives
~
Then ~
:0326 follows from (47), (48), and ~
6 Conclusion
From a practical standpoint, this paper gives the best result to date for a cutting plane
method for the convex feasibility problem based on the volumetric barrier. From the stand-point
of theoretical complexity, the most interesting open problem is the use of central cuts
with the volumetric barrier, while requiring only O(1) Newton (or Newton-like) steps following
the introduction of a cut, as is possible when shallow cuts are employed ([14], [3]).
Although the affine step (40) is sufficient to obtain an O(1) bound on ~
as in Theorem
4.6, this bound is too weak relative to - oe min to show that O(1) steps suffice to return to
a suitable proximity of the new volumetric center ~ !. As a result it becomes necessary to use
a proximity measure based on - in place of -, leading to a worst-case decrease of
n)
instead of
\Omega\Gamma/1 in the steps on Step 5 of the algorithm. In practice the algorithm might
of course do much better than these worst-case bounds indicate, but serious computational
work using the volumetric barrier has not yet been conducted.
For the analytic center cutting plane method it is relatively easy to show that O(1) steps
suffice to return to a suitable proximity of the new analytic center following the addition of
a central cut [7]. (The basic analytic center cutting plane method is not a polynomial time
algorithm, however. To date the only polynomial cutting plane algorithm based on analytic
centers, due to Atkinson and Vaidya [4], uses shallow cuts.) The complexity analysis for
the analytic center cutting plane method can also be extended to multiple cuts ([11], [15]),
and deep cuts ([6], [8]). Similar results for the volumetric cutting plane method would
be desirable. In [13] a result allowing multiple cuts is developed, but in addition to the
very small constants required throughout [13], the multiple cut result requires a "Selective
Orthonormalization" procedure that weakens the original cuts in the interest of constructing
a feasible affine step.



--R

"Large step volumetric potential reduction algorithms for linear programming,"
"Volumetric path following algorithms for linear program- ming,"
"On Vaidya's volumetric cutting plane method for convex programming,"
"A cutting plane algorithm for convex programming that uses analytic centers,"
"The ellipsoid method: a survey,"
"Using the primal dual infeasible Newton method in the analytic center method for problems defined by deep cutting planes,"
"Complexity analysis of an interior point cutting plane method for convex feasibility problems,"
"Shallow, deep, and very deep cuts in the analytic center cutting plane method,"
Geometric Algorithms and Combinatorial Optimization
"Complexity of some cutting plane methods that use analytic cen- ters,"
"Analysis of a cutting plane method that uses weighted analytic centers and multiple cuts,"
"Complexity estimates of some cutting plane methods based on analytical barrier,"
"A long step cutting plane algorithm that uses the volumetric barrier,"
"A new algorithm for minimizing convex functions over convex sets,"
"Complexity analysis of the analytic center cutting plane method that uses multiple cuts,"
--TR
convex programming;cutting plane method;volumetric barrier