9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Numerical experiments with modern methods for large scale QP-problems

Numerical experiments with modern methods for large scale QP-problems

P. Spellucci

Technical University at Darmstadt, Department of Mathematics Schlo gartenstr. 7, D 64289 Darmstadt, Germany

We describe the outcome of numerical experiments using three approaches for solving convex QP-problems in standard form 1 xT Bx + bT x = min ; 2 AT x ? a = 0 ; (0.1) x 0; namely the unconstrained technique of Kanzow 14], the bound constrained technique of Friedlander, Mart nez and Santos 8] and the author's bound constrained quadratic extended Lagrangian 23]. These three methods solve (0.1) by a single unconstrained respectively bound constrained minimization. For our test purposes a test generator has been written which generates problems of this type with free choice of the condition number of the reduced Hessian, condition number of matrix of gradients of binding constraints and number of binding constraints. The exact solution is randomly generated. As a minimizer the new limited-memory BFGS-method (for bound constrained problems) of Byrd, Lu, Nocedal and Zhu 2] has been chosen. This allows using exactly the same minimization technology with exactly the same termination criteria to be used for all three approaches. It turns out that any of these methods is in considerable troubles if the QP-problem is only slightly illconditioned. We discuss the reasons why and possible remedies. With respect to computing e ort the method of Friedlander et al. turns out to be the best choice. But in all the "black box"-use of L BFGS B proves to be ine cient. Possible enhancements are indicated. We also shortly discuss the usage of interior point methods as an alternative. AMS subject classi cation. primary 90C20, secondary 65K05 Keywords. quadratic programming, QP, exact penalty function

!

Abstract

1 INTRODUCTION

The solution of large convex quadratic programs has interest in its own right, see e.g. 15], 19], and also in the context of large scale nonlinear programming using the SQP method. Large scale quadratic programs can be solved in a variety of ways. These may be classi ed as direct active set methods (primal or dual feasible), specialized multiplier methods or exact penalty function methods. The classical way is to satisfy equality and binding inequality constraints exactly during iteration using a projection or elimination technique 11]. This however makes necessary using a QR- or LU-decomposition of the Jacobian of those constraints or a decomposition of a matrix of a corresponding KKT-system, which may be very costly, if there is no favorable sparsity structure of the Jacobian which doesn't interfere with that of the Hessian of the objective. Inequality constraints may be handled by interior point methods too, e.g. 3], 10]. If there are only box constraints, the active set and the projected gradient technique can be combined to yield highly e cient methods 5], 18], 19], 24]. For problems of very high dimension and/or dense constraints these active set methods become untractable however. An alternative is to set up an exact di erentiable augmented Lagrangian to be minimized simultaneously with respect to the primal and the dual variables without any additional constraints 16]. This type of function however is not in the class C2 globally and not quadratic of course. Therefore e ciency of this approach is not so obvious. This is even more the case for exact penalty methods where the dual variables depend on the primal ones 12], 21]. 1

Using duality theory a general convex QP-problem may be transformed into a bound constrained one. This process involves solution of a linear equation with the Hessian as coe cient matrix for any intermediate value of the dual variable. In the general case this will be very costly again. However, if the Hessian is of a special structure (diagonal or block diagonal e. g.), this approach is very attractive. Relevant work has been done by Mangasarian 17]. If there are inequality constraints only, a bound constrained exact di erentiable quadratic penalty function can be obtained from the Wolfe dual problem. This has been shown by Han and Mangasarian in 13]. The determination of the corresponding penalty-parameter however is not an easy task. Numerical tests with this approach have been disappointing 6]. Recently Friedlander, Mart nez and Santos 8] showed, that the general convex QP-problem can be solved by nding one stationary point of a quartic function subject to bound constraints. This function is free of parameters. Kanzow 14] goes a step further and gives a transformation of a general convex QP into an completely unconstrained (nonconvex) minimization problem. Spellucci 23] gave an approach for transforming a general convex QP problem into a bound constrained convex one. His approach however involves the adaptive determination of two penaltyparameters. A method for doing this is given in 23], which works rather well. The relative merits of these approaches are unclear. The present paper describes the outcome of a numerical comparison of the last three named approaches. It turns out that none of these may be recommended as a general solver as they stand. Possible improvements and alternatives are discussed.

2 NOTATION

We brie y describe now the notation used in this paper. All matrices and vectors are real. Vectors are column vectors, if not explicitly transposed, T is the transposition symbol. If J is a subset of IN; AJ denotes the matrix composed from columns of A with indices in J and similarly xJ the subvector of x with indices in J . J BJ is a submatrix of the square matrix B with row and column indices from J . Superscripts on vectors denote elements of sequences. jj jj denotes the euclidean norm and its subordinate matrix norm. e is a vector of one's of a suitable dimension.

3 THE PROBLEM TO BE SOLVED

We consider the following type of problem:

! 1 f (x) = 2 xT Bx + bT x = min ; x2

(3.1) (3.2) (3.3) (3.4) (3.5)

where = fx 2 IRn : AT x ? a = 0; x 0g: Any convex QP can be written in this form. We assume

B = B T ; z T Bz > 0 for all z 6= 0 such that AT z = 0; A 2 IRn m ; m < n; rank (A) = m; 9x0 : Ax0 = a; x0 > 0:

Under these hypotheses, the problem has an unique solution x with bounded multipliers ; . (Since the Slater condition (3.5) implies the Mangasarian-Fromowitz condition). The necessary and su cient optimality conditions for (3.1) read

Bx + b ? A ? = 0; x 0; 0; xi i = 0 for i 2 f1; : : :; ng; AT x ? a = 0:

2

(3.6) (3.7) (3.8)

Neglecting the positivity constraints these may be written as a nonlinear system of equations, using

X def diag(x1 ; : : : ; xn ) = 0 Bx + b ? A ? AT x ? a F (x; ; ) = @ X

1 A

= 0:

The sensitivity of the solution triple (x ; ; ) is determined by the condition number of the Jacobian of F at the solution. This reads

JF (x; ; ) =

0 B ?A ?I 1 @ AT O O A :

O X

Evaluated at the solution the term X cancels out because of the complementarity condition. For special choices of B and A it is possible to compute these eigenvalues explicitly. This will be done in discussing the numerical results. Given the conditions above it is also possible to transform the problem into one with inequality constraints only. This is the content of the following

JF is the root of the quotient of the largest by the smallest of the eigenvalues of JFT JF . This matrix computes as 0 B2 + AAT + 2 ?BA ?B + X 1 ?AT B AT A AT A : JFT JF (x; ; ) = @ (3.9) ?B + X A I + X2

is the diagonal matrix with entries i . If we use the 2-norm, then the condition number of the matrix

Theorem 3.1 Consider the extended QP-problem

1 ! f (x) + w + 2 w2 = min x2 ~ ~ = f(x; w) 2 IRn+1 : AT x ? a + we 0; ?AT x + a + we 0; x 0; w 0g :

If (x ; ; ) is a Kuhn-Tucker-triple for problem (3.1) and there holds

(3.10) (3.11)

> jj jj1

then problem (3.10) has the solution (x ; 0). Conversely, if problem (3.10) has a solution (x ; w ) with w = 0, then x is a solution of (3.1) with multipliers

= + ? ?

corresponding to the equality constraints, where + and ? are the multipliers for the rst to sets of inequalities describing ~ in (3.11).

in this case are necessary and su cient characterizations of the solution. 2 Therefore we might use interior point methods in order to solve problem (3.1). This might be an attractive alternative to the methods mentioned rst. For the solution of (3.1) we consider the method of Friedlander, Mart nez and Santos 8], the exact penalty function method of Kanzow 14] and the exact quadratic augmented Lagrangian of Spellucci, 23]. We compare the numerical results with those obtained by tranforming the problem according theorem 3.1 followed by a subsequent solution using a shifted logarithmic barrier function method based on work of Polyak 22], Conn, Gould and Toint 4], which is fully described in 7]. We compile the properties of these approaches here and refer the reader to the original papers for the proofs. 3

Proof: The proof follows directly from considering the corresponding Kuhn-Tucker-conditions, which

4 THE METHOD OF FRIEDLANDER, MARTINEZ AND SANTOS

The essence of this approach is given by

Theorem 4.1 In addition to the assumptions of section 3 let be bounded. Then x solves (3.1) with some multipliers ; if and only if the triple (x ; ; ) is a stationary point of the problem ? ! (4.1) M (x; ; ) = 1 jjBx + b ? A ? jj2 + jjAT x ? ajj2 + (xT )2 = x min 0 : 0; 2 Any stationary point of this problem yields a global minimizer of M . Remarks:

2

1. For the proof of theorem 4.1 boundedness of is essential. 2. M is a nonconvex quartic. Therefore this approach transforms a QP-problem into a more general bound constrained nonconvex one. 3. The intersection of the level sets of M with the feasible domain may be unbounded even for B positive de nite. E.g. for the problem 1 2 ! 2 x = min subject to x ? 1 = 0; x 0 we get M (x; ; ) = ((x ? ? )2 + (x ? 1)2 + x2 2)=2 with M (0; ? ; ) 1=2 for 0. 4. If the multipliers of (3.1) are nonunique, then the problem (4.1) will have nonunique solutions. 5. The Hessian of M reads 0 B2 + AAT + T ?BA ?B + xT 1 A: ?AT B AT A AT r2 M = @ (4.2) T T ?B + x A I + xx Its properties will be discussed later.

5 KANZOW'S UNCONSTRAINED FUNCTION

In the paper 14] Kanzow gave a function which allows the solution of problem (3.1) by a single unconstrained minimization. We extend his results a little showing

Theorem 5.1 Consider the problem

! (xi ; i ) = min ; K (x; ; ) = 1 jjBx + b ? A ? jj2 + jjAT x ? ajj2 + 2 i=1

?

n X

(5.1)

where The following holds:

( ; ) = (

p

2+ 2?

? )2 :

1. If x is a solution of (3.1) with multipliers ; , then (x ; ; ) solves (5.1). 2. Any stationary point of K is a global minimizer of K .

4

3. If the feasible domain of (3.1) is bounded, then K has a stationary point. 4. If strict complementarity and constraint regularity hold at (x ; ; ) and the projection of B on the kernel of AT is positive de nite, then the Hessian r2K is positive de nite there.

that is in nitely di erentiable as long as is arguments do not vanish simultaneously. By the strict complementarity assumption this is excluded. Without loss of generality let us assume that

Proof : The rst three assertions are shown in 14]. In order to show the fourth we rst observe

xi = 0 for i = 1; : : : ; j0 and > 0 otherwise :

By assumption the matrix

is of full rank. An easy computation yields

def

N def (A; If1;:::;j0 g ) =

HK = r2K (x ; ; ) =

where

0 B2 + AAT + J ?BA ?B 1 @ ?AT B 0 AT A AT A

?B

A I + J0

(5.2)

J0 = diag(1 ? sign(xi )) ; J0 = I ? J0 and sign(0) = 0 of course. Let z 2 IR2n+m be partitioned according to the partitioning of r2K , z T = (uT ; vT ; wT ) : We have to show that z T HK z > 0 for z 6= 0. We compute z T HK z = jjBu ? Av ? wjj2 + jjJ0 ujj2 + jjJ0wjj2 + jjAT ujj2 : Assume z T HK z = 0. Then J0 u = 0 ; J0 w = 0 ; AT u = 0 ; Bu ? Av = J0 w ; since I = J0 + J0. Obviously uT w = 0 : Hence uT Bu = 0 and since B is positive semide nite, we get Bu = 0 :

This in turn implies and by the regularity assumption Therefore Let and (A; If1;:::;j0 g )

v wf1;:::;j0 g

= 0

v = 0; J0w = 0 : w = 0:

QA =

R O

with Q unitary and R upper triangular

s = Qu :

5

Then

0 = AT u = AT QT Qu = (RT ; O)s ; hence s = J0 s and u = QT J0s. But

T 0 = uT Bu = sT J0 QBQT J0s:

2 Since by assumption B is positive de nite on the kernel of AT and J0 = J0 we get

J0 s = 0 ; hence s = 0 ; hence u = 0 :

This yields z = 0 as required.

Remarks :

2

1. K is globally in C 1 and in C 1 as long as xi + i > 0 8i. 2. K is nonconvex and behaves strongly nonquadratic, although its growth-behaviour is quadratic. A picture of clari es this.

gure 1

3. K has unbounded level sets even if B is positive de nite. The example due to Kanzow, used already in the previous section, gives

K (x; ; ) = ((x ? ? )2 + (x ? 1)2 + ( x2 +

with K (0; ? ; ) 1=2 for 0.

p

2?x?

)2 )=2

6

gure 2

4. If the QP-multipliers are nonunique, then K will have a continuum of global minimizers.

6 SPELLUCCI'S EXACT QUADRATIC AUGMENTED LAGRANGIAN SUBJECT TO BOUND CONSTRAINTS

This follows the ideas of Lucidi 16] to form an exact di erentiable augmented Lagrangian. However, the sign of the ordinary Lagrangian has to be reversed here to obtain convexity. We let

L(x; ; ) = f (x) ? T (AT x ? a) ? T x

(x; ; ; %; ) = ?L(x; ; ) + % kAT x ? ak2 + 2 kBx + b ? A ? k2: 2 This augmented Lagrangian is to be jointly minimized with respect to x; ; under the constraints x 0, 0. For suitable %; > 0 is convex and bounded from below on the set ~ = IR2n+m \ fx; : x 0; 0g: is an ordinary quadratic function of x; ; . So the highly e cient methods of e.g. 5], 18], 19], 24] are available to minimize . Under the assumptions (3.3), (3.4), (3.5) the problem (3.1), (3.2) is equivalent to problem (6.1), (6.2):

! (x; ; ; %; ) = min ~ ; (x; ; )2 ~ = f(x; ; ) : x 0; 0g:

and

(6.1) (6.2)

More precisely we have

7

Theorem 6.1 Let the assumptions of section 3 be satis ed. Then for every % > 0 and

>

0

def

u u = jjmax uT Z T BZu ujj=1

T

where Z is an orthonormal basis of the kernel of AT is convex and the intersection of the level sets of with ~ are bounded. x solves (3.1) with multipliers ; if and only if (x ; ; ) solves (6.1), (6.2).

Proof: The proof may be found in 23]. The Hessian of reads

2

0 T 2 B ?B + %AA + B A ? BA I ? B r2 = B A T ? A T B B AT A AT I @

I? B A I

1 C C: C A

(6.3)

Remarks:

1. is an ordinary quadratic. E cient algorithms for minimizing convex quadratics subject to bound constraints are well known, see e.g. 18]. 2. The result of the previous theorem can be extended to the case of an inde nite B , provided Z T BZ positive de nite, see 23]. This however requires an additional and larger lower bound for the parameter %, namely ? 1 + jjBjj + jjBjj2=( 1 ? 1 ) = minf 2g ; (6.4) %

0

i

i

where i are the singular values of A. 3. Since the minimal eigenvalue 1= 0 of Z T BZ is unknown in practice, an algorithm for its adaptive estimation must be devised. Such an algorithm is given in 23], which works reasonable and is used in our experiments too. 4. If the feasible set of (3.1) is empty, then is unbounded from below, see the example below. This is a disadvantage compared with the functions M and K . 5. If the matrix (A; IA ), where A = fi : xi = 0g, is of full rank, then the multipliers ; are unique. Because of equivalence of solutions, will have an unique minimizer on ~ . Moreover the projected Hessian of is positive de nite in this case (provided ?I + B + %AAT positive de nite of course).

2

Let us give a little example: Example: Let n = 2; m = 1.

B =

?1 0 ; AT = ? 2 1 ; a = (?1) ; b = 0 1

0 0

:

Clearly, there is no x 0 such that 2x1 + x2 + 1 = 0 and therefore we expect the method to fail for every ; % > 0, that is, is not bounded from below. The singular value of A and the minimal eigenvalue 1= 0 of the projected Hessian (with respect to the equalities) compute as p 3 1= 0 = 5 : 1 = 5; 8

From this data we can compute 0 and 0( ) using (6.4). Computing we obtain 1 (x; ; ) = ? 2 (?(x1 )2 + (x2 )2) ? x1 1 ? x2 2 ? (2x1 + x2 + 1) % (2x1 + x2 + 1)2 + ((x1 + 2 + 1 )2 + (x2 ? ? 2 )2) +2 2

with the constraints x1 0; x2 0; 1 0; 2 0. x1 = x2 = 0; 1 = ?2 ; 2 = ? ; 0 is feasible and for ! ?1 we obtain ! ?1, regardless how large ; % are chosen, as expected. If we change a to become a = 1; the problem becomes feasible. The unique optimal solution is 1 = ? 1 ; 1 = 0; 2 = 1 : x1 = 2 ; x2 = 0; 4 4 Now reads 1 (x; ; ) = ? 2 (?(x1 )2 + (x2 )2 ) ? x1 1 ? x2 2 ? (2x1 + x2 ? 1) + % (2x1 + x2 ? 1)2 + 2 ((x1 + 2 + 1 )2 + (x2 ? ? 2)2 ): 2

We get

0 x + + 2 + 2%(2x + x ? 1) + (x + 2 + ) 1 1 B ?x2 +1 2 + + %(2x11 + x22 ? 1) + (x12 ? ? 21) C B C r (x; ; ) = B 2x1 + x2 ? 1 + (2(x1 + 2 + 1) ? (x2 ? ? 2)) C ; B C @ A x1 + (x1 + 2 + 1 )

x2 ? (x2 ? ? 2)

r (x ; ; ) = (0; 0; 0; 1 ; 0)T ; 2

0 1 + 4% + 2% B 2% %+ ?1 B 1? r2 (x; ; ) = B 2 + 2 B 1+ @ 0

0 1? For > 0 = 5 and 3

2+2 1? 5 2

1+ 0 2 0

1 1? C C : C C 0 A

0

r2 will be positive semide nite with exactly one eigenvalue 0 . The corresponding eigenvector has the form (0; 0; 1; ?2; 1)T . This is not a direction to in nity in ~ . Using x def (x; ; ) and r ( x ) =

given above we get

1 ( x ) = ( x ) + r ( x )T ( x ? x ) + 2 ( x ? x )T r2 ( x )( x ? x ) 1 1 ( x )+ 2 ( x ) for 1 0 : But 1 0 for x 2 ~ . Clearly x minimizes on ~ . 2 For Kanzow's example we get 1 (x; ; ) = 2 (% + ? 1)x2 + (1 ? )(x + x ) + + 2 ( 2 + 2 ) ? ? %x ? % 2 and for = 1 + ; > 0 its Hessian is positive semide nite with an eigenvector (0; ? ; ) for the single eigenvalue 0. If ! 1 along this direction, then grows linearly to 1.

3 % > %0( ) = 1 ( 5 + 1 + 3 16 5 ) 5 ?

9

gure 3

7 THE OPTIMIZER

Any of the three approaches discussed above leads to an high dimensional bound constrained or unconstrained problem. It is well known that di erent implementations of even the same algorithm may yield quite di erent reliability and e ciency scores. In order to avoid such e ects we decided to use one and the same minimization code for these three approaches. Since we have high dimensional applications in mind we choose the limited memory bound constrained method of Byrd, Lu, Nocedal and Zhu 2] which may be used e ciently for unconstrained minimization, too. We used the original implementation obtainable now via netlib with the exception of setting the internal parameter "gtol" to 0:1, i.e. requiring a more precise step size selection, which worked better. The method uses a new representation of the BFGS-update in a limited memory fashion, using back values of the vector sk?j ; yk?j ; j = 0; : : : ; p ? 1 for some selected p. For details see the original paper and 1]. The termination criteria used and other details have been completely identical, the di erences lying in the evaluation of the function and its gradient only. The algorithm for adapting the penalty parameters for Spellucci's function is located in the routine which evaluates the function. A restart is issued if these parameters have been changed. Based on the results in 2] we used the parameters ISBMIN=1 and p = 5; 15 in our tests. The code uses the following termination criteria ( with f representing the function to be minimized) : 1: jfnew ? fcur j 1(1 + jfcur j) ; 1 = 10?13 : This is the internal criterion of L BFGS B with factr = 103. This case is indicated by a "1" in the tables below. 2: jjPrf jj 2(1 + jjrf jj) ; 2 = 10?6 ; where P denotes projection on the box (the identity for Kanzows function). This case is indicated by a "0" below. 10

3: Too many iterations (currently that means more than 90000), indicated by a "-1" or failure of convexifying ( or becoming huge, i.e. larger than 1013), indicated by "-2". .

8 THE PROBLEM GENERATOR

In order to be able to control precision and condition-dependency of the di erent methods we decided to use arti cially generated test cases of the form (3.1). At rst we generated the solution (x ; ; ) of the problem using uniformly distributed pseudo-random numbers in given intervals:

xi 2

if i = 1; : : : ; j0 if i = j0 + 1; : : : ; n i 2 ?1; 1] 8 i = 1; : : : ; m min; 1] if i = 1; : : : ; j0 i 2 f0g if i = j0 + 1; : : : ; n ;

min; 1]

f0g

(8.1)

where 0 < min < 1 and j0 gives the number of xi equal to zero in the solution1. In a second step the eigenvalues i of the matrix B and the singular values i of A where generated at random with

i i

2 2

min; 1]

min; 1]

8 i = 1; : : : ; n 8 i = 1; : : : ; m

but but

m+1 = min

; n?j0 = 1 1 = min ; m = 1;

(8.2)

where 0 < min; min < 1. Hence the condition numbers of the matrices B and A are exactly 1= min and 1= min respectively. Given these we can de ne A by a singular values decomposition and B by a spectral decomposition ^ A = U 0 V T and B = U BU T ; (8.3)

^ where is the diagonal matrix of the singular values i and B the diagonal matrix of the generated eigenvalues i . U and V are made up from Householderpre ectors represented by vectors u 1] 2 IRm ; u 2] 2 IRn?m?j0 ; u 3] 2 IRj0 and v 2 IRm of length 2 each:

0 U =@

Im ? u 1](u 1])T

0 0

In?m?j0 ? u 2](u 2])T

0

0

Ij0 ? u 3](u 3])T

0 0

1 A

and V = Im ? vvT : (8.4)

For later reference we write U in block form

U =

0O O U 1 III @ O UII O A :

UI O O

Note that V is symmectric and UU T = In and V V = Im . The vectors u 1] ; u 2] ; u 3] and v are also generated at random. In a last step we compute b and a such that

Bx + b ? A ? = 0 AT x ? a = 0

1

(8.5)

note that n m + j must be satis ed in order to have x a regular point (multipliers unique)

0

11

hold. Using this we exactly know the true (unique) solution as well as the condition number of the constraints and the reduced Hessian (see below).

Theorem 8.1 If n m + j0 and the matrix A is de ned by (8.3) with all singular values i > 0 (i =

1; : : : ; m), then x is a regular point and therefore the Lagrange multipliers are unique.

Proof: In the solution x the constraints h(x) := AT x ? a = 0 and gi (x) := xi = 0 8 i = 1; : : : ; j0

(8.6)

are binding. Therefore we have to show that the matrix ?rh(x )jrg ? (8.7) f1;:::;j0g (x ) = AjIf1;:::;j0 g has linearly independent columns, where If1;:::;j0 g is the submatrix with columns 1; : : : ; j0 from the unit matrix I 2 IRn n . By (8.3) and (8.4) we have that 0 1 0 A: 0 ? A=@ ? (8.8) 1] (u 1])T T Im ? u Im ? vv Therefore (8.7) becomes 0 1 Ij0 0 ?AjI 0 ? 0 A: (8.9) f1;:::;j0 g = @ ? 1] (u 1])T T Im ? u Im ? vv 0 But (8.9) has linearly independent columns because Im ? u 1](u 1])T struction and n m + j0. This generator was run with the values

?

?I ? vvT m

is regular by con-

2

n 2 f1000; 2000; : : :; 10000g ; (m; j0) 2 f(n=10; n=10); (9n=10; 9n=100)g ; min = min = min 2 f0:1; 0:01; 0:001; 0:0001g ; p 2 f5; 15g : Hence each of the methods has been tested using 160 testcases, with conditioning varying from "good" to "mildly illconditioned". All these testcases all well-scaled. The combination (n; n=10; n=10) yields a problem with a large number of free primal variables varying from 800 to 8000, whereas the combination (n; 9n=10; 9n=100) yields 10 to 100 free primal variables. p is the number of back values used. Theoretically one might conclude that a large p should be "good". The variables were initialized as follows: x0 = (1; : : : ; 1)T ; 0 = (0; : : : ; 0)T ; 0 = (1; : : : ; 1)T : The outcome is discussed in the next section.

1: We always have n > m + j0 in our examples. Hence the primal as well as the dual solution is unique. Due to the special structure of the examples we also know the projected Hessians of Friedlander-Mart nez-Santos' and Spellucci's function. These read, after a unitary block-diagonal similarity transformation with the matrix

Remarks:

0 UT O O O II B O UIT O O B O O VT O @

O O O I

12

1 C C A

(r2M )T;proj (r2 )T;proj

=

0 B2 ^II O B O BI2 + ^ B @ ^ 0 B B @

=

O 2 OC; C 2 O ? BI OA O O O I 2 ^ ^ ?BII + BII O ^ I + BI + % 2 ^2 O ?B ^ O ? BI O O

O ^ ?BI

1

(8.10)

O ^ ? BI O

2

O O O I

1 C: C A

(8.11)

The eigenvalues of these matrices can be computed formally. They are

for (r2 M )T;proj and

; i = m + 1; : : : ; n ? m ? j0 ; 1 with multiplicity j0 ; 1 2 + 2 q 2 2 + 4=4 ; i = 1; : : : ; m i i i 2 i i

i

2

? i+

i

2

; i = m + 1; : : : ; n ? m ? j0

2 2 2 i + i ) + % i ? i)

1( ( 2 q 2 2 ( ( i + i ) + % i2 ? i )2=4 +

with multiplicity j0 ;

i (1 ?

2

i?

% i2 ) ;

i = 1; : : : ; m :

for (r2 )T;proj . E.g. if m = m = 10?4 and = 2 104; % = 1 we get eigenvalue pairs (2:6 10?8; 3:8 10?9) and (2:6 10?4; 3:8 10?5) respectively and of course eigenvalues 1 and 2 104. Generally speaking with in the order of 2= min and % = 1 both matrices have essentially the same conditioning. For Kanzows function there is no projection of course. After a unitary similarity transformation with the block-diagonal matrix diag(U T ; V T ; U T ) this becomes 0 B2 + 2 O 1 ^I ^ ^ O ?BI ?BI O O B O ^2 ^ BII O O O ?BII O C B C B O ^III + I O ^ C O B O O ?BIII C B 2 (r2 K )T = B ?BI (8.12) B ^ O O O O C: C B ?BI B ^ C O O 2I O O C B O ?B C ^II @ O O O 2I O A ^ O O ?BIII O O O I Here ^ BI = diag( 1 ; : : : ; m ) ; ^ BII = diag( m+1; : : : ; n?j0 ) ; ^ BIII = diag( n?j0 +1; : : : ; n ) : The eigenvalues of this matrix can also be computed formally, the resulting formulas being a little involved. We prefer to give some speci c values. E.g. with m = m = 10?4 we get an eigenvalue triple (2; 1:7 10?8; 2:9 10?9) and with n?j0 = 10?4 a pair (2 + 5 10?9; 5 10?9). T Using the same similarity transformation we can also represent the matrix JF JF (x; ; ) (see

13

(3.9)) as

T (JF JF (x ; ; ))T

0 B2 + 2 O ^ ^ O ? BI B IO 2 ^ BII O O B B O ^III + D1 O O B B 2 = B ?BI O O B ^ B ?BI ^ B O O B O ?B ^II @ O O

O O

^ ?BIII

O

O O ^ O ?BII O ^ O O ?BIII O O I + D2 O O O I + D3 O O O I

^ ?BI

1 C C C C C; C C C C A

where

T D1 = UIII diag( 1 ; : : : ; j0 )UIII ; D2 = UIT diag(xn?m+1 ; : : : ; xn )UI ; T D3 = UII diag(xj0 +1 ; : : : ; xn?m )UII :

(8.13)

We observe that both matrices are quite similar and even identical if all nonzero components of x and are equal to one. Using these representations it is obvious that the three approaches considered essential square the conditioning of the problem. Spellucci's approach will also severely be a ected by a bad choice of the penalty parameters. 2: The problems generated are all well scaled. From the representation of the Hessians given above it is obvious, that di erent scalings in B and A will a ect the conditioning strongly. 3: The matrices B and A are dense. Because of their special structure it nevertheless requires only O(n) operations to evaluate any one of the functions or its gradient. This corresponds to a very sparse real-life application.

2

9 AN INTERIOR POINT APPROACH

Using theorem 3.1 we may transform our problem into an inequality constrained QP-problem of the form 1 ~ b ! (9.1) f (x) = 2 xT Bx + ~T x = min subject to c(x) = C T x + c0 0 : Problems of this type may be solved e ciently by interior point methods. We decided to use an implementation of a shifted log-barrier approach (see 22], 4], 7]). Here the function

r X (x; ; s) def f (x) ? = i log(ci (x) + si ) i=1

(9.2)

is minimized with respect to x for given parameter-vectors > 0 and s > 0. r is the number of components of inequalities c, r = n + 2m + 1 here. A sequence of weights k and shifts sk has to be constructed such that sk & s 0; k ! 0; suitably and xk is de ned as an approximate minimizer of the (convex) function (:; k ; sk ) on Sk = fx 2 IRn : c(x) + sk > 0g. Given xk , multiplier estimates are computed from ~k def i = and new weights by

ci (xk ) + sk ; i :

k i

(9.3)

k+1 = ~ k sk+1 i i i

14

( and of (3.6) may be recovered from ~.) If the problem (9.1) satis es the regularity condition, the strict complementarity condition and the second order su ciency condition, convergence of this process can be shown, see 22]. The Hessian of reads

i r2 (x; k ; sk ) = B + Cdiag( (c (x) + sk )2 )C T : x i i k

(9.4)

~k ! ~ and xk ! x r0 of the eigenvalues of r2 tend to in nity (if s = 0) or become very large at least (since the nonzero x components of s will be small), where r0 is the number of binding constraints. This is a disadvantage of this approach, which however is not too pronounced in practice, since the iteration is terminated if the optimality criteria of the original problem are satis ed to su cient precision. The approximate minimizer xk is determined by a truncated Newton-iteration based on the Lanczos-process, the details of which may be found in 7].

As

10 NUMERICAL RESULTS

The complete and detailed list of results is to be found in the appendix. Here we present an overwiew only, showing precision's obtained and computing time needed. Since nal precision is determined primarily by the conditioning of the problem, we have collected the problems into four classes corresponding the value of min, since min = min = min. Since we have 10 choices for n and two choices of p and m each, there are 40 problems in each class and hence a total of 160 testcases. The meaning of the headings is DXR : jjx ? xcomp jj=jjx jj, DLR : jj ? comp jj=jj jj, DMR : jj ? comp jj=jj jj. Results for Friedlander & al. method, values based on 40 runs each 10?1 10?2 10?3 10?4

min

DXR 2

5 3 1 3

10?6; 4 10?4; 3 10?3; 1 10?3; 3

10?5] 10?3] 10?2] 10?2]

DMR 2 DLR 2 6 10?5; 1 10?3] 7 10?7; 3 10?5] 5 10?2; 0:1] 1 10?5; 3 10?3] ?2; 0:1] 8 10 2 10?5; 0:03] 0:09; 0:2] 3 10?5; 0:06]

The summarized results concerning the precision obtained with Spellucci's approach are given in the following table. The method showed 10 failures, where more than 90000 steps were needed without reaching the desired precision: Results for Spellucci's method based on 40 runs each (with 10 failures) 10?1 10?2 10?3 10?4

min

DXR 2

1 7 2 3

10?6; 2 10?5] 10?5; 3 10?4] 10?4; 0:1] 10?3; 0:3]

DMR 2 DLR 2 2 10?5; 3 10?4] 2 10?11; 3 10?6] 5 10?3; 4 10?2] 4 10?12; 1 10?6] 0:05; 0:09] 6 10?12; 0:02] 0:04; 0:09] 2 10?11; 0:04]

For Kanzow's method the summarized results are Results for Kanzows method based on 40 runs each (with 1 failure) 10?1 10?2 10?3 10?4

min

DXR 2

2 2 7 1

10?5; 1 10?3; 2 10?3; 4 10?2; 5

10?2] 10?2] 10?2] 10?2]

DMR 2 DLR 2 4 10?4; 1 10?2] 9 10?8; 3 10?2] 0:2; 0:3] 6 10?3; 8 10?2] 0:1; 0:2] 8 10?3; 0:1] 0:1; 0:3] 6 10?3; 0:1]

15

Here we observe a disappointing low precision also for the very well conditioned cases (the algorithm terminated with the internal termination criterion in these cases due to extremely slow progress in the function value). Results for the interior point method based on 20 runs each (since there is no variable p)

min 10?1 10?2 10?3 10?4

DXR 2

4 3 2 3

10?7; 7 10?4; 6 10?3; 8 10?3; 3

10?6] 10?2] 10?2] 10?2]

DMR 2 DLR 2 ?6; 1 10?4] 1 10?9; 7 10?6] 2 10 0:03; 0:3] 2 10?6; 0:1] 0:05; 0:3] 5 10?5; 0:1] 0:04; 0:3] 2 10?5; 0:1]

Here the precision for the primal variables is a bit better, whereas for the dual ones it is disappointing again. Computing time is shown in the following table. The meaning of the headings is as follows: N=number of primal variables, M=number of equations (i.e. 2N+M=number of primal and dual variables), J0=number of binding bounds on the primal variables, I2 f1; 2; 3; 4g : min = min = min = 10?I . F following a number means termination with more than 90000 steps without reaching the desired precision. There are two lines for each combination of N, M, J0, I, the rst is for p = 5 and the second for p = 15. For the interior point method there is no second entry of course. FMS stands for the Friedlander et.al., SPE for Spellucci's, KAN for Kanzow's and INTP for the interior point method. Time is in seconds for a HP9000/735/135 using a f77 -K +O3 compiler call.

N 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 3000 M 100 100 100 100 100 100 100 100 900 900 900 900 900 900 900 900 200 200 200 200 200 200 200 200 1800 1800 1800 1800 1800 1800 1800 1800 300 J0 100 100 100 100 100 100 100 100 90 90 90 90 90 90 90 90 200 200 200 200 200 200 200 200 180 180 180 180 180 180 180 180 300 I 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 FMS .19E+02 .36E+02 .32E+02 .74E+02 .73E+02 .16E+03 .59E+02 .12E+03 .36E+02 .83E+02 .16E+03 .27E+03 .14E+03 .31E+03 .15E+03 .30E+03 .41E+02 .84E+02 .15E+03 .29E+03 .25E+03 .50E+03 .27E+03 .46E+03 .10E+03 .24E+03 .44E+03 .93E+03 .48E+03 .12E+04 .51E+03 .11E+04 .97E+02 SPEL .19E+02 .47E+02 .13E+03 .39E+03 .34E+03 .45E+03 .66E+03 .75E+03 .31E+02 .94E+02 .35E+03 .97E+03 .39E+03 .10E+04 .52E+03 .13E+04 .61E+02 .12E+03 .23E+03 .62E+03 .49E+04 .40E+04 .59E+04 .21E+04 .11E+03 .31E+03 .69E+03 .16E+04 .99E+03 .27E+04 .17E+04 .34E+04 .13E+03 KAN .12E+03 .40E+03 .13E+03 .27E+03 .12E+03 .41E+03 .12E+03 .29E+03 .71E+03 .94E+03 .75E+03 .20E+04 .67E+03 .15E+04 .49E+03 .16E+04 .39E+03 .60E+03 .46E+03 .13E+04 .27E+03 .63E+03 .34E+03 .83E+03 .15E+04 .45E+04 .20E+04 .39E+04 .17E+04 .31E+04 .15E+04 .30E+04 .15E+04 INTP .76E+01 .11E+02 .43E+02 .57E+02 .14E+02 .15E+02 .14E+02 .17E+02 .17E+02 .35E+02 .47E+02 .18E+03 .33E+02 .35E+02 .53E+02 .56E+02 .45E+02

16

3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 6000 6000 6000 6000 6000 6000 6000 6000

300 300 300 300 300 300 300 2700 2700 2700 2700 2700 2700 2700 2700 400 400 400 400 400 400 400 400 3600 3600 3600 3600 3600 3600 3600 3600 500 500 500 500 500 500 500 500 4500 4500 4500 4500 4500 4500 4500 4500 600 600 600 600 600 600 600 600

300 300 300 300 300 300 300 270 270 270 270 270 270 270 270 400 400 400 400 400 400 400 400 360 360 360 360 360 360 360 360 500 500 500 500 500 500 500 500 450 450 450 450 450 450 450 450 600 600 600 600 600 600 600 600

1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4

.15E+03 .36E+03 .60E+03 .34E+03 .63E+03 .34E+03 .53E+03 .21E+03 .43E+03 .10E+04 .18E+04 .10E+04 .19E+04 .95E+03 .18E+04 .14E+03 .21E+03 .47E+03 .64E+03 .53E+03 .10E+04 .60E+03 .11E+04 .38E+03 .77E+03 .14E+04 .28E+04 .15E+04 .27E+04 .17E+04 .32E+04 .20E+03 .36E+03 .10E+04 .13E+04 .11E+04 .16E+04 .96E+03 .16E+04 .52E+03 .10E+04 .23E+04 .41E+04 .29E+04 .44E+04 .29E+04 .50E+04 .24E+03 .47E+03 .12E+04 .17E+04 .97E+03 .16E+04 .10E+04 .18E+04

.24E+03 .75E+03 .21E+04 .39E+04 .27E+05F .37E+04 .32E+04 .20E+03 .47E+03 .16E+04 .30E+04 .10E+05 .74E+04 .11E+05 .70E+04 .15E+03 .37E+03 .12E+04 .24E+04 .44E+03 .56E+04 .23E+04 .60E+04 .30E+03 .72E+03 .23E+04 .60E+04 .55E+04 .92E+04 .41E+04 .70E+04 .22E+03 .49E+03 .13E+04 .24E+04 .55E+04 .73E+04 .45E+04 .84E+04 .41E+03 .90E+03 .28E+04 .62E+04 .37E+05F .67E+05 .37E+05F .71E+05F .39E+03 .82E+03 .17E+04 .32E+04 .20E+05 .18E+05 .28E+05F .55E+05F

.13E+04 .95E+03 .19E+04 .12E+04 .22E+04 .14E+04 .19E+04 .51E+04 .87E+04 .65E+04 .92E+04 .45E+04 .85E+04 .46E+04 .82E+04 .16E+04 .90E+04 .10E+05 .81E+04 .19E+04 .35E+04 .16E+04 .52E+04 .11E+05 .20E+05 .55E+04 .98E+04 .70E+04 .12E+05 .79E+04 .13E+05 .13E+04 .19E+04 .86E+04 .56E+04 .24E+04 .46E+04 .29E+04 .41E+04 .17E+05 .43E+05 .12E+05 .22E+05 .74E+04 .14E+05 .64E+04 .14E+05 .29E+04 .11E+05 .18E+05 .14E+05 .41E+04 .71E+04 .42E+04 .72E+04

.44E+02 .47E+02 .48E+02 .60E+02 .74E+02 .12E+03 .12E+03 .54E+02 .86E+02 .25E+03 .45E+03 .85E+02 .13E+03 .17E+03 .12E+03 .75E+02 .12E+03 .32E+03 .40E+03 .12E+03 .17E+03 .27E+03 .23E+03 .90E+02 .15E+03 .34E+03 .38E+03

17

6000 6000 6000 6000 6000 6000 6000 6000 7000 7000 7000 7000 7000 7000 7000 7000 7000 7000 7000 7000 7000 7000 7000 7000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 9000 9000 9000 9000 9000 9000 9000 9000 9000 9000 9000 9000 9000 9000 9000

5400 5400 5400 5400 5400 5400 5400 5400 700 700 700 700 700 700 700 700 6300 6300 6300 6300 6300 6300 6300 6300 800 800 800 800 800 800 800 800 7200 7200 7200 7200 7200 7200 7200 7200 900 900 900 900 900 900 900 900 8100 8100 8100 8100 8100 8100 8100

540 540 540 540 540 540 540 540 700 700 700 700 700 700 700 700 630 630 630 630 630 630 630 630 800 800 800 800 800 800 800 800 720 720 720 720 720 720 720 720 900 900 900 900 900 900 900 900 810 810 810 810 810 810 810

1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4

.74E+03 .15E+04 .28E+04 .53E+04 .34E+04 .68E+04 .38E+04 .80E+04 .34E+03 .71E+03 .12E+04 .21E+04 .16E+04 .30E+04 .16E+04 .32E+04 .91E+03 .18E+04 .37E+04 .65E+04 .44E+04 .90E+04 .46E+04 .81E+04 .46E+03 .72E+03 .13E+04 .27E+04 .16E+04 .32E+04 .18E+04 .30E+04 .13E+04 .24E+04 .55E+04 .98E+04 .72E+04 .12E+05 .60E+04 .11E+05 .46E+03 .89E+03 .13E+04 .34E+04 .20E+04 .31E+04 .22E+04 .38E+04 .15E+04 .30E+04 .60E+04 .12E+05 .74E+04 .15E+05 .82E+04

.48E+03 .14E+04 .40E+04 .91E+04 .77E+04 .18E+05 .10E+05 .15E+05 .38E+03 .69E+03 .22E+04 .40E+04 .24E+05 .26E+05 .33E+05F .60E+05 .62E+03 .15E+04 .53E+04 .10E+05 .93E+04 .16E+05 .12E+05 .22E+05 .44E+03 .10E+04 .24E+04 .50E+04 .80E+04 .79E+04 .16E+05 .11E+05 .83E+03 .20E+04 .68E+04 .12E+05 .40E+05 .19E+05 .45E+05 .28E+05 .59E+03 .13E+04 .31E+04 .73E+04 .60E+04 .15E+05 .65E+04 .17E+05 .98E+03 .21E+04 .68E+04 .13E+05 .12E+05 .23E+05 .13E+05

.14E+05 .24E+05 .99E+04 .21E+05 .15E+05 .30E+05 .81E+04 .26E+05 .33E+05 .53E+05 .51E+04 .11E+05 .39E+04 .71E+04 .33E+04 .67E+04 .20E+05 .68E+05 .31E+05 .43E+05 .15E+05 .26E+05 .16E+05 .24E+05 .21E+04 .29E+05 .14E+05 .29E+05 .44E+04 .89E+04 .43E+04 .77E+04 .52E+05 .89E+05 .22E+05 .40E+05 .11E+05 .24E+05 .11E+05 .23E+05 .97E+04 .18E+05 .15E+05 .97E+04 .58E+04 .97E+04 .65E+04 .11E+05 .36E+05 .58E+05 .36E+05 .68E+05 .13E+05 .30E+05 .14E+05

.17E+03 .22E+03 .33E+03 .34E+03 .12E+03 .21E+03 .40E+03 .45E+03 .21E+03 .28E+03 .34E+03 .27E+03 .15E+03 .25E+03 .40E+03 .80E+03 .25E+03 .34E+03 .41E+03 .48E+03 .18E+03 .27E+03 .73E+03 .83E+03 .31E+03 .47E+03 .52E+03 .54E+03

18

9000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000

8100 1000 1000 1000 1000 1000 1000 1000 1000 9000 9000 9000 9000 9000 9000 9000 9000

810 1000 1000 1000 1000 1000 1000 1000 1000 900 900 900 900 900 900 900 900

4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4

.15E+05 .56E+03 .10E+04 .24E+04 .35E+04 .24E+04 .40E+04 .28E+04 .45E+04 .19E+04 .34E+04 .71E+04 .14E+05 .85E+04 .16E+05 .84E+04 .16E+05

.20E+05 .67E+03 .15E+04 .33E+04 .67E+04 .52E+05F .99E+05F .51E+05F .86E+05 .98E+03 .29E+04 .74E+04 .15E+05 .22E+05 .32E+05 .17E+05 .34E+05

.25E+05 .73E+04 .74E+04 .19E+05 .34E+05 .97E+04 .15E+05 .89E+04 .14E+05 .74E+05F .11E+06 .32E+05 .65E+05 .20E+05 .70E+05 .24E+05 .45E+05

.22E+03 .38E+03 .56E+03 .12E+04 .37E+03 .46E+03 .66E+03 .61E+03

11 DISCUSSION OF RESULTS

With the termination criteria previously described in mind we rst observe a disappointing low accuracy in the computed results. Only the unrealistic well conditioned cases indicated by "I=1" give reasonable values. In the other cases the precision degrades down to an 10%-error, especially for the variable (the multipliers corresponding to the equalities). Further we see from the detailed results (to be found in the appendix) that increasing p reduces in most cases the number of function evaluations resp. the number of steps only very slightly while increasing the computing e ort very much. Clearly p = 5 is a much better choice than p = 15. (A higher p makes things even worse. This observation is compatible with the results in 2].) If we compare the number of free variables and the number of steps, we see that L BFGS B behaves very much like an ordinary cg-method (having in mind that our examples exhibit a general distribution of eigenvalues, no clusters of eigenvalues). Clearly a good preconditioner would have to be invented to overcome this. But this is not our main concern here, we simply used the code as a "black box", and any experienced person knows that this will end up with such an observation ~ ~ in most cases. A good preconditioner might consist in transforming x into B ?1x where B is obtained ~ ~ by a sparse incomplete Cholesky-decomposition of B and into R?1 , where R is obtained from a sparse incomplete QR-decomposition of A. Because of the interaction of B 2 and AAT in the left upper diagonal block of the Hessians this even might not su ce. Let us return to the rst point, which in our opinion lets appear all three approaches as of questionable value. The limiting precision of any minimization method will be determined by the precision of function- and gradient-evaluation and the eigenvalue distribution of the (projected) Hessian. Because of the scaling of the problem the (absolute) rounding errors in the evaluation of the functions will be of order = O(n"m ) for the function M and K and = O(maxf ; %gn"m) for , where "m denotes the relative machine precision. From the Taylorexpansion and the special form of the Hessians we p conclude that such errors will introduce errors of p p the order of magnitude 2 for the variable and 2 = min resp. 2 = min for the variables and x ( provided the correct face is identi ed nally). This is to be observed indeed, the precision in the variables being worst. Some of the x; -variables are not decoupled and their conditioning may become even worse. However, since here the variables 1 ; : : : ; m are chosen at random in min; 1] whereas 1 = min and m = 1 this e ect is not too pronounced. The same result is obtained if we consider the e ect of terminating the iteration with the (projected) gradient less than in norm, with replacing p , that is only the square-root of the condition number of the Hessian enters then. This is due to the special form of the gradient and the Hessian. Given the termination criteria described above, we see that the internal termination criterion of L BFGS B has been chosen such that termination occurs only when the change in the function is in the order of magnitude of its roundo -error. That is, a further sharpening of this criterion is impossible. Nevertheless, for the runs with K and we observed quite 19

often the termination indicator "1", that is, the required precision in the (projected) gradient was not obtained and the method terminates because of too small changes in the function. Concerning the precision when terminating with the (projected) gradient "su ciently small", namely 10?6 (relative) we might hope that a sharpening of this requirement is possible, at least for the suite of examples used here. However, experimentation showed that this is not the case. Instead, the method then terminates with its internal termination criterion due to slow progress in the objective function. Comparing the T Hessians computed in (4.2), (5.2) and (6.3) with the matrix JF JF (see (3.9)) we observe that all three approaches essentially have the conditioning of the original KT-system squared, a disastrous e ect. This e ect is worsened for Spellucci's function due to the need of estimating the penalty-parameters, which inevitably will yield an overestimation, and even a modest factor of 10 has a detrimental e ect here. If we consider the computing time needed, we see that "FMS" is best in 141 testcases and "SPEL" in the remaining 19. In the well conditioned cases "SPEL" never works much worse than "FMS", whereas in the illconditioned ones it has its 10 failures. Here must be increased by the method from 1 to 103 or 104. Since presently a factor of 5 is used for doing that, this implies 5 or 6 restarts. Presently (xk ; k ; k ) is not reset to its starting value in case of a restart. Changing this and other details may possibly improve Spellucci's algorithm considerably. Kanzows approach performs by far worsest. The reason is the following: there is no such strong decoupling of variables as for the other two approaches. Moreover active bounds help to reduce the number of variables and therefore increase the e ciency rather than decreasing it. One should observe that we have been fair with respect to Kanzows approach, since the conditioning of the projected Hessians is as worse as that of Kanzows full Hessian. In a real life application this will usually not be the case and then the situation with Kanzows approach would even deteriorate. How far the results given above fall from an e cient problem solution becomes clear, if we consider the results obtained for exactly the same testcases with the interior point method using the shifted logarithmic barrier function applied to the problem obtained using theorem 3.1. Obviously we again get trouble with the nal precision, which is clearly not better than for the other approaches. This is due to two e ects: rstly to the increasing illconditioning of the Hessian of as the solution is approached and secondly to the narrowing of the feasible set Sk with respect to the x?component as the solution is approached and the slack variable w forced down to zero. In the limit the feasible set has empty interior, which means that a fundamental supposition of interior point methods becomes violated. However we observe a striking di erence. Firstly the computing e ort is now almost independent of the conditioning of the original problem (we attribute this to the truncated Newton-method, which works obviously much better the limited memory method). Secondly the total computing time is by an order of magnitude below that of the methods discussed before. This again is due to two reasons: rstly the number of variables remains n and is therefore about one third of that of the primal-dual methods. Secondly the speed of convergence of the truncated Newton method seems to be much better. Considering the nal precision in the dual variables we see that sometimes the method works quite well, whereas in most cases their nal precision is very bad. This depends much on the choice of the sequence fsk g and more work has to be done to improve on that.

12 CONCLUSION

The results obtained show that the three exact penalty approaches for the solution of equality constrained QP-problems cannot be recommended as they stand. Whether introduction of preconditioning based solely on the matrices B and A will help is questionable, considering the representations of the Hessians (8.10), (8.11), (8.12). A preconditioner for B 2 + AAT however will be too costly. The transformation into an inequality constrained problem and subsequent solution by an interior point method has more promise, but more research has to be done in order to improve the limiting precision of this solution method.

References

1] Byrd, R.H.; Nocedal, J.; Schnabel, R.B.: Representation of quasi-Newton matrices and their use 20

2] 3] 4] 5] 6] 7] 8] 9] 10] 11] 12] 13] 14] 15] 16] 17] 18] 19] 20]

in limited memory methods. Math. Prog. 63, (1994), 129{156 . Byrd, R.H.; Lu, P.; Nocedal, J.; Zhu, C.: A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Comp. 16, (1995), 1190{1208 . Carpenter, T.J.; Shanno, D.F.: An interior point method for quadratic programs based on conjugate projected gradients. Comp. Optim. Appl. 2, (1993), 5{28 . Conn, A.R.; Gould, N.; Toint, Ph.L.: A note on using alternative second-order models for the subproblems arising in barrier function methods for minimzation. Num. Math. 68, (1994), 17{33 . Coleman, Th.F.; Hulbert, L.A.: A globally and superlinearly convergent algorithm for convex quadratic programs with simple bounds. SIOPT 3, (1993), 298{321 . Felkel, R.: Eine duale Penalty-Funktion zur Losung grosser schwach besetzter quadratischer Optimierungsprobleme. Diploma Thesis. TH Darmstadt, Dept. Math. 1995 . (in German, available from the author on request) . Felkel, R.: An interior point method for large scale QP problems. THD Mathematics Department Report 1850(1996). Available through http://www.mathematik.th-darmstadt.de/ags/ag8/assi/felkel.html Friedlander, Ana; Mart nez, J. M.; Santos, A. S.: On the resolution of linearly constrained convex minimization problems. SIOPT 4, (1994), 331-339 . Gill, Ph.E.; Murray, W.; Wright,M.: Practical methods of optimization. New York: Acad. Prss 1980 . Goldfarb, D.; Liu, S.: An O(n3 L) primal interior point algorithm for convex quadratic programming. Math. Prog. 49, 325{340, (1991). Gould, N.I.M.: An algorithm for large scale quadratic programming. I.M.A.J. Numer. Anal. 11, 299{323, (1991) . Grippo, L.; Lucidi, S.: A di erentiable exact penalty function for bound constrained quadratic programming problems. Optimization 22, (1991), 557-578 Han, S.P.; Mangasarian, O.L.: A dual di erentiable exact penalty function. Math. Prog. 25, (1983) , 293{306 . Kanzow, Ch.: An unconstrained optimization technique for large-scale linearly constrained convex minimization problems. Computing 53, (1994), 101{117 . Lin, Y. Y.; Pang, S. Y.: Iterative methods for large convex quadratic programs: A survey. SIAM J. Conrol and Optimization 25, (1987), 383-411 . Lucidi, S.: New results on a class of exact augmented Lagrangians. J.O.T.A. 58, (1988), 259{282 . Mangasarian, O.L.: Sparsity preserving SOR-algorithms for separable quadratic and linear programming. Comput. Oper. Res. 11, (1984), 105{112 . More, J.J.; Toraldo, G.: On the solution of large quadratic programming problems with bound constraints. SIOPT 1, (1991), 93{113 . More, J.J.-Toraldo, G.: Algorithms for bound constrained quadratic programming problems. Num.Math. 55, (1989), 377{400 . Nash, S.G.: Newton-type minimization via the Lanczos method, SINUM 21, (1984), 770{788 . 21

21] di Pillo, E.; Grippo, L.: An exact penalty method with global convergence properties for nonlinear programming problems. Math. Prog. 36, 1{18, (1986). 22] Polyak, R.: Modi ed barrier functions (theory and methods). Math. Prog. 54, (1992), 177{222 . 23] Spellucci, P.: Solving general convex QP problems via an exact quadratic augmented Lagrangian with bound constraints. THD Math. Dept. Report 1563 (1993), Revised 6/96. Available through http://www.mathematik.th-darmstadt.de/ags/ag8/prof/spellucci.html . 24] Yang, E.K.; Tolle, J.W.: A class of methods for solving large convex quadratic programs subject to box constraints. Math. Prog. 51, (1991), 223{228 . 25] Zou, X., et alii: Numerical experience with limited-memory Quasi-Newton- and truncated Newtonmethods. SIOPT 3, (1993), 582{608 .

22

13 APPENDIX: DETAILED NUMERICAL RESULTS

In this appendix the list of summarized reults is given. The meaning of the columns is as follows 1. 2. 3. total number of unknowns. M: The number of equations. J0: The number of binding bounds for the primal variables. Due to the complementarity condition the total number of binding inequalities is always n of course. 4. I: I=1,2,3,4 indicates the case

min = min = min = 10?I

2N+M: The

:

5. 6. 7. 8.

T :

The termination indicator (see above).

DXR, DLR, DMR : TIME : #FG

jjx ? xcomp jj=jjx jj; jj ? comp jj=jj jj; jj ? comp jj=jj jj.

The CPU-time used in seconds. : The number of calls to the function/gradient-evaluation-routine.

Any combination of parameters appears two times, the rst run is with p = 5 and the second with p = 15. The results have been obtained on an HP9000/735/125 workstation with 128MB main memory using f77 -K +O3 (optimization without the vectorizing feature). The results for the Friedlander et al. approach are

2N+M M 2100 100 2100 100 2100 100 2100 100 2100 100 2100 100 2100 100 2100 100 2900 900 2900 900 2900 900 2900 900 2900 900 2900 900 2900 900 2900 900 4200 200 4200 200 4200 200 4200 200 4200 200 4200 200 4200 200 4200 200 5800 1800 5800 1800 J0 100 100 100 100 100 100 100 100 90 90 90 90 90 90 90 90 200 200 200 200 200 200 200 200 180 180 I 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 T 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 DXR .4E-04 .2E-04 .6E-03 .4E-03 .4E-02 .7E-02 .3E-01 .3E-01 .2E-04 .3E-04 .2E-02 .3E-02 .4E-02 .4E-02 .7E-02 .8E-02 .9E-05 .1E-04 .6E-03 .6E-03 .8E-02 .8E-02 .1E-01 .1E-01 .2E-04 .1E-04 DMR .1E-02 .4E-03 .9E-01 .9E-01 .8E-01 .8E-01 .1E+00 .1E+00 .2E-03 .3E-03 .8E-01 .9E-01 .1E+00 .1E+00 .1E+00 .1E+00 .3E-03 .4E-03 .6E-01 .6E-01 .9E-01 .8E-01 .9E-01 .9E-01 .2E-03 .1E-03 DLR .3E-05 .6E-05 .2E-03 .5E-03 .7E-02 .3E-03 .6E-01 .6E-01 .9E-05 .1E-04 .6E-03 .6E-03 .3E-01 .2E-01 .5E-01 .5E-01 .2E-04 .3E-04 .7E-03 .7E-03 .3E-03 .3E-03 .3E-03 .2E-03 .9E-05 .1E-04 TIME .19E+02 .36E+02 .32E+02 .74E+02 .73E+02 .16E+03 .59E+02 .12E+03 .36E+02 .83E+02 .16E+03 .27E+03 .14E+03 .31E+03 .15E+03 .30E+03 .41E+02 .84E+02 .15E+03 .29E+03 .25E+03 .50E+03 .27E+03 .46E+03 .10E+03 .24E+03 #FG 1382 986 2127 2090 5234 5065 4451 3728 1455 1415 5922 4100 5634 5048 5752 4865 1251 1245 4180 3610 6938 6309 7819 6143 1813 1954

23

5800 5800 5800 5800 5800 5800 6300 6300 6300 6300 6300 6300 6300 6300 8700 8700 8700 8700 8700 8700 8700 8700 8400 8400 8400 8400 8400 8400 8400 8400 11600 11600 11600 11600 11600 11600 11600 11600 10500 10500 10500 10500 10500 10500 10500 10500 14500 14500 14500 14500 14500 14500 14500 14500 12600

1800 1800 1800 1800 1800 1800 300 300 300 300 300 300 300 300 2700 2700 2700 2700 2700 2700 2700 2700 400 400 400 400 400 400 400 400 3600 3600 3600 3600 3600 3600 3600 3600 500 500 500 500 500 500 500 500 4500 4500 4500 4500 4500 4500 4500 4500 600

180 180 180 180 180 180 300 300 300 300 300 300 300 300 270 270 270 270 270 270 270 270 400 400 400 400 400 400 400 400 360 360 360 360 360 360 360 360 500 500 500 500 500 500 500 500 450 450 450 450 450 450 450 450 600

2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

.2E-02 .2E-02 .6E-02 .3E-02 .1E-01 .1E-01 .2E-04 .2E-04 .9E-03 .1E-02 .1E-01 .1E-01 .3E-01 .3E-01 .2E-04 .2E-04 .1E-02 .1E-02 .3E-02 .3E-02 .2E-01 .2E-01 .8E-05 .2E-04 .6E-03 .7E-03 .8E-02 .7E-02 .2E-01 .2E-01 .9E-05 .1E-04 .2E-02 .2E-02 .4E-02 .3E-02 .6E-02 .6E-02 .2E-04 .2E-04 .3E-03 .5E-03 .5E-02 .7E-02 .3E-01 .3E-01 .8E-05 .9E-05 .2E-02 .1E-02 .3E-02 .4E-02 .9E-02 .9E-02 .5E-05

.7E-01 .7E-01 .1E+00 .1E+00 .1E+00 .1E+00 .4E-03 .3E-03 .1E+00 .1E+00 .1E+00 .1E+00 .1E+00 .1E+00 .2E-03 .2E-03 .7E-01 .7E-01 .1E+00 .1E+00 .1E+00 .1E+00 .2E-03 .5E-03 .8E-01 .8E-01 .9E-01 .9E-01 .9E-01 .9E-01 .1E-03 .1E-03 .8E-01 .8E-01 .1E+00 .1E+00 .1E+00 .1E+00 .6E-03 .5E-03 .5E-01 .8E-01 .1E+00 .1E+00 .2E+00 .2E+00 .5E-04 .8E-04 .7E-01 .6E-01 .1E+00 .1E+00 .1E+00 .1E+00 .2E-03

.3E-03 .2E-03 .1E-01 .1E-01 .2E-01 .2E-01 .7E-06 .2E-05 .1E-04 .2E-04 .5E-02 .5E-02 .1E-01 .2E-01 .5E-05 .7E-05 .3E-02 .3E-02 .3E-01 .3E-01 .4E-01 .4E-01 .4E-05 .4E-05 .1E-04 .4E-04 .4E-04 .4E-04 .3E-04 .3E-04 .5E-05 .8E-05 .2E-02 .1E-02 .5E-02 .4E-02 .1E-01 .6E-02 .7E-05 .6E-05 .5E-03 .2E-02 .2E-02 .2E-02 .2E-02 .2E-02 .6E-05 .2E-05 .6E-03 .6E-03 .2E-01 .2E-01 .3E-01 .3E-01 .1E-04

.44E+03 .93E+03 .48E+03 .12E+04 .51E+03 .11E+04 .97E+02 .15E+03 .36E+03 .60E+03 .34E+03 .63E+03 .34E+03 .53E+03 .21E+03 .43E+03 .10E+04 .18E+04 .10E+04 .19E+04 .95E+03 .18E+04 .14E+03 .21E+03 .47E+03 .64E+03 .53E+03 .10E+04 .60E+03 .11E+04 .38E+03 .77E+03 .14E+04 .28E+04 .15E+04 .27E+04 .17E+04 .32E+04 .20E+03 .36E+03 .10E+04 .13E+04 .11E+04 .16E+04 .96E+03 .16E+04 .52E+03 .10E+04 .23E+04 .41E+04 .29E+04 .44E+04 .29E+04 .50E+04 .24E+03

7386 6693 7766 8748 8362 8136 1576 1237 6215 4821 5866 5157 5752 4277 2395 2366 10492 9629 10065 9336 9391 8629 1596 1403 5461 3714 6342 6166 7470 6590 3016 3033 10326 10584 10801 9425 11972 10995 1931 1957 9611 6301 10928 8087 8883 7749 3059 3101 13223 12383 16124 12133 15949 13653 2132

24

12600 12600 12600 12600 12600 12600 12600 17400 17400 17400 17400 17400 17400 17400 17400 14700 14700 14700 14700 14700 14700 14700 14700 20300 20300 20300 20300 20300 20300 20300 20300 16800 16800 16800 16800 16800 16800 16800 16800 23200 23200 23200 23200 23200 23200 23200 23200 18900 18900 18900 18900 18900 18900 18900 18900

600 600 600 600 600 600 600 5400 5400 5400 5400 5400 5400 5400 5400 700 700 700 700 700 700 700 700 6300 6300 6300 6300 6300 6300 6300 6300 800 800 800 800 800 800 800 800 7200 7200 7200 7200 7200 7200 7200 7200 900 900 900 900 900 900 900 900

600 600 600 600 600 600 600 540 540 540 540 540 540 540 540 700 700 700 700 700 700 700 700 630 630 630 630 630 630 630 630 800 800 800 800 800 800 800 800 720 720 720 720 720 720 720 720 900 900 900 900 900 900 900 900

1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

.7E-05 .3E-03 .4E-03 .7E-02 .7E-02 .2E-01 .2E-01 .2E-04 .9E-05 .2E-02 .2E-02 .2E-02 .2E-02 .3E-02 .3E-02 .2E-04 .1E-04 .7E-03 .1E-02 .1E-02 .1E-02 .1E-01 .1E-01 .7E-05 .1E-04 .1E-02 .1E-02 .2E-02 .2E-02 .5E-02 .5E-02 .2E-04 .8E-05 .1E-02 .1E-02 .6E-02 .3E-02 .1E-01 .1E-01 .1E-04 .6E-05 .1E-02 .1E-02 .3E-02 .3E-02 .1E-01 .1E-01 .5E-05 .6E-05 .1E-02 .7E-03 .9E-02 .9E-02 .2E-01 .2E-01

.2E-03 .6E-01 .7E-01 .1E+00 .1E+00 .1E+00 .1E+00 .2E-03 .9E-04 .9E-01 .8E-01 .1E+00 .1E+00 .1E+00 .1E+00 .4E-03 .3E-03 .1E+00 .1E+00 .1E+00 .1E+00 .1E+00 .1E+00 .6E-04 .1E-03 .6E-01 .6E-01 .1E+00 .1E+00 .1E+00 .1E+00 .5E-03 .2E-03 .1E+00 .1E+00 .1E+00 .1E+00 .1E+00 .1E+00 .9E-04 .6E-04 .6E-01 .6E-01 .1E+00 .1E+00 .1E+00 .1E+00 .2E-03 .2E-03 .1E+00 .8E-01 .1E+00 .1E+00 .1E+00 .1E+00

.1E-04 .4E-03 .1E-02 .1E-02 .1E-02 .1E-02 .1E-02 .2E-05 .7E-05 .8E-03 .7E-03 .7E-02 .4E-02 .3E-01 .2E-01 .9E-06 .9E-05 .8E-03 .8E-03 .1E-02 .1E-02 .1E-01 .1E-01 .8E-05 .3E-05 .1E-02 .1E-02 .2E-01 .1E-01 .2E-01 .2E-01 .1E-05 .3E-05 .3E-04 .1E-04 .1E-01 .1E-01 .1E-01 .1E-01 .4E-05 .6E-05 .9E-03 .9E-03 .3E-02 .2E-02 .3E-01 .3E-01 .1E-04 .9E-05 .3E-04 .2E-04 .2E-04 .4E-04 .4E-03 .4E-04

.47E+03 .12E+04 .17E+04 .97E+03 .16E+04 .10E+04 .18E+04 .74E+03 .15E+04 .28E+04 .53E+04 .34E+04 .68E+04 .38E+04 .80E+04 .34E+03 .71E+03 .12E+04 .21E+04 .16E+04 .30E+04 .16E+04 .32E+04 .91E+03 .18E+04 .37E+04 .65E+04 .44E+04 .90E+04 .46E+04 .81E+04 .46E+03 .72E+03 .13E+04 .27E+04 .16E+04 .32E+04 .18E+04 .30E+04 .13E+04 .24E+04 .55E+04 .98E+04 .72E+04 .12E+05 .60E+04 .11E+05 .46E+03 .89E+03 .13E+04 .34E+04 .20E+04 .31E+04 .22E+04 .38E+04

2254 9894 6882 7361 5765 7739 6837 3382 3547 12847 12439 14739 14388 16816 17575 2273 2764 8118 7127 10722 10818 10204 10997 3656 3470 14513 12521 16057 16421 16459 14137 2484 2113 6932 7291 8650 8865 9723 8565 4358 4080 18652 17014 24147 18744 18696 17563 2341 2428 6074 7950 9801 7623 11404 9571

25

26100 26100 26100 26100 26100 26100 26100 26100 21000 21000 21000 21000 21000 21000 21000 21000 29000 29000 29000 29000 29000 29000 29000 29000

8100 8100 8100 8100 8100 8100 8100 8100 1000 1000 1000 1000 1000 1000 1000 1000 9000 9000 9000 9000 9000 9000 9000 9000

810 810 810 810 810 810 810 810 1000 1000 1000 1000 1000 1000 1000 1000 900 900 900 900 900 900 900 900

1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

.2E-04 .7E-05 .2E-02 .1E-02 .2E-02 .2E-02 .3E-02 .3E-02 .6E-05 .8E-05 .4E-03 .6E-03 .3E-02 .2E-02 .1E-01 .1E-01 .9E-05 .1E-04 .2E-02 .1E-02 .2E-02 .2E-02 .1E-01 .8E-02

.2E-03 .7E-04 .7E-01 .6E-01 .1E+00 .1E+00 .1E+00 .1E+00 .3E-03 .4E-03 .5E-01 .6E-01 .1E+00 .1E+00 .1E+00 .1E+00 .9E-04 .1E-03 .7E-01 .6E-01 .1E+00 .1E+00 .1E+00 .1E+00

.2E-05 .9E-05 .3E-03 .2E-03 .2E-01 .1E-01 .3E-01 .3E-01 .2E-04 .2E-04 .6E-03 .1E-02 .9E-02 .9E-02 .9E-02 .1E-01 .3E-05 .2E-05 .7E-03 .6E-03 .1E-01 .1E-01 .2E-01 .2E-01

.15E+04 .30E+04 .60E+04 .12E+05 .74E+04 .15E+05 .82E+04 .15E+05 .56E+03 .10E+04 .24E+04 .35E+04 .24E+04 .40E+04 .28E+04 .45E+04 .19E+04 .34E+04 .71E+04 .14E+05 .85E+04 .16E+05 .84E+04 .16E+05

4384 4453 17928 18212 21121 22249 23120 22027 2528 2560 10052 7662 9829 8298 11783 9538 4862 4206 18375 19440 21130 20640 20742 20147

26

The results for Spellucci's method follow

2N+M 2100 2100 2100 2100 2100 2100 2100 2100 2900 2900 2900 2900 2900 2900 2900 2900 4200 4200 4200 4200 4200 4200 4200 4200 5800 5800 5800 5800 5800 5800 5800 5800 6300 6300 6300 6300 6300 6300 6300 6300 8700 8700 8700 8700 8700 8700 8700 8700 8400 8400 8400 8400 M 100 100 100 100 100 100 100 100 900 900 900 900 900 900 900 900 200 200 200 200 200 200 200 200 1800 1800 1800 1800 1800 1800 1800 1800 300 300 300 300 300 300 300 300 2700 2700 2700 2700 2700 2700 2700 2700 400 400 400 400 J0 100 100 100 100 100 100 100 100 90 90 90 90 90 90 90 90 200 200 200 200 200 200 200 200 180 180 180 180 180 180 180 180 300 300 300 300 300 300 300 300 270 270 270 270 270 270 270 270 400 400 400 400 I 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 T 0 0 1 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 1 1 1 -1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 DLX .8E-05 .1E-04 .3E-03 .2E-03 .8E-01 .8E-01 .8E-01 .8E-01 .1E-04 .1E-04 .1E-03 .1E-03 .9E-01 .9E-01 .9E-01 .9E-01 .4E-05 .1E-04 .1E-03 .3E-03 .6E-03 .6E-03 .3E-02 .5E-01 .1E-04 .5E-05 .2E-03 .2E-03 .1E+00 .1E+00 .2E-01 .1E+00 .5E-05 .5E-05 .2E-03 .2E-03 .3E-02 .1E+02 .6E-01 .1E+00 .1E-04 .1E-04 .7E-04 .2E-03 .2E-02 .3E-01 .3E-01 .2E-01 .7E-05 .4E-05 .3E-03 .2E-03 DLM .1E-03 .3E-03 .4E-01 .3E-01 .8E-01 .8E-01 .8E-01 .8E-01 .8E-04 .8E-04 .8E-02 .7E-02 .6E-01 .5E-01 .6E-01 .6E-01 .8E-04 .2E-03 .1E-01 .9E-02 .7E-01 .6E-01 .4E-01 .4E-01 .9E-04 .4E-04 .1E-01 .1E-01 .5E-01 .5E-01 .6E-01 .6E-01 .1E-03 .1E-03 .4E-01 .4E-01 .8E-01 .7E-01 .8E-01 .8E-01 .1E-03 .1E-03 .5E-02 .1E-01 .8E-01 .7E-01 .9E-01 .8E-01 .2E-03 .5E-04 .7E-02 .3E-01 DLR .1E-06 .2E-06 .2E-06 .9E-07 .1E-05 .9E-06 .6E-06 .7E-06 .6E-06 .4E-06 .3E-07 .3E-06 .2E-07 .2E-06 .8E-07 .8E-08 .7E-10 .4E-06 .1E-07 .1E-06 .5E-07 .1E-06 .1E-06 .7E-07 .2E-06 .2E-08 .2E-07 .2E-09 .2E-01 .2E-01 .8E-04 .2E-01 .9E-10 .2E-06 .1E-06 .3E-10 .3E-05 .4E-01 .6E-07 .4E-03 .4E-10 .8E-09 .1E-05 .2E-06 .3E-02 .2E-02 .4E-01 .3E-01 .6E-07 .3E-05 .1E-05 .3E-07 TIME .19E+02 .47E+02 .13E+03 .39E+03 .34E+03 .45E+03 .66E+03 .75E+03 .31E+02 .94E+02 .35E+03 .97E+03 .39E+03 .10E+04 .52E+03 .13E+04 .61E+02 .12E+03 .23E+03 .62E+03 .49E+04 .40E+04 .59E+04 .21E+04 .11E+03 .31E+03 .69E+03 .16E+04 .99E+03 .27E+04 .17E+04 .34E+04 .13E+03 .24E+03 .75E+03 .21E+04 .39E+04 .27E+05 .37E+04 .32E+04 .20E+03 .47E+03 .16E+04 .30E+04 .10E+05 .74E+04 .11E+05 .70E+04 .15E+03 .37E+03 .12E+04 .24E+04 #FG 511 552 3503 4575 8887 4895 17364 8891 504 683 5654 6896 6228 7554 8567 9460 686 630 2695 3377 54773 21599 66487 11541 789 995 4937 5408 7025 8445 11699 10383 889 794 5017 7228 27464 90016 25877 10850 902 1036 7384 6643 46373 16884 50560 16020 725 923 5819 6165 RHO .500E+01 .500E+01 .500E+01 .500E+01 .250E+02 .500E+01 .250E+02 .500E+01 .500E+01 .500E+01 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .125E+03 .125E+03 .125E+03 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .625E+03 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .125E+03 .250E+02 .125E+03 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 ETA .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .625E+03 .313E+04 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .125E+03 .125E+03 .125E+03 .125E+03 .250E+02 .250E+02 .125E+03 .125E+03 .313E+04 .313E+04 .313E+04 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .125E+03 .125E+03 .625E+03 .125E+03 .250E+02 .250E+02 .125E+03 .125E+03 .313E+04 .156E+05 .313E+04 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .313E+04 .625E+03 .313E+04 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03

27

8400 8400 8400 8400 11600 11600 11600 11600 11600 11600 11600 11600 10500 10500 10500 10500 10500 10500 10500 10500 14500 14500 14500 14500 14500 14500 14500 14500 12600 12600 12600 12600 12600 12600 12600 12600 17400 17400 17400 17400 17400 17400 17400 17400 14700 14700 14700 14700 14700 14700 14700 14700 20300 20300 20300

400 400 400 400 3600 3600 3600 3600 3600 3600 3600 3600 500 500 500 500 500 500 500 500 4500 4500 4500 4500 4500 4500 4500 4500 600 600 600 600 600 600 600 600 5400 5400 5400 5400 5400 5400 5400 5400 700 700 700 700 700 700 700 700 6300 6300 6300

400 400 400 400 360 360 360 360 360 360 360 360 500 500 500 500 500 500 500 500 450 450 450 450 450 450 450 450 600 600 600 600 600 600 600 600 540 540 540 540 540 540 540 540 700 700 700 700 700 700 700 700 630 630 630

3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2

1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 -1 1 -1 -1 0 0 1 1 1 1 -1 -1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 -1 1 0 0 0

.1E+00 .4E-01 .6E-01 .7E-01 .1E-04 .1E-04 .2E-03 .2E-03 .3E-01 .3E-01 .3E-01 .3E-01 .1E-04 .8E-05 .2E-03 .2E-03 .9E-01 .6E-01 .2E+00 .1E+00 .7E-05 .1E-04 .2E-03 .2E-03 .2E+00 .4E-02 .1E+03 .3E+01 .8E-05 .1E-05 .2E-03 .2E-03 .2E-03 .4E-02 .5E+01 .3E+02 .1E-04 .2E-04 .1E-03 .2E-03 .2E-01 .2E-01 .2E-01 .2E-01 .1E-04 .2E-04 .2E-03 .2E-03 .8E-02 .3E-03 .4E+00 .1E-01 .1E-04 .2E-04 .2E-03

.9E-01 .7E-01 .7E-01 .7E-01 .8E-04 .1E-03 .1E-01 .1E-01 .6E-01 .6E-01 .7E-01 .7E-01 .3E-03 .2E-03 .4E-01 .4E-01 .5E-01 .6E-01 .6E-01 .6E-01 .6E-04 .9E-04 .1E-01 .1E-01 .6E-01 .5E-01 .8E-01 .8E-01 .2E-03 .2E-04 .3E-01 .4E-01 .6E-01 .6E-01 .6E-01 .6E-01 .9E-04 .1E-03 .8E-02 .1E-01 .7E-01 .8E-01 .7E-01 .7E-01 .3E-03 .3E-03 .4E-01 .3E-01 .7E-01 .6E-01 .8E-01 .7E-01 .1E-03 .2E-03 .1E-01

.1E-06 .1E-04 .1E-06 .2E-05 .2E-07 .2E-07 .4E-07 .1E-07 .4E-03 .4E-03 .2E-02 .2E-02 .8E-07 .1E-05 .5E-06 .5E-07 .2E-06 .5E-06 .4E-05 .1E-04 .2E-08 .2E-07 .3E-07 .6E-08 .6E-02 .6E-04 .2E+01 .4E-01 .2E-06 .1E-07 .7E-07 .8E-07 .6E-11 .8E-05 .2E-01 .1E+00 .1E-05 .2E-11 .2E-06 .2E-06 .3E-07 .3E-07 .1E-09 .3E-07 .1E-07 .1E-05 .5E-07 .4E-11 .1E-03 .6E-07 .7E-02 .8E-04 .7E-08 .1E-06 .8E-07

.44E+03 .56E+04 .23E+04 .60E+04 .30E+03 .72E+03 .23E+04 .60E+04 .55E+04 .92E+04 .41E+04 .70E+04 .22E+03 .49E+03 .13E+04 .24E+04 .55E+04 .73E+04 .45E+04 .84E+04 .41E+03 .90E+03 .28E+04 .62E+04 .37E+05 .67E+05 .37E+05 .71E+05 .39E+03 .82E+03 .17E+04 .32E+04 .20E+05 .18E+05 .28E+05 .55E+05 .48E+03 .14E+04 .40E+04 .91E+04 .77E+04 .18E+05 .10E+05 .15E+05 .38E+03 .69E+03 .22E+04 .40E+04 .24E+05 .26E+05 .33E+05 .60E+05 .62E+03 .15E+04 .53E+04

2183 14431 11518 15598 937 1150 7681 9631 17560 14622 12981 11216 829 978 4997 4851 20966 14910 16964 17043 988 1118 6728 7954 90011 84425 90022 90013 1194 1311 5453 5049 66150 30522 90013 90016 933 1377 7869 9066 15198 18107 20648 15667 969 939 5740 5631 65779 36740 90013 85418 1006 1237 8572

.250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .125E+03 .125E+03 .781E+05 .125E+03 .250E+02 .250E+02 .250E+02 .250E+02 .625E+03 .250E+02 .125E+03 .625E+03 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .125E+03 .250E+02 .250E+02 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .125E+03 .250E+02 .250E+02 .250E+02

.125E+03 .625E+03 .625E+03 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .625E+03 .625E+03 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .625E+03 .625E+03 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .313E+04 .313E+04 .781E+05 .156E+05 .250E+02 .250E+02 .125E+03 .125E+03 .313E+04 .313E+04 .156E+05 .781E+05 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .625E+03 .625E+03 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .313E+04 .313E+04 .313E+04 .313E+04 .250E+02 .250E+02 .125E+03

28

20300 20300 20300 20300 20300 16800 16800 16800 16800 16800 16800 16800 16800 23200 23200 23200 23200 23200 23200 23200 23200 18900 18900 18900 18900 18900 18900 18900 18900 26100 26100 26100 26100 26100 26100 26100 26100 21000 21000 21000 21000 21000 21000 21000 21000 29000 29000 29000 29000 29000 29000 29000 29000

6300 6300 6300 6300 6300 800 800 800 800 800 800 800 800 7200 7200 7200 7200 7200 7200 7200 7200 900 900 900 900 900 900 900 900 8100 8100 8100 8100 8100 8100 8100 8100 1000 1000 1000 1000 1000 1000 1000 1000 9000 9000 9000 9000 9000 9000 9000 9000

630 630 630 630 630 800 800 800 800 800 800 800 800 720 720 720 720 720 720 720 720 900 900 900 900 900 900 900 900 810 810 810 810 810 810 810 810 1000 1000 1000 1000 1000 1000 1000 1000 900 900 900 900 900 900 900 900

2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4

0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 -1 -1 -1 1 0 0 0 0 1 1 1 1

.2E-03 .1E-01 .1E-01 .1E-01 .1E-01 .1E-04 .7E-05 .2E-03 .2E-03 .2E-01 .2E-01 .3E-01 .3E+00 .1E-04 .1E-04 .2E-03 .2E-03 .9E-03 .2E-01 .2E-01 .2E-01 .1E-04 .7E-05 .3E-03 .1E-03 .3E-01 .3E-01 .4E-01 .4E-01 .1E-04 .4E-05 .2E-03 .2E-03 .1E-01 .1E-01 .1E-01 .1E-01 .4E-05 .3E-05 .4E-03 .1E-03 .1E+02 .1E+02 .1E+01 .1E-01 .1E-04 .1E-04 .3E-03 .3E-03 .1E-02 .8E-03 .1E-01 .1E-01

.1E-01 .5E-01 .6E-01 .5E-01 .5E-01 .3E-03 .2E-03 .1E-01 .2E-01 .9E-01 .9E-01 .8E-01 .8E-01 .1E-03 .1E-03 .1E-01 .1E-01 .8E-01 .7E-01 .8E-01 .7E-01 .2E-03 .2E-03 .2E-01 .1E-01 .7E-01 .7E-01 .8E-01 .6E-01 .1E-03 .3E-04 .1E-01 .1E-01 .5E-01 .7E-01 .7E-01 .7E-01 .8E-04 .7E-04 .1E-01 .1E-01 .1E-01 .9E-01 .6E-01 .4E-01 .9E-04 .1E-03 .2E-01 .2E-01 .7E-01 .7E-01 .7E-01 .7E-01

.1E-05 .4E-06 .5E-06 .7E-10 .3E-07 .6E-07 .3E-06 .6E-06 .1E-07 .6E-06 .2E-04 .4E-05 .2E-03 .2E-06 .6E-11 .6E-07 .1E-05 .1E-06 .2E-07 .2E-10 .5E-04 .5E-07 .4E-10 .5E-07 .1E-06 .4E-05 .9E-05 .1E-04 .1E-04 .2E-09 .1E-08 .4E-08 .7E-07 .4E-05 .5E-07 .2E-01 .2E-01 .4E-05 .5E-07 .2E-07 .2E-07 .3E-01 .6E-01 .6E-01 .8E-05 .2E-06 .2E-11 .4E-06 .7E-07 .2E-03 .2E-03 .9E-03 .9E-03

.10E+05 .93E+04 .16E+05 .12E+05 .22E+05 .44E+03 .10E+04 .24E+04 .50E+04 .80E+04 .79E+04 .16E+05 .11E+05 .83E+03 .20E+04 .68E+04 .12E+05 .40E+05 .19E+05 .45E+05 .28E+05 .59E+03 .13E+04 .31E+04 .73E+04 .60E+04 .15E+05 .65E+04 .17E+05 .98E+03 .21E+04 .68E+04 .13E+05 .12E+05 .23E+05 .13E+05 .20E+05 .67E+03 .15E+04 .33E+04 .67E+04 .52E+05 .99E+05 .51E+05 .86E+05 .98E+03 .29E+04 .74E+04 .15E+05 .22E+05 .32E+05 .17E+05 .34E+05

8339 15140 13634 20128 19067 950 1201 5313 5774 17595 11159 36778 13819 1160 1488 9692 8636 57965 14584 64336 20318 1148 1312 5947 7391 11723 16050 12618 18454 1157 1367 8351 8089 16012 15207 16517 12820 1139 1391 5599 6307 90008 90008 90013 81064 1077 1623 8295 8987 24358 17741 19371 19507

.250E+02 .250E+02 .125E+03 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .151E+03 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .125E+03 .125E+03 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .125E+03 .625E+03 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02 .250E+02

.125E+03 .625E+03 .625E+03 .625E+03 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .625E+03 .313E+04 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .313E+04 .625E+03 .313E+04 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .625E+03 .625E+03 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .625E+03 .625E+03 .625E+03 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .625E+03 .156E+05 .313E+04 .250E+02 .250E+02 .125E+03 .125E+03 .625E+03 .625E+03 .625E+03 .625E+03

29

The results for Kanzows method are

2N+M 2100 2100 2100 2100 2100 2100 2100 2100 2900 2900 2900 2900 2900 2900 2900 2900 4200 4200 4200 4200 4200 4200 4200 4200 5800 5800 5800 5800 5800 5800 5800 5800 6300 6300 6300 6300 6300 6300 6300 6300 8700 8700 8700 8700 8700 8700 8700 8700 8400 8400 8400 8400 M 100 100 100 100 100 100 100 100 900 900 900 900 900 900 900 900 200 200 200 200 200 200 200 200 1800 1800 1800 1800 1800 1800 1800 1800 300 300 300 300 300 300 300 300 2700 2700 2700 2700 2700 2700 2700 2700 400 400 400 400 J0 100 100 100 100 100 100 100 100 90 90 90 90 90 90 90 90 200 200 200 200 200 200 200 200 180 180 180 180 180 180 180 180 300 300 300 300 300 300 300 300 270 270 270 270 270 270 270 270 400 400 400 400 I 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 T 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 DXR .5E-04 .3E-04 .6E-02 .6E-02 .4E-01 .2E-01 .5E-01 .5E-01 .6E-02 .8E-02 .9E-02 .8E-02 .3E-01 .3E-01 .5E-01 .5E-01 .2E-04 .2E-04 .1E-01 .1E-01 .2E-01 .1E-01 .2E-01 .2E-01 .1E-01 .6E-02 .1E-01 .1E-01 .1E-01 .1E-01 .2E-01 .2E-01 .2E-04 .3E-04 .3E-02 .3E-02 .1E-01 .1E-01 .2E-01 .2E-01 .5E-02 .5E-02 .1E-01 .1E-01 .1E-01 .1E-01 .2E-01 .2E-01 .9E-02 .5E-02 .6E-02 .6E-02 DMR .1E-02 .7E-03 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .4E-01 .7E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .4E-03 .4E-03 .2E+00 .2E+00 .1E+00 .1E+00 .1E+00 .1E+00 .8E-01 .6E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .5E-03 .5E-03 .2E+00 .2E+00 .1E+00 .1E+00 .1E+00 .1E+00 .3E-01 .3E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .1E+00 .8E-01 .3E+00 .3E+00 DLR .2E-06 .4E-06 .2E-01 .2E-01 .4E-01 .2E-01 .4E-01 .4E-01 .1E-01 .3E-01 .8E-01 .8E-01 .1E+00 .9E-01 .1E+00 .9E-01 .1E-06 .2E-06 .3E-01 .3E-01 .2E-01 .2E-01 .3E-01 .1E-01 .3E-01 .2E-01 .6E-01 .6E-01 .9E-01 .9E-01 .9E-01 .9E-01 .9E-07 .6E-06 .1E-01 .1E-01 .1E-01 .1E-01 .1E-01 .1E-01 .1E-01 .1E-01 .8E-01 .8E-01 .9E-01 .9E-01 .9E-01 .9E-01 .2E-01 .9E-02 .6E-02 .6E-02 TIME .12E+03 .40E+03 .13E+03 .27E+03 .12E+03 .41E+03 .12E+03 .29E+03 .71E+03 .94E+03 .75E+03 .20E+04 .67E+03 .15E+04 .49E+03 .16E+04 .39E+03 .60E+03 .46E+03 .13E+04 .27E+03 .63E+03 .34E+03 .83E+03 .15E+04 .45E+04 .20E+04 .39E+04 .17E+04 .31E+04 .15E+04 .30E+04 .15E+04 .13E+04 .95E+03 .19E+04 .12E+04 .22E+04 .14E+04 .19E+04 .51E+04 .87E+04 .65E+04 .92E+04 .45E+04 .85E+04 .46E+04 .82E+04 .16E+04 .90E+04 .10E+05 .81E+04 #FG 2964 3727 3978 3122 3432 4340 3554 3087 11821 5741 15595 15505 15406 13556 11410 13609 3454 2532 5524 5994 3255 3130 4225 4300 10867 12255 15843 11572 15437 10859 12123 10473 9158 4125 7531 7029 9551 7549 10156 6323 22304 15199 30652 19710 22396 19462 23036 18075 7267 15196 46110 19686

30

8400 8400 8400 8400 11600 11600 11600 11600 11600 11600 11600 11600 10500 10500 10500 10500 10500 10500 10500 10500 14500 14500 14500 14500 14500 14500 14500 14500 12600 12600 12600 12600 12600 12600 12600 12600 17400 17400 17400 17400 17400 17400 17400 17400 14700 14700 14700 14700 14700 14700 14700 14700 20300 20300 20300

400 400 400 400 3600 3600 3600 3600 3600 3600 3600 3600 500 500 500 500 500 500 500 500 4500 4500 4500 4500 4500 4500 4500 4500 600 600 600 600 600 600 600 600 5400 5400 5400 5400 5400 5400 5400 5400 700 700 700 700 700 700 700 700 6300 6300 6300

400 400 400 400 360 360 360 360 360 360 360 360 500 500 500 500 500 500 500 500 450 450 450 450 450 450 450 450 600 600 600 600 600 600 600 600 540 540 540 540 540 540 540 540 700 700 700 700 700 700 700 700 630 630 630

3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0

.2E-01 .2E-01 .3E-01 .2E-01 .8E-02 .8E-02 .1E-01 .1E-01 .2E-01 .2E-01 .3E-01 .4E-01 .4E-02 .4E-02 .5E-02 .5E-02 .1E-01 .7E-02 .2E-01 .2E-01 .7E-02 .7E-02 .2E-01 .2E-01 .2E-01 .2E-01 .2E-01 .2E-01 .7E-02 .4E-02 .3E-02 .3E-02 .1E-01 .1E-01 .2E-01 .2E-01 .1E-01 .1E-01 .1E-01 .1E-01 .1E-01 .1E-01 .3E-01 .2E-01 .3E-02 .2E-02 .3E-02 .2E-02 .1E-01 .8E-02 .2E-01 .2E-01 .1E-01 .6E-02 .9E-02

.2E+00 .2E+00 .3E+00 .2E+00 .4E-01 .4E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .1E+00 .1E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .6E-01 .6E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .1E+00 .8E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .6E-01 .6E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .6E-01 .5E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .6E-01 .3E-01 .2E+00

.1E-01 .1E-01 .9E-02 .6E-02 .1E-01 .1E-01 .8E-01 .7E-01 .7E-01 .7E-01 .7E-01 .7E-01 .2E-01 .2E-01 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .8E-01 .8E-01 .7E-01 .7E-01 .7E-01 .7E-01 .3E-01 .9E-02 .2E-01 .2E-01 .9E-02 .8E-02 .8E-02 .8E-02 .3E-01 .3E-01 .8E-01 .8E-01 .8E-01 .8E-01 .9E-01 .8E-01 .1E-01 .8E-03 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .8E-02 .7E-01

.19E+04 .35E+04 .16E+04 .52E+04 .11E+05 .20E+05 .55E+04 .98E+04 .70E+04 .12E+05 .79E+04 .13E+05 .13E+04 .19E+04 .86E+04 .56E+04 .24E+04 .46E+04 .29E+04 .41E+04 .17E+05 .43E+05 .12E+05 .22E+05 .74E+04 .14E+05 .64E+04 .14E+05 .29E+04 .11E+05 .18E+05 .14E+05 .41E+04 .71E+04 .42E+04 .72E+04 .14E+05 .24E+05 .99E+04 .21E+05 .15E+05 .30E+05 .81E+04 .26E+05 .33E+05 .53E+05 .51E+04 .11E+05 .39E+04 .71E+04 .33E+04 .67E+04 .20E+05 .68E+05 .31E+05

10433 8481 8628 12967 33337 23876 21929 19009 31448 25021 34748 26503 6525 4383 30051 11075 9688 8299 10669 7721 41039 36974 35190 28218 24429 22234 21697 21782 7837 10689 52585 20635 14256 11178 14525 11276 26450 18903 23532 23383 39597 35092 21613 30795 70823 40177 14060 13687 10589 9022 9336 8342 31669 40418 55268

31

20300 20300 20300 20300 20300 16800 16800 16800 16800 16800 16800 16800 16800 23200 23200 23200 23200 23200 23200 23200 23200 18900 18900 18900 18900 18900 18900 18900 18900 26100 26100 26100 26100 26100 26100 26100 26100 21000 21000 21000 21000 21000 21000 21000 21000 29000 29000 29000 29000 29000 29000 29000 29000

6300 6300 6300 6300 6300 800 800 800 800 800 800 800 800 7200 7200 7200 7200 7200 7200 7200 7200 900 900 900 900 900 900 900 900 8100 8100 8100 8100 8100 8100 8100 8100 1000 1000 1000 1000 1000 1000 1000 1000 9000 9000 9000 9000 9000 9000 9000 9000

630 630 630 630 630 800 800 800 800 800 800 800 800 720 720 720 720 720 720 720 720 900 900 900 900 900 900 900 900 810 810 810 810 810 810 810 810 1000 1000 1000 1000 1000 1000 1000 1000 900 900 900 900 900 900 900 900

2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4

0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0

.9E-02 .8E-02 .2E-01 .1E-01 .2E-01 .5E-02 .5E-02 .4E-02 .4E-02 .2E-01 .2E-01 .2E-01 .2E-01 .1E-01 .1E-01 .1E-01 .1E-01 .5E-01 .5E-01 .4E-01 .4E-01 .3E-02 .3E-02 .5E-02 .5E-02 .7E-02 .8E-02 .2E-01 .2E-01 .7E-02 .7E-02 .2E-01 .1E-01 .1E-01 .1E-01 .1E-01 .1E-01 .8E-02 .4E-02 .6E-02 .6E-02 .8E-02 .6E-02 .2E-01 .2E-01 .6E-02 .4E-02 .1E-01 .1E-01 .2E-01 .3E-01 .2E-01 .2E-01

.2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .8E-01 .9E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .5E-01 .5E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .5E-01 .5E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .4E-01 .4E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .1E+00 .9E-01 .3E+00 .3E+00 .2E+00 .2E+00 .2E+00 .2E+00 .3E-01 .2E-01 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00 .2E+00

.7E-01 .7E-01 .8E-01 .7E-01 .8E-01 .2E-01 .2E-01 .2E-01 .2E-01 .2E-01 .2E-01 .2E-01 .2E-01 .1E-01 .1E-01 .7E-01 .7E-01 .8E-01 .8E-01 .8E-01 .8E-01 .4E-02 .4E-02 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .1E-01 .1E-01 .6E-01 .5E-01 .6E-01 .6E-01 .6E-01 .6E-01 .2E-01 .2E-01 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .3E-01 .1E-01 .8E-02 .5E-01 .5E-01 .5E-01 .4E-01 .5E-01 .5E-01

.43E+05 .15E+05 .26E+05 .16E+05 .24E+05 .21E+04 .29E+05 .14E+05 .29E+05 .44E+04 .89E+04 .43E+04 .77E+04 .52E+05 .89E+05 .22E+05 .40E+05 .11E+05 .24E+05 .11E+05 .23E+05 .97E+04 .18E+05 .15E+05 .97E+04 .58E+04 .97E+04 .65E+04 .11E+05 .36E+05 .58E+05 .36E+05 .68E+05 .13E+05 .30E+05 .14E+05 .25E+05 .73E+04 .74E+04 .19E+05 .34E+05 .97E+04 .15E+05 .89E+04 .14E+05 .74E+05 .11E+06 .32E+05 .65E+05 .20E+05 .70E+05 .24E+05 .45E+05

33267 30918 24024 35951 26682 6860 23143 33309 29041 12481 11513 12287 10333 81255 54771 43889 35225 24124 25171 27121 25859 18475 12038 31971 11938 14211 11597 15880 12766 51392 33184 58045 49973 26525 28362 27132 24129 13222 7942 37480 26933 21920 15613 20290 13977 91954 52298 47058 36065 33740 47873 35569 33555

32

For the interior point algorithm we obtained the following results (the meaning of the columns is the same as above. #F is the number of function evaluations, #FG the number of simultaneous evaluations of the function and its gradient and #H*D the number of Hessian- times-vector operations):

FEPS=1.D-7 CEPS=1.D-6 FEASEPS=1.D-6 N M J0 I T DXR DMR DLR TIME 1000 100 100 1 2 .7E-05 .6E-04 .7E-05 .76E+01 1000 100 100 2 2 .2E-01 .3E+00 .2E-01 .11E+02 1000 100 100 3 2 .6E-02 .2E+00 .2E-03 .43E+02 1000 100 100 4 2 .2E-01 .2E+00 .2E-03 .57E+02 1000 900 90 1 1 .1E-05 .1E-04 .1E-07 .14E+02 1000 900 90 2 2 .1E-01 .2E+00 .4E-01 .15E+02 1000 900 90 3 2 .3E-01 .3E+00 .1E+00 .14E+02 1000 900 90 4 2 .1E-01 .2E+00 .1E+00 .17E+02 2000 200 200 1 1 .5E-05 .1E-03 .1E-06 .17E+02 2000 200 200 2 2 .6E-03 .3E-01 .7E-04 .35E+02 2000 200 200 3 2 .4E-01 .2E+00 .4E-01 .47E+02 2000 200 200 4 2 .3E-01 .4E-01 .3E-03 .18E+03 2000 1800 180 1 2 .7E-06 .5E-05 .7E-07 .33E+02 2000 1800 180 2 2 .3E-01 .2E+00 .1E+00 .35E+02 2000 1800 180 3 2 .2E-01 .2E+00 .7E-01 .53E+02 2000 1800 180 4 2 .2E-01 .2E+00 .8E-01 .56E+02 3000 300 300 1 2 .3E-05 .9E-05 .6E-06 .45E+02 3000 300 300 2 2 .6E-01 .3E+00 .8E-01 .44E+02 3000 300 300 3 2 .8E-01 .3E+00 .9E-01 .47E+02 3000 300 300 4 2 .8E-01 .3E+00 .9E-01 .48E+02 3000 2700 270 1 2 .9E-06 .8E-05 .6E-07 .60E+02 3000 2700 270 2 2 .8E-02 .1E+00 .1E-01 .74E+02 3000 2700 270 3 2 .1E-01 .2E+00 .7E-01 .12E+03 3000 2700 270 4 2 .1E-01 .2E+00 .8E-01 .12E+03 4000 400 400 1 1 .4E-05 .1E-03 .7E-07 .54E+02 4000 400 400 2 2 .4E-02 .2E+00 .2E-01 .86E+02 4000 400 400 3 2 .4E-02 .5E-01 .7E-04 .25E+03 4000 400 400 4 2 .1E-01 .5E-01 .2E-04 .45E+03 4000 3600 360 1 1 .6E-06 .5E-05 .1E-07 .85E+02 4000 3600 360 2 2 .9E-02 .1E+00 .2E-01 .13E+03 4000 3600 360 3 2 .1E-01 .2E+00 .6E-01 .17E+03 4000 3600 360 4 2 .2E-01 .2E+00 .7E-01 .12E+03 5000 500 500 1 1 .2E-05 .5E-04 .2E-07 .75E+02 5000 500 500 2 2 .6E-02 .2E+00 .1E-01 .12E+03 5000 500 500 3 2 .3E-02 .1E+00 .5E-04 .32E+03 5000 500 500 4 2 .2E-01 .1E+00 .8E-02 .40E+03 5000 4500 450 1 1 .5E-06 .5E-05 .3E-08 .12E+03 5000 4500 450 2 2 .7E-02 .1E+00 .7E-02 .17E+03 5000 4500 450 3 2 .1E-01 .2E+00 .7E-01 .27E+03 5000 4500 450 4 2 .2E-01 .2E+00 .8E-01 .23E+03 6000 600 600 1 1 .4E-05 .1E-03 .5E-07 .90E+02 6000 600 600 2 2 .3E-02 .2E+00 .9E-02 .15E+03 6000 600 600 3 2 .2E-02 .7E-01 .5E-04 .34E+03 6000 600 600 4 2 .1E-01 .7E-01 .4E-04 .38E+03 6000 5400 540 1 2 .2E-06 .2E-05 .1E-08 .17E+03 6000 5400 540 2 2 .5E-02 .1E+00 .3E-02 .22E+03 6000 5400 540 3 2 .7E-02 .2E+00 .6E-01 .33E+03 6000 5400 540 4 2 .1E-01 .2E+00 .8E-01 .34E+03 7000 700 700 1 1 .3E-05 .8E-04 .3E-07 .12E+03 #F 207 269 755 815 239 254 240 266 193 366 441 1221 225 234 336 354 256 245 259 263 234 278 418 436 218 315 743 896 223 306 404 292 219 311 691 749 225 299 455 397 204 298 608 650 236 283 404 421 202 #F&G 129 155 449 482 147 151 143 157 122 222 241 675 141 140 192 201 155 143 150 152 146 164 234 243 135 180 427 508 140 178 228 172 136 178 395 427 141 175 253 224 128 172 354 378 144 168 227 236 127 #H*D 1697 2439 7875 9429 1973 2205 2079 2334 1592 3220 4464 14415 1938 2111 3220 3421 2402 2390 2554 2600 2120 2669 4294 4501 2030 3294 8664 13008 2040 3123 4284 2931 2108 3377 8415 9881 2168 3152 5117 4386 2009 3329 7231 7905 2344 3040 4638 4927 2055

33

7000 7000 7000 7000 7000 7000 7000 8000 8000 8000 8000 8000 8000 8000 8000 9000 9000 9000 9000 9000 9000 9000 9000 10000 10000 10000 10000 10000 10000 10000 10000

700 700 700 6300 6300 6300 6300 800 800 800 800 7200 7200 7200 7200 900 900 900 900 8100 8100 8100 8100 1000 1000 1000 1000 9000 9000 9000 9000

700 700 700 630 630 630 630 800 800 800 800 720 720 720 720 900 900 900 900 810 810 810 810 1000 1000 1000 1000 900 900 900 900

2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

2 2 2 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 1 2 2 2

.4E-03 .4E-02 .2E-01 .7E-06 .8E-02 .8E-02 .1E-01 .1E-05 .3E-03 .7E-02 .1E-01 .4E-06 .5E-02 .7E-02 .1E-01 .2E-05 .2E-02 .2E-02 .2E-01 .9E-06 .4E-02 .7E-02 .1E-01 .2E-05 .3E-03 .6E-02 .9E-02 .3E-05 .6E-02 .8E-02 .1E-01

.6E-01 .1E+00 .1E+00 .6E-05 .1E+00 .2E+00 .2E+00 .4E-04 .4E-01 .2E+00 .7E-01 .4E-05 .1E+00 .2E+00 .2E+00 .5E-04 .1E+00 .7E-01 .7E-01 .8E-05 .1E+00 .1E+00 .2E+00 .5E-04 .4E-01 .2E+00 .7E-01 .2E-04 .1E+00 .2E+00 .2E+00

.5E-05 .5E-04 .8E-02 .4E-08 .2E-01 .7E-01 .8E-01 .1E-07 .2E-05 .2E-01 .9E-04 .3E-08 .4E-02 .5E-01 .6E-01 .1E-07 .6E-02 .2E-04 .2E-03 .1E-07 .2E-02 .4E-01 .5E-01 .5E-08 .3E-05 .2E-01 .2E-04 .3E-08 .9E-02 .5E-01 .8E-01

.21E+03 .40E+03 .45E+03 .21E+03 .28E+03 .34E+03 .27E+03 .15E+03 .25E+03 .40E+03 .80E+03 .25E+03 .34E+03 .41E+03 .48E+03 .18E+03 .27E+03 .73E+03 .83E+03 .31E+03 .47E+03 .52E+03 .54E+03 .22E+03 .38E+03 .56E+03 .12E+04 .37E+03 .46E+03 .66E+03 .61E+03

351 614 658 228 287 347 284 209 349 489 882 237 294 347 397 202 282 664 722 233 329 352 361 211 348 452 813 234 269 367 340

214 3756 361 7184 386 7858 143 2390 169 3264 199 4026 168 3183 131 2232 211 3922 267 6261 490 11835 147 2545 174 3443 197 4146 223 4880 127 2205 164 3475 375 8915 406 9985 142 2557 189 3942 201 4351 207 4557 132 2418 211 4170 249 6162 460 12092 142 2608 160 3324 208 4773 193 4380

34

- Numerical methods for large-scale nonlinear
- Analysis TRUNCATED QZ METHODS FOR LARGE SCALE GENERALIZED EIGENVALUE PROBLEMS
- Numerical experiments with some explicit pseudo two-step RK methods on a shared memory comp
- Large-scale machine learning with stochastic gradient descent
- Krylov subspace methods for large-scale matrix problems in control
- M Raydan-Gradient method with dynamical retards for large-scale optimization problems.
- Scalable, efficient ion-photon coupling with phase Fresnel lenses for large-scale quantum c
- Introduction Performance of Hybrid Methods for Large-Scale Unconstrained Optimization as Ap
- Global Inexact Newton Methods for Very Large Scale Nonlinear Problems
- Interior-point methods with decomposition for solving large-scale linear programs
- 学霸百科
- 新词新语