Smoothing Methods for Linear Programs with a More Flexible Update of the Smoothing Parameter.
We consider a smoothing-type method for the solution of linear programs. Its main idea is to reformulate the corresponding central path conditions as a nonlinear system of equations, to which a variant of Newton's method is applied. The method is shown to be globally and locally quadratically convergent under suitable assumptions. In contrast to a number of recently proposed smoothing-type methods, the current work allows a more flexible updating of the smoothing parameter. Furthermore, compared with previous smoothing-type methods, the current implementation of the new method gives significantly better numerical results on the netlib test suite.
Introduction
Consider the linear program
x s.t.
are the given data and A is assumed to be of full rank,
m. The classical method for the solution of this minimization problem is
Dantzig's simplex algorithm, see, e.g., [11, 1]. During the last two decades, however, interior-point
methods have become quite popular and are now viewed as being serious alternatives
to the simplex method, especially for large-scale problems.
More recently, so-called smoothing-type methods have also been investigated for the
solution of linear programs. These smoothing-type methods join some of the properties of
interior-point methods. To explain this in more detail, consider the optimality conditions
(2)
of the linear program (1), and recall that (1) has a solution if and only if (2) has a solution.
The most successful interior-point methods try to solve the optimality conditions (2) by
solving (inexactly) a sequence of perturbed problems (also called the central path conditions)
where  > 0 denotes a suitable parameter. Typically, interior-point methods apply some
kind of Newton method to the equations within these perturbed optimality conditions and
guarantee the positivity of the primal and dual variables by an appropriate line search.
Many smoothing-type methods follow a similar pattern: They also try to solve (inexactly)
a sequence of perturbed problems (3). To this end, however, they rst reformulate the
system (3) as a nonlinear system of equations and then apply Newton's method to this
reformulated system. In this way, smoothing-type methods avoid the explicit inequality
constraints, and therefore the iterates generated by these methods do not necessarily belong
to the positive orthant. More details on smoothing methods are given in Section 2.
The algorithm to be presented in this manuscript belongs to the class of smoothing-type
methods. It is closely related to some methods recently proposed by Burke and Xu [2, 3]
and further investigated by the authors in [13, 14]. In contrast to these methods, however,
we allow a more
exible choice for the parameter  . Since the precise way this parameter
is updated within the algorithm has an enormous in
uence on the entire behaviour of the
algorithm, we feel that this is a highly important topic. The second motivation for writing
this paper is the fact that our current code gives signicantly better numerical results than
previous implementations of smoothing-type methods. For some further background on
smoothing-type methods, the interested reader is referred to [4, 6, 7, 8, 16, 17, 20, 22, 23]
and references therein.
The paper is organized as follows: We develop our algorithm in Section 2, give a detailed
statement and show that it is well-dened. Section 3 then discusses the global and local
convergence properties of our algorithm. In particular, it will be shown that the method has
the same nice global convergence properties as the method suggested by Burke and Xu [3].
Section 4 indicates that the method works quite well on the whole netlib test suite. We then
close this paper with some nal remarks in Section 5.
A few words about our notation: R n denotes the n-dimensional real vector space. For
we use the subscript x i in order to indicate the ith component of x, whereas a
superscript like in x k is used to indicate that this is the kth iterate of a sequence fx k g  R n .
Quite often, we will consider a triple of the form
and s 2 R n ; of course, w is then a vector in R n+m+n . In order to simplify our notation,
however, we will usually write instead of using the mathematically more correct
is a vector whose components are all nonnegative, we
simply write x  0; an expression like x  0 has a similar meaning. Finally, the symbol k  k
is used for the Euclidean vector norm.
2 Description of Algorithm
In this section, we want to derive our predictor-corrector smoothing method for the solution
of the optimality conditions (2). Furthermore, we will see that the method is well-dened.
Since the main idea of our method is based on a suitable reformulation of the optimality
conditions (2), we begin with a very simple way to reformulate this system. To this end, let
denote the so-called minimum function
and let  dened by
Since ' has the property that
a  0; b  0; ab
it follows that  can be used in order to get a characterization of the complementarity
conditions:
Consequently, a vector w a solution of the optimality
conditions (2) if and only if it satises the nonlinear system of equations
The main disadvantage of the mapping  is that it is not dierentiable everywhere. In order
to overcome this nonsmoothness, several researchers (see, e.g., [7, 5, 18, 21]) have proposed
to approximate the minimum function ' by a continuously dierentiable mapping with the
help of a so-called smoothing parameter  . In particular, the function
has become quite popular and is typically called the Chen-Harker-Kanzow-Smale smoothing
function in the literature [5, 18, 21]. Based on this function, we may dene the mappings
and
(w) :=
Obviously,   is a smooth approximation of  for every  > 0, and coincides with  in the
limiting case Furthermore, it was observed in [18] that a vector w
solves the nonlinear system of equations
if and only if this vector is a solution of the central path conditions (3). Solving the system (4)
by, say, Newton's method, is therefore closely related to several primal-dual path-following
methods which have become quite popular during the last 15 years, cf. [24].
However, due to our numerical experience [13, 14] and motivated by some stronger theoretical
results obtained by Burke and Xu [3], we prefer to view  as an independent variable
(rather than a parameter). To make this clear in our notation, we write
and, similarly,
from now on. Since the nonlinear system (4) contains only equations and
we add one more equation and
dene a mapping
cf. [3]. We also need the following generalization of the function :
here,  2 (0; 1] denotes a suitable centering parameter, and : [0; 1) ! R is a function
having the following properties:
(P.1) is continuously dierentiable with
For each  0 > 0, there is a constant
(possibly depending on  0 ) such that
The following functions satisfy all these properties:
In fact, it is quite easy to see that all three examples satisfy properties (P.1), (P.2), and
(P.3). Furthermore, the mapping
being independent
of  0 . Also the mapping () :=
being independent
of  0 . On the other hand, a simple calculation shows that the third example does satisfy
with
depends on  0 .
Note that the choice corresponds to the one used in [2, 3], whereas here we aim to
generalize the approach from [2, 3] in order to allow a more
exible procedure to decrease  .
Since the precise reduction of  has a signicant in
uence on the overall performance of
our smoothing-type method, we feel that such a generalization is very important from a
computational point of view.
Before we give a precise statement of our algorithm, let us add some further comments
on the properties of the function : (P.1) is obviously needed since we want to apply a
Newton-type method to the system of equations  hence has to be
su-ciently smooth. The second property (P.2) implies that is strictly monotonically
increasing. Together with 0 from property (P.1), this means that the nonlinear
system of equations
is equivalent to the optimality conditions (2) themselves (and not to the central path conditions
(3)) since the last row immediately gives The third property (P.3) will be used in
order to show that the algorithm to be presented below is well-dened, cf. the proof of Lemma
2.2 (c). Furthermore, properties (P.3) and (P.4) together will guarantee that the sequence
is monotonically decreasing and converges to zero, see the proof of Theorem 3.3.
We now return to the description of the algorithm. The method to be presented below is a
predictor-corrector algorithm with the predictor step being responsible for the local fast rate
of convergence, and with the corrector step guaranteeing global convergence. More precisely,
the predictor step consists of one Newton iteration applied to the system (x; ; s;
followed by a suitable update of  which tries to reduce  as much as possible. The corrector
step then applies one Newton iteration to the system  but with the usual
right-hand side  being replaced by  centering parameter
1). This Newton step is followed by an Armijo-type line search.
The computation of all iterates is carried out in such a way that they belong to the
neighbourhood
of the central path, where  > 0 denotes a suitable constant. In addition, we will see later
that all iterates automatically satisfy the inequality (x; s; )  0, which will be important
in order to establish a result regarding the boundedness of the iterates, cf. Lemma 3.1 and
Proposition 3.2 below.
The precise statement of our algorithm is as follows (recall that  and  ; denote the
mappings from (5) and (6), respectively).
Algorithm 2.1 (Predictor-Corrector Smoothing Method)
Choose w 0 :=
and select   k(x
0, and set k := 0.
(Termination Criterion)
If
Compute a solution (w of the
linear system
then set
else compute  is the nonnegative integer such that
(Corrector Step)
Choose
R n  R m  R n  R of the linear system
such that
and go to Step (S.1).
Algorithm 2.1 is closely related to some other methods recently investigated by dierent
authors. For example, if we take then the above algorithm is almost identical
with a method proposed by Burke and Xu [3]. It is not completely identical since we use a
dierent update for ^
w k in the predictor step, namely for the case ' This is necessary
in order to prove our global convergence results, Theorem 3.3 and Corollary 3.4 below. On
the other hand, Algorithm 2.1 is similar to a method used by the authors in [14]; in fact,
taking once again almost have the method from [14]. The only dierence that
remains is that we use a dierent right-hand side in the predictor step, namely (w k ;  k ),
whereas [14] uses (w k ; 0). The latter choice seems to give slightly better local properties,
however, the current version allows to prove better global convergence properties.
From now on, we always assume that the termination parameter " in Algorithm 2.1 is
equal to zero and that Algorithm 2.1 generates an innite sequence
we assume that the stopping criteria in Steps (S.1) and (S.2) are never satised. This is
not at all restrictive since otherwise w k or w k would be a solution of the optimality
conditions (2).
We rst note that Algorithm 2.1 is well-dened.
Lemma 2.2 The following statements hold for any k 2 N:
(a) The linear systems (7) and (8) have a unique solution.
(b) There is a unique  k satisfying the conditions in Step (S.2).
(c) The stepsize ^
t k in (S.3) is uniquely dened.
Consequently, Algorithm 2.1 is well-dened.
Proof. Taking into account the structure of the Jacobians  0 (w; ) and  0
using
the fact that 0 () > 0 by property (P.2), part (a) is an immediate consequence of, e.g., [12,
Proposition 3.1]. The second statement follows from [13, Proposition 3.2] and is essentially
due to Burke and Xu [3]. In order to verify the third statement, assume there is an iteration
index k such that
for all ' 2 N . Since k(^x
we obtain from property (P.3) that
Taking this inequality into account, the proof can now be completed by using a standard
argument for the Armijo line search rule. 2
We next state some simple properties of Algorithm 2.1 to which we will refer a couple of
times in our subsequent analysis.
Lemma 2.3 The sequences fw k generated by Algorithm 2.1 have
the following properties:
(a) A T
(b)  k   0 (1
denotes the
constant from property (P.4).
(c)
Proof. Part (a) holds for our choice of the starting point Hence it
holds for all k 2 N since Newton's method solves linear systems exactly. In order to verify
statement (b), we rst note that we get
from the fourth block row of the linear equation (8). Since
it therefore follows from property (P.4) and the updating rules in steps (S.2) and (S.3) of
Algorithm 2.1 that
Using a simple induction argument, we see that (b) holds. Finally, statement (c) is a direct
consequence of the updating rules in Algorithm 2.1. 2
3 Convergence Properties
In this section, we analyze the global and local convergence properties of Algorithm 2.1.
Since the analysis for the local rate of convergence is essentially the same as in [3] (recall
that our predictor step is identically to the one from [3]), we focus on the global properties. In
particular, we will show that all iterates remain bounded under a strict feasibility
assumption. This was noted by Burke and Xu [3] for a particular member of our class of
methods (namely for the choice () :=  ), but is not true for many other smoothing-type
methods like those from [5, 6, 7, 8, 13, 14, 22, 23].
The central observation which allows us to prove the boundedness of the iterates
is that they automatically satisfy the inequality
for all k 2 N provided this inequality holds for This is precisely the statement of our
rst result.
Lemma 3.1 The sequences fw k
generated
by Algorithm 2.1 have the following properties:
(a) (^x
(b)
Proof. We rst derive some useful inequalities, and then verify the two statements simultaneously
by induction on k.
We begin with some preliminary discussions regarding statement (a). To this end, let
be xed for the moment, and assume that we take ^
in Step (S.2) of
Algorithm 2.1. Since each component of the function  is concave, we then obtain
From the third block row of (7), we have
Hence we get from (11):
We claim that the right-hand side of (12) is nonpositive. To prove this statement, we rst
note that
with
@
@

0:
Hence it remains to show that
However, this is obvious since the last row of the linear system (7) implies
We next derive some useful inequalities regarding statement (b). To this end, we still
assume that k 2 N is xed. Using once again the fact that  is a concave function in each
component, we obtain from (8)
and this completes our preliminary discussions.
We now verify statements (a) and (b) by induction on k. For
0 by our choice of the starting point w and the initial smoothing parameter
in Step (S.0) of Algorithm 2.1. Therefore, if we set ^
in Step (S.2) of
Algorithm 2.1, we also have ^
On the other hand, if we
in Step (S.2), the argument used in the beginning of this proof shows
that the inequality (^x
holds in this case.
Suppose that we have
immediately implies that we have Consequently, if we have
in Step (S.2) of Algorithm 2.1, we obviously have (^x
erwise, i.e., if we set ^
in Step (S.2), the argument used in the beginning
part of this proof shows that the same inequality holds. This completes the formal proof by
induction. 2
We next show that the sequence fw k g generated by Algorithm 2.1 remains bounded provided
that there is a strictly feasible point for the optimality conditions (2), i.e., a vector ^
x
Proposition 3.2 Assume that there is a strictly feasible point for the optimality conditions
(2). Then the sequence fw k generated by Algorithm 2.1 is bounded.
Proof. The statement is essentially due to Burke and Xu [3], and we include a proof here
only for the sake of completeness.
Assume that the sequence fw k generated by Algorithm 2.1 is un-
bounded. Since f k g is monotonically decreasing by Lemma 2.3 (b), it follows from Lemma
2.3 (c) that
for all k 2 N . The denition of the (smoothed) minimum function therefore implies that there
is no index ng such that x k
i !1 on a subsequence, since otherwise
we would have '(x k
in turn, would imply k(x on a
subsequence in contrast to (14). Therefore, all components of the two sequences fx k g and
are bounded from below, i.e.,
and s k
where
R denotes a suitable (possibly negative) constant.
On the other hand, the sequence fw k unbounded by assumption.
This implies that there is at least one component ng such that x k
on a subsequence since otherwise the two sequences fx k g and fs k g would be
bounded which, in turn, would imply the boundedness of the sequence f k g as well because
we have A T  2.3 (a)) and because A is assumed to have
full rank.
be a strictly feasible point for (2) whose existence
is guaranteed by our assumption. Then, in particular, we have
Since we also have
for all k 2 N by Lemma 2.3 (a), we get
A
by subtracting these equations. Premultiplying the rst equation in (16) with (^x x k ) T and
taking into account the second equation in (16) gives
Reordering this equation, we obtain
for all k 2 N . Using (15) as well as ^
in view of the strict feasibility of the
it follows from (17) and the fact that x k
on a
subsequence for at least one index ng that
Hence there exists a component ng (independent of k) such that
on a suitable subsequence.
using Lemma 3.1 (b), we have
for all k 2 N . Taking into account the denition of  and looking at the j-th component,
this implies
for all k 2 N . Using (18) and (15), we see that we necessarily have x k
those k belonging to the subsequence for which (18) holds. Therefore, taking the square in
(19), we obtain
after some simplications. However, since the right-hand side of this expression is bounded
by 4 2
0 , this gives a contradiction to (18). 2
We next prove a global convergence result for Algorithm 2.1. Note that this result is dierent
from the one provided by Burke and Xu [3] and is more in the spirit of those from [22, 13,
14]. (Burke and Xu [3] use a stronger assumption in order to prove a global linear rate of
convergence for the sequence f k g.)
Theorem 3.3 Assume that the sequence fw k generated by Algorithm 2.1
has at least one accumulation point. Then f k g converges to zero.
Proof. Since the sequence f k g is monotonically decreasing (by Lemma 2.3 (b)) and bounded
from below by zero, it converges to a number    0. If  0, we are done.
So assume that   > 0. Then the updating rules in Step (S.2) of Algorithm 2.1 immediately
give
for all k 2 N su-ciently large. Subsequencing if necessary, we assume without loss of
generality that (20) holds for all k 2 N . Then Lemma 2.3 (b) and ^
Y
Y
by assumption, it follows from (21) that lim Therefore, the
stepsize
does not satisfy the line search criterion (9) for all k 2 N large enough.
Hence we have
for all these k 2 N .
Now let w be an accumulation point of the sequence fw k g, and let fw k gK
be a subsequence converging to w  . Since , we can assume without
loss of generality that the subsequence f^ k g K converges to some number ^
Furthermore, since   > 0, it follows from (20) and Lemma 2.2 (a) that the corresponding
subsequence
converges to a vector
is the unique solution of the linear equation
cf. (8). Using f^ k g K ! 0 and taking the limit k !1 on the subset K, we then obtain from
(20) and (22) that
On the other hand, we get from (22), (10), property (P.3), (20), Lemma 2.3 (c), and
that
for all k 2 N su-ciently large. Using (20), this implies
is a continuously dierentiable function at due to (24), taking the
limit k !1 for k 2 K then gives
^x
^s
denotes the solution of the linear system (23).
Using (23) then gives
a contradiction to (24). Hence we cannot
have   > 0. 2
Due to Proposition 3.2, the assumed existence of an accumulation point in Theorem 3.3 is
automatically satised if there is a strictly feasible point for the optimality conditions (2).
An immediate consequence of Theorem 3.3 is the following result.
Corollary 3.4 Every accumulation point of a sequence fw k generated by
Algorithm 2.1 is a solution of the optimality conditions (2).
Proof. The short proof is essentially the same as in [14], for example, and we include it
here for the sake of completeness. | Let w be an accumulation point of the
sequence fw k K denote a subsequence converging to w  . Then
we have  k ! 0 in view of Theorem 3.3. Hence Lemma 2.3 (c) implies
i.e., we have x   0; s   0 and x
due to the denition of .
Lemma 2.3 (a) also shows that we have A T   we see that
indeed a solution of the optimality conditions (2). 2
We nally state our local rate of convergence result. Since our predictor step coincides with
the one by Burke and Xu [3], the proof of this result is essentially the same as in [3], and we
therefore omit the details here.
Theorem 3.5 Let the parameter  satisfy the inequality  > 2
n, assume that the optimality
conditions (2) have a unique solution w suppose that the sequence
generated by Algorithm 2.1 converges to w  . Then f k g converges
globally linearly and locally quadratically to zero.
The central observation in order to prove Theorem 3.5 is that the sequence of Jacobian
matrices  0 (w k ;  k ) converges to a nonsingular matrix under the assumption of Theorem 3.5.
In fact, as noted in [3, 12], the convergence of this sequence to a nonsingular Jacobian matrix
is equivalent to the unique solvability of the optimality conditions (2).
We implemented Algorithm 2.1 in C. In order to simplify the work, we took the PCx code
from [10, 9] and modied it in an appropriate way. PCx is a predictor-corrector interior-point
solver for linear programs, written in C and calling a FORTRAN subroutine in order to solve
certain linear systems using the sparse Cholesky method by Ng and Peyton [19]. Since the
linear systems occuring in Algorithm 2.1 have essentially the same structure as those arising
in interior-point methods, it was possible to use the numerical linear algebra part from PCx
for our implementation of Algorithm 2.1. We also apply the preprocessor from PCx before
starting our method.
The initial point w is the same as the one used for our numerical experiments
in [14] and was constructed in the following way:
(a) Solve AA T using a sparse Cholesky code in order to compute y 0
(b)
(c) Solve AA T using a sparse Cholesky code to compute  0
Note that this starting point is feasible in the sense that it satises the linear equations
b. Furthermore, the initial smoothing parameter was set to
i.e.,  0 is equal to the initial residual of the optimality conditions (2) (recall that the starting
vector satises the linear equations in (2) exactly, at least up to numerical inaccuracies). In
order to guarantee that however, we sometimes have to enlarge the value
of  0 so that it satises the inequalities
ng with x 0
Note that the same was done in [14]. We also took the stopping criterion from [14], i.e., we
terminate the iteration if one of the following conditions hold:
(a)
Finally, the centering parameter ^
k was chosen as follows: We let ^
0:1, start with ^
if the predictor step was successful (i.e., if we were allowed to take ^
otherwise. This strategy guarantees that all centering parameters belong to the interval
According to our experience, a larger value of usually gives faster convergence,
but the entire behaviour of our method becomes more unstable, whereas a smaller value of
the centering parameter gives a more stable behaviour, while the overall number of iterations
increases. The dynamic choice of ^
above tries to combine these observations in a
suitable way.
The remaining parameters from Step (S.0) of Algorithm 2.1 were chosen as follows:
We rst consider the function () :=  (this, more or less, corresponds to the method from
All test runs were done on a SUN Enterprise 450 with 480 MHz. Table 1 contains the
corresponding results, with the columns of Table 1 having the following meanings:
problem: name of the test problem in the netlib collection,
m: number of equality constraints (after preprocessing),
n: number of variables (after preprocessing),
k: number of iterations until termination,
P: number of accepted predictor steps,
value of  k at the nal iterate,
value of k(w k )k 1 at the nal iterate,
primal objective: value of the primal objective function at nal iterate.
Moreover, we give the number of iterations needed by the related method from [14] in
parantheses after the number of iterations used by our new method.

Table

1: Numerical results for Algorithm 2.1
problem objective
1.758e 04 5.50184589e+03
adlittle
aro
agg 390 477 22 (23) 17 3.8e 02 6.257e 04 3.59917673e+07
agg2 514 750 22 (25)
agg3 514 750 21 (30)
beaconfd 86 171 21 (18) 5.156e 04 3.35924858e+04
blend
3.652e 04 3.35213568e+02
4.166e 06 3.15018729e+02
bore3d 81 138 14 (28) 11 5.9e 3.980e
brandy 133 238 3.469e 04 1.51850990e+03
9.161e 04 2.69000997e+03
cycle 1420 2773
5.207e
d2q06c 2132 5728 48 (57)
d6cube 403 5443

Table

results for Algorithm 2.1
problem objective
degen2 2.901e
degen3
d
001 | | | (|) | | | |
f800 322 826 28 (36) 17 1.2e 5.876e 04 5.55679564e+05
nnis 438 935 20 (31) 17 2.0e 7.843e 04 1.72791066e+05
8.491e
t2d 7.494e 04 6.84642932e+04
9.397e
forplan 121 447 26 (28) 17 2.2e 4.722e 04 6.64218959e+02
ganges 1113 1510 20 (25) 19 2.4e 1.218e 04 1.09585736e+05
greenbea | | | (25) | | | |
greenbeb 1932 4154 43 (35) 13 1.7e 9.559e 04 4.30226026e+06
israel 174 316 17 (27) 15 1.0e 02 4.732e 04 8.96644822e+05
kb2 43 68 1.653e 06 1.74990013e+03
lot 133 346 23 (35) 12 3.2e 7.087e 04 2.52647043e+01
maros 655 1437 22 (37) 14 2.4e 1.738e 04 5.80637437e+04
8.053e 04 1.49718517e+06
3.330e 04 3.20619729e+02
nesm 654 2922 46 (52) 9 4.7e 04 4.718e 04 1.40760365e+07
perold 593 1374 26 (33) 12 2.1e 6.564e 04 9.38075527e+03
pilot 1368 4543 71 (81) 9 9.0e
pilot.ja 810 1804
pilot.we 701 2814 36 9.981e 04 2.72010753e+06
6.888e 04 2.58113924e+03
4.059e 04 4.49727619e+03
recipe 4.205e
2.793e
sc50a 8.546e
sc50b 48 76 7.714e 06 7.00000047e+01
1.049e 04 1.47534331e+07
4.563e 04 2.33138982e+06
6.230e 04 1.84167590e+04
1.834e 04 3.66602616e+04
9.098e 04 5.49012545e+04
scorpion 340 412 19 (21) 14 2.4e 04 1.815e 05 1.87812482e+03
2.169e 04 9.04293215e+02

Table

results for Algorithm 2.1
problem objective
7.203e 06 8.66666364e+00
3.131e
8.910e 06 1.41224999e+03
8.233e
1.051e
seba 448 901 19 (23) 12 2.5e 1.550e 06 1.57116000e+04
share1b 112 248 29 (43) 14 2.2e 3.762e 04 7.65893186e+04
share2b 96 162 8.099e
shell 487 1451 19 (22)
ship04l 292 1905 22 (20) 7.616e 04 1.79332454e+06
ship04s 216 1281 1.561e 04 1.79871470e+06
ship08l 470 3121 25 (21) 15 2.1e 7.592e 04 1.90905521e+06
ship08s 276 1604 15 (20) 13 3.0e 02 7.416e 04 1.92009821e+06
ship12l 610 4171 21 (21) 13 7.0e 2.670e 04 1.47018792e+06
ship12s 340 1943 7.548e
2.548e
stair 356 532
standata 314 796
standgub 314 796
standmps 422 1192 14 (18) 12 9.6e 4.418e
stocfor2 1980 2868 14
stocfor3 15362 22228 23 (63) 19 2.8e 04 5.514e 05 3.99767839e+04
stocfor3old 15362 22228 23 (70) 19 2.8e 04 5.514e 05 3.99767839e+04
truss 1000 8806 3.621e 04 4.58815785e+05
vtp.base

Table

clearly indicates that our current implementation works much better than our
previous code from [14]. In fact, for almost all examples we were able to reduce the number
of iterations considerably.
We nally state some results for the function () := giving
another complete list, however, we illustrate the typical behaviour of this method by presenting
the corresponding results for those test examples why lie between kb2 and scagr7
(this list includes the di-cult pilot* problems) in Table 2.

Table

2: Numerical results with quadratic function
problem objective
kb2 43 68 15 9 2.0e 2.458e
lot 133 346 22 9 3.0e 6.715e 04 2.52647449e+01
maros 655 1437 20 11 3.0e 3.805e 04 5.80637438e+04
9.450e 04 1.49718510e+06
modszk1 665 1599 26 11 2.5e 3.087e
nesm 654 2922
perold 593 1374 55 11 5.7e 05 2.585e 04 9.38075528e+03
pilot 1368 4543 53 7 1.4e 04 2.953e 04 5.57310815e+02
pilot.we 701 2814 43 4 9.8e 04 9.283e 04 2.72010754e+06
5.672e 04 2.58113925e+03
3.573e 04 4.49727619e+03
recipe 1.928e
1.193e 04 5.22020686e+01
sc50a 3.224e
sc50b 48 76 11 9 4.1e 4.955e
9.326e
Concluding Remarks
We have presented a class of smoothing-type methods for the solution of linear programs.
This class of methods has similar convergence properties as the one by Burke and Xu [3], for
example, but allows a more
exible choice for the updating of the smoothing parameter  .
The numerical results presented for our implementation of this smoothing-type method are
very encouraging and, in particular, signicantly better than for all previous implementa-
tions. The results also indicate that the precise updating of the smoothing parameter plays a
very important role for the overall behaviour of the methods. However, this subject certainly
needs to be investigated further.



--R

Introduction to Linear Programming.


A global and local superlinear continuation-smoothing method for P 0 and R 0 NCP or monotone NCP

A global linear and local quadratic noninterior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions
A class of smoothing functions for nonlinear and mixed complementarity problems.
Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities.
PCx: An interior-point code for linear programming
PCx User Guide.
Linear Programming and Extensions.
On the solution of linear programs by Jacobian smoothing methods.

Improved smoothing-type methods for the solution of linear programs
A special Newton-type optimization method
A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems
Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems
Some noninterior continuation methods for linear complementarity prob- lems
Block sparse Cholesky algorithm on advanced uniprocessor computers.
A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities.
Algorithms for solving equations.
Analysis of a non-interior continuation method based on Chen-Mangasarian smoothing functions for complementarity problems
bounds and superlinear convergence analysis of some Newton-type methods in optimization

--TR
Block sparse Cholesky algorithms on advanced uniprocessor computers
A non-interior-point continuation method for linear complementarity problems
A class of smoothing functions for nonlinear and mixed complementarity problems
Some Noninterior Continuation Methods for LinearComplementarity Problems
Primal-dual interior-point methods
Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities
A Global Linear and Local Quadratic Noninterior Continuation Method for Nonlinear Complementarity Problems Based on Chen--Mangasarian Smoothing Functions
A Global and Local Superlinear Continuation-Smoothing Method for <i>P</i><sub><FONT SIZE="-1">0</sub></FONT> and <i>R</i><sub><FONT SIZE="-1">0</sub></FONT> NCP or Monotone NCP
A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems
A Complexity Bound of a Predictor-Corrector Smoothing Method Using CHKS-Functions for Monotone LCP
global convergence;linear programs;central path;quadratic convergence;smoothing method