C ALGORITHM 778, COLLECTED ALGORITHMS FROM ACM. C THIS WORK PUBLISHED IN TRANSACTIONS ON MATHEMATICAL SOFTWARE, C VOL. 23,NO. 4, December, 1997, P. 550--560. #! /bin/sh # This is a shell archive, meaning: # 1. Remove everything above the #! /bin/sh line. # 2. Save the resulting text in a file. # 3. Execute the file with /bin/sh (not csh) to create the files: # Doc # Drivers # Info # Src # This archive created: Fri Jul 31 08:51:37 1998 export PATH; PATH=/bin:$PATH if test ! -d 'Doc' then mkdir 'Doc' fi cd 'Doc' if test -f 'Makefile' then echo shar: will not over-write existing file "'Makefile'" else cat << \SHAR_EOF > 'Makefile' FC = epcf90 FFLAGS = -sloppy -C -d1 -g -temp=/tmp -u DRIVER1 = driver1.o DRIVER2 = driver2.o DRIVER3 = driver3.o ROUTINES = src.o blas1.o dpmeps.o linpack.o timer.o all : lbfgsb1 lbfgsb2 lbfgsb3 lbfgsb1 : $(DRIVER1) $(ROUTINES) $(FC) $(FFLAGS) $(DRIVER1) $(ROUTINES) -o x.lbfgsb1 lbfgsb2 : $(DRIVER2) $(ROUTINES) $(FC) $(FFLAGS) $(DRIVER2) $(ROUTINES) -o x.lbfgsb2 lbfgsb3 : $(DRIVER3) $(ROUTINES) $(FC) $(FFLAGS) $(DRIVER3) $(ROUTINES) -o x.lbfgsb3 SHAR_EOF fi # end of overwriting check if test -f 'Readme' then echo shar: will not over-write existing file "'Readme'" else cat << \SHAR_EOF > 'Readme' L-BFGS-B (version 2.3) April 1997 This directory contains the limited memory code for solving bound constrained optimization problems. A makefile is provided for Unix users. We recommend that the user read driver1.f, which gives a good idea of how the code works as well as directions on how to adapt the timing routine to particular systems. Two articles are also included [1] algorithm.ps - describes the algorithm [2] compact.ps - presents the compact form of matrices A description of the use of the code is appended to this file. Users interested in understanding the algorithm should read [1] and possibly also [2]. _______________________________________________________________________ For questions and help contact Ciyou Zhu or Jorge Nocedal ciyou@ece.nwu.edu nocedal@ece.nwu.edu _______________________________________________________________________ To run the code on a Unix machine simply type make This will create (among others) the file x.lbfgsb1* which is the executable file for the simplest driver in the package. One can execute the program by typing x.lbfgsb1 ************************************************************************ How to use L-BFGS-B ************************************************************************ The simplest way to use the code is to modify one of the drivers provided in the package. Most users will only need to make a few changes to the drivers to run their applications. L-BFGS-B is written in FORTRAN 77, in double precision. The user is required to calculate the function value f and its gradient g. In order to allow the user complete control over these computations, reverse communication is used. The routine setulb.f must be called repeatedly under the control of the variable task. The calling statement of L-BFGS-B is call setulb(n,m,x,l,u,nbd,f,g,factr,pgtol,wa,iwa,task,iprint, + csave,lsave,isave,dsave) Following is a description of all the parameters used in this call. c n is an INTEGER variable that must be set by the user to the c number of variables. It is not altered by the routine. c c m is an INTEGER variable that must be set by the user to the c number of corrections used in the limited memory matrix. c It is not altered by the routine. Values of m < 3 are c not recommended, and large values of m can result in excessive c computing time. The range 3 <= m <= 20 is recommended. c c x is a DOUBLE PRECISION array of length n. On initial entry c it must be set by the user to the values of the initial c estimate of the solution vector. Upon successful exit, it c contains the values of the variables at the best point c found (usually an approximate solution). c c l is a DOUBLE PRECISION array of length n that must be set by c the user to the values of the lower bounds on the variables. If c the i-th variable has no lower bound, l(i) need not be defined. c c u is a DOUBLE PRECISION array of length n that must be set by c the user to the values of the upper bounds on the variables. If c the i-th variable has no upper bound, u(i) need not be defined. c c nbd is an INTEGER array of dimension n that must be set by the c user to the type of bounds imposed on the variables: c nbd(i)=0 if x(i) is unbounded, c 1 if x(i) has only a lower bound, c 2 if x(i) has both lower and upper bounds, c 3 if x(i) has only an upper bound. c c f is a DOUBLE PRECISION variable. If the routine setulb returns c with task(1:2)= 'FG', then f must be set by the user to c contain the value of the function at the point x. c c g is a DOUBLE PRECISION array of length n. If the routine setulb c returns with taskb(1:2)= 'FG', then g must be set by the user to c contain the components of the gradient at the point x. c c factr is a DOUBLE PRECISION variable that must be set by the user. c It is a tolerance in the termination test for the algorithm. c The iteration will stop when c c (f^k - f^{k+1})/max{|f^k|,|f^{k+1}|,1} <= factr*epsmch c c where epsmch is the machine precision which is automatically c generated by the code. Typical values for factr on a computer c with 15 digits of accuracy in double precision are: c factr=1.d+12 for low accuracy; c 1.d+7 for moderate accuracy; c 1.d+1 for extremely high accuracy. c The user can suppress this termination test by setting factr=0. c c pgtol is a double precision variable. c On entry pgtol >= 0 is specified by the user. The iteration c will stop when c c max{|proj g_i | i = 1, ..., n} <= pgtol c c where pg_i is the ith component of the projected gradient. c The user can suppress this termination test by setting pgtol=0. c c wa is a DOUBLE PRECISION array of length c (2mmax + 4)nmax + 11mmax^2 + 8mmax used as workspace. c This array must not be altered by the user. c c iwa is an INTEGER array of length 3nmax used as c workspace. This array must not be altered by the user. c c task is a CHARACTER string of length 60. c On first entry, it must be set to 'START'. c On a return with task(1:2)='FG', the user must evaluate the c function f and gradient g at the returned value of x. c On a return with task(1:5)='NEW_X', an iteration of the c algorithm has concluded, and f and g contain f(x) and g(x) c respectively. The user can decide whether to continue or stop c the iteration. c When c task(1:4)='CONV', the termination test in L-BFGS-B has been c satisfied; c task(1:4)='ABNO', the routine has terminated abnormally c without being able to satisfy the termination conditions, c x contains the best approximation found, c f and g contain f(x) and g(x) respectively; c task(1:5)='ERROR', the routine has detected an error in the c input parameters; c On exit with task = 'CONV', 'ABNO' or 'ERROR', the variable task c contains additional information that the user can print. c This array should not be altered unless the user wants to c stop the run for some reason. See driver2 or driver3 c for a detailed explanation on how to stop the run c by assigning task(1:4)='STOP' in the driver. c c iprint is an INTEGER variable that must be set by the user. c It controls the frequency and type of output generated: c iprint<0 no output is generated; c iprint=0 print only one line at the last iteration; c 0100 print details of every iteration including x and g; c When iprint > 0, the file iterate.dat will be created to c summarize the iteration. c c csave is a CHARACTER working array of length 60. c c lsave is a LOGICAL working array of dimension 4. c On exit with task = 'NEW_X', the following information is c available: c lsave(1) = .true. the initial x did not satisfy the bounds; c lsave(2) = .true. the problem contains bounds; c lsave(3) = .true. each variable has upper and lower bounds. c c isave is an INTEGER working array of dimension 44. c On exit with task = 'NEW_X', it contains information that c the user may want to access: c isave(30) = the current iteration number; c isave(34) = the total number of function and gradient c evaluations; c isave(36) = the number of function value or gradient c evaluations in the current iteration; c isave(38) = the number of free variables in the current c iteration; c isave(39) = the number of active constraints at the current c iteration; c c see the subroutine setulb.f for a description of other c information contained in isave c c dsave is a DOUBLE PRECISION working array of dimension 29. c On exit with task = 'NEW_X', it contains information that c the user may want to access: c dsave(2) = the value of f at the previous iteration; c dsave(5) = the machine precision epsmch generated by the code; c dsave(13) = the infinity norm of the projected gradient; c c see the subroutine setulb.f for a description of other c information contained in dsave SHAR_EOF fi # end of overwriting check if test -f 'algorithm.ps' then echo shar: will not over-write existing file "'algorithm.ps'" else cat << \SHAR_EOF > 'algorithm.ps' %!PS-Adobe-2.0 %%Creator: dvips 5.47 Copyright 1986-91 Radical Eye Software %%Title: pp8.dvi %%Pages: 25 1 %%BoundingBox: 0 0 612 792 %%EndComments %%BeginProcSet: tex.pro /TeXDict 200 dict def TeXDict begin /N /def load def /B{bind def}N /S /exch load def /X{S N}B /TR /translate load N /isls false N /vsize 10 N /@rigin{ isls{[0 1 -1 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale Resolution VResolution vsize neg mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@letter{/vsize 10 N}B /@landscape{/isls true N /vsize -1 N}B /@a4{/vsize 10.6929133858 N}B /@a3{ /vsize 15.5531 N}B /@ledger{/vsize 16 N}B /@legal{/vsize 13 N}B /@manualfeed{ statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail} B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]{ch-image} imagemask restore}B /D{/cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto}N /eop{clear SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook}if /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for}N /p /show load N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval(Display)eq}{pop false}ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /a{ moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{ S p tail}B /c{-4 M}B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w }B /q{p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{clear SS restore}B end %%EndProcSet TeXDict begin 1000 300 300 @start /Fa 7 85 df<001F0000001F0000003F8000003B8000 003B8000007BC0000073C0000071C00000F1E00000E1E00000E0E00001E0F00001E0F00001C0F0 0003C0780003C078000380780007803C0007803C0007003C000FFFFE000FFFFE000FFFFE001E00 0F001E000F003C000F803C0007803C000780780007C0780003C0780003C0F00003E01B207F9F1E >65 D<001FC000FFF801FFFC03E03C07800C0F00001E00003E00003C00007C0000780000780000 780000F00000F00000F00000F00000F00000F00000F00000F000007800007800007800007C0000 3C00003E00001E00000F000207800E03E03E01FFFC00FFF0001FC017227DA01D>67 D69 D76 D78 D<003F000000FFC00003FFF00007E1F8000F807C001F003E001E001E003C000F003C000F007800 07807800078078000780F00003C0F00003C0F00003C0F00003C0F00003C0F00003C0F00003C0F0 0003C0F00003C0F80007C07800078078000780780007803C000F003C000F001E001E001F003E00 0F807C0007E1F80003FFF00000FFC000003F00001A227DA021>I84 D E /Fb 1 49 df<081C1C3838383070706060C0C0060D7E8D09>48 D E /Fc 4 50 df0 D<020002000200C218F2783AE00F800F803A E0F278C2180200020002000D0E7E8E12>3 D<060F0F0E1E1E1C3C383830707060E0C04008117F 910A>48 D<0F8007C019E01C202070301040184008C00C80048007800480070004800380048007 80048004C00C400860082030381010E01E600F8007C01E0E7E8D23>I E /Fd 17 114 df34 DI<00001C00003C0000F80001E00003C0000780000F00000E00001E0000 3C00003C00003C0000780000780000780000780000780000780000780000780000780000780000 780000780000780000780000780000780000780000780000780000780000780000780000780000 780000780000780000780000780000780000780000780000780000780000780000780000780000 780000780000F00000F00000F00001E00001E00003C0000380000700000E00001C0000780000E0 0000E000007800001C00000E000007000003800003C00001E00001E00000F00000F00000F00000 780000780000780000780000780000780000780000780000780000780000780000780000780000 780000780000780000780000780000780000780000780000780000780000780000780000780000 7800007800007800007800007800007800007800007800007800007800007800007800003C0000 3C00003C00001E00000E00000F000007800003C00001E00000F800003C00001C167C7B8121>40 D50 DI< E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E0 00E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000 E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E0 00E000E000E000E000E000E000E000E000E000E000E000E000FFFCFFFCFFFC0E4A73811C>I<00 1C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C 001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00 1C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C 001C001C001C001C001C001C001C001C001C001C001C001CFFFCFFFCFFFC0E4A80811C>III<0018007800F001E003C00780 0F001F001E003E003C007C007C007800F800F800F800F800F800F800F800F800F800F800F800F8 00F800F800F800F800F800F800F800F800F800F800F8000D25707E25>I58 D<007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C 007C007C007C007C007C00F800F800F800F001F001E003E003C0078007000E001C003800F000C0 00F00038001C000E000700078003C003E001E001F000F000F800F800F8007C007C007C007C007C 007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C007C0E 4D798025>60 D62 D104 DI<00000000020000000006000000000C000000000C000000001800000000180000000030 00000000300000000060000000006000000000C000000000C00000000180000000018000000003 000000000300000000060000000006000000000C000000000C0000000018000000001800000000 30000000003000000000600008000060001C0000C0003C0000C000CE000180000E000180000E00 03000007000300000700060000038006000003800C000001C00C000001C018000001E018000000 E030000000E0300000007060000000706000000038C000000038C00000001D800000001D800000 001F000000000F000000000E000000000600000027327C812A>112 D<00000000020000000006 0000000006000000000C000000000C000000000C00000000180000000018000000001800000000 300000000030000000003000000000600000000060000000006000000000C000000000C0000000 00C000000001800000000180000000018000000003000000000300000000030000000006000000 00060000000006000000000C000000000C000000000C0000000018000000001800000000180000 00003000000000300000000030000000006000000000600008000060001C0000C0003C0000C000 7C0000C000DC000180008E000180000E000180000E000300000700030000070003000007000600 000380060000038006000003800C000003800C000001C00C000001C018000001C018000000E018 000000E030000000E030000000E03000000070600000007060000000706000000038C000000038 C000000038C00000001D800000001D800000001D800000001F000000000F000000000F00000000 0E00000000060000000006000000274B7C812A>I E /Fe 18 118 df<01E0033006100C100810 1818101830183010603060307FF06030C060C060C060C0C0C0C0C180C1004300660038000D177E 9610>18 D<60F0F070101020204040040A7D830A>59 D<1FFFFE381C0E201C04601C04401C0440 380480380400380000380000700000700000700000700000E00000E00000E00000E00001C00001 C00001C00001C00003C0007FFC0017177F9615>84 D<071018F0307060706060C060C060C06080 C080C480C4C1C446C838700E0E7E8D13>97 D<7C00180018001800180030003000300030006780 68C070406060C060C060C060C06080C080C08180C10046003C000B177E960F>I<07C00C201070 20706000C000C000C00080008000C010C02060C03F000C0E7E8D0F>I<003E000C000C000C000C 0018001800180018073018F0307060706060C060C060C06080C080C480C4C1C446C838700F177E 9612>I<000E0013003700360060006000600060006007FC00C000C000C000C000C00180018001 8001800180018003000300030003006600E600CC007800101D7E9611>102 D<0300038003000000000000000000000000001C002400460046008C000C001800180018003100 3100320032001C0009177F960C>105 D<00180038001000000000000000000000000001C00220 04300430086000600060006000C000C000C000C001800180018001806300E300C60078000D1D80 960E>I<1F0006000600060006000C000C000C000C00181C1866188E190C32003C003F00318060 C060C460C460C8C0C8C0700F177E9612>I<3E0C0C0C0C181818183030303060606060C0C8C8C8 D07007177E960B>I<383C1E0044C6630047028100460301008E0703000C0603000C0603000C06 0600180C0600180C0620180C0C20180C0C4030180440301807801B0E7F8D1F>I<383C0044C600 4702004602008E06000C06000C06000C0C00180C00180C40181840181880300880300F00120E7F 8D15>I<07C00C20101020186018C018C018C01880308030C060C0C061803E000D0E7E8D11>I<1C 3C22462382230346030603060306030C060C060C0C0C081A3019E018001800300030003000FC00 1014808D12>I<030003000600060006000600FFC00C000C000C00180018001800180030003080 3080310031001E000A147F930D>116 D<1C0200260600460600460600860C000C0C000C0C000C 0C001818001818801818801838800C5900078E00110E7F8D14>I E /Ff 19 121 df0 D<400004C0000C6000183000301800600C00C0 06018003030001860000CC0000780000300000300000780000CC000186000303000601800C00C0 180060300030600018C0000C40000416187A9623>2 D<03C00FF01FF83FFC7FFE7FFEFFFFFFFF FFFFFFFFFFFFFFFF7FFE7FFE3FFC1FF80FF003C010127D9317>15 D17 D<000000C0000003C000000F0000003C000000F0000003C00000070000001C00000078000001E0 0000078000001E00000078000000E0000000780000001E0000000780000001E000000078000000 1C0000000700000003C0000000F00000003C0000000F00000003C0000000C00000000000000000 00000000000000000000000000000000000000007FFFFF80FFFFFFC01A247C9C23>20 DI<00000004 00000000020000000002000000000100000000008000000000400000000020FFFFFFFFFCFFFFFF FFFC00000000200000000040000000008000000001000000000200000000020000000004002610 7D922D>33 D<03E0001F000FFC007FC01C7E00C020301F018010600F8300084007C600084003EC 00088001F800048001F800048000F8000480007C000480007E000480007E00044000DF00084001 8F8008400307C018200603E030100C01F8E00FF800FFC003E0001F0026147D932D>49 D<003FF800FFF803C0000700000C0000180000300000300000600000600000C00000C00000C000 00FFFFF8FFFFF8C00000C00000C000006000006000003000003000001800000C000007000003C0 0000FFF8003FF8151C7C981E>I<400001C0000360000660000660000630000C30000C30000C18 00181800181800180FFFF00FFFF00C00300600600600600600600300C00300C001818001818001 818000C30000C30000C300006600006600006600003C00003C00003C000018000018001821809F 19>56 D<00001E000F00FF0011810F0020C60F8060E40780407807C0407003E0407801E0207801 F0307800F0187800F80C780078047C003C067C0038027C0060027C0180027FFE00427C3C00467C 3C00447C3C00447C3C0038783C0000783C0000783C0000783C0000783C0000783C0040781E00E0 703C0020703C0020601E0810E01E3008C00FC0078003001E227EA021>60 D<00000010000000003000000000F000000000F000000000F000000001F000000001F000000002 F000000002F000000004F00000000CF000000008F000000018F000000010F000000020F0000000 20F000000040F8000000C0F8000000807800000180780000030078000002007800000600780000 0DFFF800000FFFF800001800780000300078000060007C0040E0007C00C0C0003C00E380003C00 FF00003E00FE00003F80FE00001F00780000000021237FA024>65 D<00007FFFE00003FFFFF000 0E3801E000303800C0006078000000E078000001C070000001807000000000F000000000F00000 0000E000000000E000000001E000000001C000000001C000000003FFF8000003FFF00000038000 0000070000000007000000000F000000000E000000000E000000001C000000001C000000003800 0000003800000030700000007870000000FCC00000007F800000003E0000000024207F9E21>70 D<000F0038006000E001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C0 038007001E00F8001E000700038001C001C001C001C001C001C001C001C001C001C001C001C001 C001C001C000E000600038000F102D7DA117>102 DI106 D<4020C030C030C030C030C030C030C030C030C030C030 C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C0 30C030C030C030C030C030C030C030C030C030C030C030C030C030C03040200C2E7BA117>I114 D<0F80184030207010E030E070E020E000E000600070003000180006 00198030C070606070E030E038E038E03860387030307018600CC0030000C00060007000300038 00382038703860384070206010C00F800D297D9F14>120 D E /Fg 50 123 df<007C0001C3000701810E01C11E00C11C00E23C00E27800E27800E47800E4F000E8F000F0F0 00F0F000E0F000E07000E07003E030046118383207C01C18147E931D>11 D<0000F800030600040600080300100300200300400700400700800700800601000E01000C0107 F80104700207D802001C02001C02001E04001E04001E04001E04001E08003C08003C08003C0800 781800701400F01400E01201C0218700207C002000002000004000004000004000004000008000 0080000080000018297F9F1A>I<03E0040FF0081FF8083FF810301C10400C10C0042080042000 024000024000028000028000028000030000030000030000020000020000020000060000060000 0600000C00000C00000C00000C00001800001800001800001000161E7F9318>I<001E00006300 00C38001C1800381800301C00701C00F01C00E01C01E03C01C03C03C03C03C03C03C03C0780780 7FFF807FFF80780780F00F00F00F00F00F00F00E00F01E00E01C00E03C00E03800E03000607000 60E00070C0003180001E000012207E9F15>18 D<07000001C00000E00000E00000F00000700000 7000007800003800003800003C00001C00001C00001E00000E00000E00000F00000700000F0000 378000638000C38001C3C00381C00701C00E01E01C00E03800E07000F0F00070E00070C0003815 207D9F1B>21 D<000F800038C000606000C07001C0700380780380780700780700780700780E00 F00E00F00E00F00E01E01C01C01C01C01E03801E0700390C0038F0003800003800007000007000 00700000700000E00000E00000E00000C00000151E7F9318>26 D<70F8F8F87005057C840D>58 D<70F8FCFC74040404080810102040060E7C840D>I<000001C00000078000001E000000780000 01E00000078000000E00000038000000F0000003C000000F0000003C000000F0000000F0000000 3C0000000F00000003C0000000F0000000380000000E0000000780000001E0000000780000001E 0000000780000001C01A1A7C9723>I<000100030003000600060006000C000C000C0018001800 1800300030003000600060006000C000C000C00180018001800300030003000600060006000C00 0C000C00180018001800300030003000600060006000C000C000C000102D7DA117>II<00000200000006000000 0E0000000E0000001E0000001F0000002F0000002F0000004F0000008F0000008F0000010F0000 010F0000020F0000040F0000040F0000080F8000080780001007800020078000200780007FFF80 0040078000800780018007800100078002000780020007C0040003C00C0003C01E0007C0FF807F FC1E207E9F22>65 D<00FFFFE0000F0078000F003C000F001C000F001E001E001E001E001E001E 001E001E001E003C003C003C003C003C0078003C00F0007803C0007FFF80007803C0007801E000 F000F000F000F000F000F000F0007001E000F001E000F001E000F001E000E003C001E003C003C0 03C0038003C00F0007801E00FFFFF0001F1F7E9E22>I<00FFFFE000000F007800000F001C0000 0F000E00000F000700001E000700001E000380001E000380001E000380003C000380003C000380 003C000380003C000380007800078000780007800078000780007800078000F0000F0000F0000F 0000F0000E0000F0001E0001E0001C0001E0003C0001E000380001E000700003C000E00003C001 C00003C003800003C007000007803C0000FFFFF00000211F7E9E26>68 D<00FFF9FFF0000F801F 00000F001E00000F001E00000F001E00001E003C00001E003C00001E003C00001E003C00003C00 7800003C007800003C007800003C007800007800F000007FFFF000007800F000007800F00000F0 01E00000F001E00000F001E00000F001E00001E003C00001E003C00001E003C00001E003C00003 C007800003C007800003C007800003C007800007C00F8000FFF8FFF800241F7E9E26>72 D<00FFFC000F80000F00000F00000F00001E00001E00001E00001E00003C00003C00003C00003C 0000780000780000780000780000F00000F00000F00000F00001E00001E00001E00001E00003C0 0003C00003C00003C00007C000FFFC00161F7F9E14>I<00FFFC00000F8000000F0000000F0000 000F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C0000007800 0000780000007800000078000000F0000000F0000000F0000000F0004001E0008001E0008001E0 018001E0010003C0030003C0030003C0060003C00E0007803C00FFFFFC001A1F7E9E1F>76 D<00FF00001FF0000F00003F00000B80003E00000B80005E00000B80005E0000138000BC000013 80013C00001380013C00001380023C000023800278000023800478000023800878000021C00878 000041C010F0000041C020F0000041C020F0000041C040F0000081C041E0000081C081E0000081 C101E0000081C101E0000100E203C0000100E203C0000100E403C0000100E803C0000200E80780 000200F00780000200F00780000600E00780000F00C00F8000FFE0C1FFF8002C1F7E9E2C>I<00 FF803FF0000F800780000F800200000BC00200000BC002000013C004000011E004000011E00400 0011E004000020F008000020F008000020F808000020780800004078100000403C100000403C10 0000403C100000801E200000801E200000801E200000800F200001000F400001000F4000010007 C000010007C00002000780000200038000020003800006000380000F00010000FFE0010000241F 7E9E25>I<0001FC0000070700001C01C0003000E000E0006001C0007003800070078000380700 00380E0000381E0000381C0000383C0000383C00003878000078780000787800007878000078F0 0000F0F00000F0F00000E0F00001E0F00001C0F00003C0700003807000070078000F0038001E00 38003C001C0070000E00E0000783800001FC00001D217E9F23>I<00FFFFC0000F0070000F0038 000F001C000F001E001E001E001E001E001E001E001E001E003C003C003C003C003C0078003C00 70007800E000780380007FFE000078000000F0000000F0000000F0000000F0000001E0000001E0 000001E0000001E0000003C0000003C0000003C0000003C0000007C00000FFFC00001F1F7E9E1D >I<00FFFF80000F01E0000F0070000F0038000F003C001E003C001E003C001E003C001E003C00 3C0078003C0078003C00F0003C01E00078038000780F00007FF80000781C0000F00E0000F00F00 00F0070000F0078001E00F0001E00F0001E00F0001E00F0003C01E0003C01E0203C01E0203C01E 0407C00E04FFFC0718000003E01F207E9E23>82 D<0007E0800018118000300B000060070000C0 070001C0030001800200038002000380020003800200038000000380000003C0000003F8000003 FF800001FFC00000FFE000003FF0000003F0000000F00000007000000070000000700020007000 20007000200060006000E0006000C0006001C00070018000E8030000C60E000081F8000019217D 9F1C>I87 D89 D<007FFFF800FC00F000E001E000C003 C0018007800100078003000F0002001E0002003C00040078000000F8000000F0000001E0000003 C00000078000000F0000000F0000001E0000003C00000078008000F0008001F0010001E0010003 C00300078002000F0006001E0004003E000C003C003C007800F800FFFFF8001D1F7D9E1F>I<00 F1800389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F0 0E10F01C20F01C20703C20705C40308C400F078014147E9318>97 D<07803F8007000700070007 000E000E000E000E001C001C001CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE01EE01E E01CE03CE038607060E031C01F0010207E9F14>I<007C01C207010E0F1E0F1C0E3C0478007800 7800F000F000F000F000F00070017002300418380FC010147E9314>I<0000780003F800007000 00700000700000700000E00000E00000E00000E00001C00001C000F1C00389C00707800E03801C 03803C0380380700780700780700780700F00E00F00E00F00E00F00E10F01C20F01C20703C2070 5C40308C400F078015207E9F18>I<007C01C207010E011C013C013802780C7BF07C00F000F000 F000F0007000700170023004183807C010147E9315>I<00007C0000CE00019E00039E00030C00 0700000700000700000700000E00000E00000E0000FFF0000E00000E00001C00001C00001C0000 1C00001C0000380000380000380000380000380000700000700000700000700000700000E00000 E00000E00000E00000C00001C000318000798000F300006200003C000017297E9F16>I<001E30 00713800E0F001C0700380700780700700E00F00E00F00E00F00E01E01C01E01C01E01C01E01C0 1E03801E03800E07800E0B8006170001E700000700000700000E00000E00300E00781C00F03800 6070003FC000151D809316>I<00E001E001E000C000000000000000000000000000000E001300 23804380438043808700070007000E000E001C001C001C20384038403840388019000E000B1F7E 9E10>105 D<0000C00001E00001E00001C0000000000000000000000000000000000000000000 001E00006300004380008380010380010380020700000700000700000700000E00000E00000E00 000E00001C00001C00001C00001C0000380000380000380000380000700000700030700078E000 F1C0006380003E00001328819E13>I<01E0000FE00001C00001C00001C00001C0000380000380 000380000380000700000700000701E00706100E08700E10F00E20F00E40601C80001D00001E00 001FC000387000383800383800381C20703840703840703840701880E01880600F0014207E9F18 >I<03C01FC0038003800380038007000700070007000E000E000E000E001C001C001C001C0038 003800380038007000700070007100E200E200E200E200640038000A207E9F0E>I<1E07C07C00 231861860023A032030043C0340300438038038043803803808700700700070070070007007007 0007007007000E00E00E000E00E00E000E00E00E000E00E01C101C01C01C201C01C038201C01C0 38401C01C0184038038018801801800F0024147E9328>I<1E07802318C023A06043C070438070 4380708700E00700E00700E00700E00E01C00E01C00E01C00E03821C03841C07041C07081C0308 3803101801E017147E931B>I<03C1E004621804741C08781C08701E08701E10E01E00E01E00E0 1E00E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0072380071E000700000700 000E00000E00000E00000E00001C00001C0000FFC000171D819317>112 D<00F0400388C00705800E03801C03803C0380380700780700780700780700F00E00F00E00F00E 00F00E00F01C00F01C00703C00705C0030B8000F38000038000038000070000070000070000070 0000E00000E0000FFE00121D7E9314>I<1E1E0023210023C38043C78043878043830087000007 00000700000700000E00000E00000E00000E00001C00001C00001C00001C000038000018000011 147E9315>I<007C018203010603060706060E00078007F803FC01FE001F00077007F006F006E0 04400820301FC010147E9315>I<00C000E001C001C001C001C003800380FFF803800700070007 0007000E000E000E000E001C001C001C001C10382038203820384018800F000D1C7F9B10>I<0F 00601180702180E021C0E041C0E04380E08381C00701C00701C00701C00E03800E03800E03800E 03840E07080C07080C07080E0F1006131003E1E016147E931A>I<0F01801183C02183E021C1E0 41C0E04380608380400700400700400700400E00800E00800E00800E01000E01000C02000E0400 0E040006180001E00013147E9316>I<0F006060118070F02180E0F821C0E07841C0E0384380E0 188381C0100701C0100701C0100701C0100E0380200E0380200E0380200E0380400E0380400E03 80800E078080060781000709860001F078001D147E9321>I<03C1C00C62201034701038F02038 F020386040700000700000700000700000E00000E00000E00000E02061C040F1C040F1C080E2C0 80446300383C0014147E931A>I<0F00601180702180E021C0E041C0E04380E08381C00701C007 01C00701C00E03800E03800E03800E03800E07000C07000C07000E0F00061E0003EE00000E0000 0E00001C0078180078380070700060600021C0001F0000141D7E9316>I<01E02003F04007F8C0 0C1F8008010000020000040000080000100000600000C000010000020000040080080100100300 3F060061FC0040F80080700013147E9315>I E /Fh 42 123 df<00700000F800007000007000 207020F07078F870F8FE73F83F27E007AF0000F80000F80007AF003F27E0FE73F8F870F8F07078 20702000700000700000F80000700015167DA41C>42 D<387CFEFEFE7C3807077C8610>46 D<00180000780001F800FFF800FFF80001F80001F80001F80001F80001F80001F80001F80001F8 0001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F8 0001F80001F80001F80001F8007FFFE07FFFE013207C9F1C>49 D<03FC000FFF003C1FC07007E0 7C07F0FE03F0FE03F8FE03F8FE01F87C01F83803F80003F80003F00003F00007E00007C0000F80 001F00003E0000380000700000E01801C0180380180700180E00380FFFF01FFFF03FFFF07FFFF0 FFFFF0FFFFF015207D9F1C>I<00FE0007FFC00F07E01E03F03F03F03F81F83F81F83F81F81F03 F81F03F00003F00003E00007C0001F8001FE0001FF000007C00001F00001F80000FC0000FC3C00 FE7E00FEFF00FEFF00FEFF00FEFF00FC7E01FC7801F81E07F00FFFC001FE0017207E9F1C>I<00 00E00001E00003E00003E00007E0000FE0001FE0001FE00037E00077E000E7E001C7E00187E003 07E00707E00E07E00C07E01807E03807E07007E0E007E0FFFFFEFFFFFE0007E00007E00007E000 07E00007E00007E00007E000FFFE00FFFE17207E9F1C>I<1000201E01E01FFFC01FFF801FFF00 1FFE001FF8001BC00018000018000018000018000019FC001FFF001E0FC01807E01803E00003F0 0003F00003F80003F83803F87C03F8FE03F8FE03F8FC03F0FC03F07007E03007C01C1F800FFF00 03F80015207D9F1C>I<001F8000FFE003F07007C0F00F01F81F01F83E01F83E01F87E00F07C00 007C0000FC0800FC7FC0FCFFE0FD80F0FF00F8FE007CFE007CFC007EFC007EFC007EFC007E7C00 7E7C007E7C007E3C007C3E007C1E00F80F00F00783E003FFC000FF0017207E9F1C>I<60000078 00007FFFFE7FFFFE7FFFFC7FFFF87FFFF87FFFF0E00060E000C0C00180C00300C0030000060000 0C00001C0000180000380000780000780000F00000F00000F00001F00001F00001F00003F00003 F00003F00003F00003F00003F00003F00001E00017227DA11C>I66 D<0003FE0080001FFF818000FF01E38001F8003F8003E0001F8007C0000F 800F800007801F800007803F000003803F000003807F000001807E000001807E00000180FE0000 0000FE00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE000000007E00 0000007E000001807F000001803F000001803F000003801F800003000F8000030007C000060003 F0000C0001F800380000FF00F000001FFFC0000003FE000021227DA128>I69 DI<0003FE0040001FFFC0C0007F00F1C001F8003FC003F0000FC007C00007C00FC000 03C01F800003C03F000001C03F000001C07F000000C07E000000C07E000000C0FE00000000FE00 000000FE00000000FE00000000FE00000000FE00000000FE00000000FE000FFFFC7E000FFFFC7F 00001FC07F00001FC03F00001FC03F00001FC01F80001FC00FC0001FC007E0001FC003F0001FC0 01FC003FC0007F80E7C0001FFFC3C00003FF00C026227DA12C>I73 D76 DII<0007FC0000003FFF800000FC07E00003F001F80007E000FC000FC0007E001F8000 3F001F80003F003F00001F803F00001F807F00001FC07E00000FC07E00000FC0FE00000FE0FE00 000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE07E 00000FC07F00001FC07F00001FC03F00001F803F80003F801F80003F000FC0007E0007E000FC00 03F001F80000FC07E000003FFF80000007FC000023227DA12A>I<01FC0407FF8C1F03FC3C007C 7C003C78001C78001CF8000CF8000CFC000CFC0000FF0000FFE0007FFF007FFFC03FFFF01FFFF8 0FFFFC03FFFE003FFE0003FF00007F00003F00003FC0001FC0001FC0001FE0001EE0001EF0003C FC003CFF00F8C7FFE080FF8018227DA11F>83 D<7FFFFFFF807FFFFFFF807E03F80F807803F807 807003F803806003F80180E003F801C0E003F801C0C003F800C0C003F800C0C003F800C0C003F8 00C00003F800000003F800000003F800000003F800000003F800000003F800000003F800000003 F800000003F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F800000003F800000003F800000003F800000003F8000003FFFFF80003FFFFF80022227EA127 >I<07FC001FFF803F07C03F03E03F01E03F01F01E01F00001F00001F0003FF003FDF01FC1F03F 01F07E01F0FC01F0FC01F0FC01F0FC01F07E02F07E0CF81FF87F07E03F18167E951B>97 DI<00FF8007FFE00F83 F01F03F03E03F07E03F07C01E07C0000FC0000FC0000FC0000FC0000FC0000FC00007C00007E00 007E00003E00301F00600FC0E007FF8000FE0014167E9519>I<0001FE000001FE0000003E0000 003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E00 01FC3E0007FFBE000F81FE001F007E003E003E007E003E007C003E00FC003E00FC003E00FC003E 00FC003E00FC003E00FC003E00FC003E00FC003E007C003E007C003E003E007E001E00FE000F83 BE0007FF3FC001FC3FC01A237EA21F>I<00FE0007FF800F87C01E01E03E01F07C00F07C00F8FC 00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00007E00003E00181F00300FC07003 FFC000FF0015167E951A>I<003F8000FFC001E3E003C7E007C7E00F87E00F83C00F80000F8000 0F80000F80000F80000F8000FFFC00FFFC000F80000F80000F80000F80000F80000F80000F8000 0F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80007FF8007FF800 13237FA211>I<03FC1E0FFF7F1F0F8F3E07CF3C03C07C03E07C03E07C03E07C03E07C03E03C03 C03E07C01F0F801FFF0013FC003000003000003800003FFF801FFFF00FFFF81FFFFC3800FC7000 3EF0001EF0001EF0001EF0001E78003C7C007C3F01F80FFFE001FF0018217E951C>II<1C003E007F007F007F003E001C 000000000000000000000000000000FF00FF001F001F001F001F001F001F001F001F001F001F00 1F001F001F001F001F001F001F001F00FFE0FFE00B247EA310>I108 DII<00FE0007FFC00F83E01E00 F03E00F87C007C7C007C7C007CFC007EFC007EFC007EFC007EFC007EFC007EFC007E7C007C7C00 7C3E00F81F01F00F83E007FFC000FE0017167E951C>II114 D<0FF3003FFF00781F00600700E00300E00300F00300FC00007FE0007FF8003FFE000FFF0001FF 00000F80C00780C00380E00380E00380F00700FC0E00EFFC00C7F00011167E9516>I<01800001 80000180000180000380000380000780000780000F80003F8000FFFF00FFFF000F80000F80000F 80000F80000F80000F80000F80000F80000F80000F80000F80000F81800F81800F81800F81800F 81800F830007C30003FE0000F80011207F9F16>II120 DI<7FFFF0 7FFFF07C03E07007C0600FC0E01F80C01F00C03E00C07E0000FC0000F80001F00003F03007E030 07C0300F80701F80703F00603E00E07C03E0FFFFE0FFFFE014167E9519>I E /Fi 51 122 df<60F0F07010101020204080040B7D830B>44 DI<60 F0F06004047D830B>I<078018603030303060186018E01CE01CE01CE01CE01CE01CE01CE01CE0 1CE01CE01CE01C6018601870383030186007800E187E9713>48 D<03000700FF00070007000700 07000700070007000700070007000700070007000700070007000700070007000700FFF00C187D 9713>I<0F80106020304038803CC01CE01C401C003C003800380070006000C001800100020004 040804100430083FF87FF8FFF80E187E9713>I<0F8010E0207060787038203800780070007000 6000C00F8000E000700038003C003CE03CE03CC03C4038407030E00F800E187E9713>I<003000 30007000F000F001700370027004700C7008701070307020704070C070FFFF0070007000700070 0070007007FF10187F9713>I<30183FF03FE03FC02000200020002000200027C0386020300038 0018001C001C401CE01CE01C80184038403030E00F800E187E9713>I<01E006100C1818383038 300070006000E000E7C0E860F030F018E018E01CE01CE01C601C601C701830183030186007C00E 187E9713>I<40007FFE7FFC7FFC40088010801080200040004000800180018001000300030003 00030007000700070007000700070002000F197E9813>I<078018603030201860186018601870 103C303E600F8007C019F030F86038401CC00CC00CC00CC00C6008201018600FC00E187E9713> I<07801860303070306018E018E018E01CE01CE01C601C603C303C185C0F9C001C001800180038 70307060604021801F000E187E9713>I<60F0F060000000000000000060F0F070101010202040 8004177D8F0B>59 D<007F00000180C000060030000800080010000400203E020020E1020041C0 810043807100838070808700708087007080870070808700708087007080870070808380708043 80708041C0F10020E13100203E1E0010000000080000000600038001803E00007FE000191A7E99 1E>64 D<000C0000000C0000000C0000001E0000001E0000003F00000027000000270000004380 0000438000004380000081C0000081C0000081C0000100E0000100E00001FFE000020070000200 700006007800040038000400380008001C0008001C001C001E00FF00FFC01A1A7F991D>II<003F0201C0C603002E0E001E1C000E1C0006380006780002700002700002F00000F0 0000F00000F00000F00000F000007000027000027800023800041C00041C00080E000803003001 C0C0003F00171A7E991C>IIII<003F020001C0 C60003002E000E001E001C000E001C00060038000600780002007000020070000200F0000000F0 000000F0000000F0000000F0000000F001FFC070000E0070000E0078000E0038000E001C000E00 1C000E000E000E000300160001C06600003F82001A1A7E991E>I73 D76 D78 D<007F000001C1C000070070000E00 38001C001C003C001E0038000E0078000F0070000700F0000780F0000780F0000780F0000780F0 000780F0000780F0000780F000078078000F0078000F0038000E003C001E001C001C000E003800 0700700001C1C000007F0000191A7E991E>I82 D<0FC21836200E6006C006C002C002C002E00070007E003FE01F F807FC003E000E00070003800380038003C002C006E004D81887E0101A7E9915>I<7FFFFF0070 1C0700401C0100401C0100C01C0180801C0080801C0080801C0080001C0000001C0000001C0000 001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C00 00001C0000001C0000001C0000001C000003FFE000191A7F991C>II<3F8070C0 70E020700070007007F01C7030707070E070E071E071E0F171FB1E3C10107E8F13>97 DI<07F80C1C381C30087000E000E000E000E000E000E0007000300438080C1807 E00E107F8F11>I<007E00000E00000E00000E00000E00000E00000E00000E00000E00000E0003 CE000C3E00380E00300E00700E00E00E00E00E00E00E00E00E00E00E00E00E00600E00700E0038 1E001C2E0007CFC0121A7F9915>I<07C01C3030187018600CE00CFFFCE000E000E000E0006000 300438080C1807E00E107F8F11>I<01F0031807380E100E000E000E000E000E000E00FFC00E00 0E000E000E000E000E000E000E000E000E000E000E000E000E007FE00D1A80990C>I<0FCE1873 30307038703870387038303018602FC02000600070003FF03FFC1FFE600FC003C003C003C00360 06381C07E010187F8F13>II<18003C003C001800000000000000000000000000 FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C00FF80091A80990A>I< FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C 001C001C001C001C001C00FF80091A80990A>108 DII<07E01C38300C700E 6006E007E007E007E007E007E0076006700E381C1C3807E010107F8F13>II114 D<1F2060E04020C020C020F0007F003FC01FE000F080708030C030C020F0408F800C107F8F0F> I<0400040004000C000C001C003C00FFC01C001C001C001C001C001C001C001C001C201C201C20 1C201C200E4003800B177F960F>III I121 D E /Fj 2 51 df<0C003C00CC000C000C000C000C000C000C000C000C000C000C000C000C00FF 8009107E8F0F>49 D<1F00618040C08060C0600060006000C00180030006000C00102020207FC0 FFC00B107F8F0F>I E /Fk 9 62 df<0030000030000030000030000030000030000030000030 00003000003000003000FFFFFCFFFFFC0030000030000030000030000030000030000030000030 0000300000300000300016187E931B>43 D<07C018303018701C600C600CE00EE00EE00EE00EE0 0EE00EE00EE00EE00E600C600C701C30181C7007C00F157F9412>48 D<03000700FF0007000700 0700070007000700070007000700070007000700070007000700070007007FF00C157E9412>I< 0F8030E040708030C038E0384038003800700070006000C00180030006000C08080810183FF07F F0FFF00D157E9412>I<0FE030306018701C701C001C00180038006007E000300018000C000E00 0EE00EE00EC00C401830300FE00F157F9412>I<00300030007000F001F0017002700470087018 70107020704070C070FFFE0070007000700070007003FE0F157F9412>I<20303FE03FC0240020 002000200020002F8030E020700030003800384038E038E0388030406020C01F000D157E9412> I<01F00608080C181C301C70006000E000E3E0EC30F018F00CE00EE00EE00E600E600E300C3018 183007C00F157F9412>I61 D E /Fl 51 123 df<00003FE00000E01000018038000380780003007800 070030000700000007000000070000000E0000000E0000000E000000FFFFE0000E00E0001C01C0 001C01C0001C01C0001C01C0001C03800038038000380380003803800038070000380700007007 000070071000700E2000700E2000700E2000E00E2000E0064000E0038000E0000000C0000001C0 000001C000003180000079800000F3000000620000003C0000001D29829F1A>12 D<1C3C3C3C3C040408081020204080060E7D840E>44 D<7FF0FFE07FE00C037D8A10>I<70F8F8 F0E005057B840E>I<000F800030E000E07001C0700380300380380700380F00780F00780E0078 1E00781E00703C00F03C00F03C00F03C00F07801E07801E07801E07801C07003C0F003C0F00380 F00780F00700700700700E00701C003038001870000FC000151F7C9D17>48 D<000200020006000E003C00DC031C001C0038003800380038007000700070007000E000E000E0 00E001C001C001C001C003800380038003800780FFF80F1E7B9D17>I<070F1F1F0E0000000000 000000000070F8F8F0E008147B930E>58 D<00000200000006000000060000000E0000001E0000 001E0000003F0000002F0000004F0000004F0000008F0000010F0000010F0000020F0000020F00 00040F00000C0F0000080F0000100F0000100F0000200F80003FFF800040078000C00780008007 8001000780010007800200078002000780060007801E000F80FF807FF81D207E9F22>65 D<01FFFFC0001E00F0001E0078001E0038001E003C003C003C003C003C003C003C003C003C0078 007800780078007800F0007801E000F0078000FFFE0000F00F8000F003C001E001C001E001E001 E001E001E001E003C001E003C001E003C001E003C001C0078003C00780078007800F0007801E00 0F007800FFFFE0001E1F7D9E20>I<0000FE0200078186001C004C0038003C0060003C00C0001C 01C0001803800018070000180F0000181E0000101E0000103C0000003C00000078000000780000 007800000078000000F0000000F0000000F0000000F0000000F000008070000080700000807000 01003800010038000200180004000C001800060020000381C00000FE00001F217A9F21>I<01FF FF80001E00E0001E0070001E0038001E001C003C001C003C000E003C000E003C000E0078000E00 78000E0078000E0078000E00F0001E00F0001E00F0001E00F0001E01E0003C01E0003C01E0003C 01E0007803C0007003C0007003C000E003C001C0078001C00780038007800E0007801C000F0070 00FFFFC0001F1F7D9E22>I<01FFFFFE001E001C001E000C001E0004001E0004003C0004003C00 04003C0004003C00040078080800780800007808000078180000F0300000FFF00000F0300000F0 300001E0200001E0200001E0200001E0001003C0002003C0002003C0004003C000400780008007 80018007800100078007000F001F00FFFFFE001F1F7D9E1F>I<01FFF3FFE0001F003E00001E00 3C00001E003C00001E003C00003C007800003C007800003C007800003C007800007800F0000078 00F000007800F000007800F00000F001E00000FFFFE00000F001E00000F001E00001E003C00001 E003C00001E003C00001E003C00003C007800003C007800003C007800003C007800007800F0000 07800F000007800F000007800F00000F801F0000FFF1FFE000231F7D9E22>72 D<01FFF0001F00001E00001E00001E00003C00003C00003C00003C000078000078000078000078 0000F00000F00000F00000F00001E00001E00001E00001E00003C00003C00003C00003C0000780 000780000780000780000F8000FFF800141F7D9E12>I<001FFF0000F80000F00000F00000F000 01E00001E00001E00001E00003C00003C00003C00003C0000780000780000780000780000F0000 0F00000F00000F00001E00001E00301E00781E00F83C00F83C00F0780080700040E00021C0001F 000018207D9E18>I<01FFF03FE0001F000F80001E000E00001E000800001E001000003C002000 003C004000003C010000003C020000007804000000780800000078100000007830000000F0F000 0000F1F8000000F278000000F478000001E83C000001F03C000001E03C000001E01E000003C01E 000003C01E000003C00F000003C00F000007800F00000780078000078007800007800780000F80 07C000FFF03FF800231F7D9E23>I<01FFF800001F0000001E0000001E0000001E0000003C0000 003C0000003C0000003C00000078000000780000007800000078000000F0000000F0000000F000 0000F0000001E0000001E0000001E0000001E0008003C0010003C0010003C0030003C002000780 06000780060007800C0007801C000F007800FFFFF800191F7D9E1D>I<01FE00007FC0001E0000 FC00001E0000F80000170001780000170001780000270002F00000270004F00000270004F00000 270008F00000470009E00000470011E00000470021E00000470021E00000870043C00000838043 C00000838083C00000838083C00001038107800001038207800001038207800001038407800002 03840F00000203880F00000203900F00000203900F00000401E01E00000401E01E00000401C01E 00000C01801E00001C01803E0000FF8103FFC0002A1F7D9E29>I<01FF007FE0001F000F00001F 0004000017800400001780040000278008000023C008000023C008000023C008000041E0100000 41E010000041F010000040F010000080F0200000807820000080782000008078200001003C4000 01003C400001003C400001001E400002001E800002001E800002000F800002000F800004000F00 00040007000004000700000C000700001C00020000FF80020000231F7D9E22>I<0001FC000007 0700001C01C0003000E000E0006001C000700380007007800038070000380E0000381E0000381C 0000383C0000383C00003878000078780000787800007878000078F00000F0F00000F0F00000E0 F00001E0F00001C0F00003C0700003807000070078000F0038001E0038003C001C0070000E00E0 000783800001FC00001D217A9F23>I<01FFFF80001E00E0001E0070001E0038001E003C003C00 3C003C003C003C003C003C003C0078007800780078007800F0007800E000F003C000F00F0000FF FC0000F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C0000007 8000000780000007800000078000000F800000FFF000001E1F7D9E1F>I<01FFFF00001E03C000 1E00E0001E0070001E0078003C0078003C0078003C0078003C0078007800F0007800F0007801E0 007801C000F0070000F01E0000FFF00000F0380001E01C0001E01E0001E00E0001E00F0003C01E 0003C01E0003C01E0003C01E0007803C0007803C0807803C0807803C100F801C10FFF00C200000 07C01D207D9E21>82 D<0007E040001C18C0003005800060038000C0038001C001800180010003 80010003800100038001000380000003C0000003C0000003F8000001FF800001FFE000007FF000 001FF0000001F80000007800000078000000380000003800200038002000380020003000600070 00600060006000E0007000C000E8038000C606000081F800001A217D9F1A>I<0FFFFFF01E0780 E0180780201007802020078020200F0020600F0020400F0020400F0020801E0040001E0000001E 0000001E0000003C0000003C0000003C0000003C00000078000000780000007800000078000000 F0000000F0000000F0000000F0000001E0000001E0000001E0000001E0000003E00000FFFF0000 1C1F789E21>I<7FFC1FF807C003C00780010007800100078001000F0002000F0002000F000200 0F0002001E0004001E0004001E0004001E0004003C0008003C0008003C0008003C000800780010 00780010007800100078001000F0002000F0002000F0002000F0004000F0004000700080007001 000030020000380400000C18000007E000001D20779E22>I<007FFFF800FC00F000E001E000C0 03C0008007800180078001000F0001001E0001003C00020078000000F8000000F0000001E00000 03C00000078000000F0000000F0000001E0000003C00000078010000F0010001F0020001E00200 03C00600078004000F000C001E0008003E0018003C0038007801F000FFFFF0001D1F7D9E1C>90 D<00F1800389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F00E 00F00E20F01C40F01C40703C40705C40308C800F070013147C9317>97 D<07803F800700070007 0007000E000E000E000E001C001C001CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE01E E01EE01CE03CE038607060E031C01F0010207B9F15>I<007E0001C1000300800E07801E07801C 07003C0200780000780000780000F00000F00000F00000F00000F0000070010070020030040018 380007C00011147C9315>I<0000780003F80000700000700000700000700000E00000E00000E0 0000E00001C00001C000F1C00389C00707800E03801C03803C0380380700780700780700780700 F00E00F00E00F00E00F00E20F01C40F01C40703C40705C40308C800F070015207C9F17>I<007C 01C207010E011C013C013802780C7BF07C00F000F000F000F0007000700170023804183807C010 147C9315>I<00007800019C00033C00033C000718000700000700000E00000E00000E00000E00 000E0001FFE0001C00001C00001C00001C00003800003800003800003800003800007000007000 00700000700000700000700000E00000E00000E00000E00000C00001C00001C000018000318000 7B0000F300006600003C00001629829F0E>I<003C6000E27001C1E00380E00700E00F00E00E01 C01E01C01E01C01E01C03C03803C03803C03803C03803C07003C07001C0F001C17000C2E0003CE 00000E00000E00001C00001C00301C00783800F0700060E0003F8000141D7E9315>I<01E0000F E00001C00001C00001C00001C000038000038000038000038000070000070000071E000763000E 81800F01C00E01C00E01C01C03801C03801C03801C0380380700380700380700380E10700E2070 0C20701C20700C40E00CC060070014207D9F17>I<00C001E001E001C000000000000000000000 000000000E003300230043804300470087000E000E000E001C001C001C00384038803080708031 0033001C000B1F7C9E0E>I<0001800003C00003C0000380000000000000000000000000000000 000000000000003C00004600008700008700010700010700020E00000E00000E00000E00001C00 001C00001C00001C0000380000380000380000380000700000700000700000700000E00000E000 30E00079C000F180006300003C00001228829E0E>I<03C01FC003800380038003800700070007 0007000E000E000E000E001C001C001C001C0038003800380038007000700070007100E200E200 E200E200640038000A207C9F0C>108 D<1C0F80F0002630C318004740640C004780680E004700 700E004700700E008E00E01C000E00E01C000E00E01C000E00E01C001C01C038001C01C038001C 01C038001C01C0708038038071003803806100380380E100380380620070070066003003003800 21147C9325>I<1C0F802630C04740604780604700704700708E00E00E00E00E00E00E00E01C01 C01C01C01C01C01C03843803883803083807083803107003303001C016147C931A>I<007C0001 C3000301800E01C01E01C01C01E03C01E07801E07801E07801E0F003C0F003C0F003C0F00780F0 0700700F00700E0030180018700007C00013147C9317>I<01C1E002621804741C04781C04701E 04701E08E01E00E01E00E01E00E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0 072380071E000700000700000E00000E00000E00000E00001C00001C0000FFC000171D809317> I<00F0400388C00705800E03801C03803C0380380700780700780700780700F00E00F00E00F00E 00F00E00F01C00F01C00703C00705C0030B8000F38000038000038000070000070000070000070 0000E00000E0000FFE00121D7C9315>I<1C1E002661004783804787804707804703008E00000E 00000E00000E00001C00001C00001C00001C000038000038000038000038000070000030000011 147C9313>I<00FC030206010C030C070C060C000F800FF007F803FC003E000E700EF00CF00CE0 08401020601F8010147D9313>I<018001C0038003800380038007000700FFF007000E000E000E 000E001C001C001C001C003800380038003820704070407080708031001E000C1C7C9B0F>I<0E 00C03300E02301C04381C04301C04701C08703800E03800E03800E03801C07001C07001C07001C 07101C0E20180E20180E201C1E200C264007C38014147C9318>I<0E03803307802307C04383C0 4301C04700C08700800E00800E00800E00801C01001C01001C01001C02001C02001C04001C0400 1C08000E300003C00012147C9315>I<0E00C1C03300E3C02301C3E04381C1E04301C0E04701C0 60870380400E0380400E0380400E0380401C0700801C0700801C0700801C0701001C0701001C06 02001C0F02000C0F04000E13080003E1F0001B147C931E>I<0383800CC4401068E01071E02071 E02070C040E00000E00000E00000E00001C00001C00001C00001C040638080F38080F38100E581 0084C60078780013147D9315>I<0E00C03300E02301C04381C04301C04701C08703800E03800E 03800E03801C07001C07001C07001C07001C0E00180E00180E001C1E000C3C0007DC00001C0000 1C00003800F03800F07000E06000C0C0004380003E0000131D7C9316>I<01C04003E08007F180 0C1F00080200000400000800001000002000004000008000010000020000040100080200100200 3E0C0063FC0041F80080E00012147D9313>I E /Fm 86 124 df<00008000000001C000000001 C000000003E000000003E000000005F000000004F000000008F80000000878000000107C000000 103C000000203E000000201E000000401F000000400F000000800F80000080078000010007C000 010003C000020003E000020001E000040001F000040000F000080000F80008000078001000007C 001000003C002000003E002000001E007FFFFFFF007FFFFFFF00FFFFFFFF8021207E9F26>1 D<001F83E000F06E3001C078780380F8780300F030070070000700700007007000070070000700 70000700700007007000FFFFFF8007007000070070000700700007007000070070000700700007 007000070070000700700007007000070070000700700007007000070070000700700007007000 07007000070070007FE3FF001D20809F1B>11 D<003F0000E0C001C0C00381E00701E00701E007 0000070000070000070000070000070000FFFFE00700E00700E00700E00700E00700E00700E007 00E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E07FC3FE17 20809F19>I<001F81F80000F04F040001C07C06000380F80F000300F00F000700F00F00070070 000007007000000700700000070070000007007000000700700000FFFFFFFF0007007007000700 700700070070070007007007000700700700070070070007007007000700700700070070070007 007007000700700700070070070007007007000700700700070070070007007007000700700700 07007007007FE3FE3FF02420809F26>14 D<07070F1C383060C00808779F17>19 D22 D<7038F87CFC7EFC7E743A040204020402080408041008100820104020 0F0E7E9F17>34 D<70F8FCFC74040404080810102040060E7C9F0D>39 D<002000400080010002 0006000C000C00180018003000300030007000600060006000E000E000E000E000E000E000E000 E000E000E000E000E0006000600060007000300030003000180018000C000C0006000200010000 80004000200B2E7DA112>I<800040002000100008000C00060006000300030001800180018001 C000C000C000C000E000E000E000E000E000E000E000E000E000E000E000E000C000C000C001C0 01800180018003000300060006000C00080010002000400080000B2E7DA112>I<000600000006 000000060000000600000006000000060000000600000006000000060000000600000006000000 060000000600000006000000060000FFFFFFF0FFFFFFF000060000000600000006000000060000 000600000006000000060000000600000006000000060000000600000006000000060000000600 00000600001C207D9A23>43 D<70F8FCFC74040404080810102040060E7C840D>II<70F8F8F87005057C840D>I<000100030003000600060006000C000C000C00180018 001800300030003000600060006000C000C000C00180018001800300030003000600060006000C 000C000C00180018001800300030003000600060006000C000C000C000102D7DA117>I<03F000 0E1C001C0E00180600380700700380700380700380700380F003C0F003C0F003C0F003C0F003C0 F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0700380700380700380780780380700 1806001C0E000E1C0003F000121F7E9D17>I<018003800F80F380038003800380038003800380 03800380038003800380038003800380038003800380038003800380038003800380038007C0FF FE0F1E7C9D17>I<03F0000C1C00100E00200700400780800780F007C0F803C0F803C0F803C020 07C00007C0000780000780000F00000E00001C0000380000700000600000C00001800003000006 00400C00401800401000803FFF807FFF80FFFF80121E7E9D17>I<03F0000C1C00100E00200F00 780F80780780780780380F80000F80000F00000F00000E00001C0000380003F000003C00000E00 000F000007800007800007C02007C0F807C0F807C0F807C0F00780400780400F00200E001C3C00 03F000121F7E9D17>I<000600000600000E00000E00001E00002E00002E00004E00008E00008E 00010E00020E00020E00040E00080E00080E00100E00200E00200E00400E00C00E00FFFFF0000E 00000E00000E00000E00000E00000E00000E0000FFE0141E7F9D17>I<1803001FFE001FFC001F F8001FE00010000010000010000010000010000010000011F000161C00180E0010070010078000 03800003800003C00003C00003C07003C0F003C0F003C0E00380400380400700200600100E000C 380003E000121F7E9D17>I<007C000182000701000E03800C07801C0780380300380000780000 700000700000F1F000F21C00F40600F80700F80380F80380F003C0F003C0F003C0F003C0F003C0 7003C07003C07003803803803807001807000C0E00061C0001F000121F7E9D17>I<4000007FFF C07FFF807FFF804001008002008002008004000008000008000010000020000020000040000040 0000C00000C00001C0000180000380000380000380000380000780000780000780000780000780 00078000078000030000121F7D9D17>I<03F0000C0C0010060030030020018060018060018060 01807001807803003E03003F06001FC8000FF00003F80007FC000C7E00103F00300F8060038040 01C0C001C0C000C0C000C0C000C0C000806001802001001002000C0C0003F000121F7E9D17>I< 03F0000E18001C0C00380600380700700700700380F00380F00380F003C0F003C0F003C0F003C0 F003C07007C07007C03807C0180BC00E13C003E3C0000380000380000380000700300700780600 780E00700C002018001070000FC000121F7E9D17>I<70F8F8F8700000000000000000000070F8 F8F87005147C930D>I<70F8F8F8700000000000000000000070F0F8F878080808101010202040 051D7C930D>I<7FFFFFE0FFFFFFF0000000000000000000000000000000000000000000000000 0000000000000000FFFFFFF07FFFFFE01C0C7D9023>61 D<001F800000E0700001000800060006 000800010008000100100F00802030C0402060404040C0202041C01C2041C01C2081801C108380 1C1083801C1083801C1083801C1083801C1083801C1081801C1041C01C1041C01C1040C03C2020 605C202030CC40100F0780080000000800000006000070010001C000E01F00001FF0001C207D9F 23>64 D<000100000003800000038000000380000007C0000007C0000007C0000009E0000009E0 000009E0000010F0000010F0000010F00000207800002078000020780000403C0000403C000040 3C0000801E0000801E0000FFFE0001000F0001000F0001000F0002000780020007800200078004 0003C00E0003C01F0007E0FFC03FFE1F207F9F22>II<000FC0 40007030C001C009C0038005C0070003C00E0001C01E0000C01C0000C03C0000C07C0000407C00 004078000040F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8 000000780000007C0000407C0000403C0000401C0000401E0000800E0000800700010003800200 01C0040000703800000FC0001A217D9F21>IIII<000FE0200078186000E004E0038002E007 0001E00F0000E01E0000601E0000603C0000603C0000207C00002078000020F8000000F8000000 F8000000F8000000F8000000F8000000F8000000F8007FFCF80003E0780001E07C0001E03C0001 E03C0001E01E0001E01E0001E00F0001E0070001E0038002E000E0046000781820000FE0001E21 7D9F24>III<0FFFC0007C00003C00003C00003C00003C00003C00003C00003C00003C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C 00203C00F83C00F83C00F83C00F0380040780040700030E0000F800012207E9E17>IIIII<001F800000F0F00001C0380007801E000F000F000E0007001E00 07803C0003C03C0003C07C0003E0780001E0780001E0F80001F0F80001F0F80001F0F80001F0F8 0001F0F80001F0F80001F0F80001F0F80001F0780001E07C0003E07C0003E03C0003C03C0003C0 1E0007800E0007000F000F0007801E0001C0380000F0F000001F80001C217D9F23>II<001F800000F0F00001C0380007801E000F000F000E0007001E0007803C 0003C03C0003C07C0003E07C0003E0780001E0F80001F0F80001F0F80001F0F80001F0F80001F0 F80001F0F80001F0F80001F0F80001F0780001E0780001E07C0003E03C0003C03C0F03C01E1087 800E2047000F204F0007A03E0001E0380000F0F010001FB0100000301000003830000038700000 3FF000001FE000001FE000000FC0000007801C297D9F23>II<07E0800C1980100780300380600180600180E00180E00080E00080E00080F00000F000 007800007F00003FF0001FFC000FFE0003FF00001F800007800003C00003C00001C08001C08001 C08001C08001C0C00180C00380E00300F00600CE0C0081F80012217D9F19>I<7FFFFFE0780F01 E0600F0060400F0020400F0020C00F0030800F0010800F0010800F0010800F0010000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000001F800007FFFE00 1C1F7E9E21>IIII<7FF83FF80FE00FC007C0070003C0020001E0040001F00C0000F00800007810 00007C1000003C2000003E4000001E4000000F8000000F8000000780000003C0000007E0000005 E0000009F0000018F8000010780000207C0000603C0000401E0000801F0001800F000100078002 0007C0070003C01F8007E0FFE01FFE1F1F7F9E22>II<7FFFF8 7C00F87000F06001E04001E0C003C0C003C0800780800F80800F00001E00001E00003C00003C00 00780000F80000F00001E00001E00003C00403C0040780040F80040F000C1E000C1E00083C0018 3C0018780038F801F8FFFFF8161F7D9E1C>II<08041008201020 1040204020804080408040B85CFC7EFC7E7C3E381C0F0E7B9F17>II<0C001E0033006180C0C080400A067A9E17>I<1FE000303000781800781C00300E00000E0000 0E00000E0000FE00078E001E0E00380E00780E00F00E10F00E10F00E10F01E10781E103867200F 83C014147E9317>97 D<0E0000FE00000E00000E00000E00000E00000E00000E00000E00000E00 000E00000E00000E3E000EC3800F01C00F00E00E00E00E00700E00700E00780E00780E00780E00 780E00780E00780E00700E00700E00E00F00E00D01C00CC300083E0015207F9F19>I<03F80E0C 1C1E381E380C70007000F000F000F000F000F000F00070007000380138011C020E0C03F010147E 9314>I<000380003F800003800003800003800003800003800003800003800003800003800003 8003E380061B801C0780380380380380700380700380F00380F00380F00380F00380F00380F003 807003807003803803803807801C07800E1B8003E3F815207E9F19>I<03F0000E1C001C0E0038 0700380700700700700380F00380F00380FFFF80F00000F00000F0000070000070000038008018 00800C010007060001F80011147F9314>I<007C00C6018F038F07060700070007000700070007 000700FFF007000700070007000700070007000700070007000700070007000700070007000700 07007FF01020809F0E>I<0000E003E3300E3C301C1C30380E00780F00780F00780F00780F0078 0F00380E001C1C001E380033E0002000002000003000003000003FFE001FFF800FFFC03001E060 0070C00030C00030C00030C000306000603000C01C038003FC00141F7F9417>I<0E0000FE0000 0E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E3E000E43000E8180 0F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C0FFE7FC16207F9F19>I<1C001E003E001E001C0000000000000000000000 00000E007E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 00FFC00A1F809E0C>I<00E001F001F001F000E0000000000000000000000000007007F000F000 700070007000700070007000700070007000700070007000700070007000700070007000700070 00706070F060F0C061803F000C28829E0E>I<0E0000FE00000E00000E00000E00000E00000E00 000E00000E00000E00000E00000E00000E0FF00E03C00E03000E02000E04000E08000E10000E30 000E70000EF8000F38000E1C000E1E000E0E000E07000E07800E03800E03C00E03E0FFCFF81520 7F9F18>I<0E00FE000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE00B20809F0C>I<0E1F 01F000FE618618000E81C81C000F00F00E000F00F00E000E00E00E000E00E00E000E00E00E000E 00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E00 0E00E00E000E00E00E000E00E00E00FFE7FE7FE023147F9326>I<0E3E00FE43000E81800F01C0 0F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C0FFE7FC16147F9319>I<01F800070E001C03803801C03801C07000E07000E0F000 F0F000F0F000F0F000F0F000F0F000F07000E07000E03801C03801C01C0380070E0001F8001414 7F9317>I<0E3E00FEC3800F01C00F00E00E00E00E00F00E00700E00780E00780E00780E00780E 00780E00780E00700E00F00E00E00F01E00F01C00EC3000E3E000E00000E00000E00000E00000E 00000E00000E00000E0000FFE000151D7F9319>I<03E0800619801C05803C0780380380780380 700380F00380F00380F00380F00380F00380F003807003807803803803803807801C0B800E1380 03E380000380000380000380000380000380000380000380000380003FF8151D7E9318>I<0E78 FE8C0F1E0F1E0F0C0E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE00F 147F9312>I<1F9030704030C010C010C010E00078007F803FE00FF00070803880188018C018C0 18E030D0608F800D147E9312>I<020002000200060006000E000E003E00FFF80E000E000E000E 000E000E000E000E000E000E000E000E080E080E080E080E080610031001E00D1C7F9B12>I<0E 01C0FE1FC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E03C00603C0030DC001F1FC16147F9319>III<7FC3FC0F01E00701C00701800381 0001C20000E40000EC00007800003800003C00007C00004E000087000107000303800201C00601 E01E01E0FF07FE1714809318>II<3FFF380E200E201C40 384078407000E001E001C00380078007010E011E011C0338027006700EFFFE10147F9314>II E /Fn 50 124 df45 D<387CFEFEFE7C3807077C860F>I<00E00001E0000FE000FFE000F3E00003E00003E00003E000 03E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E000 03E00003E00003E00003E00003E00003E000FFFF80FFFF80111D7C9C1A>49 D<07F0001FFE00383F007C1F80FE0FC0FE0FC0FE0FE0FE07E07C07E03807E0000FE0000FC0000F C0001F80001F00003E0000780000F00000E00001C0000380600700600E00601C00E01FFFC03FFF C07FFFC0FFFFC0FFFFC0131D7D9C1A>I<01FC0007FF000E0F801E0FC03F07E03F07E03F07E03F 07E01E0FC0000FC0000F80001F0001FC0001FC00000F800007C00003E00003F00003F83803F87C 03F8FE03F8FE03F8FE03F0FC03F07807E03C0FC01FFF8003FC00151D7E9C1A>I<3803803FFF80 3FFF003FFE003FFC003FF0003F800030000030000030000030000033F80037FE003C1F00380F80 1007C00007C00007E00007E07807E0FC07E0FC07E0FC07E0FC07C0780FC0600F80381F001FFC00 07F000131D7D9C1A>53 D<387CFEFEFE7C38000000000000387CFEFEFE7C3807147C930F>58 D<0000E000000000E000000001F000000001F000000001F000000003F800000003F800000006FC 00000006FC0000000EFE0000000C7E0000000C7E000000183F000000183F000000303F80000030 1F800000701FC00000600FC00000600FC00000C007E00000FFFFE00001FFFFF000018003F00001 8003F000030001F800030001F800060001FC00060000FC000E0000FE00FFE00FFFE0FFE00FFFE0 231F7E9E28>65 DI<0007FC02003FFF0E00FE03DE03F000FE07 E0003E0FC0001E1F80001E3F00000E3F00000E7F0000067E0000067E000006FE000000FE000000 FE000000FE000000FE000000FE000000FE0000007E0000007E0000067F0000063F0000063F0000 0C1F80000C0FC0001807E0003803F0007000FE01C0003FFF800007FC001F1F7D9E26>IIII<0007FC0200003FFF 0E0000FE03DE0003F000FE0007E0003E000FC0001E001F80001E003F00000E003F00000E007F00 0006007E000006007E00000600FE00000000FE00000000FE00000000FE00000000FE00000000FE 003FFFE0FE003FFFE07E00007E007E00007E007F00007E003F00007E003F00007E001F80007E00 0FC0007E0007E0007E0003F000FE0000FE01FE00003FFF8E000007FC0600231F7D9E29>III76 DII<001FF80000FFFF0001F81F8007E007E00FC003F01F8001F81F 0000F83F0000FC7F0000FE7E00007E7E00007EFE00007FFE00007FFE00007FFE00007FFE00007F FE00007FFE00007FFE00007FFE00007F7E00007E7F0000FE7F0000FE3F0000FC3F8001FC1F8001 F80FC003F007E007E001F81F8000FFFF00001FF800201F7D9E27>II82 D<03FC080FFF381E03F83800F8700078700038F00038F00018F00018F800 00FC00007FC0007FFE003FFF801FFFE00FFFF007FFF000FFF80007F80000FC00007C00003CC000 3CC0003CC0003CE00038E00078F80070FE01E0E7FFC081FF00161F7D9E1D>I<7FFFFFFC7FFFFF FC7C07E07C7007E01C6007E00C6007E00CE007E00EC007E006C007E006C007E006C007E0060007 E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E00000 07E0000007E0000007E0000007E0000007E0000007E0000007E00003FFFFC003FFFFC01F1E7E9D 24>II89 D<3FFFFF803FFFFF803F803F003E007F0038007E003800FC 007001FC007001F8006003F0006007F0006007E000000FC000001FC000001F8000003F0000007F 0000007E000000FC000001FC018001F8018003F0018007F0018007E003800FC003801FC003001F 8007003F000F007F001F007E007F00FFFFFF00FFFFFF00191F7D9E20>I<07FC001FFF003F0F80 3F07C03F03E03F03E00C03E00003E0007FE007FBE01F03E03C03E07C03E0F803E0F803E0F803E0 FC05E07E0DE03FF8FE0FE07E17147F9319>97 DI<01FE0007FF801F0FC03E0FC03E0FC07C0FC07C0300FC0000FC0000FC0000FC0000 FC0000FC00007C00007E00003E00603F00C01F81C007FF0001FC0013147E9317>I<0007F80007 F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F801F8F80FFEF81F83 F83E01F87E00F87C00F87C00F8FC00F8FC00F8FC00F8FC00F8FC00F8FC00F87C00F87C00F87E00 F83E01F81F07F80FFEFF03F8FF18207E9F1D>I<01FE0007FF800F83C01E01E03E00F07C00F07C 00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00003E00181E00180F807007FFE000 FF8015147F9318>I<001F8000FFC001F3E003E7E003C7E007C7E007C3C007C00007C00007C000 07C00007C000FFFC00FFFC0007C00007C00007C00007C00007C00007C00007C00007C00007C000 07C00007C00007C00007C00007C00007C00007C0003FFC003FFC0013207F9F10>I<01FC3C07FF FE0F079E1E03DE3E03E03E03E03E03E03E03E03E03E01E03C00F07800FFF0009FC001800001800 001C00001FFF800FFFF007FFF81FFFFC3C007C70003EF0001EF0001EF0001E78003C78003C3F01 F80FFFE001FF00171E7F931A>II< 1C003E007F007F007F003E001C00000000000000000000000000FF00FF001F001F001F001F001F 001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B217EA00E>I<0038007C00 FE00FE00FE007C003800000000000000000000000001FE01FE003E003E003E003E003E003E003E 003E003E003E003E003E003E003E003E003E003E003E003E003E303E783EFC3CFC7C78783FF01F C00F2A83A010>IIIII<01FF0007FFC01F83F03E00F83E00F87C007C7C007CFC007EFC007EFC007EFC007EFC 007EFC007E7C007C7C007C3E00F83E00F81F83F007FFC001FF0017147F931A>II114 D<0FE63FFE701E600EE006E006F800FFC07FF83FFC1FFE03FE001FC007C007E007F006F81EFFFC C7F010147E9315>I<01800180018003800380038007800F803F80FFFCFFFC0F800F800F800F80 0F800F800F800F800F800F800F860F860F860F860F8607CC03F801F00F1D7F9C14>II121 D<3FFFE03FFFE03C07C0380F80701F80603F00603E00607C0000F80001F80003F00003E06007C0 600F80601F80E03F00C03E01C07C03C0FFFFC0FFFFC013147F9317>II E /Fo 46 123 df<003F07E00001C09C18000380F018000701F03C000E01E03C000E 00E018000E00E000000E00E000000E00E000000E00E000000E00E00000FFFFFFFC000E00E01C00 0E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C 000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C007FC7FC FF80211D809C23>14 D45 D<60F0F06004047C830C>I<000600000006 000000060000000F0000000F0000000F00000017800000178000001780000023C0000023C00000 23C0000041E0000041E0000041E0000080F0000080F0000180F8000100780001FFF80003007C00 02003C0002003C0006003E0004001E0004001E000C001F001E001F00FF80FFF01C1D7F9C1F>65 DI<001F808000E0618001801980070007800E0003801C0003801C 00018038000180780000807800008070000080F0000000F0000000F0000000F0000000F0000000 F0000000F0000000F0000000700000807800008078000080380000801C0001001C0001000E0002 00070004000180080000E03000001FC000191E7E9C1E>III< FFFFF80F00780F00180F00080F00080F000C0F00040F00040F02040F02000F02000F02000F0600 0FFE000F06000F02000F02000F02000F02000F00000F00000F00000F00000F00000F00000F0000 0F8000FFF800161C7E9B1B>I<001F808000E0618001801980070007800E0003801C0003801C00 018038000180780000807800008070000080F0000000F0000000F0000000F0000000F0000000F0 000000F000FFF0F0000F80700007807800078078000780380007801C0007801C0007800E000780 07000B800180118000E06080001F80001C1E7E9C21>III78 D<003F800000E0E0000380380007001C000E000E001C0007003C00 078038000380780003C0780003C0700001C0F00001E0F00001E0F00001E0F00001E0F00001E0F0 0001E0F00001E0F00001E0700001C0780003C0780003C0380003803C0007801C0007000E000E00 07001C000380380000E0E000003F80001B1E7E9C20>I82 D<07E0801C1980300580 700380600180E00180E00080E00080E00080F00000F800007C00007FC0003FF8001FFE0007FF00 00FF80000F800007C00003C00001C08001C08001C08001C0C00180C00180E00300D00200CC0C00 83F800121E7E9C17>I<7FFFFFC0700F01C0600F00C0400F0040400F0040C00F0020800F002080 0F0020800F0020000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000 000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000001F80 0003FFFC001B1C7F9B1E>IIII89 D<1FC000307000783800781C00301C0000 1C00001C0001FC000F1C00381C00701C00601C00E01C40E01C40E01C40603C40304E801F870012 127E9115>97 DI<07E00C301878307870306000E000E000 E000E000E000E00060007004300418080C3007C00E127E9112>I<003F00000700000700000700 00070000070000070000070000070000070000070003E7000C1700180F00300700700700600700 E00700E00700E00700E00700E00700E00700600700700700300700180F000C370007C7E0131D7E 9C17>I<03E00C301818300C700E6006E006FFFEE000E000E000E00060007002300218040C1803 E00F127F9112>I<00F8018C071E061E0E0C0E000E000E000E000E000E00FFE00E000E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E007FE00F1D809C0D>I<00038003C4 C00C38C01C3880181800381C00381C00381C00381C001818001C38000C300013C0001000003000 001800001FF8001FFF001FFF803003806001C0C000C0C000C0C000C06001803003001C0E0007F8 00121C7F9215>II<18003C003C00180000000000000000 00000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00 1C00FF80091D7F9C0C>I<00C001E001E000C000000000000000000000000000000FE000E000E0 00E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E060E0F0 C0F1C061803E000B25839C0D>IIIII<03F0000E1C00180600300300700380600180E001 C0E001C0E001C0E001C0E001C0E001C06001807003803003001806000E1C0003F00012127F9115 >II114 D<1F9030704030C010C010E010F8007F803FE00FF000F88038 8018C018C018E010D0608FC00D127F9110>I<04000400040004000C000C001C003C00FFE01C00 1C001C001C001C001C001C001C001C001C101C101C101C101C100C100E2003C00C1A7F9910>I< FC1F801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C0380 1C03801C07800C07800E1B8003E3F014127F9117>III<7F8FF00F03800F030007020003840001C80001D80000F00000700000780000F800 009C00010E00020E000607000403801E07C0FF0FF81512809116>II<7FFC7038 6038407040F040E041C003C0038007000F040E041C043C0C380870087038FFF80E127F9112>I E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300 TeXDict begin %%EndSetup %%Page: 1 1 bop 634 120 a Fo(NOR)m(THWESTERN)13 b(UNIVERSITY)617 170 y(Departmen)o(t)h (of)f(Electrical)h(Engineering)753 220 y(and)f(Computer)g(Science)332 789 y Fn(A)k(LIMITED)g(MEMOR)l(Y)g(ALGORITHM)h(F)o(OR)f(BOUND)547 846 y(CONSTRAINED)h(OPTIMIZA)l(TION)933 1058 y Fm(b)o(y)289 1162 y Fl(R)o(ichar)n(d)e(H.)g(Byr)n(d)621 1145 y Fk(1)641 1162 y Fl(,)g(Peihuang)g(Lu)926 1145 y Fk(2)946 1162 y Fl(,)33 b(Jor)n(ge)16 b(No)n(c)n(e)n(dal)1271 1145 y Fk(2)1305 1162 y Fl(and)h(Ciyou)f(Zhu)1604 1145 y Fk(2)694 1573 y Fm(T)l(ec)o(hnical)h(Rep)q (ort)e(NAM-08)767 1724 y(Revised:)21 b(Ma)o(y)15 b(1994)p 0 2253 766 2 v 52 2280 a Fj(1)81 2296 y Fi(Computer)e(Science)h(Departmen)o(t,) f(Univ)o(ersit)o(y)h(of)e(Colorado)h(at)g(Boulder,)g(Boulder)h(Colorado)g (80309.)j(This)c(author)g(w)o(as)0 2342 y(supp)q(orted)i(b)o(y)e(NSF)g(gran)o (t)g(CCR-9101795,)h(AR)o(O)e(gran)o(t)i(D)o(AAL)e(03-91-G-0151,)i(and)g(AF)o (OSR)f(gran)o(t)g(AF)o(OSR-90-0109.)52 2371 y Fj(2)86 2387 y Fi(Departmen)o(t)k(of)g(Electrical)i(Engineering)g(and)f(Computer)f (Science,)i(North)o(w)o(estern)e(Univ)o(ersit)o(y)m(,)i(Ev)n(anston)f(Il)f (60208;)0 2433 y(no)q(cedal@eecs.n)o(wu.edu.)22 b(These)14 b(authors)h(w)o(ere)f(supp)q(orted)h(b)o(y)f(National)i(Science)f(F)m (oundation)h(Gran)o(ts)f(CCR-9101359)g(and)0 2479 y(ASC-9213149,)f(and)f(b)o (y)h(Departmen)o(t)f(of)g(Energy)h(Gran)o(t)f(DE-F)o(G02-87ER25047-A004.)945 2603 y Fm(1)p eop %%Page: 1 2 bop 332 120 a Fn(A)17 b(LIMITED)g(MEMOR)l(Y)g(ALGORITHM)h(F)o(OR)f(BOUND)547 177 y(CONSTRAINED)h(OPTIMIZA)l(TION)933 389 y Fm(b)o(y)344 493 y Fl(R)o(ichar)n(d)f(H.)f(Byr)n(d,)g(Peihuang)h(Lu,)f(Jor)n(ge)g(No)n(c)n (e)n(dal)f(and)h(Ciyou)h(Zhu)829 963 y Fm(ABSTRA)o(CT)114 1098 y Fo(An)h(algorithm)e(for)i(solving)g(large)g(nonlinear)g(optimization)e (problems)i(with)g(simple)f(b)q(ounds)i(is)f(de-)114 1148 y(scrib)q(ed.)32 b(It)18 b(is)h(based)f(on)g(the)h(gradien)o(t)f(pro)r(jection)h(metho)q(d)e (and)i(uses)g(a)f(limited)e(memory)g(BF)o(GS)114 1197 y(matrix)c(to)i(appro)o (ximate)e(the)i(Hessian)h(of)f(the)g(ob)r(jectiv)o(e)h(function.)j(It)c(is)g (sho)o(wn)g(ho)o(w)g(to)g(tak)o(e)g(adv)n(an-)114 1247 y(tage)f(of)f(the)h (form)e(of)h(the)i(limited)c(memory)h(appro)o(ximation)e(to)k(implemen)o(t)d (the)k(algorithm)c(e\016cien)o(tly)m(.)114 1297 y(The)k(results)h(of)e(n)o (umerical)g(tests)i(on)f(a)f(set)i(of)e(large)h(problems)f(are)h(rep)q (orted.)0 1442 y Fl(Key)20 b(wor)n(ds:)28 b Fm(b)q(ound)20 b(constrained)g(optimization,)h(limited)g(memory)e(metho)q(d,)h(nonlinear)h (optimization,)0 1499 y(quasi-Newton)16 b(metho)q(d,)f(large-scale)h (optimization.)0 1575 y Fl(A)o(bbr)n(eviate)n(d)f(title:)20 b Fm(A)c(Limited)g(Memory)f(Metho)q(d)0 1751 y Fh(1.)j(In)n(tro)r(duction.)0 1832 y Fm(In)f(this)g(pap)q(er)g(w)o(e)g(describ)q(e)h(a)e(limited)j(memory)d (quasi-Newton)h(algorithm)g(for)f(solving)h(large)g(nonlinear)0 1888 y(optimization)f(problems)g(with)g(simple)g(b)q(ounds)g(on)f(the)h(v)m (ariables.)21 b(W)l(e)15 b(write)g(this)h(problem)g(as)875 1990 y(min)8 b Fg(f)d Fm(\()p Fg(x)p Fm(\))773 b(\(1)p Fg(:)p Fm(1\))731 2093 y(sub)s(ject)20 b(to)40 b Fg(l)13 b Ff(\024)g Fg(x)f Ff(\024)h Fg(u;)645 b Fm(\(1)p Fg(:)p Fm(2\))0 2176 y(where)20 b Fg(f)26 b Fm(:)21 b Ff(<)251 2160 y Fe(n)295 2176 y Ff(!)g(<)f Fm(is)h(a)f(nonlinear)h(function)g(whose)f(gradien)o(t)g Fg(g)i Fm(is)e(a)o(v)m(ailable,)j(the)d(v)o(ectors)g Fg(l)g Fm(and)g Fg(u)0 2232 y Fm(represen)o(t)f(lo)o(w)o(er)f(and)h(upp)q(er)g(b)q (ounds)h(on)e(the)h(v)m(ariables,)h(and)f(the)f(n)o(um)o(b)q(er)h(of)f(v)m (ariables)i Fg(n)f Fm(is)g(assumed)0 2289 y(to)d(b)q(e)h(large.)23 b(The)17 b(algorithm)f(do)q(es)h(not)f(require)h(second)g(deriv)m(ativ)o(es)h (or)d(kno)o(wledge)i(of)f(the)h(structure)f(of)0 2345 y(the)f(ob)s(jectiv)o (e)h(function,)g(and)f(can)h(therefore)f(b)q(e)h(applied)h(when)f(the)g (Hessian)g(matrix)f(is)h(not)f(practical)h(to)0 2402 y(compute.)k(A)15 b(limited)i(memory)d(quasi-Newton)h(up)q(date)h(is)f(used)h(to)e(appro)o (ximate)g(the)h(Hessian)h(matrix)f(in)0 2458 y(suc)o(h)h(a)e(w)o(a)o(y)h (that)f(the)h(storage)f(required)j(is)e(linear)i(in)f Fg(n)p Fm(.)945 2603 y(1)p eop %%Page: 2 3 bop 71 120 a Fm(The)15 b(algorithm)h(describ)q(ed)i(in)e(this)g(pap)q(er)g (is)g(similar)h(to)e(the)h(algorithms)f(prop)q(osed)h(b)o(y)g(Conn,)f(Gould)0 177 y(and)f(T)l(oin)o(t)f([9)o(])g(and)h(Mor)o(\023)-21 b(e)11 b(and)j(T)l(oraldo)f([20)o(],)g(in)h(that)f(the)g(gradien)o(t)h(pro)s (jection)f(metho)q(d)h(is)f(used)h(to)f(deter-)0 233 y(mine)k(a)e(set)h(of)f (activ)o(e)h(constrain)o(ts)f(at)g(eac)o(h)h(iteration.)22 b(Our)16 b(algorithm)g(is)g(distinguished)i(from)d(the)h(these)0 289 y(metho)q(ds)d(b)o(y)g(our)f(use)i(of)e(line)j(searc)o(hes)e(\(as)f(opp)q (osed)h(to)f(trust)h(regions\))f(but)h(mainly)h(b)o(y)f(our)g(use)g(of)f (limited)0 346 y(memory)18 b(BF)o(GS)g(matrices)g(to)g(appro)o(ximate)g(the)g (Hessian)i(of)e(the)g(ob)s(jectiv)o(e)h(function.)30 b(The)19 b(prop)q(erties)0 402 y(of)e(these)h(limited)i(memory)d(matrices)h(ha)o(v)o (e)f(far)g(reac)o(hing)h(consequences)h(in)g(the)f(implemen)o(tation)h(of)e (the)0 459 y(metho)q(d,)c(as)g(will)h(b)q(e)g(discussed)g(later)f(on.)19 b(W)l(e)13 b(\014nd)h(that)e(b)o(y)h(making)g(use)g(of)g(the)g(compact)f (represen)o(tations)0 515 y(of)g(limited)j(memory)d(matrices)h(describ)q(ed)i (b)o(y)e(Byrd,)g(No)q(cedal)h(and)f(Sc)o(hnab)q(el)i([6)o(],)e(the)g (computational)g(cost)0 572 y(of)i(one)g(iteration)h(of)e(the)i(algorithm)f (can)g(b)q(e)h(k)o(ept)f(to)g(b)q(e)g(of)g(order)g Fg(n)p Fm(.)71 628 y(W)l(e)h(used)h(the)g(gradien)o(t)f(pro)s(jection)g(approac)o(h)g([16)o (],)g([17],)f([3])h(to)g(determine)h(the)g(activ)o(e)f(set,)g(b)q(ecause)0 685 y(recen)o(t)k(studies)i([7)o(],)f([5)o(])f(indicate)i(that)e(it)g(p)q (ossess)h(go)q(o)q(d)f(theoretical)h(prop)q(erties,)h(and)e(b)q(ecause)i(it)e (also)0 741 y(app)q(ears)c(to)f(b)q(e)i(e\016cien)o(t)f(on)g(man)o(y)g(large) f(problems)i([8)o(],)f([20)o(].)21 b(Ho)o(w)o(ev)o(er)15 b(some)h(of)f(the)h (main)g(comp)q(onen)o(ts)0 798 y(of)i(our)g(algorithm)h(could)h(b)q(e)f (useful)g(in)h(other)e(framew)o(orks,)g(as)g(long)h(as)f(limited)i(memory)e (matrices)h(are)0 854 y(used)d(to)e(appro)o(ximate)h(the)g(Hessian)h(of)f (the)g(ob)s(jectiv)o(e)h(function.)0 1006 y Fh(2.)i(Outline)g(of)h(the)f (algorithm.)71 1086 y Fm(A)o(t)c(the)h(b)q(eginning)i(of)e(eac)o(h)g (iteration,)g(the)g(curren)o(t)g(iterate)g Fg(x)1179 1093 y Fe(k)1200 1086 y Fm(,)g(the)g(function)h(v)m(alue)g Fg(f)1623 1093 y Fe(k)1645 1086 y Fm(,)e(the)h(gradien)o(t)0 1143 y Fg(g)22 1150 y Fe(k)43 1143 y Fm(,)f(and)h(a)f(p)q(ositiv)o(e)h(de\014nite)h(limited) g(memory)e(appro)o(ximation)g Fg(B)1187 1150 y Fe(k)1223 1143 y Fm(are)g(giv)o(en.)20 b(This)15 b(allo)o(ws)g(us)f(to)g(form)g(a)0 1199 y(quadratic)h(mo)q(del)i(of)d Fg(f)21 b Fm(at)14 b Fg(x)514 1206 y Fe(k)535 1199 y Fm(,)419 1315 y Fg(m)459 1322 y Fe(k)480 1315 y Fm(\()p Fg(x)p Fm(\))e(=)h Fg(f)5 b Fm(\()p Fg(x)673 1322 y Fe(k)694 1315 y Fm(\))10 b(+)g Fg(g)791 1296 y Fe(T)789 1326 y(k)818 1315 y Fm(\()p Fg(x)g Ff(\000)g Fg(x)943 1322 y Fe(k)965 1315 y Fm(\))f(+)1043 1284 y(1)p 1043 1304 23 2 v 1043 1346 a(2)1070 1315 y(\()p Fg(x)h Ff(\000)h Fg(x)1196 1322 y Fe(k)1217 1315 y Fm(\))1235 1296 y Fe(T)1262 1315 y Fg(B)1296 1322 y Fe(k)1318 1315 y Fm(\()p Fg(x)f Ff(\000)g Fg(x)1443 1322 y Fe(k)1464 1315 y Fm(\))p Fg(:)325 b Fm(\(2)p Fg(:)p Fm(1\))0 1427 y(Just)17 b(as)f(in)h(the)g(metho)q(d)f(studied)i(b)o(y) f(Conn,)f(Gould)h(and)g(T)l(oin)o(t)f([9])g(the)g(algorithm)h(appro)o (ximately)f(min-)0 1483 y(imizes)22 b Fg(m)182 1490 y Fe(k)204 1483 y Fm(\()p Fg(x)p Fm(\))e(sub)s(ject)h(to)f(the)i(b)q(ounds)g(giv)o(en)f (b)o(y)g(\(1.2\).)36 b(This)22 b(is)f(done)h(b)o(y)f(\014rst)f(using)i(the)f (gradien)o(t)0 1540 y(pro)s(jection)13 b(metho)q(d)g(to)g(\014nd)h(a)e(set)h (of)g(activ)o(e)g(b)q(ounds,)h(follo)o(w)o(ed)g(b)o(y)f(a)g(minimization)i (of)e Fg(m)1606 1547 y Fe(k)1640 1540 y Fm(treating)g(those)0 1596 y(b)q(ounds)j(as)f(equalit)o(y)h(constrain)o(ts.)71 1653 y(T)l(o)e(do)i(this,)f(w)o(e)g(\014rst)g(consider)h(the)f(piece-wise)i (linear)g(path)724 1752 y Fg(x)p Fm(\()p Fg(t)p Fm(\))c(=)g Fg(P)6 b Fm(\()p Fg(x)942 1759 y Fe(k)973 1752 y Ff(\000)11 b Fg(tg)1057 1759 y Fe(k)1078 1752 y Fg(;)d(l)q(;)g(u)p Fm(\))p Fg(;)0 1851 y Fm(obtained)16 b(b)o(y)f(pro)s(jecting)g(the)g(steep)q(est)h (descen)o(t)f(direction)i(on)o(to)d(the)h(feasible)i(region,)e(where)619 2005 y Fg(P)6 b Fm(\()p Fg(x;)i(l)q(;)g(u)p Fm(\))799 2012 y Fe(i)823 2005 y Fm(=)871 1906 y Fd(8)871 1944 y(>)871 1956 y(<)871 2031 y(>)871 2043 y(:)929 1948 y Fg(l)943 1955 y Fe(i)1011 1948 y Fm(if)15 b Fg(x)1078 1955 y Fe(i)1105 1948 y Fg(<)e(l)1167 1955 y Fe(i)929 2005 y Fg(x)955 2012 y Fe(i)1011 2005 y Fm(if)i Fg(x)1078 2012 y Fe(i)1105 2005 y Ff(2)e Fm([)p Fg(l)1175 2012 y Fe(i)1188 2005 y Fg(;)8 b(u)1235 2012 y Fe(i)1249 2005 y Fm(])929 2061 y Fg(u)955 2068 y Fe(i)1011 2061 y Fm(if)15 b Fg(x)1078 2068 y Fe(i)1105 2061 y Fg(>)e(u)1179 2068 y Fe(i)1193 2061 y Fm(.)1820 2005 y(\(2)p Fg(:)p Fm(2\))0 2159 y(W)l(e)j(then)h(compute)f (the)h(generalized)h(Cauc)o(h)o(y)e(p)q(oin)o(t)h Fg(x)995 2142 y Fe(c)1012 2159 y Fm(,)f(whic)o(h)h(is)g(de\014ned)h(as)e(the)g (\014rst)g(lo)q(cal)h(minimizer)0 2215 y(of)e(the)g(univ)m(ariate,)h (piece-wise)i(quadratic)786 2314 y Fg(q)806 2321 y Fe(k)828 2314 y Fm(\()p Fg(t)p Fm(\))12 b(=)h Fg(m)980 2321 y Fe(k)1001 2314 y Fm(\()p Fg(x)p Fm(\()p Fg(t)p Fm(\)\))p Fg(:)0 2413 y Fm(The)i(v)m(ariables)h(whose)f(v)m(alue)h(at)e Fg(x)613 2397 y Fe(c)645 2413 y Fm(is)h(at)f(lo)o(w)o(er)h(or)f(upp)q(er)i(b)q(ound,)f (comprising)h(the)f(activ)o(e)g(set)f Ff(A)p Fm(\()p Fg(x)1790 2397 y Fe(c)1808 2413 y Fm(\),)g(are)0 2470 y(held)i(\014xed.)k(W)l(e)14 b(then)h(consider)g(the)f(follo)o(wing)h(quadratic)g(problem)g(o)o(v)o(er)e (the)h(subspace)h(of)f(free)g(v)m(ariables,)945 2603 y(2)p eop %%Page: 3 4 bop 612 177 a Fm(min)10 b Ff(f)p Fg(m)760 184 y Fe(k)781 177 y Fm(\()p Fg(x)p Fm(\))i(:)23 b Fg(x)917 184 y Fe(i)943 177 y Fm(=)13 b Fg(x)1017 158 y Fe(c)1017 188 y(i)1035 177 y Fg(;)27 b Ff(8)p Fg(i)13 b Ff(2)g(A)p Fm(\()p Fg(x)1252 158 y Fe(c)1269 177 y Fm(\))p Ff(g)510 b Fm(\(2)p Fg(:)p Fm(3\))590 260 y(sub)s(ject)21 b(to)29 b Fg(l)838 267 y Fe(i)865 260 y Ff(\024)13 b Fg(x)939 267 y Fe(i)965 260 y Ff(\024)g Fg(u)1039 267 y Fe(i)1099 260 y Ff(8)p Fg(i)k(=)-28 b Ff(2)13 b(A)p Fm(\()p Fg(x)1275 241 y Fe(c)1293 260 y Fm(\))p Fg(:)496 b Fm(\(2)p Fg(:)p Fm(4\))0 343 y(W)l(e)15 b(\014rst)g(solv)o(e)h(or)e(appro)o(ximately)i(solv)o(e)f (\(2.3\),)f(ignoring)i(the)f(b)q(ounds)h(on)f(the)h(free)f(v)m(ariables,)h (whic)o(h)g(can)0 400 y(b)q(e)h(accomplished)h(either)g(b)o(y)e(direct)h(or)f (iterativ)o(e)h(metho)q(ds)g(on)f(the)h(subspace)g(of)f(free)g(v)m(ariables,) i(or)e(b)o(y)h(a)0 456 y(dual)h(approac)o(h,)e(handling)i(the)f(activ)o(e)g (b)q(ounds)g(in)h(\(2.3\))d(b)o(y)i(Lagrange)f(m)o(ultipliers.)26 b(When)17 b(an)g(iterativ)o(e)0 513 y(metho)q(d)d(is)h(emplo)o(y)o(ed)g(w)o (e)e(use)i Fg(x)578 496 y Fe(c)609 513 y Fm(as)f(the)g(starting)g(p)q(oin)o (t)g(for)g(this)g(iteration.)20 b(W)l(e)14 b(then)g(truncate)g(the)g(path)0 569 y(to)o(w)o(ard)g(the)h(solution)h(so)f(as)g(to)f(satisfy)h(the)g(b)q (ounds)h(\(2.4\).)71 626 y(After)f(an)g(appro)o(ximate)g(solution)20 b(\026)-26 b Fg(x)715 633 y Fe(k)q Fk(+1)797 626 y Fm(of)15 b(this)h(problem)g(has)g(b)q(een)g(obtained,)g(w)o(e)g(compute)f(the)h(new)0 682 y(iterate)f Fg(x)170 689 y Fe(k)q Fk(+1)252 682 y Fm(b)o(y)g(a)g(line)h (searc)o(h)f(along)h Fg(d)722 689 y Fe(k)755 682 y Fm(=)g(\026)-26 b Fg(x)829 689 y Fe(k)q Fk(+1)906 682 y Ff(\000)10 b Fg(x)977 689 y Fe(k)1014 682 y Fm(that)k(satis\014es)i(the)f(su\016cien)o(t)h (decrease)f(condition)670 784 y Fg(f)5 b Fm(\()p Fg(x)741 791 y Fe(k)q Fk(+1)807 784 y Fm(\))12 b Ff(\024)h Fg(f)5 b Fm(\()p Fg(x)956 791 y Fe(k)977 784 y Fm(\))10 b(+)h Fg(\013\025)1107 791 y Fe(k)1128 784 y Fg(g)1152 766 y Fe(T)1150 796 y(k)1178 784 y Fg(d)1202 791 y Fe(k)1223 784 y Fg(;)584 b Fm(\(2)p Fg(:)p Fm(5\))0 886 y(and)15 b(that)g(also)g(attempts)f(to)h(enforce)g(the)g(curv)m (ature)h(condition)763 989 y Ff(j)p Fg(g)800 970 y Fe(T)798 1000 y(k)q Fk(+1)863 989 y Fg(d)887 996 y Fe(k)908 989 y Ff(j)c(\024)h Fg(\014)r Ff(j)p Fg(g)1046 970 y Fe(T)1044 1000 y(k)1073 989 y Fg(d)1097 996 y Fe(k)1118 989 y Ff(j)p Fg(;)676 b Fm(\(2)p Fg(:)p Fm(6\))0 1091 y(where)12 b Fg(\025)155 1098 y Fe(k)187 1091 y Fm(is)f(the)h(steplength)g(and)f Fg(\013)p Fm(,)h Fg(\014)h Fm(are)e(parameters)g(that)f(ha)o(v)o(e)h(the)g(v)m(alues)i(10)1447 1074 y Fc(\000)p Fk(4)1505 1091 y Fm(and)e(0)p Fg(:)p Fm(9,)g(resp)q(ectiv)o (ely)l(,)0 1147 y(in)20 b(our)f(co)q(de.)33 b(The)19 b(line)i(searc)o(h,)f (whic)o(h)g(ensures)g(that)e(the)i(iterates)f(remain)h(in)g(the)f(feasible)i (region,)f(is)0 1204 y(describ)q(ed)d(in)f Ff(x)p Fm(6.)j(W)l(e)c(then)g(ev)m (aluate)h(the)f(gradien)o(t)g(at)f Fg(x)1025 1211 y Fe(k)q Fk(+1)1091 1204 y Fm(,)h(compute)g(a)g(new)g(limited)h(memory)f(Hessian)0 1260 y(appro)o(ximation)g Fg(B)337 1267 y Fe(k)q Fk(+1)419 1260 y Fm(and)h(b)q(egin)g(a)f(new)g(iteration.)71 1316 y(Because)d(in)g(our) f(algorithm)g(ev)o(ery)g(Hessian)h(appro)o(ximation)f Fg(B)1181 1323 y Fe(k)1214 1316 y Fm(is)h(p)q(ositiv)o(e)g(de\014nite,)h(the)f(appro)o (ximate)0 1373 y(solution)19 b(\026)-26 b Fg(x)198 1380 y Fe(k)q Fk(+1)279 1373 y Fm(of)15 b(the)g(quadratic)h(problem)f(\(2.3\)-\(2.4\))d (de\014nes)17 b(a)d(descen)o(t)i(direction)g Fg(d)1567 1380 y Fe(k)1601 1373 y Fm(=)g(\026)-26 b Fg(x)1675 1380 y Fe(k)q Fk(+1)1751 1373 y Ff(\000)11 b Fg(x)1823 1380 y Fe(k)1859 1373 y Fm(for)0 1429 y(the)16 b(ob)s(jectiv)o(e)f(function)h Fg(f)5 b Fm(.)21 b(T)l(o)15 b(see)h(this,)f(\014rst)g(note)h(that)e(the)i (generalized)h(Cauc)o(h)o(y)e(p)q(oin)o(t)h Fg(x)1669 1413 y Fe(c)1686 1429 y Fm(,)f(whic)o(h)i(is)f(a)0 1486 y(minimizer)h(of)e Fg(m)304 1493 y Fe(k)325 1486 y Fm(\()p Fg(x)p Fm(\))g(on)g(the)h(pro)s (jected)f(steep)q(est)g(descen)o(t)h(direction,)g(satis\014es)g Fg(m)1489 1493 y Fe(k)1510 1486 y Fm(\()p Fg(x)1554 1493 y Fe(k)1575 1486 y Fm(\))c Fg(>)h(m)1693 1493 y Fe(k)1715 1486 y Fm(\()p Fg(x)1759 1469 y Fe(c)1776 1486 y Fm(\))i(if)g(the)0 1542 y(pro)s(jected)d(gradien)o(t)h(is)g(nonzero.)19 b(Since)14 b(the)f(p)q(oin)o(t)j(\026)-26 b Fg(x)937 1549 y Fe(k)q Fk(+1)1016 1542 y Fm(is)13 b(on)g(a)f(path)h(from)f Fg(x)1390 1526 y Fe(c)1420 1542 y Fm(to)g(the)g(minimizer)j(of)d(\(2.3\),)0 1599 y(along)i(whic)o(h)g Fg(m)288 1606 y Fe(k)323 1599 y Fm(decreases,)g(the)g(v)m(alue)h(of)f Fg(m)816 1606 y Fe(k)851 1599 y Fm(at)i(\026)-26 b Fg(x)931 1606 y Fe(k)q Fk(+1)1011 1599 y Fm(is)14 b(no)g(larger)g(than)f(its)h(v)m (alue)h(at)e Fg(x)1607 1582 y Fe(c)1625 1599 y Fm(.)19 b(Therefore)14 b(w)o(e)0 1655 y(ha)o(v)o(e)290 1712 y Fg(f)5 b Fm(\()p Fg(x)361 1719 y Fe(k)382 1712 y Fm(\))12 b(=)h Fg(m)500 1719 y Fe(k)521 1712 y Fm(\()p Fg(x)565 1719 y Fe(k)586 1712 y Fm(\))g Fg(>)g(m)705 1719 y Fe(k)726 1712 y Fm(\()p Fg(x)770 1693 y Fe(c)787 1712 y Fm(\))f Ff(\025)h Fg(m)905 1719 y Fe(k)926 1712 y Fm(\()s(\026)-26 b Fg(x)970 1719 y Fe(k)q Fk(+1)1036 1712 y Fm(\))13 b(=)g Fg(f)5 b Fm(\()p Fg(x)1186 1719 y Fe(k)1207 1712 y Fm(\))10 b(+)g Fg(g)1304 1693 y Fe(T)1302 1723 y(k)1331 1712 y Fg(d)1355 1719 y Fe(k)1386 1712 y Fm(+)1436 1694 y Fk(1)p 1436 1701 18 2 v 1436 1727 a(2)1459 1712 y Fg(d)1483 1693 y Fe(T)1483 1723 y(k)1510 1712 y Fg(B)1544 1719 y Fe(k)1566 1712 y Fg(d)1590 1719 y Fe(k)1611 1712 y Fg(:)0 1795 y Fm(This)17 b(inequalit)o(y)g(implies)h(that)d Fg(g)594 1779 y Fe(T)592 1808 y(k)621 1795 y Fg(d)645 1802 y Fe(k)680 1795 y Fg(<)f Fm(0)i(if)g Fg(B)844 1802 y Fe(k)882 1795 y Fm(is)h(p)q(ositiv)o(e)g(de\014nite)g(and)f Fg(d)1373 1802 y Fe(k)1410 1795 y Fm(is)g(not)g(zero.)22 b(In)16 b(this)h(pap)q(er)0 1852 y(w)o(e)c(do)g(not)f(presen)o(t)i(an)o(y)e(con)o(v)o(ergence)i(analysis) f(or)g(study)g(the)g(p)q(ossibilit)o(y)i(of)e(zigzagging.)20 b(Ho)o(w)o(ev)o(er,)12 b(giv)o(en)0 1908 y(the)j(use)g(of)g(gradien)o(t)g (pro)s(jection)g(in)h(the)f(step)g(computation)g(w)o(e)g(b)q(eliev)o(e)i (analyses)e(similar)h(to)f(those)g(in)g([7])0 1964 y(and)g([9)o(])g(should)g (b)q(e)h(p)q(ossible,)g(and)f(that)f(zigzagging)h(should)h(only)f(b)q(e)h(a)e (problem)h(in)h(the)f(degenerate)g(case.)71 2021 y(The)j(Hessian)h(appro)o (ximations)f Fg(B)694 2028 y Fe(k)734 2021 y Fm(used)h(in)g(our)f(algorithm)h (are)f(limited)i(memory)e(BF)o(GS)f(matrices)0 2077 y(\(No)q(cedal)j([21)o(]) g(and)g(Byrd,)g(No)q(cedal)h(and)f(Sc)o(hnab)q(el)h([6]\).)32 b(Ev)o(en)20 b(though)g(these)f(matrices)h(do)g(not)f(tak)o(e)0 2134 y(adv)m(an)o(tage)12 b(of)h(the)f(structure)h(of)f(the)h(problem,)h (they)f(require)g(only)g(a)g(small)g(amoun)o(t)f(of)h(storage)e(and,)i(as)g (w)o(e)0 2190 y(will)i(sho)o(w,)e(allo)o(w)h(the)f(computation)h(of)f(the)g (generalized)j(Cauc)o(h)o(y)d(p)q(oin)o(t)h(and)g(the)f(subspace)h (minimization)0 2247 y(to)20 b(b)q(e)h(p)q(erformed)f(in)h Fg(O)q Fm(\()p Fg(n)p Fm(\))f(op)q(erations.)36 b(The)20 b(new)h(algorithm)f (therefore)g(has)h(similar)g(computational)0 2303 y(demands)d(as)g(the)g (limited)i(memory)d(algorithm)h(\(L-BF)o(GS\))g(for)f(unconstrained)i (problems)g(describ)q(ed)g(b)o(y)0 2360 y(Liu)d(and)g(No)q(cedal)g([18)o(])f (and)g(Gilb)q(ert)i(and)e(Lemar)o(\023)-21 b(ec)o(hal)15 b([14)o(].)71 2416 y(In)e(the)g(next)g(three)f(sections)i(w)o(e)e(describ)q(e)j(in)e (detail)h(the)f(limited)h(memory)f(matrices,)g(the)f(computation)0 2473 y(of)j(the)g(Cauc)o(h)o(y)g(p)q(oin)o(t,)g(and)h(the)f(minimization)i (of)e(the)g(quadratic)h(problem)g(on)f(a)g(subspace.)945 2603 y(3)p eop %%Page: 4 5 bop 0 120 a Fh(3.)18 b(Limited)e(Memory)h(BF)n(GS)i(Matrices.)71 201 y Fm(In)f(our)g(algorithm,)g(the)g(limited)i(memory)d(BF)o(GS)g(matrices) h(are)g(represen)o(ted)g(in)h(the)f(compact)f(form)0 258 y(describ)q(ed)i(b)o (y)f(Byrd,)f(No)q(cedal)i(and)e(Sc)o(hnab)q(el)j([6)o(].)26 b(A)o(t)17 b(ev)o(ery)g(iterate)g Fg(x)1309 265 y Fe(k)1348 258 y Fm(the)h(algorithm)f(stores)g(a)g(small)0 314 y(n)o(um)o(b)q(er,)e(sa)o (y)g Fg(m)p Fm(,)f(of)h(correction)h(pairs)f Ff(f)p Fg(s)744 321 y Fe(i)758 314 y Fg(;)8 b(y)801 321 y Fe(i)815 314 y Ff(g)p Fg(;)17 b(i)12 b Fm(=)h Fg(k)e Ff(\000)g Fm(1)p Fg(;)d(:)g(:)g(:)t(;)g(k)j Ff(\000)f Fg(m)p Fm(,)15 b(where)625 416 y Fg(s)646 423 y Fe(k)681 416 y Fm(=)e Fg(x)755 423 y Fe(k)q Fk(+1)831 416 y Ff(\000)e Fg(x)903 423 y Fe(k)924 416 y Fg(;)47 b(y)1006 423 y Fe(k)1041 416 y Fm(=)13 b Fg(g)1111 423 y Fe(k)q Fk(+1)1187 416 y Ff(\000)d Fg(g)1254 423 y Fe(k)1275 416 y Fg(:)0 519 y Fm(These)h(correction)h(pairs)f (con)o(tain)g(information)g(ab)q(out)g(the)g(curv)m(ature)g(of)g(the)g (function,)h(and)f(in)h(conjunction)0 575 y(with)k(the)f(BF)o(GS)g(form)o (ula,)f(de\014ne)i(the)g(limited)h(memory)d(iteration)i(matrix)f Fg(B)1404 582 y Fe(k)1425 575 y Fm(.)20 b(The)c(question)g(is)f(ho)o(w)g(to)0 632 y(b)q(est)g(represen)o(t)h(these)f(matrices)g(without)g(explicitly)j (forming)e(them.)71 688 y(In)g([6])f(it)i(is)g(prop)q(osed)f(to)g(use)g(a)g (compact)g(\(or)f(outer)h(pro)q(duct\))g(form)g(to)f(de\014ne)j(the)e (limited)i(memory)0 744 y(matrix)d Fg(B)182 751 y Fe(k)219 744 y Fm(in)h(terms)e(of)h(the)h Fg(n)10 b Ff(\002)g Fg(m)15 b Fm(correction)h(matrices)432 847 y Fg(Y)458 854 y Fe(k)493 847 y Fm(=)d([)o Fg(y)575 854 y Fe(k)q Fc(\000)p Fe(m)656 847 y Fg(;)8 b(:)g(:)g(:)t(;)g(y)779 854 y Fe(k)q Fc(\000)p Fk(1)845 847 y Fm(])g Fg(;)157 b(S)1064 854 y Fe(k)1098 847 y Fm(=)13 b([)o Fg(s)1179 854 y Fe(k)q Fc(\000)p Fe(m)1259 847 y Fg(;)8 b(:)g(:)g(:)d(;)j(s)1382 854 y Fe(k)q Fc(\000)p Fk(1)1448 847 y Fm(])f Fg(:)339 b Fm(\(3)p Fg(:)p Fm(1\))0 949 y(More)11 b(sp)q(eci\014cally)m(,)k(it)d(is)h(sho)o(wn)f(in)g([6])f(that)h(if)g Fg(\022)i Fm(is)f(a)e(p)q(ositiv)o(e)j(scaling)f(parameter,)e(and)h(if)h(the) f Fg(m)g Fm(correction)0 1005 y(pairs)i Ff(f)p Fg(s)154 1012 y Fe(i)169 1005 y Fg(;)8 b(y)212 1012 y Fe(i)225 1005 y Ff(g)248 986 y Fe(k)q Fc(\000)p Fe(m)248 1019 y(i)p Fk(=)p Fe(k)q Fc(\000)p Fk(1)354 1005 y Fm(,)14 b(satisfy)g Fg(s)543 989 y Fe(T)543 1017 y(i)570 1005 y Fg(y)592 1012 y Fe(i)619 1005 y Fg(>)f Fm(0,)h(then)h(the)f(matrix)g(obtained)h(b)o(y)f(up)q(dating)h Fg(\022)q(I)j(m)p Fm(-times,)c(using)h(the)0 1069 y(BF)o(GS)g(form)o(ula)f (and)i(the)f(pairs)h Ff(f)p Fg(s)626 1076 y Fe(i)640 1069 y Fg(;)8 b(y)683 1076 y Fe(i)696 1069 y Ff(g)719 1050 y Fe(k)q Fc(\000)p Fe(m)719 1083 y(i)p Fk(=)p Fe(k)q Fc(\000)p Fk(1)840 1069 y Fm(can)15 b(b)q(e)h(written)g(as)744 1178 y Fg(B)778 1185 y Fe(k)813 1178 y Fm(=)d Fg(\022)q(I)h Ff(\000)d Fg(W)1006 1185 y Fe(k)1027 1178 y Fg(M)1071 1185 y Fe(k)1092 1178 y Fg(W)1141 1159 y Fe(T)1135 1189 y(k)1820 1178 y Fm(\(3)p Fg(:)p Fm(2\))0 1280 y(where)759 1336 y Fg(W)802 1343 y Fe(k)836 1336 y Fm(=)884 1289 y Fd(h)925 1336 y Fg(Y)951 1343 y Fe(k)1014 1336 y Fg(\022)q(S)1064 1343 y Fe(k)1107 1289 y Fd(i)1134 1336 y Fg(;)673 b Fm(\(3)p Fg(:)p Fm(3\))682 1506 y Fg(M)726 1513 y Fe(k)760 1506 y Fm(=)808 1434 y Fd(")853 1477 y Ff(\000)p Fg(D)926 1484 y Fe(k)1025 1477 y Fg(L)1056 1461 y Fe(T)1056 1491 y(k)874 1534 y Fg(L)905 1541 y Fe(k)989 1534 y Fg(\022)q(S)1042 1517 y Fe(T)1039 1547 y(k)1070 1534 y Fg(S)1098 1541 y Fe(k)1140 1434 y Fd(#)1164 1445 y Fc(\000)p Fk(1)1211 1506 y Fg(;)596 b Fm(\(3)p Fg(:)p Fm(4\))0 1619 y(and)15 b(where)h Fg(L)251 1626 y Fe(k)287 1619 y Fm(and)g Fg(D)414 1626 y Fe(k)450 1619 y Fm(are)f(the)g Fg(m)10 b Ff(\002)g Fg(m)15 b Fm(matrices)461 1750 y(\()p Fg(L)510 1757 y Fe(k)531 1750 y Fm(\))549 1757 y Fe(i;j)601 1750 y Fm(=)649 1678 y Fd(\()703 1722 y Fm(\()p Fg(s)742 1729 y Fe(k)q Fc(\000)p Fe(m)p Fc(\000)p Fk(1+)p Fe(i)907 1722 y Fm(\))925 1705 y Fe(T)952 1722 y Fm(\()p Fg(y)992 1729 y Fe(k)q Fc(\000)p Fe(m)p Fc(\000)p Fk(1+)p Fe(j)1160 1722 y Fm(\))42 b(if)15 b Fg(i)e(>)g(j)703 1778 y Fm(0)494 b(otherwise)p Fg(;)1820 1750 y Fm(\(3)p Fg(:)p Fm(5\))580 1900 y Fg(D)618 1907 y Fe(k)651 1900 y Fm(=)13 b Fg(diag)793 1853 y Fd(h)813 1900 y Fg(s)834 1881 y Fe(T)834 1911 y(k)q Fc(\000)p Fe(m)914 1900 y Fg(y)936 1907 y Fe(k)q Fc(\000)p Fe(m)1017 1900 y Fg(;)8 b(:)g(:)g(:)t(;)g(s)1139 1881 y Fe(T)1139 1911 y(k)q Fc(\000)p Fk(1)1205 1900 y Fg(y)1227 1907 y Fe(k)q Fc(\000)p Fk(1)1294 1853 y Fd(i)1321 1900 y Fg(:)486 b Fm(\(3)p Fg(:)p Fm(6\))0 1991 y(\(W)l(e)19 b(should)h(p)q(oin)o(t)f(out)g (that)f(\(3.2\))f(is)j(a)e(sligh)o(t)i(rearrangemen)o(t)e(of)g(equation)i (\(3.5\))d(in)j([6)o(]\).)30 b(Note)19 b(that)0 2047 y(since)c Fg(M)154 2054 y Fe(k)189 2047 y Fm(is)f(a)f(2)p Fg(m)7 b Ff(\002)g Fm(2)p Fg(m)14 b Fm(matrix,)f(and)h(since)g Fg(m)g Fm(is)g(c)o(hosen)g(to)f (b)q(e)h(a)g(small)g(in)o(teger,)g(the)f(cost)h(of)f(computing)0 2104 y(the)h(in)o(v)o(erse)g(in)h(\(3.4\))d(is)i(negligible.)22 b(It)14 b(is)h(sho)o(wn)e(in)i([6)o(])e(that)h(b)o(y)f(using)i(the)f(compact) f(represen)o(tation)h(\(3.2\))0 2160 y(v)m(arious)h(computations)f(in)o(v)o (olving)i Fg(B)665 2167 y Fe(k)701 2160 y Fm(b)q(ecome)f(inexp)q(ensiv)o(e.) 22 b(In)15 b(particular,)g(the)g(pro)q(duct)g(of)f Fg(B)1734 2167 y Fe(k)1770 2160 y Fm(times)h(a)0 2217 y(v)o(ector,)f(whic)o(h)i(o)q (ccurs)g(often)f(in)h(the)f(algorithm)g(of)g(this)h(pap)q(er,)f(can)g(b)q(e)h (p)q(erformed)f(e\016cien)o(tly)l(.)71 2273 y(There)k(is)g(a)f(similar)i (represen)o(tation)f(of)g(the)f(in)o(v)o(erse)i(limited)g(memory)f(BF)o(GS)f (matrix)g Fg(H)1708 2280 y Fe(k)1748 2273 y Fm(that)g(ap-)0 2330 y(pro)o(ximates)d(the)g(in)o(v)o(erse)h(of)e(the)i(Hessian)g(matrix:)731 2448 y Fg(H)769 2455 y Fe(k)803 2448 y Ff(\021)856 2418 y Fm(1)p 856 2438 23 2 v 856 2479 a Fg(\022)884 2448 y(I)d Fm(+)976 2437 y(\026)963 2448 y Fg(W)1006 2455 y Fe(k)1044 2437 y Fm(\026)1027 2448 y Fg(M)1071 2455 y Fe(k)1106 2437 y Fm(\026)1093 2448 y Fg(W)1142 2430 y Fe(T)1136 2460 y(k)1169 2448 y Fg(;)638 b Fm(\(3)p Fg(:)p Fm(7\))945 2603 y(4)p eop %%Page: 5 6 bop 0 120 a Fm(where)774 165 y(\026)761 177 y Fg(W)804 184 y Fe(k)838 177 y Ff(\021)886 129 y Fd(h)931 159 y Fk(1)p 931 166 18 2 v 931 192 a Fe(\022)954 177 y Fg(Y)980 184 y Fe(k)1043 177 y Fg(S)1071 184 y Fe(k)1113 177 y Fg(;)1134 129 y Fd(i)538 366 y Fm(\026)521 378 y Fg(M)565 385 y Fe(k)599 378 y Ff(\021)647 281 y Fd(2)647 354 y(6)647 381 y(4)747 321 y Fm(0)264 b Ff(\000)p Fg(R)1104 302 y Fc(\000)p Fk(1)1104 335 y Fe(k)696 436 y Ff(\000)p Fg(R)766 417 y Fc(\000)p Fe(T)766 450 y(k)862 436 y Fg(R)897 417 y Fc(\000)p Fe(T)897 450 y(k)952 436 y Fm(\()p Fg(D)1008 443 y Fe(k)1039 436 y Fm(+)1089 418 y Fk(1)p 1089 425 V 1089 452 a Fe(\022)1112 436 y Fg(Y)1149 419 y Fe(T)1138 449 y(k)1176 436 y Fg(Y)1202 443 y Fe(k)1224 436 y Fm(\))p Fg(R)1277 417 y Fc(\000)p Fk(1)1277 450 y Fe(k)1344 281 y Fd(3)1344 354 y(7)1344 381 y(5)1379 378 y Fg(;)0 535 y Fm(and)459 613 y(\()p Fg(R)512 620 y Fe(k)532 613 y Fm(\))550 620 y Fe(i;j)603 613 y Fm(=)651 541 y Fd(\()705 585 y Fm(\()p Fg(s)744 592 y Fe(k)q Fc(\000)p Fe(m)p Fc(\000)p Fk(1+)p Fe(i)908 585 y Fm(\))926 568 y Fe(T)954 585 y Fm(\()p Fg(y)994 592 y Fe(k)q Fc(\000)p Fe(m)p Fc(\000)p Fk(1+)p Fe(j)1162 585 y Fm(\))41 b(if)16 b Fg(i)c Ff(\024)h Fg(j)705 641 y Fm(0)493 b(otherwise.)1820 613 y(\(3)p Fg(:)p Fm(8\))0 729 y(\(W)l(e)15 b(note)g(that)f(\(3.7\))g(is)i(a)f(sligh)o(t)g (rearrangemen)o(t)g(of)f(equation)i(\(3.1\))d(in)j([6]\).)71 785 y(Represen)o(tations)21 b(of)e(limited)k(memory)c(matrices)i(analogous)f (to)f(these)i(also)f(exist)h(for)f(other)g(quasi-)0 842 y(Newton)15 b(up)q(date)g(form)o(ulae,)f(suc)o(h)h(as)g(SR1)g(or)f(DFP)h(\(see)f([6]\),)g (and)h(in)g(principle)j(could)e(b)q(e)f(used)h(for)e Fg(B)1839 849 y Fe(k)1876 842 y Fm(in)0 898 y(our)e(algorithm.)19 b(W)l(e)13 b(consider)g(here)g(only)g(BF)o(GS)f(since)h(w)o(e)f(ha)o(v)o(e)g (considerable)i(computational)f(exp)q(erience)0 955 y(in)j(the)f (unconstrained)i(case)e(indicating)i(the)e(limited)i(memory)e(BF)o(GS)g(p)q (erforms)f(w)o(ell.)71 1011 y(Since)k(the)f(b)q(ounds)g(on)g(the)g(problem)g (ma)o(y)f(prev)o(en)o(t)h(the)f(line)j(searc)o(h)d(from)g(satisfying)h (\(2.6\))e(\(see)i Ff(x)p Fm(6\),)0 1068 y(w)o(e)g(cannot)g(guaran)o(tee)g (that)g(the)g(condition)i Fg(s)835 1051 y Fe(T)835 1081 y(k)863 1068 y Fg(y)885 1075 y Fe(k)923 1068 y Fg(>)d Fm(0)h(alw)o(a)o(ys)g(holds)h (\(cf.)26 b(Dennis)19 b(and)e(Sc)o(hnab)q(el)i([12)o(]\).)0 1124 y(Therefore)d(to)f(main)o(tain)h(the)f(p)q(ositiv)o(e)i(de\014niteness)g (of)f(the)f(limited)j(memory)d(BF)o(GS)g(matrix,)g(w)o(e)h(discard)0 1181 y(a)f(correction)g(pair)h Ff(f)p Fg(s)388 1188 y Fe(k)409 1181 y Fg(;)8 b(y)452 1188 y Fe(k)473 1181 y Ff(g)15 b Fm(if)h(the)f(curv)m (ature)g(condition)799 1283 y Fg(s)820 1264 y Fe(T)820 1294 y(k)848 1283 y Fg(y)870 1290 y Fe(k)904 1283 y Fg(>)e Fm(eps)d Ff(k)p Fg(y)r Ff(k)1095 1264 y Fk(2)1820 1283 y Fm(\(3)p Fg(:)p Fm(9\))0 1385 y(is)20 b(not)g(satis\014ed)g(for)g(a)f(small)i(p)q(ositiv)o(e) g(constan)o(t)e(eps.)34 b(If)20 b(this)g(happ)q(ens)h(w)o(e)f(do)g(not)f (delete)i(the)f(oldest)0 1441 y(correction)11 b(pair,)g(as)f(is)h(normally)g (done)g(in)g(limited)i(memory)d(up)q(dating.)19 b(This)11 b(means)f(that)g (the)h Fg(m)f Fm(directions)0 1498 y(in)16 b Fg(S)81 1505 y Fe(k)117 1498 y Fm(and)g Fg(Y)232 1505 y Fe(k)269 1498 y Fm(ma)o(y)e (actually)i(include)i(some)d(with)g(indices)i(less)f(than)f Fg(k)c Ff(\000)g Fg(m)p Fm(.)0 1654 y Fh(4.)37 b(The)18 b(generalized)f(Cauc) n(h)n(y)j(p)r(oin)n(t.)71 1735 y Fm(The)e(ob)s(jectiv)o(e)h(of)f(the)h(pro)q (cedure)h(describ)q(ed)g(in)g(this)f(section)g(is)g(to)f(\014nd)i(the)e (\014rst)h(lo)q(cal)g(minimizer)0 1792 y(of)d(the)g(quadratic)g(mo)q(del)h (along)g(the)f(piece-wise)i(linear)g(path)e(obtained)g(b)o(y)g(pro)s(jecting) g(p)q(oin)o(ts)h(along)f(the)0 1848 y(steep)q(est)f(descen)o(t)g(direction,)g Fg(x)560 1855 y Fe(k)590 1848 y Ff(\000)10 b Fg(tg)673 1855 y Fe(k)694 1848 y Fm(,)k(on)o(to)g(the)g(feasible)i(region.)k(W)l(e)15 b(de\014ne)g Fg(x)1448 1832 y Fk(0)1481 1848 y Fm(=)e Fg(x)1555 1855 y Fe(k)1591 1848 y Fm(and,)h(throughout)0 1905 y(this)21 b(section,)h(drop)e(the)g(index)i Fg(k)f Fm(of)f(the)h(outer)f(iteration,)h (so)f(that)g Fg(g)r(;)8 b(x)19 b Fm(and)h Fg(B)j Fm(stand)e(for)e Fg(g)1731 1912 y Fe(k)1752 1905 y Fg(;)8 b(x)1799 1912 y Fe(k)1840 1905 y Fm(and)0 1961 y Fg(B)34 1968 y Fe(k)56 1961 y Fm(.)31 b(W)l(e)19 b(use)h(subscripts)f(to)g(denote)g(the)g(comp)q(onen)o(ts)g(of)g (a)g(v)o(ector;)g(for)g(example)h Fg(g)1557 1968 y Fe(i)1589 1961 y Fm(denotes)g(the)f Fg(i)p Fm(-th)0 2017 y(comp)q(onen)o(t)e(of)f Fg(g)r Fm(.)23 b(Sup)q(erscripts)18 b(will)g(b)q(e)f(used)g(to)f(represen)o (t)h(iterates)f(during)h(the)g(piece-wise)i(searc)o(h)d(for)0 2074 y(the)f(Cauc)o(h)o(y)g(p)q(oin)o(t.)71 2130 y(T)l(o)f(de\014ne)j(the)e (breakp)q(oin)o(ts)h(in)g(eac)o(h)f(co)q(ordinate)h(direction)g(w)o(e)f (compute)631 2288 y Fg(t)647 2295 y Fe(i)674 2288 y Fm(=)722 2189 y Fd(8)722 2226 y(>)722 2239 y(<)722 2314 y(>)722 2326 y(:)780 2231 y Fm(\()p Fg(x)824 2215 y Fk(0)824 2243 y Fe(i)853 2231 y Ff(\000)c Fg(u)925 2238 y Fe(i)939 2231 y Fm(\))p Fg(=g)1002 2238 y Fe(i)1057 2231 y Fm(if)k Fg(g)1120 2238 y Fe(i)1147 2231 y Fg(<)e Fm(0)780 2288 y(\()p Fg(x)824 2271 y Fk(0)824 2300 y Fe(i)853 2288 y Ff(\000)e Fg(l)913 2295 y Fe(i)926 2288 y Fm(\))p Fg(=g)989 2295 y Fe(i)1057 2288 y Fm(if)k Fg(g)1120 2295 y Fe(i)1147 2288 y Fg(>)e Fm(0)780 2344 y Ff(1)232 b Fm(otherwise,)1820 2288 y(\(4)p Fg(:)p Fm(1\))945 2603 y(5)p eop %%Page: 6 7 bop 0 120 a Fm(and)12 b(sort)f Ff(f)p Fg(t)212 127 y Fe(i)226 120 y Fg(;)d(i)k Fm(=)h(1)p Fg(;)8 b(:)g(:)g(:)t(;)g(n)p Ff(g)j Fm(in)i(increasing)g(order)f(to)f(obtain)h(the)g(ordered)h(set)e Ff(f)p Fg(t)1416 104 y Fe(j)1447 120 y Fm(:)i Fg(t)1489 104 y Fe(j)1520 120 y Ff(\024)g Fg(t)1584 104 y Fe(j)r Fk(+1)1648 120 y Fg(;)8 b(j)14 b Fm(=)f(1)p Fg(;)8 b(:::;)g(n)p Ff(g)p Fm(.)0 177 y(This)15 b(is)f(done)h(b)o(y)f(means)g(of)f(a)h(heapsort)f (algorithm)h([1].)19 b(W)l(e)14 b(then)g(searc)o(h)g(along)g Fg(P)6 b Fm(\()p Fg(x)1527 160 y Fk(0)1555 177 y Ff(\000)i Fg(tg)r(;)g(l)q(;)g(u)p Fm(\),)j(a)j(piece-)0 233 y(wise)i(linear)g(path)f (whic)o(h)h(can)g(b)q(e)f(expressed)h(as)636 365 y Fg(x)662 372 y Fe(i)676 365 y Fm(\()p Fg(t)p Fm(\))d(=)788 293 y Fd(\()843 337 y Fg(x)869 320 y Fk(0)869 349 y Fe(i)898 337 y Ff(\000)e Fg(tg)982 344 y Fe(i)1052 337 y Fm(if)k Fg(t)e Ff(\024)g Fg(t)1186 344 y Fe(i)843 393 y Fg(x)869 377 y Fk(0)869 406 y Fe(i)898 393 y Ff(\000)e Fg(t)960 400 y Fe(i)974 393 y Fg(g)996 400 y Fe(i)1052 393 y Fm(otherwise.)0 504 y(Supp)q(ose)16 b(that)f(w)o(e)g(are)g (examining)h(the)f(in)o(terv)m(al)i([)p Fg(t)910 488 y Fe(j)r Fc(\000)p Fk(1)973 504 y Fg(;)8 b(t)1010 488 y Fe(j)1028 504 y Fm(].)19 b(Let)d(us)f(de\014ne)h(the)g(\()p Fg(j)c Ff(\000)e Fm(1\)-th)15 b(breakp)q(oin)o(t)g(as)811 607 y Fg(x)837 588 y Fe(j)r Fc(\000)p Fk(1)913 607 y Fm(=)e Fg(x)p Fm(\()p Fg(t)1021 588 y Fe(j)r Fc(\000)p Fk(1)1085 607 y Fm(\))0 709 y(so)i(that)f(on)h([)p Fg(t)246 692 y Fe(j)r Fc(\000)p Fk(1)310 709 y Fg(;)8 b(t)347 692 y Fe(j)365 709 y Fm(])738 765 y Fg(x)p Fm(\()p Fg(t)p Fm(\))k(=)h Fg(x)902 746 y Fe(j)r Fc(\000)p Fk(1)976 765 y Fm(+)d(\001)p Fg(td)1099 746 y Fe(j)r Fc(\000)p Fk(1)1163 765 y Fg(;)0 849 y Fm(where)823 905 y(\001)p Fg(t)j Fm(=)g Fg(t)e Ff(\000)f Fg(t)1026 886 y Fe(j)r Fc(\000)p Fk(1)0 988 y Fm(and)617 1066 y Fg(d)641 1044 y Fe(j)r Fc(\000)p Fk(1)641 1079 y Fe(i)717 1066 y Fm(=)765 994 y Fd(\()819 1038 y Ff(\000)p Fg(g)876 1045 y Fe(i)932 1038 y Fm(if)16 b Fg(t)990 1021 y Fe(j)r Fc(\000)p Fk(1)1066 1038 y Fg(<)d(t)1130 1045 y Fe(i)819 1094 y Fm(0)90 b(otherwise)p Fg(:)1820 1066 y Fm(\(4)p Fg(:)p Fm(2\))71 1187 y(Using)15 b(this)h(notation)f(w)o(e)g(wr