Monday, January 4, 2016

The Domino Method of Nonlinear Integer/Continuous/Discrete Programming Seeking To Solve a Modified Broyden Tridiagonal Problem

Jsun Yui Wong

The following computer program seeks to solve an enlarged version of Example 3 on page 290 of  Ge, Liu, and Xu [4, page 290, modified Broyden tridiagonal function]–    http://www.scirp.org/journal/ojapps  The present paper considers the case of 4000 equations with 4000 variables. One notes the starting vectors, 94 A(KK) = FIX(RND * 6).


0 DEFDBL A-Z
3 DEFINT J, K

4 DIM X(32768), A(32768), L(32768), K(32768)

5 FOR JJJJ = -32000 TO 32000

    14 RANDOMIZE JJJJ
    15 REM   h = 1 / (32760 + 1)


    16 M = -1D+50

    91 FOR KK = 1 TO 4000

        94 A(KK) = FIX(RND * 6)


    95 NEXT KK

    128 FOR I = 1 TO 12000 STEP 1


        129 FOR K = 1 TO 4000


            131 X(K) = A(K)
        132 NEXT K

        155 FOR IPP = 1 TO FIX(1 + RND * 3)
            181 B = 1 + FIX(RND * 4003)

            183 R = (1 - RND * 2) * A(B)

            187 IF RND < .25 THEN X(B) = A(B) + RND * R ELSE IF RND < .333 THEN X(B) = A(B) + RND ^ 4 * R ELSE IF RND < .5 THEN X(B) = A(B) + RND ^ 7 * R ELSE IF RND < .5 THEN X(B) = FIX(A(B)) ELSE X(B) = FIX(A(B)) + 1
        191 NEXT IPP


        555 X(2) = ((3 - 2 * X(1)) * X(1) + 1) / 2


        605 FOR J44 = 2 TO 3999

            609 X(J44 + 1) = ((3 - 2 * X(J44)) * X(J44) - X(J44 - 1) + 2) / 2

        611 NEXT J44


        699 P1 = (3 - 2 * X(4000)) * X(4000) - X(3999)



        999 P = -ABS(P1)


        1451 IF P <= M THEN 1670
        1657 FOR KEW = 1 TO 4000


            1658 A(KEW) = X(KEW)
        1659 NEXT KEW
        1661 M = P
        1666 REM PRINT A(1), A(4000), M, JJJJ

        1668 IF M > -.000000000001 THEN 1912

    1670 NEXT I
    1890 REM IF M < -5555 THEN 1999

    1912 PRINT A(1), A(2), A(3)
    1915 PRINT A(3997), A(3998), A(3999)
    1917 PRINT A(4000), M, JJJJ

1999 NEXT JJJJ

This computer program was run with qb64v1000-win [12]. Copied by hand from the screen, the computer program’s complete output through JJJJ= -31994 is shown below.

3.903018182689294        -8.879023660369297        -93.1071057432964
 -1.#IND        -1.#IND         -1.#IND
-1.#IND         -1.#IND      -32000

0      .5     1.5
1      1      1
1      0      -31999

4.34741353824193          -11.87888416512631        -160.0999220252991
 -1.#IND        -1.#IND         -1.#IND
-1.#IND         -1.#IND      -31998

1.653270079584755        .24660316332695       .482456585035189
1      1      1
1      0      -31997

3.02737948516394          -4.123957319445566         -23.70664969435698
 -1.#IND        -1.#IND         -1.#IND
-1.#IND         -1.#IND      -31996

3.613930553710306        -7.139598216475422         -62.49022529426731
 -1.#IND        -1.#IND         -1.#IND
-1.#IND         -1.#IND      -31995

1      1      1
1      1      1
1      0      -31994

Above there is no rounding by hand; it is just straight copying by hand from the screen.

Of the 4000 unknowns, only the 7 A’s of line 1912 through line 1917 are shown above.

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [12], the wall-clock time for obtaining the output through JJJJ= -31994 was four minutes.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References

[1] R. L. Burden, J. D. Faires, Annette M. Burden. Numerical Analysis, Tenth Edition. Cengage Learning, 2016.

[2] Huiping Cao, Global Convergence of Schubert’s Method for Solving Sparse Nonlinear Equations, Abstract and Applied Analysis, Volume 2014, Article ID 251587, 12 pages. Hindawi Publishing Corporation. http://dx.doi.org/10.1155/2014/251587

[3] C. A. Floudas, Deterministic Global Optimization. Kluwer Academic Publishers, 2000.
 
[4] Rendong Ge, Lijun Liu, Yi Xu, Neural Network Approach for Solving Singular Convex Optimization with Bounded Variables, Open Journal of Applied Sciences, 2013, 3, 285-292.  Published Online July 2013.  http://www.scirp.org/journal/ojapps

[5] Tianmin Han, Yuhuan Han, Solving Large Scale Nonlinear Equations by a New ODE Numerical Integration Method, Applied Mathematics, 2010, 1, 222-229.
http://www.SciRP.org/journal/am

[6] William La Cruz, Jose Mario Martinez, Marcos Raydan, Spectral residual method without gradient information for solving large-scale nonlinear systems of equations: Theory and experiments. Technical Report RT-04-08, July 2004.
http://www.ime.unicamp.br/~martinez/lmrreport.pdf

[7] William La Cruz, Jose Mario Martinez, Marcos Raydan, Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Mathematics of Computation, vol. 75, no. 255, pp.1429-1448, 2006.

[8] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.

[9] Alexander P. Morgan, A Method for Computing All Solutions to Systems of Polynomial Equations, ACM Transactions on Mathematical Software, Vol. 9, No. 1, March 1983, Pages 1-17. https://folk.uib.no/ssu029/pdf_file/Morgan83.pdf

[10] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery. Numerical recipes: the art of scientific computing, third ed. Cambridge University Press, 2007.

[11] J. Rice. Numerical Methods, Software, and Analysis, Second Edition. Academic Press, 1993.

[12] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64

[13] M. Ziani, F. Guyomarc’h, An Autoadaptive Limited Memory Broyden’s Method To Solve Systems of Nonlinear Equations, Applied Mathematics and Computation 205 (2008) pp. 202-211. web.info.uvt.ro/~cristiana.drogoescu/MC/broyden.pdf

No comments:

Post a Comment